गणितीय अनुकूलन समस्याओं में ढाल के तरीकों का अवलोकन

प्रस्तावना

यह आलेख फ़ंक्शन ढाल के उपयोग के आधार पर गणितीय अनुकूलन समस्याओं को हल करने के तरीकों पर ध्यान केंद्रित करेगा। मुख्य लक्ष्य लेख में सभी सबसे महत्वपूर्ण विचारों को इकट्ठा करना है जो किसी भी तरह इस पद्धति और इसके विभिन्न संशोधनों से संबंधित हैं।





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

लेखक से ध्यान दें

लेखन के समय, मैंने एक शोध प्रबंध का बचाव किया, जिसके कार्य के लिए मुझे गणितीय अनुकूलन के मूल सैद्धांतिक तरीकों की गहरी समझ होनी चाहिए। फिर भी, मेरी आँखें (बाकी सभी से) अभी भी डरावने लंबे फॉर्मूलों से धुंधली हैं, इसलिए मैंने मुख्य विचारों को अलग करने के लिए बहुत समय बिताया जो कि ढाल के तरीकों के विभिन्न रूपों की विशेषता होगी। मेरा व्यक्तिगत लक्ष्य एक लेख लिखना है जिसमें विषय की अधिक या कम विस्तृत समझ के लिए आवश्यक न्यूनतम जानकारी हो। लेकिन तैयार रहें, कोई भी बिना फॉर्मूला के नहीं कर सकता।

समस्या का बयान

विधि का वर्णन करने से पहले, आपको पहले समस्या का वर्णन करना होगा, अर्थात्: "कई हैं $$$\ mathcal {K}$ और कार्य करते हैं $$$f: \ mathcal {K} \ rightarrow \ mathbb {R}$ एक बिंदु खोजने की जरूरत है $$$x ^ * \ in \ mathcal {K}$ ऐसा है $$$f (x) \ geq f (x ^ *)$ सभी के लिए $$$x \ in \ mathcal {K}$ ", जो आमतौर पर इस तरह लिखा जाता है

$$

$$f (x) \ rightarrow \ min_ {x \ in \ mathcal {K}}$$

सिद्धांत रूप में , यह आमतौर पर माना जाता है कि $$$च$ एक अलग और उत्तल कार्य है, और $$$\ mathcal {K}$ - उत्तल सेट (और भी बेहतर, अगर बिल्कुल भी $$$\ mathcal {K} = \ mathbb {R} ^ n$ ), यह हमें ढाल वंश को लागू करने की सफलता की कुछ गारंटी देता है। व्यवहार में, ढाल वंश को तब भी सफलतापूर्वक लागू किया जाता है, जब कार्य में उपरोक्त गुणों में से कोई भी नहीं होता है (लेख में बाद में एक उदाहरण)।

थोड़ा सा गणित

मान लीजिए कि अभी हमें केवल एक-आयामी फ़ंक्शन का न्यूनतम पता लगाने की आवश्यकता है

$$

$$f (x) \ rightarrow \ min_ {x \ in \ mathbb {R}}$$

17 वीं शताब्दी में, पियरे फर्मेट एक कसौटी पर खरा उतरा जिसने सरल अनुकूलन समस्याओं को हल करना संभव बना दिया, अर्थात् $$$x ^ *$ - न्यूनतम बिंदु $$$f ^ *$ तो

$$

$$f '(x ^ *) = 0$$

जहाँ $$$च ’$ - व्युत्पन्न $$$च$ । यह मानदंड एक रैखिक सन्निकटन पर आधारित है।

$$

$$f (x) \ लगभग f (x ^ *) + f '(x ^ *) (x-x ^ *) $$$

करीब $$$x$ को $$$x ^ *$ , और अधिक सटीक इस सन्निकटन। दाईं ओर एक अभिव्यक्ति है कि, जब $$$f '(x ^ *) \ neq 0$ शायद अधिक पसंद है $$$च (x ^ *)$ कम कसौटी का मुख्य सार है। बहुआयामी मामले में, इसी तरह रैखिक सन्निकटन से $$$f (x) \ लगभग f (x ^ *) + \ n नाबला f (x ^ *) ^ T (x-x ^ *)$ (बाद $$$x ^ Ty = \ sum_ {i = 1} ^ nx_iy_i$ - मानक स्केलर उत्पाद, लेखन का रूप इस तथ्य के कारण है कि स्केलर उत्पाद एक स्तंभ वेक्टर द्वारा पंक्ति वेक्टर के मैट्रिक्स उत्पाद के समान है), मानदंड प्राप्त किया जाता है

$$

$$\ n नबला f (x ^ *) = 0।$$

मूल्य $$$\ n नबला f (x ^ *)$ - समारोह ढाल $$$च$ बिंदु पर $$$x ^ *$ । इसके अलावा, शून्य की प्रवणता की समानता का अर्थ है, सभी आंशिक व्युत्पन्न की शून्य से समानता, इसलिए, बहुआयामी मामले में, कोई भी इस मानदंड को क्रमिक रूप से प्रत्येक चर के लिए अलग-अलग रूप से लागू कर सकता है।

यह ध्यान देने योग्य है कि ये स्थितियां आवश्यक हैं, लेकिन पर्याप्त नहीं है, सबसे सरल उदाहरण 0 के लिए है $$$f (x) = x ^ 2$ और $$$f (x) = x ^ 3$


यह मानदंड उत्तल कार्य के मामले में पर्याप्त है, मोटे तौर पर इस वजह से उत्तल कार्यों के लिए इतने सारे परिणाम प्राप्त करना संभव था।

द्विघात कार्य

में द्विघात कार्य $$$\ mathbb {R} ^ n$ रूप का एक कार्य है

$$

$$f (x) = f (x_1, x_2, \ ldots, x_n) = \ frac {1} {2} \ sum_ {i, j = 1} ^ na_ {ij} x_ix_j- sum_ {i = 1} ^ n b_ix_i + c$$

स्थान बचाने के लिए (और अनुक्रमित के साथ कम परेशान करने के लिए), यह फ़ंक्शन आमतौर पर मैट्रिक्स रूप में लिखा जाता है:

$$

$$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c,$$

जहाँ $$$x = (x_1, \ ldots, x_n) ^ T$ । $$$b = (b_1, \ ldots, b_n) ^ T$ । $$$ए$ एक मैट्रिक्स है जिस पर चौराहे पर है $$$मैं$ तार और $$$ज$ स्तंभ मान है
$$$\ frac {1} {2} (a_ {ij} + a_ {ji})$ ( $$$ए$ यह सममित हो जाता है - यह महत्वपूर्ण है)। अगला। जब एक द्विघात फ़ंक्शन का उल्लेख होता है, तो मेरे पास उपरोक्त फ़ंक्शन होगा।

मैं इस बारे में क्यों बात कर रहा हूं? तथ्य यह है कि द्विघात कार्य दो कारणों से अनुकूलन में महत्वपूर्ण हैं:

1. वे व्यवहार में भी होते हैं, उदाहरण के लिए, एक रैखिक कम से कम वर्ग प्रतिगमन का निर्माण करते समय
2. द्विघात फ़ंक्शन का ग्रेडिएंट एक रैखिक फ़ंक्शन है, विशेष रूप से ऊपर के फ़ंक्शन के लिए
   

   $$

   $$\ frac {\ आंशिक} {\ आंशिक x_i} f (x_1, x_2, \ ldots, x_n) = a_ {ii} x_i + \ sum_ {j \ neq i} \ frac {{}} (a_ {ij) } + a_ {ji}) x_j -b_i,$$
   
   या मैट्रिक्स रूप में
   

   $$

   $$\ n नाबला f (x) = Ax-b,$$
   
   इस प्रकार प्रणाली $$$\ n नबला f (x) = 0$ - रैखिक प्रणाली। एक प्रणाली जो रैखिक की तुलना में सरल है, मौजूद नहीं है। सोचा था कि मैं प्राप्त करने की कोशिश कर रहा था एक द्विघात समारोह का अनुकूलन - अनुकूलन समस्याओं का सबसे सरल वर्ग । दूसरी ओर, तथ्य यह है कि $$$\ n नबला f (x ^ *) = 0$ - आवश्यक न्यूनतम शर्तें अनुकूलन समस्याओं के माध्यम से रैखिक प्रणालियों को हल करना संभव बनाती हैं। थोड़ी देर बाद मैं आपको समझाने की कोशिश करूंगा कि यह समझ में आता है।
   

उपयोगी ढाल गुण

खैर, हमें पता चला है कि यदि कोई फ़ंक्शन अलग-अलग है (इसमें सभी वेरिएबल्स के संबंध में डेरिवेटिव है), तो न्यूनतम बिंदु पर ग्रेडिएंट शून्य के बराबर होना चाहिए। लेकिन क्या गैर-शून्य होने पर ढाल कोई उपयोगी जानकारी लेती है?

आइए एक सरल समस्या को हल करने का प्रयास करें: बिंदु दिया गया है $$$x$ बिंदु खोजें $$$\ bar {x}$ ऐसा है $$$f (\ bar {x}) <f (x)$ । आगे एक बिंदु लेते हैं $$$x$ फिर से रैखिक सन्निकटन का उपयोग $$$f (\ bar {x}) \ लगभग f (x) + \ nabla f (x) ^ T (\ बार {x} -x)$ । अगर आप लेते हैं $$$\ bar {x} = x- \ Alpha \ nabla f (x)$ । $$$\ अल्फा> 0$ तो हम प्राप्त करते हैं

$$

$$f (\ bar {x}) \ लगभग f (x) - \ alpha \ | \ nabla f (x) \ | ^ 2 <f (x)।$$

इसी तरह, अगर $$$\ अल्फा <0$ तो $$$f (\ bar {x})$ और होगा $$$च (x)$ (बाद $$$|| x || = \ sqrt {x_1 ^ 2 + x_2 ^ 2 + \ ldots + x_n ^ 2}$ )। फिर से, चूंकि हमने सन्निकटन का उपयोग किया था, ये विचार केवल छोटे के लिए सही होंगे $$$\ अल्फा$ । ऊपर संक्षेप में, यदि $$$\ n नबला f (x) \ neq 0$ , फिर ढाल कार्य में सबसे बड़ी स्थानीय वृद्धि की दिशा को इंगित करता है ।

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



ध्यान दें कि प्रपत्र के समीकरण द्वारा परिभाषित सतह के लिए $$$च (x) = c$ । $$$\ n नबला च (x)$ इस सतह पर सामान्य (सामान्य लोगों में - लंबवत) सेट करता है। यह भी ध्यान दें कि हालांकि ढाल समारोह में सबसे बड़ी वृद्धि की दिशा में दिखाती है, लेकिन इस बात की कोई गारंटी नहीं है कि ढाल के विपरीत दिशा में, आप एक न्यूनतम (उदाहरण के लिए, बाईं तस्वीर) पा सकते हैं।

धीरे-धीरे उतरना

मूल ढाल मूल विधि के लिए केवल एक छोटा सा कदम बचा था: हमने बिंदु से सीखा $$$x$ बात हो रही है $$$\ bar {x}$ कम फ़ंक्शन मान के साथ $$$च$ । क्या यह कई बार हमें दोहराने से रोकता है? वास्तव में, यह ढाल मूल है: हम अनुक्रम का निर्माण करते हैं

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k)।$$

मूल्य $$$\ Alpha_k$ स्टेप साइज कहा जाता है (मशीन लर्निंग में - सीखने की गति )। पसंद के बारे में कुछ शब्द $$$\ Alpha_k$ : अगर $$$\ Alpha_k$ - बहुत छोटा, क्रम धीरे-धीरे बदलता है, जो एल्गोरिथ्म को बहुत कुशल नहीं बनाता है; अगर $$$\ Alpha_k$ बहुत बड़ा है, तो रैखिक सन्निकटन खराब हो जाता है, और शायद गलत भी। व्यवहार में, चरण आकार को अक्सर अनुभवजन्य रूप से चुना जाता है, सिद्धांत रूप में, एक लिप्सीटेज ग्रेडिएंट आमतौर पर माना जाता है, अर्थात् यदि

$$

$$\ | \ n नाबला f (x) - \ nabla f (y) \ | \ leq L_ x-y \ |$$

सभी के लिए $$$x, y$ तो $$$\ Alpha_k <\ frac {2} {L}$ गारंटी घट जाती है $$$च (x_k)$ ।

द्विघात कार्यों के लिए विश्लेषण

अगर $$$ए$ एक सममित उल्टे मैट्रिक्स है, $$$Ax ^ * = b$ फिर द्विघात कार्य के लिए $$$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c$ बिंदु $$$x ^ *$ न्यूनतम बिंदु ( UPD) है बशर्ते कि यह न्यूनतम सभी पर मौजूद हो - $$$च$ के करीब नहीं ले जाता है $$$- \ infty$ मूल्यों केवल अगर $$$ए$ सकारात्मक निश्चित), और ढाल वंश विधि के लिए हम निम्नलिखित प्राप्त कर सकते हैं

$$

$$x_ {k + 1} -x ^ * = x_k- \ alpha_k \ nabla f (x_k) -x ^ * = x_k- \ alpha_k (Ax_k-b) -x ^ * =$$

$$

$$(x_k-x ^ *) - \ Alpha_kA (x_k-x ^ *) = = (I- \ Alpha_k A) (x_k-x ^ *),$$

जहाँ $$$मैं$ आइडेंटिटी मैट्रिक्स है, अर्थात $$$Ix = x$ सभी के लिए $$$x$ । अगर, हालांकि, $$$\ Alpha_k \ equiv \ Alpha$ यह निकल जाएगा

$$

$$\ | x_ {k} -x ^ * \ | = \ | (I- \ अल्फा A) ^ k (x_0-x ^ * *) \ | \ leq \ | I- \ अल्फा A \ | ^ k \ | x_0 -x ^ * \ |$$

बाईं ओर की अभिव्यक्ति चरण में प्राप्त सन्निकटन से दूरी है $$$k$ ढाल न्यूनतम बिंदु पर, दाईं ओर - प्रपत्र की एक अभिव्यक्ति $$$\ lambda ^ k \ beta$ जो अगर शून्य में परिवर्तित हो जाता है $$$| \ lambda | <1$ (जिस शर्त पर मैंने लिखा था $$$\ अल्फा$ पिछले पैराग्राफ में, वास्तव में यही गारंटी है)। यह मूल अनुमान यह सुनिश्चित करता है कि ढाल मूल रूप से परिवर्तित हो जाए।

ग्रेडिएंट डिसेंट मॉडिफिकेशन

अब मैं ढाल वंश के आमतौर पर इस्तेमाल किए जाने वाले संशोधनों के बारे में थोड़ी बात करना चाहूंगा, मुख्य रूप से तथाकथित

जड़त्वीय या त्वरित ढाल के तरीके

इस वर्ग की सभी विधियों को निम्नानुसार व्यक्त किया गया है

$$

$$x_ {k + 1} = x_k- \ Alpha_k \ nabla f (x_k) + \ Beta_k (x_k-x_ {k-1})।$$

अंतिम शब्द इसी "जड़ता" की विशेषता है, प्रत्येक चरण में एल्गोरिथ्म ढाल के खिलाफ जाने की कोशिश करता है, लेकिन साथ ही यह आंशिक रूप से जड़ता द्वारा उसी दिशा में चलता है जैसा कि पिछले पुनरावृत्ति में होता है। इस तरह के तरीकों में दो महत्वपूर्ण गुण हैं:

1. वे व्यावहारिक रूप से कम्प्यूटेशनल योजना में सामान्य ढाल वंश को जटिल नहीं करते हैं।
2. सावधानी से चयन के साथ $$$\ Alpha_k, \ Beta_k$ इस तरह की विधियां एक क्रमिक रूप से चयनित कदम के साथ साधारण ढाल वंश की तुलना में तेजी से परिमाण का एक क्रम हैं।

ऐसी पहली विधियों में से एक 20 वीं शताब्दी के मध्य में दिखाई दी और इसे भारी बॉल विधि कहा गया , जिसने इस विधि की जड़ता की प्रकृति को बताया: इस विधि में $$$\ Alpha_k, \ Beta_k$ से स्वतंत्र $$$k$ और उद्देश्य समारोह के आधार पर ध्यान से चयनित। यह ध्यान देने योग्य है $$$\ Alpha_k$ कुछ भी हो सकता है लेकिन $$$\ beta_k$ - आमतौर पर एक से थोड़ा कम ।

भारी गेंद विधि सबसे सरल जड़त्वीय विधि है, लेकिन बहुत पहले नहीं। इस मामले में, मेरी राय में, इन विधियों के सार को समझने के लिए बहुत पहली विधि काफी महत्वपूर्ण है।

चेबीशेव विधि

हां, हां, इस प्रकार की पहली विधि का आविष्कार चेबीशेव ने रैखिक समीकरणों की प्रणालियों को हल करने के लिए किया था। ढाल वंश के विश्लेषण में कुछ बिंदु पर, निम्नलिखित समानता प्राप्त की गई थी

$$

$$x_ {k + 1} -x ^ * = (I- \ Alpha_k A) (x_k-x ^ *) = \ ldots =$$

$$

$$(I- \ Alpha_kA) (I- \ Alpha_ {k-1} A) \ ldots (I- \ Alpha_1A) (x_0-x ^ *) = P_k (A) (x_0-x ^ *),$$

जहाँ $$$P_k$ कुछ डिग्री बहुपद है $$$k$ । उठा लेने की कोशिश क्यों नहीं की गई $$$\ Alpha_k$ ताकि $$$P_k (A) (x_0-x ^ *)$ क्या यह छोटा था? सार्वभौमिक बहुपदों में से एक गाँठ जो शून्य से कम से कम विचलित होती है, चेबीशेव बहुपद है। चेबीशेव की विधि अनिवार्य रूप से वंश मापदंडों का चयन करने में शामिल है ताकि $$$P_k$ चेब्शेव का एक बहुपद था। वास्तव में एक छोटी सी समस्या है: एक सामान्य ढाल वंश के लिए, यह बस संभव नहीं है। हालांकि, जड़त्वीय विधियों के लिए, यह संभव है। यह मुख्य रूप से इस तथ्य के कारण है कि चेबीशेव बहुपद दूसरे क्रम के पुनरावृत्ति संबंध को संतुष्ट करते हैं

$$

$$T_ {n + 1} (x) = 2xT_n (x) -T_ {n-1} (x),$$

इसलिए, उन्हें ढाल वंश के लिए नहीं बनाया जा सकता है, जो केवल एक पिछले मूल्य से एक नए मूल्य की गणना करता है, और जड़ता के लिए यह इस तथ्य के कारण संभव हो जाता है कि दो पिछले मूल्यों का उपयोग किया जाता है। यह पता चला है कि गणना की जटिलता $$$\ Alpha_k, \ Beta_k$ पर निर्भर नहीं करता है $$$k$ न ही अंतरिक्ष का आकार $$$एन$ ।

संयुग्मन विधि

एक और बहुत ही रोचक और महत्वपूर्ण तथ्य (हैमिल्टन-केली प्रमेय का एक परिणाम): किसी भी वर्ग मैट्रिक्स के लिए $$$ए$ आकार $$$n \ n n$ एक बहुपद है $$$पी$ डिग्री नहीं $$$एन$ जिसके लिए $$$P (A) = 0$ । यह दिलचस्प क्यों है? यह सब एक ही समानता के बारे में है

$$

$$x_ {k + 1} -x ^ * = P_k (A) (x_0-x ^ *)।$$

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

1. ढाल वंश का एक पुनरावृत्ति (खाता पैरामीटर गणना में लेने के बिना) में एक वेक्टर और 2-3 वेक्टर परिवर्धन द्वारा एक मैट्रिक्स गुणन होता है
2. मापदंडों की गणना के लिए वेक्टर द्वारा 1-2 मैट्रिक्स गुणा, वेक्टर द्वारा 2-3 स्केलर वेक्टर गुणा, और वैक्टर के कई अतिरिक्त की आवश्यकता होती है।

कम्प्यूटेशनल योजना में सबसे कठिन बात एक वेक्टर द्वारा मैट्रिक्स का गुणन है, यह आमतौर पर समय में किया जाता है $$$\ mathcal {O} (n ^ 2)$ हालांकि, एक विशेष कार्यान्वयन के लिए, इसमें किया जा सकता है $$$\ mathcal {O} (m)$ जहाँ $$$एम$ - में नॉनजेरो तत्वों की संख्या $$$ए$ । संयुग्म ढाल विधि के अभिसरण को देखते हुए, इससे अधिक नहीं $$$एन$ पुनरावृत्तियों को एल्गोरिथम की समग्र जटिलता मिलती है $$$\ mathcal {O} (nm)$ , जो सभी मामलों में बदतर नहीं है $$$\ mathcal {O} (n ^ 3)$ गॉस या चॉल्स्की विधि के लिए, लेकिन बहुत बेहतर अगर $$$m << n ^ 2$ ऐसा बहुत कम नहीं है।

संयुग्म ढाल प्रक्रिया भी अच्छी तरह से काम करती है अगर $$$च$ एक द्विघात फ़ंक्शन नहीं है, लेकिन यह कई चरणों में सीमित नहीं है और अक्सर छोटे अतिरिक्त संशोधनों की आवश्यकता होती है

नेस्टरोव विधि

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

$$

$$x_ {k + 1} = x_k- \ alp_k \ nabla f (x_k + \ beta_k (x_k-x_ {k-1})) + \ Beta_k (x_k-x_ {k-1}),$$

यह किसी भी जटिल गणना का अर्थ नहीं है $$$\ Alpha_k, \ Beta_k$ जैसा कि संयुग्म ढाल विधि में, सामान्य तौर पर, विधि का व्यवहार भारी गेंद विधि के समान होता है, लेकिन इसका अभिसरण आमतौर पर सिद्धांत और व्यवहार दोनों में बहुत अधिक विश्वसनीय होता है।

स्टोचैस्टिक ग्रेडिएंट डिसेंट

सामान्य ढाल वंश से केवल औपचारिक अंतर एक ढाल के बजाय एक फ़ंक्शन का उपयोग है $$$g (x, \ थीटा)$ ऐसा है $$$E_ \ theta g (x, \ theta) = \ nabla f (x)$ ( $$$E_ \ थीटा$ - यादृच्छिक अपेक्षा $$$$ थीटा$ ), तो स्टोचैस्टिक ग्रेडिएंट डिसेंट का रूप है

$$

$$x_ {k + 1} = x_k- \ alpha_kg (x_k, \ theta_k)।$$

$$$\ theta_k$ - यह कुछ यादृच्छिक पैरामीटर है जो हम प्रभावित नहीं करते हैं, लेकिन एक ही समय में हम औसतन ग्रेडिएंट के खिलाफ जाते हैं। एक उदाहरण के रूप में, कार्यों पर विचार करें

$$

$$f (x) = \ frac {1} {2m} \ sum_ {j = 1} ^ m_ x-y_j_ | ^ 2, ~~ \ nabla f (x) = \ frac {1} / मेरा} \ sum_ {j = 1} ^ m (x-y_j)$$

और

$$

$$g (x, i) = x-y_i।$$

अगर $$$मैं$ मान लेता है $$$1, \ ldots, m$ समान रूप से संभावना सिर्फ औसत $$$जी$ एक ढाल है $$$च$ । यह उदाहरण निम्नलिखित का संकेत भी है: ग्रेडिएंट की गणना की जटिलता $$$एम$ कम्प्यूटेशनल जटिलता से कई गुना अधिक $$$जी$ । यह स्टोकेस्टिक क्रमिक वंश को उसी समय में करने की अनुमति देता है $$$एम$ और अधिक पुनरावृत्तियों। इस तथ्य के बावजूद कि स्टोकेस्टिक प्रवणता वंश आमतौर पर सामान्य से धीमी गति से परिवर्तित होता है, पुनरावृत्तियों की इतनी बड़ी वृद्धि के कारण, प्रति यूनिट समय में अभिसरण दर में सुधार करना संभव है। जहां तक ​​मुझे पता है, इस समय स्टोकेस्टिक ग्रेडिएंट डिसेंट्रिएस अधिकांश न्यूरल नेटवर्क को प्रशिक्षित करने का मूल तरीका है, जो सभी प्रमुख एमएल पुस्तकालयों में लागू किया जाता है: टेंसोरफ्लो, टार्च, कैफ, सीएनटीके, आदि।

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

उप-ढाल वंश

यह भिन्नता आपको गैर-भिन्न कार्यों के साथ काम करने की अनुमति देती है, मैं इसे और अधिक विस्तार से वर्णन करूंगा। हमें फिर से रैखिक सन्निकटन को याद करना होगा - तथ्य यह है कि एक ढाल, एक अलग समारोह के माध्यम से उत्तलता की एक सरल विशेषता है $$$च$ उत्तल अगर और केवल अगर $$$f (y) \ geq f (x) + \ nabla f (x) ^ T (y-x)$ सभी के लिए $$$x, y$ । यह पता चला है कि एक उत्तल फ़ंक्शन को अलग करने की आवश्यकता नहीं है, लेकिन किसी भी बिंदु के लिए $$$x$ निश्चित रूप से इस तरह के एक वेक्टर है $$$जी$ कि $$$f (y) \ geq f (x) + g ^ T (y-x)$ सभी के लिए $$$य$ । ऐसा सदिश $$$जी$ जिसे आमतौर पर सबग्रेडिएंट कहा जाता है $$$च$ बिंदु पर $$$x$ सभी उपग्रहों के बिंदुओं के लिए सेट $$$x$ जिसे उपखंड कहा जाता है $$$x$ और निरूपित करें $$$\ आंशिक च (x)$ (पदनाम के बावजूद - इसका आंशिक डेरिवेटिव से कोई लेना-देना नहीं है)। एक आयामी मामले में $$$जी$ एक संख्या है, और उपरोक्त संपत्ति का सीधा सा मतलब है कि ग्राफ $$$च$ से होकर गुजरने वाली लाइन के ऊपर स्थित है $$$(x, f (x))$ और ढलान होना $$$जी$ (नीचे चित्र देखें) मैं ध्यान देता हूं कि एक बिंदु के लिए कई अवशिष्ट हो सकते हैं, यहां तक ​​कि एक अनंत संख्या भी।



एक बिंदु के लिए कम से कम एक सबग्रेडिएंट की गणना करना आमतौर पर बहुत मुश्किल नहीं है, एक अविकसित वंश अनिवार्य रूप से एक ग्रेडिएंट के बजाय एक सबग्रेडिएंट का उपयोग करता है। यह पता चला है कि यह पर्याप्त है; सिद्धांत रूप में, अभिसरण दर कम हो जाती है, हालांकि, उदाहरण के लिए, तंत्रिका नेटवर्क में एक अपरिहार्य फ़ंक्शन $$$ReLU (x) = \ max (0, x)$ वे इसे सिर्फ इसलिए उपयोग करना पसंद करते हैं क्योंकि प्रशिक्षण इसके साथ तेज है (यह है, वैसे, गैर-उत्तल गैर-परिवर्तनीय फ़ंक्शन का एक उदाहरण जिसमें (उप) ग्रेडिएंट वंश सफलतापूर्वक लागू होता है। फ़ंक्शन ही। $$$रेलू$ उत्तल लेकिन बहुस्तरीय तंत्रिका नेटवर्क युक्त $$$रेलू$ , गैर-उत्तल और गैर-परिवर्तनीय)। एक उदाहरण के लिए, एक फ़ंक्शन के लिए $$$च (x) = | x |$ उपखंड की गणना बहुत सरलता से की जाती है

$$

$$\ आंशिक f (x) = \ start {मामलों} 1, & x> 0, \\ -1, और x <0, \\ [-1, 1], और x = 0। \ अंत {मामलों}$$

शायद यह जानने के लिए आखिरी महत्वपूर्ण बात यह है कि उप-ग्रेडिएंट वंश एक स्थिर चरण आकार में परिवर्तित नहीं होता है । उपरोक्त फ़ंक्शन के लिए यह देखना सबसे आसान है। $$$च (x) = | x |$ । यहां तक ​​कि एक बिंदु पर व्युत्पन्न की अनुपस्थिति अभिसरण को तोड़ती है:

1. मान लीजिए कि हमने बिंदु से शुरू किया $$$x_0$ ।
2. उप-ढाल वंश कदम:
   

   $$

   $$x_ {k + 1} = \ _ {मामलों} x_ {k} -1, & x> 0, \\ x_k + 1, & x <0, \\ ??? & x = 0। \ अंत {मामलों}$$
3. अगर $$$x_0> 0$ तो पहले कुछ कदम हम एक घटाएँगे, यदि $$$x_0 <0$ फिर जोड़ें। एक तरह से या किसी अन्य, हम कुछ बिंदु पर खुद को अंतराल में पाएंगे $$$[0, 1)$ जिससे हम मिलते हैं $$$[- 1, 0)$ , और फिर हम इन अंतरालों के दो बिंदुओं के बीच कूदेंगे।

सिद्धांत रूप में, उप-ग्रेडिएंट वंश के लिए, चरणों का क्रम लेने की सिफारिश की जाती है

$$

$$\ Alpha_k = \ frac {1} {(k + 1) ^ c}।$$

जहाँ $$$सी$ आमतौर पर $$$1$ या $$$\ frac {1} {2}$ । व्यवहार में, मैंने अक्सर सफल कदम देखे $$$\ Alpha_k = e ^ {- ck}$ , हालांकि आम तौर पर बोलने वाले ऐसे कदमों के लिए कोई अभिसरण नहीं होगा।

समीपस्थ विधियाँ

दुर्भाग्य से, मैं अनुकूलन के संदर्भ में "समीपस्थ" के लिए एक अच्छा अनुवाद नहीं जानता, इसीलिए मैं सिर्फ इस पद्धति को कहूंगा। समीपस्थ विधियाँ प्रक्षेप्य ढाल विधियों के सामान्यीकरण के रूप में प्रकट हुईं। विचार बहुत सरल है: यदि कोई फ़ंक्शन है $$$च$ राशि के रूप में प्रतिनिधित्व किया $$$f (x) = \ varphi (x) + h (x)$ जहाँ $$$\ varphi$ एक अलग-अलग उत्तल फ़ंक्शन है, और $$$ज (x)$ - उत्तल, जिसके लिए एक विशेष समीपस्थ ऑपरेटर है $$$प्रॉक्स_ह (x)$ (इस लेख में मैं अपने आप को केवल उदाहरणों तक सीमित करूंगा, सामान्य शब्दों में वर्णन नहीं करूंगा), फिर क्रमिक वंश के अभिसरण गुण $$$\ varphi$ रहने के लिए और ढाल वंश के लिए $$$च$ यदि प्रत्येक पुनरावृत्ति के बाद वर्तमान बिंदु के लिए यह समीपस्थ ऑपरेटर लागू होता है $$$x_k$ , दूसरे शब्दों में, समीपस्थ विधि का सामान्य रूप इस तरह दिखता है:

$$

$$x_ {k + 1} = prox _ {\ Alpha_kh} (x_k- \ alp_k \ nabla \ varphi (x_k))$$

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

1. $$$ज (x)$ - उत्तल सेट का सूचक कार्य $$$\ mathcal {K}$ वह है
   

   $$

   $$h (x) = \ start {case} 0, और x \ in \ mathcal {K}, \\ + \ infty, और x \ notin \ mathcal {K}। \\ \ end {केस} $$$
   
   इस मामले में $$$प्रॉक्स _ {\ Alpha_kh} (x)$ सेट पर एक प्रक्षेपण है $$$\ mathcal {K}$ , वह है, '' निकटतम $$$x$ बिंदु निर्धारित करें $$$\ mathcal {K}$ "। इस प्रकार, हम ग्रेड के लिए केवल ढाल वंश को प्रतिबंधित करते हैं $$$\ mathcal {K}$ , जो हमें प्रतिबंधों के साथ समस्याओं को हल करने की अनुमति देता है। दुर्भाग्य से, सामान्य मामले में प्रक्षेपण की गणना करना और भी मुश्किल हो सकता है, इसलिए इस पद्धति का आमतौर पर उपयोग किया जाता है यदि बाधाएं सरल हैं, उदाहरण के लिए, तथाकथित बॉक्स-बाधाएं: प्रत्येक समन्वय के लिए
   

   $$

   $$l_i \ leq x_i \ leq r_i$$
   
   
2. $$$h (x) = \ lambda \ | x \ | _1 = \ lambda \ sum_ {i =}} ^ n | x_i |$ - $$$\ ell_1$ -regulyarizatsiya। वे इस शब्द को मशीन सीखने में अनुकूलन समस्याओं से जोड़ना पसंद करते हैं ताकि पीछे हटने से बचा जा सके। इस तरह का नियमितीकरण भी कम से कम महत्वपूर्ण घटकों को शून्य करने के लिए जाता है। इस तरह के एक समारोह के लिए, समीपस्थ ऑपरेटर का रूप होता है (एक एकल समन्वय के लिए एक अभिव्यक्ति नीचे वर्णित है)
   

   $$

   $$[प्रॉक्स _ {\ अल्फ़ा ह} (x)] _ i = \ _ {केस} शुरू करें x_i- \ अल्फ़ा, और x_i> \ अल्फ़ा, \\ x_i + \ अल्फ़ा, और x_i <- \ Alpha, \\ 0, & x_i \ _ [- \ अल्फा, \ अल्फा], \ अंत {मामलों} $ मे$$
   
   जिसकी गणना करना बहुत आसान है।

निष्कर्ष

यह मेरे लिए ज्ञात ढाल विधि के मुख्य रूपों को समाप्त करता है। शायद अंत में मैं ध्यान दूंगा कि ये सभी संशोधन (शायद संयुग्म ढाल विधि को छोड़कर) आसानी से एक दूसरे के साथ बातचीत कर सकते हैं। मैंने जानबूझकर इस सूची में न्यूटन विधि और अर्ध-न्यूटन विधियों (बीएफजीएस और अन्य) को शामिल नहीं किया है: हालांकि वे एक ढाल का उपयोग करते हैं, वे अधिक जटिल तरीके हैं और विशिष्ट अतिरिक्त गणनाओं की आवश्यकता होती है, जो आमतौर पर एक ढाल की गणना करने के लिए अधिक कम्प्यूटेशनल रूप से महंगी होती हैं। फिर भी, यदि यह पाठ मांग में है, तो मुझे उन पर इसी तरह की समीक्षा करने में खुशी होगी।

प्रयुक्त / अनुशंसित साहित्य

बॉयड। एस, वैंडेनबर्ग एल। उत्तल अनुकूलन
शेवचुक जेआर एक आक्रामक दर्द के बिना संयुग्मक ढाल विधि का परिचय
बर्टसेकस डीपी उत्तल अनुकूलन सिद्धांत

नेस्टरोव यू। ई। उत्तल अनुकूलन के तरीके
गैसनिकोव ए.वी. यूनिवर्सल ग्रेडिएंट वंश