एमएम एल्गोरिथ्म: Difference between revisions
(Created page with "एमएम एल्गोरिथ्म एक पुनरावृत्त अनुकूलन विधि है जो किसी फ़ंक्शन क...") |
No edit summary |
||
| Line 1: | Line 1: | ||
एमएम एल्गोरिथ्म | एमएम एल्गोरिथ्म पुनरावृत्त [[अनुकूलन]] विधि है जो किसी फ़ंक्शन के उत्तल फ़ंक्शन का उपयोग उसकी मैक्सिमा या मिनिमा को खोजने के लिए करता है। एमएम का अर्थ "मेजराइज़-मिनिमाइज़ेशन" या "माइनराइज़-मैक्सिमाइज़ेशन" है, यह इस पर निर्भर करता है कि वांछित अनुकूलन न्यूनतमकरण है या अधिकतमकरण। नाम के बावजूद, एमएम स्वयं एल्गोरिदम नहीं है, बल्कि अनुकूलन एल्गोरिदम का निर्माण कैसे करें इसका विवरण है। | ||
अपेक्षा-अधिकतमकरण एल्गोरिदम को एमएम एल्गोरिदम के | अपेक्षा-अधिकतमकरण एल्गोरिदम को एमएम एल्गोरिदम के विशेष मामले के रूप में माना जा सकता है।<ref>{{cite web|last=Lange|first=Kenneth|title=एमएम एल्गोरिदम|url=http://www.stat.berkeley.edu/~aldous/Colloq/lange-talk.pdf}}</ref><ref>{{cite book | ||
|last1=Lange |first1=Kenneth | |last1=Lange |first1=Kenneth | ||
|title=MM Optimization Algorithms | |title=MM Optimization Algorithms | ||
| Line 19: | Line 19: | ||
}}</ref> | }}</ref> | ||
== इतिहास == | |||
==इतिहास== | |||
एमएम एल्गोरिदम का ऐतिहासिक आधार कम से कम 1970 से माना जा सकता है, जब ओर्टेगा और रीनबोल्ड्ट लाइन खोज विधियों से संबंधित अध्ययन कर रहे थे।<ref>{{cite book | एमएम एल्गोरिदम का ऐतिहासिक आधार कम से कम 1970 से माना जा सकता है, जब ओर्टेगा और रीनबोल्ड्ट लाइन खोज विधियों से संबंधित अध्ययन कर रहे थे।<ref>{{cite book | ||
|last1=Ortega |first1=J.M. | |last1=Ortega |first1=J.M. | ||
| Line 29: | Line 28: | ||
|url=https://archive.org/details/iterativesolutio0000orte | |url=https://archive.org/details/iterativesolutio0000orte | ||
|url-access=registration |isbn=9780898719468 | |url-access=registration |isbn=9780898719468 | ||
}}</ref> | }}</ref> ही अवधारणा अलग-अलग क्षेत्रों में अलग-अलग रूपों में पुनः प्रकट होती रही। 2000 में, हंटर और लैंग ने एमएम को सामान्य रूपरेखा के रूप में सामने रखा।<ref>{{cite journal | ||
|last1=Hunter|first1=D.R. | |last1=Hunter|first1=D.R. | ||
|last2=Lange|first2=K. | |last2=Lange|first2=K. | ||
| Line 39: | Line 38: | ||
|jstor=1390613 | |jstor=1390613 | ||
|citeseerx=10.1.1.206.1351 | |citeseerx=10.1.1.206.1351 | ||
}}</ref> हाल के अध्ययन{{who?|date=September 2018}} ने इस पद्धति को गणित, सांख्यिकी, [[ यंत्र अधिगम ]] और [[ अभियांत्रिकी ]] जैसे विषय क्षेत्रों की | }}</ref> हाल के अध्ययन{{who?|date=September 2018}} ने इस पद्धति को गणित, सांख्यिकी, [[ यंत्र अधिगम ]] और [[ अभियांत्रिकी ]] जैसे विषय क्षेत्रों की विस्तृत श्रृंखला में लागू किया है।{{cn|date=September 2018}} | ||
==एल्गोरिदम== | ==एल्गोरिदम== | ||
[[File:Mmalgorithm.jpg|right|thumb|एमएम एल्गोरिथ्म]]एमएम एल्गोरिथ्म | [[File:Mmalgorithm.jpg|right|thumb|एमएम एल्गोरिथ्म]]एमएम एल्गोरिथ्म सरोगेट फ़ंक्शन को ढूंढकर काम करता है जो उद्देश्य फ़ंक्शन को छोटा या प्रमुख बनाता है। सरोगेट फ़ंक्शन को अनुकूलित करने से या तो उद्देश्य फ़ंक्शन के मूल्य में सुधार होगा या इसे अपरिवर्तित छोड़ दिया जाएगा। | ||
लघुकरण-अधिकतमकरण संस्करण लेते हुए, आइए <math> f(\theta) </math> उद्देश्य अवतल फलन को अधिकतम किया जाना चाहिए। पर {{mvar|m}} एल्गोरिथम का चरण, <math> m=0,1... </math>, निर्मित कार्य <math> g(\theta|\theta_m) </math> ऑब्जेक्टिव फ़ंक्शन (सरोगेट फ़ंक्शन) का लघुकृत संस्करण कहा जाएगा <math> \theta_m </math> अगर | लघुकरण-अधिकतमकरण संस्करण लेते हुए, आइए <math> f(\theta) </math> उद्देश्य अवतल फलन को अधिकतम किया जाना चाहिए। पर {{mvar|m}} एल्गोरिथम का चरण, <math> m=0,1... </math>, निर्मित कार्य <math> g(\theta|\theta_m) </math> ऑब्जेक्टिव फ़ंक्शन (सरोगेट फ़ंक्शन) का लघुकृत संस्करण कहा जाएगा <math> \theta_m </math> अगर | ||
| Line 51: | Line 50: | ||
: <math> \theta_{m+1}=\arg\max_{\theta}g(\theta|\theta_m) </math> | : <math> \theta_{m+1}=\arg\max_{\theta}g(\theta|\theta_m) </math> | ||
उपरोक्त पुनरावृत्तीय विधि इसकी गारंटी देगी <math> f(\theta_m) </math> | उपरोक्त पुनरावृत्तीय विधि इसकी गारंटी देगी <math> f(\theta_m) </math> स्थानीय इष्टतम या काठी बिंदु के रूप में परिवर्तित हो जाएगा {{mvar|m}} अनंत तक जाता है.<ref>{{cite journal |last=Wu |first=C. F. Jeff |year=1983 |title=ईएम एल्गोरिथम के अभिसरण गुणों पर|journal=[[Annals of Statistics]] |volume=11 |issue=1 |pages=95–103 |doi= 10.1214/aos/1176346060|jstor=2240463 |doi-access=free }}</ref> उपरोक्त निर्माण द्वारा | ||
: <math> f(\theta_{m+1}) \ge g(\theta_{m+1}|\theta_m) \ge g(\theta_m|\theta_m)= f(\theta_m)</math> | : <math> f(\theta_{m+1}) \ge g(\theta_{m+1}|\theta_m) \ge g(\theta_m|\theta_m)= f(\theta_m)</math> | ||
का मार्चिंग <math>\theta_m </math> और उद्देश्य फ़ंक्शन के सापेक्ष सरोगेट फ़ंक्शन चित्र में दिखाया गया है। | का मार्चिंग <math>\theta_m </math> और उद्देश्य फ़ंक्शन के सापेक्ष सरोगेट फ़ंक्शन चित्र में दिखाया गया है। | ||
मेजराइज़-मिनिमाइज़ेशन | मेजराइज़-मिनिमाइज़ेशन ही प्रक्रिया है लेकिन न्यूनतम करने के लिए उत्तल उद्देश्य होता है। | ||
==सरोगेट फ़ंक्शन का निर्माण== | ==सरोगेट फ़ंक्शन का निर्माण== | ||
Revision as of 18:26, 11 August 2023
एमएम एल्गोरिथ्म पुनरावृत्त अनुकूलन विधि है जो किसी फ़ंक्शन के उत्तल फ़ंक्शन का उपयोग उसकी मैक्सिमा या मिनिमा को खोजने के लिए करता है। एमएम का अर्थ "मेजराइज़-मिनिमाइज़ेशन" या "माइनराइज़-मैक्सिमाइज़ेशन" है, यह इस पर निर्भर करता है कि वांछित अनुकूलन न्यूनतमकरण है या अधिकतमकरण। नाम के बावजूद, एमएम स्वयं एल्गोरिदम नहीं है, बल्कि अनुकूलन एल्गोरिदम का निर्माण कैसे करें इसका विवरण है।
अपेक्षा-अधिकतमकरण एल्गोरिदम को एमएम एल्गोरिदम के विशेष मामले के रूप में माना जा सकता है।[1][2] हालाँकि, ईएम एल्गोरिदम में सशर्त अपेक्षाएं आमतौर पर शामिल होती हैं, जबकि एमएम एल्गोरिदम में उत्तलता और असमानताएं मुख्य फोकस होती हैं, और ज्यादातर मामलों में इसे समझना और लागू करना आसान होता है।[3]
इतिहास
एमएम एल्गोरिदम का ऐतिहासिक आधार कम से कम 1970 से माना जा सकता है, जब ओर्टेगा और रीनबोल्ड्ट लाइन खोज विधियों से संबंधित अध्ययन कर रहे थे।[4] ही अवधारणा अलग-अलग क्षेत्रों में अलग-अलग रूपों में पुनः प्रकट होती रही। 2000 में, हंटर और लैंग ने एमएम को सामान्य रूपरेखा के रूप में सामने रखा।[5] हाल के अध्ययन[who?] ने इस पद्धति को गणित, सांख्यिकी, यंत्र अधिगम और अभियांत्रिकी जैसे विषय क्षेत्रों की विस्तृत श्रृंखला में लागू किया है।[citation needed]
एल्गोरिदम
एमएम एल्गोरिथ्म सरोगेट फ़ंक्शन को ढूंढकर काम करता है जो उद्देश्य फ़ंक्शन को छोटा या प्रमुख बनाता है। सरोगेट फ़ंक्शन को अनुकूलित करने से या तो उद्देश्य फ़ंक्शन के मूल्य में सुधार होगा या इसे अपरिवर्तित छोड़ दिया जाएगा।
लघुकरण-अधिकतमकरण संस्करण लेते हुए, आइए उद्देश्य अवतल फलन को अधिकतम किया जाना चाहिए। पर m एल्गोरिथम का चरण, , निर्मित कार्य ऑब्जेक्टिव फ़ंक्शन (सरोगेट फ़ंक्शन) का लघुकृत संस्करण कहा जाएगा अगर
फिर, अधिकतम करें के बजाय , और जाने
उपरोक्त पुनरावृत्तीय विधि इसकी गारंटी देगी स्थानीय इष्टतम या काठी बिंदु के रूप में परिवर्तित हो जाएगा m अनंत तक जाता है.[6] उपरोक्त निर्माण द्वारा
का मार्चिंग और उद्देश्य फ़ंक्शन के सापेक्ष सरोगेट फ़ंक्शन चित्र में दिखाया गया है।
मेजराइज़-मिनिमाइज़ेशन ही प्रक्रिया है लेकिन न्यूनतम करने के लिए उत्तल उद्देश्य होता है।
सरोगेट फ़ंक्शन का निर्माण
उद्देश्य फ़ंक्शन के वांछित प्रमुख/अल्पसंख्यक संस्करण के निर्माण के लिए कोई भी असमानता का उपयोग कर सकता है। विशिष्ट विकल्पों में शामिल हैं
- जेन्सेन की असमानता
- उत्तलता असमानता
- कॉची-श्वार्ज़ असमानता
- अंकगणित और ज्यामितीय साधनों की असमानता
- दूसरे क्रम के टेलर के माध्यम से द्विघात प्रमुखीकरण/लघुकरण, सीमित वक्रता के साथ दो-विभेदक कार्यों का विस्तार।
संदर्भ
- ↑ Lange, Kenneth. "एमएम एल्गोरिदम" (PDF).
- ↑ Lange, Kenneth (2016). MM Optimization Algorithms. SIAM. doi:10.1137/1.9781611974409. ISBN 978-1-61197-439-3.
- ↑ Lange, K.; Zhou, H. (2022). "A legacy of EM algorithms". International Statistical Review. 90: S52–S66. doi:10.1111/insr.12526.
- ↑ Ortega, J.M.; Rheinboldt, W.C. (1970). Iterative Solutions of Nonlinear Equations in Several Variables. New York: Academic. pp. 253–255. ISBN 9780898719468.
- ↑ Hunter, D.R.; Lange, K. (2000). "Quantile Regression via an MM Algorithm". Journal of Computational and Graphical Statistics. 9 (1): 60–77. CiteSeerX 10.1.1.206.1351. doi:10.2307/1390613. JSTOR 1390613.
- ↑ Wu, C. F. Jeff (1983). "ईएम एल्गोरिथम के अभिसरण गुणों पर". Annals of Statistics. 11 (1): 95–103. doi:10.1214/aos/1176346060. JSTOR 2240463.
