एमएम एल्गोरिथ्म: Difference between revisions
From Vigyanwiki
No edit summary |
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 8: | Line 8: | ||
|doi=10.1137/1.9781611974409 | |doi=10.1137/1.9781611974409 | ||
|isbn=978-1-61197-439-3 | |isbn=978-1-61197-439-3 | ||
}}</ref> | }}</ref>चूँकि, ईएम एल्गोरिदम में [[सशर्त अपेक्षा|कंडीशनल अपेक्षाएं]] सामान्यतः सम्मिलित होती हैं, जबकि एमएम एल्गोरिदम में उत्तलता और असमानताएं मुख्य फोकस होती हैं, और प्रायः स्थितियों में इसे समझना और प्रारम्भ करना सरल होता है।<ref>{{cite journal | ||
|last1=Lange|first1=K. | |last1=Lange|first1=K. | ||
|last2=Zhou|first2=H. | |last2=Zhou|first2=H. | ||
| Line 20: | Line 19: | ||
== इतिहास == | == इतिहास == | ||
एमएम एल्गोरिदम का ऐतिहासिक आधार कम से कम 1970 से माना जा सकता है, जब ओर्टेगा और रीनबोल्ड्ट लाइन | एमएम एल्गोरिदम का ऐतिहासिक आधार कम से कम 1970 से माना जा सकता है, जब ओर्टेगा और रीनबोल्ड्ट लाइन शोध विधियों से संबंधित अध्ययन कर रहे थे।<ref>{{cite book | ||
|last1=Ortega |first1=J.M. | |last1=Ortega |first1=J.M. | ||
|last2=Rheinboldt|first2=W.C. | |last2=Rheinboldt|first2=W.C. | ||
| Line 28: | Line 27: | ||
|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 38: | Line 37: | ||
|jstor=1390613 | |jstor=1390613 | ||
|citeseerx=10.1.1.206.1351 | |citeseerx=10.1.1.206.1351 | ||
}}</ref> | }}</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> f(\theta) </math> उद्देश्य अवतल फलन को अधिकतम किया जाना चाहिए। पर {{mvar|m}} एल्गोरिथम का चरण, <math> m=0,1... </math>, निर्मित फलन <math> g(\theta|\theta_m) </math> ऑब्जेक्टिव फलन (सरोगेट फलन) का लघुकृत संस्करण <math> \theta_m </math> को कहा जाएगा, यदि | ||
: <math> g(\theta|\theta_m) \le f(\theta) \text{ for all } \theta </math> | : <math> g(\theta|\theta_m) \le f(\theta) \text{ for all } \theta </math> | ||
: <math> g(\theta_m|\theta_m)=f(\theta_m) </math> | : <math> g(\theta_m|\theta_m)=f(\theta_m) </math> | ||
फिर, अधिकतम | फिर, अधिकतम <math> g(\theta|\theta_m) </math> के अतिरिक्त <math> f(\theta) </math> है: | ||
: <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> देगा कि जैसे-जैसे {{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> मार्चिंग और उद्देश्य फलन के सापेक्ष सरोगेट फलन चित्र में दिखाया गया है। | |||
मेजराइज़-मिनिमाइज़ेशन | मेजराइज़-मिनिमाइज़ेशन एक ही प्रक्रिया है किन्तु न्यूनतम करने के लिए उत्तल उद्देश्य होता है। | ||
==सरोगेट | ==सरोगेट फलन का निर्माण== | ||
उद्देश्य | उद्देश्य फलन के वांछित प्रमुख/अल्पसंख्यक संस्करण के निर्माण के लिए कोई भी असमानता का उपयोग कर सकता है। विशिष्ट विकल्पों में सम्मिलित हैं: | ||
* जेन्सेन की असमानता | * जेन्सेन की असमानता | ||
* [[उत्तलता असमानता]] | * [[उत्तलता असमानता]] | ||
* कॉची-श्वार्ज़ असमानता | * कॉची-श्वार्ज़ असमानता | ||
* [[अंकगणित और ज्यामितीय साधनों की असमानता]] | * [[अंकगणित और ज्यामितीय साधनों की असमानता]] | ||
* दूसरे क्रम के टेलर के माध्यम से द्विघात प्रमुखीकरण/लघुकरण, सीमित वक्रता के साथ दो-विभेदक | * दूसरे क्रम के टेलर के माध्यम से द्विघात प्रमुखीकरण/लघुकरण, सीमित वक्रता के साथ दो-विभेदक फलनो का विस्तार। | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 12:14, 13 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.
