समकालिक प्रक्षोभ प्रसंभाव्यता सन्निकटन

एक साथ गड़बड़ी स्टोकेस्टिक सन्निकटन (एसपीएसए) कई अज्ञात पैरामीटर वाले सिस्टम को अनुकूलित करने के लिए एक कलन विधि विधि है। यह एक प्रकार का स्टोकेस्टिक सन्निकटन एल्गोरिथम है। अनुकूलन पद्धति के रूप में, यह बड़े पैमाने पर जनसंख्या मॉडल, अनुकूली मॉडलिंग, सिमुलेशन अनुकूलन और वायुमंडलीय मॉडलिंग के लिए उपयुक्त है। एसपीएसए की वेबसाइट http://www.jhuapl.edu/SPSA पर कई उदाहरण प्रस्तुत किए गए हैं। इस विषय पर एक विस्तृत पुस्तक भटनागर एवं अन्य हैं। (2013)। इस विषय पर एक प्रारंभिक पेपर स्पैल (1987) है और मुख्य सिद्धांत और औचित्य प्रदान करने वाला मूलभूत पेपर स्पैल (1992) है।

एसपीएसए वैश्विक मिनीमा खोजने में सक्षम एक मूल विधि है, इस संपत्ति को तैयार किए हुयी धातु पे पानी चढाने की कला के रूप में अन्य तरीकों से साझा करना। इसकी मुख्य विशेषता ढाल सन्निकटन है जिसके लिए अनुकूलन समस्या के आयाम की परवाह किए बिना उद्देश्य फ़ंक्शन के केवल दो मापों की आवश्यकता होती है। याद रखें कि हम इष्टतम नियंत्रण खोजना चाहते हैं $u^{*}$ नुकसान के साथ समारोह $J(u)$:

$u^{*}=\arg \min _{u\in U}J(u).$

दोनों परिमित अंतर स्टोचैस्टिक सन्निकटन (FDSA) और एसपीएसए समान पुनरावृत्ति प्रक्रिया का उपयोग करते हैं:

$u_{n+1}=u_{n}-a_{n}{\hat {g}}_{n}(u_{n}),$

कहाँ $u_{n}=((u_{n})_{1},(u_{n})_{2},\ldots ,(u_{n})_{p})^{T}$ का प्रतिनिधित्व करता है $n^{th}$ पुनरावृति, ${\hat {g}}_{n}(u_{n})$ उद्देश्य समारोह के ढाल का अनुमान है $g(u)={\frac {\partial }{\partial u}}J(u)$ पर मूल्यांकन किया गया ${u_{n}}$, और $\{a_{n}\}$ एक धनात्मक संख्या क्रम है जो 0 में परिवर्तित हो रहा है। यदि $u_{n}$ एक पी-आयामी वेक्टर है $i^{th}$ सममित परिमित अंतर ढाल अनुमानक का घटक है:

एफडी: $({\hat {g_{n}}}(u_{n}))_{i}={\frac {J(u_{n}+c_{n}e_{i})-J(u_{n}-c_{n}e_{i})}{2c_{n}}},$

1 ≤i ≤p, जहां $e_{i}$ एक 1 के साथ इकाई वेक्टर है $i^{th}$ जगह, और $c_{n}$एक छोटी धनात्मक संख्या है जो n से घटती है। इस पद्धति के साथ, प्रत्येक के लिए J का 2p मूल्यांकन $g_{n}$ जरूरत है। स्पष्ट रूप से, जब p बड़ा होता है, तो यह अनुमानक दक्षता खो देता है।

अभी चलो $\Delta _{n}$ एक यादृच्छिक गड़बड़ी वेक्टर बनें। $i^{th}$ h> स्टोचैस्टिक गड़बड़ी ढाल अनुमानक का घटक है:

सपा: $({\hat {g_{n}}}(u_{n}))_{i}={\frac {J(u_{n}+c_{n}\Delta _{n})-J(u_{n}-c_{n}\Delta _{n})}{2c_{n}(\Delta _{n})_{i}}}.$

टिप्पणी करें कि एफडी एक समय में केवल एक दिशा को परेशान करता है, जबकि एसपी अनुमानक एक ही समय में सभी दिशाओं को परेशान करता है (सभी पी घटकों में अंश समान होता है)। प्रत्येक के लिए SPSA पद्धति में आवश्यक हानि फ़ंक्शन मापों की संख्या $g_{n}$ आयाम p से स्वतंत्र हमेशा 2 होता है। इस प्रकार, SPSA, FDSA की तुलना में p गुना कम फ़ंक्शन मूल्यांकन का उपयोग करता है, जो इसे बहुत अधिक कुशल बनाता है।

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

कन्वर्जेंस लेम्मा

द्वारा निरूपित करें

$b_{n}=E[{\hat {g}}_{n}|u_{n}]-\nabla J(u_{n})$

अनुमानक में पक्षपात ${\hat {g}}_{n}$. ये मान लीजिए $\{(\Delta _{n})_{i}\}$ शून्य-माध्य, बंधे हुए दूसरे के साथ सभी परस्पर स्वतंत्र हैं क्षण, और $E(|(\Delta _{n})_{i}|^{-1})$ समान रूप से बंधा हुआ। तब $b_{n}$→ 0 डब्ल्यू.पी. 1.

प्रमाण का रेखाचित्र

मुख्य विचार कंडीशनिंग का उपयोग करना है $\Delta _{n}$ ज़ाहिर करना $E[({\hat {g}}_{n})_{i}]$ और फिर दूसरे क्रम के टेलर विस्तार का उपयोग करने के लिए $J(u_{n}+c_{n}\Delta _{n})_{i}$ और $J(u_{n}-c_{n}\Delta _{n})_{i}$. शून्य माध्य और स्वतंत्रता का उपयोग करके बीजगणितीय जोड़तोड़ के बाद $\{(\Delta _{n})_{i}\}$, हम पाते हैं

$E[({\hat {g}}_{n})_{i}]=(g_{n})_{i}+O(c_{n}^{2})$

परिणाम परिकल्पना से आता है कि $c_{n}$→ 0।

इसके बाद हम कुछ परिकल्पनाओं को फिर से शुरू करते हैं जिनके तहत $u_{t}$ के वैश्विक न्यूनतम के सेट की संभावना में अभिसरण करता है $J(u)$. की दक्षता विधि के आकार पर निर्भर करती है $J(u)$, मापदंडों के मान $a_{n}$ और $c_{n}$ और गड़बड़ी की शर्तों का वितरण $\Delta _{ni}$. सबसे पहले, एल्गोरिथ्म मापदंडों को संतुष्ट करना चाहिए निम्नलिखित शर्तें:

• $a_{n}$ >0, $a_{n}$→0 जब n→∝ और $\sum _{n=1}^{\infty }a_{n}=\infty$. अच्छा विकल्प होगा $a_{n}={\frac {a}{n}};$ ए> 0;
• $c_{n}={\frac {c}{n^{\gamma }}}$, जहां सी> 0, $\gamma \in \left[{\frac {1}{6}},{\frac {1}{2}}\right]$;
• $\sum _{n=1}^{\infty }({\frac {a_{n}}{c_{n}}})^{2}<\infty$
• $\Delta _{ni}$ पारस्परिक रूप से स्वतंत्र शून्य-मतलब यादृच्छिक चर होना चाहिए, सममित रूप से शून्य के साथ वितरित किया जाना चाहिए $\Delta _{ni}<a_{1}<\infty$. का उलटा पहला और दूसरा क्षण $\Delta _{ni}$ परिमित होना चाहिए।

के लिए अच्छा विकल्प है $\Delta _{ni}$ रैडेमाकर बंटन है, अर्थात बर्नौली +-1 जिसकी प्रायिकता 0.5 है। अन्य विकल्प भी संभव हैं, लेकिन ध्यान दें कि समान और सामान्य वितरण का उपयोग नहीं किया जा सकता क्योंकि वे परिमित व्युत्क्रम क्षण स्थितियों को संतुष्ट नहीं करते हैं।

हानि फ़ंक्शन जे (यू) तीन बार लगातार भिन्न होने वाला फ़ंक्शन होना चाहिए और तीसरे डेरिवेटिव के अलग-अलग तत्वों को बाध्य किया जाना चाहिए: $|J^{(3)}(u)|<a_{3}<\infty$. भी, $|J(u)|\rightarrow \infty$ जैसा $u\rightarrow \infty$.

इसके साथ ही, $\nabla J$ Lipschitz निरंतर, परिबद्ध और ODE होना चाहिए ${\dot {u}}=g(u)$ प्रत्येक प्रारंभिक स्थिति के लिए एक अनूठा समाधान होना चाहिए। इन शर्तों के तहत और कुछ अन्य, $u_{k}$ J(u) के वैश्विक मिनीमा के समुच्चय की प्रायिकता में अभिसरण (गणित) (देखें मैरीक और चिन, 2008)।

यह दिखाया गया है कि भिन्नता की आवश्यकता नहीं है: निरंतरता और उत्तलता अभिसरण के लिए पर्याप्त हैं।

दूसरे क्रम (न्यूटन) विधियों का विस्तार

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

संदर्भ

• Bhatnagar, S., Prasad, H. L., and Prashanth, L. A. (2013), Stochastic Recursive Algorithms for Optimization: Simultaneous Perturbation Methods, Springer [1].
• Hirokami, T., Maeda, Y., Tsukada, H. (2006) "Parameter estimation using simultaneous perturbation stochastic approximation", Electrical Engineering in Japan, 154 (2), 30–3 [2]
• Maryak, J.L., and Chin, D.C. (2008), "Global Random Optimization by Simultaneous Perturbation Stochastic Approximation," IEEE Transactions on Automatic Control, vol. 53, pp. 780-783.
• Spall, J. C. (1987), “A Stochastic Approximation Technique for Generating Maximum Likelihood Parameter Estimates,” Proceedings of the American Control Conference, Minneapolis, MN, June 1987, pp. 1161–1167.
• Spall, J. C. (1992), “Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation,” IEEE Transactions on Automatic Control, vol. 37(3), pp. 332–341.
• Spall, J.C. (1998). "Overview of the Simultaneous Perturbation Method for Efficient Optimization" 2. Johns Hopkins APL Technical Digest, 19(4), 482–492.
• Spall, J.C. (2003) Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control, Wiley. ISBN 0-471-33052-3 (Chapter 7)