परिचय

यह लेख एक तेजी से लोकप्रिय एल्गोरिथम आकृति के बारे में एक कहानी पर चर्चा करने के लिए है: ग्रेडिएंट डिसेंट । शुरुआती लोगों के लिए, ग्रेडिएंट डिसेंट मशीन लर्निंग विजार्ड्स के लिए डीप लर्निंग की डार्क आर्ट्स को समझने और वश में करने का प्रयास करने वाला एक उपकरण है, हालांकि यह रैखिक प्रतिगमन और अनुकूलन के स्पर्शरेखा क्षेत्रों जैसे सरल क्षेत्रों में भी उपयोग करता है।

ग्रैडिएंट डिसेंट घने धुंध में ढके पहाड़ के नीचे चलने वाले हाइकर की तरह है। व्यक्ति अपने पैरों के आगे बहुत दूर नहीं देख सकता है, लेकिन वे स्थानीय रूप से महसूस कर सकते हैं कि वे कहाँ खड़े हैं, कौन सी दिशाएँ सबसे खड़ी हैं और आखिरकार, उन्हें किस दिशा में एक कदम नीचे ले जाना चाहिए ताकि वे जितनी जल्दी हो सके पहाड़ से नीचे उतर सकें। शास्त्रीय अनुकूलन में, एक महत्वपूर्ण प्रश्न यह समझ रहा है कि पर्वत के नीचे कितनी जल्दी अभिसरण हो सकता है।

क्या वह व्यक्ति हमेशा के लिए भटक जाएगा ? क्या वे स्नैक्स खत्म होने से पहले नीचे पहुंच जाएंगे ?

जंगली में महत्वपूर्ण प्रश्न, सुनिश्चित करने के लिए। लेकिन क्या होगा अगर हमने इस स्थिति को थोड़ा और रोमांचक बना दिया?

मान लीजिए पहाड़ पर यात्री अनायास ही अपने होश खो बैठा; शायद वे बड़े भाषा मॉडल और चैटजीपीटी की सुंदरता ( या डरावनी ) को पहचान कर अंधे हो गए थे।

लेकिन सब कुछ खोया नहीं है, क्योंकि उनके पास प्रतीत होता है कि सर्वज्ञ (और मैत्रीपूर्ण!) ओरेकल उनके दिमाग में बोल रहा है! और यह दैवज्ञ वहां है, शून्य से फुसफुसाते हुए, उन्हें बता रहा है कि जितनी जल्दी हो सके उस पहाड़ से बाहर निकलने के लिए उन्हें किस दिशा में कदम रखना चाहिए। एकमात्र पकड़ यह है कि, वास्तव में, यह ओरेकल पूरी तरह से सटीक सलाह नहीं देता है.. लेकिन दुर्भाग्यपूर्ण हाइकर के लिए एक शोर भाग्य उगलता है।

यह देखते हुए कि शोर का सटीक सामान्य प्रतिनिधित्व है और हमारे पास पर्वत की ज्यामिति के बारे में कुछ अतिरिक्त जानकारी है, हम इस बारे में क्या कह सकते हैं कि हाइकर कहाँ समाप्त होगा?

क्या यह Oracle हाइकर को सुरक्षा के लिए मार्गदर्शन करने में सक्षम होगा? या यात्री का भविष्य हमेशा के लिए अंधकारमय है?

विश्लेषण

कुछ लोग कहते हैं कि यह गणितज्ञों का युग है और जबकि मैं निश्चित रूप से एक नहीं हूं, मैं कह सकता हूं कि कोई भी बेवकूफ जो विस्तार से मस्तिष्कवादी हैं, शायद इस गरीब पदयात्री की स्थिति के गणितीय विश्लेषण के माध्यम से कुछ मजा आएगा। इस समस्या के लिए सटीक सूत्रीकरण नीचे दिए गए समस्या कथन में वर्णित है:

तो इस सूत्रीकरण में, हमारे कार्य की छवि हमारा पर्वत है और हम मान रहे हैं कि यह सरलता के लिए उत्तल है, जिसका अर्थ है कि इसमें केवल एक विशिष्ट स्थानीय न्यूनतम है; इसका मतलब है कि वैश्विक न्यूनतम एक स्थानीय न्यूनतम है । तो पर्वत के पास ठीक एक बिंदु है जिसे हम " तल " कहते हैं।

जैसा कि पहले संकेत दिया गया था, ओरेकल की सलाह में शोर सामान्य रूप से 0 माध्य और निरंतर भिन्नता के साथ वितरित किया जाता है। अंतत:, हम यह तय करना चाहते हैं कि हर बार पहाड़ से कितनी दूर नीचे उतरना है जब ओरेकल हाइकर को बताता है कि किस दिशा में उतरना है ताकि हम जल्द से जल्द पहाड़ से नीचे उतर सकें। इसके अतिरिक्त, हम यह देखना चाहते हैं कि क्या हम वास्तव में निश्चितता के साथ पर्वत के पूर्ण तल तक पहुँच सकते हैं।

इसके बारे में तर्क करने में हमारी मदद करने के लिए, हम पहाड़ के नीचे के लिए अज्ञात स्थान और पर्वतारोही के i वें स्थान के बीच अपेक्षित दूरी का विश्लेषण करेंगे, क्योंकि वे पहाड़ से नीचे उतर रहे हैं। एक उपयोगी लेम्मा जिसे हम अंततः सिद्ध करना चाहते हैं, नीचे दी गई है:

इस लेम्मा का प्रमाण दो चरणों में आगे बढ़ता है: पहले एक वर्तमान पुनरावृति और पूर्व पुनरावृत्ति के बीच एक सुविधाजनक पुनरावर्ती संबंध खोजना, दूसरा प्रेरण द्वारा दिखा रहा है कि वांछित संबंध रखता है।

लेम्मा 0.2 के साथ, अब हम चरण आकारों α_i के बारे में तर्क कर सकते हैं। अंततः, हम चाहते हैं कि पुनरावृत्त त्रुटि पर ऊपरी सीमा को जितना संभव हो उतना छोटा किया जाए। लेम्मा 0.2 के परिणाम का तात्पर्य है कि हम चाहते हैं कि सभी q_j मान यथासंभव छोटे हों; अधिक विशेष रूप से, हम चाहते हैं कि वे सभी सख्ती से 1 से कम हों और जितना संभव हो उतना छोटा हो। हम पहले ध्यान देते हैं कि यदि हम उस q_j < 1 को लागू करना चाहते हैं, तो इसका अर्थ है कि हमें नीचे दी गई दोनों असमानताओं को संतुष्ट करना होगा:

हम पहले α_j को इतना छोटा चुनकर इसे प्राप्त कर सकते हैं कि दोनों मात्राएँ निरपेक्ष मान की आवश्यकता के बिना 1 से छोटी हैं। इस परिस्थिति में, चूँकि a ≤ b , हम देखते हैं कि (1 - a * α_j) ≥ (1 - b * α_j). विभिन्न असमानताओं को संतुष्ट करने वाले α_j के लिए हम जो सबसे बड़ा स्टेपसाइज़ चुन सकते हैं, वह सेटिंग α_j := 1/ b है । चूँकि यह सूचकांक j पर निर्भर नहीं करता है, इसका अर्थ है α_j := 1/ b सभी j के लिए और, इसी तरह, सभी q_j := (1 - a / b )। ये अवलोकन हमें हमारे i वें पुनरावृत्ति की अपेक्षित त्रुटि को सरल बनाने की अनुमति देते हैं :

चूंकि सभी वास्तविक मूल्यवान x के लिए हम जानते हैं कि (1 - x ) ≤ exp(- x ), हम देख सकते हैं कि i के अनंत तक जाने पर अपेक्षित त्रुटि तेजी से (σ/ a ) की निरंतर ऊपरी सीमा में परिवर्तित हो जाएगी।

यह हमें क्या बताता है, शायद दुर्भाग्य से, यह है कि ओरेकल में निहित यादृच्छिकता हमारे हाइकर को अंततः पर्वत के सटीक इष्टतम तल तक पहुंचने से रोक सकती है। ऐसा इसलिए है क्योंकि हम केवल यह गारंटी दे सकते हैं कि जब मैं अनंत तक जाता हूं , तो हाइकर और न्यूनतम स्थान के बीच की अपेक्षित दूरी अधिकतम 0 के बजाय अधिकतम (σ/ a ) होती है।

टिप्पणियाँ और अन्य निर्देश

ऐसा लगता है कि हमारा हाइकर वास्तव में एक सटीक ओरेकल होने से बर्बाद हो सकता है, शायद इस हाइकर को कुछ प्राचीन यूनानियों की कंपनी में डाल दिया जाए। मुझे लगता है कि किसी के सिर में एक आवाज सुनना हमेशा अच्छी बात नहीं होती है।

अब हमारे हाइकर के भाग्य को अनदेखा करते हुए, हमें ध्यान देना चाहिए कि यह विश्लेषण अपेक्षित अर्थों में किया गया था, लेकिन एक समान परिणाम प्राप्त करना संभव है जो उच्च संभावना के साथ सही है लेकिन एक बड़ी त्रुटि के साथ। एक तरीका यह है कि लेम्मा 0.2 को इस तरह से संशोधित किया जाए कि शोर कुछ निश्चित स्थिरांक से घिरा हो और फिर यह दिखाने के लिए सामान्य यादृच्छिक चर की एकाग्रता का उपयोग करें कि उच्च संभावना के साथ शोर कुछ चुनी हुई सीमा के भीतर रहता है, जिससे आप संशोधित लेम्मा 0.2 का उपयोग कर सकते हैं। .

हमें आगे यह जोड़ना चाहिए कि यदि कोई पर्याप्त रूप से साज़िश करता है, तो आप ओरेकल आधारित ग्रेडिएंट डिसेंट को चलाने की तुलना में एक बेहतर एल्गोरिथ्म बनाने की कोशिश कर सकते हैं जैसा कि कहा गया है। उदाहरण के लिए, शायद ग्रेडिएंट डिसेंट के प्रत्येक निष्पादन पर, आप oracle m बार क्वेरी करते हैं और परिणाम को औसत करते हैं ताकि आपके अनुमानित ग्रेडिएंट में भिन्नता कम हो जाए। ग्रेडिएंट डिसेंट एल्गोरिथम के संपूर्ण निष्पादन के लिए इस तरह का दृष्टिकोण त्रुटि को कैसे कम कर सकता है? यदि आप खेलने के लिए एक मजेदार खिलौना समस्या में रुचि रखते हैं, तो यकीनन यह एक ऐसी समस्या है जिससे आप खिलवाड़ कर सकते हैं!