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

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

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

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

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

$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}$ P-आयामी वेक्टर है $i^{th}$ सममित परिमित अंतर ढाल अनुमानक का घटक है।

FD $({\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> स्टोकेस्टिक गड़बड़ी ढाल अनुमानक का घटक है।

SP : $({\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}}}.$

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

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

अभिसरण लेम्मा

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

$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 W.P. 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)।

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

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

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

संदर्भ

• 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)