मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम: Difference between revisions

Revision as of 18:37, 2 December 2023

प्रस्ताव संभाव्यता वितरण Q अगले बिंदु का प्रस्ताव करता है जिस पर यादृच्छिक चाल चल सकती है।

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

इतिहास

एल्गोरिथम का नाम आंशिक रूप से निकोलस मेट्रोपोलिस के नाम पर रखा गया है, जो 1953 के पेपर के पहले सह-लेखक थे, जिसका शीर्षक एरियाना डब्ल्यू. रोसेनब्लुथ, मार्शल रोसेनब्लथ, ऑगस्टा एच. टेलर और एडवर्ड टेलर के साथ फास्ट कंप्यूटिंग मशीनों द्वारा राज्य की गणना का समीकरण था। कई वर्षों तक एल्गोरिथम को केवल मेट्रोपोलिस एल्गोरिथम के रूप में जाना जाता था।^[1]^[2] पेपर ने सममित प्रस्ताव वितरण के मामले के लिए एल्गोरिदम का प्रस्ताव दिया, लेकिन 1970 में, डब्ल्यू.के. हेस्टिंग्स ने इसे अधिक सामान्य मामले तक विस्तारित किया।^[3]सामान्यीकृत विधि को अंततः दोनों नामों से पहचाना गया, हालांकि मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम शब्द का पहला उपयोग अस्पष्ट है।

मेट्रोपोलिस एल्गोरिथम के विकास के श्रेय के संबंध में कुछ विवाद मौजूद हैं। मेट्रोपोलिस, जो विधि के कम्प्यूटेशनल पहलुओं से परिचित थे, ने स्टैनिस्लाव उलम के साथ पुराने लेख में मोंटे कार्लो शब्द गढ़ा था, और सैद्धांतिक प्रभाग में उस समूह का नेतृत्व किया था जिसने 1952 में प्रयोगों में उपयोग किए गए MANIAC I कंप्यूटर को डिजाइन और निर्मित किया था। हालाँकि, 2003 से पहले एल्गोरिथम के विकास का कोई विस्तृत विवरण नहीं था। अपनी मृत्यु से कुछ समय पहले, मार्शल रोसेनब्लुथ ने 1953 के प्रकाशन की 50वीं वर्षगांठ के अवसर पर LANL में 2003 के सम्मेलन में भाग लिया। इस सम्मेलन में, रोसेनब्लुथ ने सांख्यिकीय यांत्रिकी के लिए मोंटे कार्लो एल्गोरिदम की उत्पत्ति नामक प्रस्तुति में एल्गोरिदम और उसके विकास का वर्णन किया।^[4] 2005 के जर्नल लेख में गुबर्नैटिस द्वारा और अधिक ऐतिहासिक स्पष्टीकरण दिया गया है^[5]50वीं वर्षगांठ सम्मेलन का पुनर्गणना। रोसेनब्लुथ ने यह स्पष्ट किया कि उन्होंने और उनकी पत्नी एरियाना ने यह काम किया, और मेट्रोपोलिस ने कंप्यूटर समय प्रदान करने के अलावा विकास में कोई भूमिका नहीं निभाई।

यह एडवर्ड टेलर के लेख का खंडन करता है, जिन्होंने अपने संस्मरणों में कहा है कि 1953 के लेख के पांच लेखकों ने दिनों (और रातों) के लिए साथ काम किया।^[6]इसके विपरीत, रोसेनब्लुथ का विस्तृत विवरण टेलर को सांख्यिकीय यांत्रिकी का लाभ उठाने और विस्तृत गतिकी का पालन करने के बजाय समग्र औसत लेने के लिए महत्वपूर्ण लेकिन प्रारंभिक सुझाव का श्रेय देता है। रोसेनब्लुथ कहते हैं, इसने उन्हें सामान्यीकृत मोंटे कार्लो दृष्टिकोण के बारे में सोचना शुरू कर दिया - विषय जिसके बारे में उनका कहना है कि उन्होंने जॉन वॉन न्यूमैन के साथ अक्सर चर्चा की थी। एरियाना रोसेनब्लुथ ने बताया (2003 में गुबर्नैटिस को) कि ऑगस्टा टेलर ने कंप्यूटर का काम शुरू किया था, लेकिन एरियाना ने खुद इसे अपने हाथ में ले लिया और स्क्रैच से कोड लिखा। उनकी मृत्यु से कुछ समय पहले दर्ज मौखिक इतिहास में,^[7]रोसेनब्लुथ ने फिर से टेलर को मूल समस्या प्रस्तुत करने, स्वयं इसे हल करने और एरियाना को कंप्यूटर प्रोग्रामिंग करने का श्रेय दिया।

अंतर्ज्ञान

मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम संभाव्यता घनत्व के साथ किसी भी संभाव्यता वितरण से नमूने खींच सकता है $P(x)$ , बशर्ते कि हम फ़ंक्शन जानते हों $f(x)$ संभाव्यता घनत्व फ़ंक्शन के आनुपातिक $P$ और के मूल्य $f(x)$ गणना की जा सकती है. आवश्यकता यह है कि $f(x)$ घनत्व के बिल्कुल बराबर होने के बजाय केवल आनुपातिक होना चाहिए, जो मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम को विशेष रूप से उपयोगी बनाता है, क्योंकि आवश्यक सामान्यीकरण कारक की गणना करना व्यवहार में अक्सर बेहद कठिन होता है।

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

चित्रण के प्रयोजन के लिए, मेट्रोपोलिस एल्गोरिदम, मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का विशेष मामला जहां प्रस्ताव फ़ंक्शन सममित है, नीचे वर्णित है।

मेट्रोपोलिस एल्गोरिदम (सममित प्रस्ताव वितरण)

होने देना $f(x)$ ऐसा फ़ंक्शन बनें जो वांछित संभाव्यता घनत्व फ़ंक्शन के समानुपाती हो $P(x)$ (उर्फ लक्ष्य वितरण)^{[lower-alpha 1]}.

आरंभीकरण: मनमाना बिंदु चुनें $x_{t}$ नमूने में पहला अवलोकन होना और मनमाना संभाव्यता घनत्व चुनना $g(x\mid y)$ (कभी-कभी लिखा जाता है $Q(x\mid y)$ ) जो अगले नमूना मूल्य के लिए उम्मीदवार का सुझाव देता है $x$ , पिछला नमूना मान दिया गया है $y$ . इस खंड में, $g$ सममित माना जाता है; दूसरे शब्दों में, इसे संतुष्ट करना होगा $g(x\mid y)=g(y\mid x)$ . सामान्य विकल्प है जाने देना $g(x\mid y)$ गाऊसी वितरण पर केन्द्रित होना $y$ , तो यह करीब इंगित करता है $y$ अगले दौरे पर जाने की अधिक संभावना है, जिससे नमूनों का क्रम यादृच्छिक चलन में बदल जाता है^{[lower-alpha 2]}. कार्यक्रम $g$ प्रस्ताव घनत्व या जम्पिंग वितरण के रूप में जाना जाता है।
प्रत्येक पुनरावृत्ति के लिए t:
- एक उम्मीदवार तैयार करें $x'$ वितरण से चुनकर अगले नमूने के लिए $g(x'\mid x_{t})$ .
- स्वीकृति अनुपात की गणना करें $\alpha =f(x')/f(x_{t})$ , जिसका उपयोग यह तय करने के लिए किया जाएगा कि उम्मीदवार को स्वीकार करना है या अस्वीकार करना है^{[lower-alpha 3]}. क्योंकि f, P के घनत्व के समानुपाती है, हमारे पास वह है $\alpha =f(x')/f(x_{t})=P(x')/P(x_{t})$ .
- स्वीकार करें या अस्वीकार करें:
  - एक समान यादृच्छिक संख्या उत्पन्न करें $u\in [0,1]$ .
  - अगर $u\leq \alpha$ , फिर सेटिंग करके उम्मीदवार को स्वीकार करें $x_{t+1}=x'$ ,
  - अगर $u>\alpha$ , फिर उम्मीदवार को अस्वीकार करें और सेट करें $x_{t+1}=x_{t}$ बजाय।

यह एल्गोरिदम नमूना स्थान के बारे में बेतरतीब ढंग से आगे बढ़ने का प्रयास करके आगे बढ़ता है, कभी-कभी चालों को स्वीकार करता है और कभी-कभी जगह पर बना रहता है। ध्यान दें कि स्वीकृति अनुपात $\alpha$ यह इंगित करता है कि नया प्रस्तावित नमूना वर्तमान नमूने के संबंध में कितना संभावित है, वितरण के अनुसार जिसका घनत्व है $P(x)$ . यदि हम किसी ऐसे बिंदु पर जाने का प्रयास करते हैं जो मौजूदा बिंदु से अधिक संभावित है (अर्थात उच्च-घनत्व वाले क्षेत्र में बिंदु) $P(x)$ के अनुरूप $\alpha >1\geq u$ ), हम इस कदम को हमेशा स्वीकार करेंगे। हालाँकि, यदि हम कम संभावित बिंदु पर जाने का प्रयास करते हैं, तो हम कभी-कभी इस कदम को अस्वीकार कर देंगे, और संभावना में सापेक्ष गिरावट जितनी अधिक होगी, उतनी अधिक संभावना है कि हम नए बिंदु को अस्वीकार कर देंगे। इस प्रकार, हम उच्च-घनत्व वाले क्षेत्रों में बने रहेंगे (और वहां से बड़ी संख्या में नमूने वापस लाएंगे)। $P(x)$ , जबकि केवल कभी-कभार ही कम घनत्व वाले क्षेत्रों का दौरा करते हैं। सहज रूप से, यही कारण है कि यह एल्गोरिदम काम करता है और नमूने लौटाता है जो घनत्व के साथ वांछित वितरण का पालन करते हैं $P(x)$ .

अनुकूली अस्वीकृति नमूनाकरण जैसे एल्गोरिदम की तुलना में^[8] जो सीधे वितरण से स्वतंत्र नमूने उत्पन्न करता है, मेट्रोपोलिस-हेस्टिंग्स और अन्य एमसीएमसी एल्गोरिदम के कई नुकसान हैं:

नमूने सहसंबद्ध हैं। हालांकि लंबी अवधि में वे सही ढंग से पालन करते हैं $P(x)$ , आस-पास के नमूनों का सेट दूसरे के साथ सहसंबद्ध होगा और वितरण को सही ढंग से प्रतिबिंबित नहीं करेगा। इसका मतलब यह है कि प्रभावी नमूना आकार वास्तव में लिए गए नमूनों की संख्या से काफी कम हो सकता है, जिससे बड़ी त्रुटियां हो सकती हैं।
यद्यपि मार्कोव श्रृंखला अंततः वांछित वितरण में परिवर्तित हो जाती है, प्रारंभिक नमूने बहुत अलग वितरण का पालन कर सकते हैं, खासकर यदि शुरुआती बिंदु कम घनत्व वाले क्षेत्र में है। परिणामस्वरूप, बर्न-इन अवधि आम तौर पर आवश्यक होती है,^[9] जहां शुरुआती संख्या में नमूने फेंके जाते हैं।

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

बहुभिन्नरूपी वितरण वितरण में, जैसा कि ऊपर वर्णित है, क्लासिक मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम में नया बहु-आयामी नमूना बिंदु चुनना शामिल है। जब आयामों की संख्या अधिक होती है, तो उपयोग करने के लिए उपयुक्त जंपिंग वितरण ढूंढना मुश्किल हो सकता है, क्योंकि अलग-अलग व्यक्तिगत आयाम बहुत अलग-अलग तरीकों से व्यवहार करते हैं, और अत्यधिक से बचने के लिए जंपिंग चौड़ाई (ऊपर देखें) ही बार में सभी आयामों के लिए बिल्कुल सही होनी चाहिए। धीमी गति से मिश्रण. वैकल्पिक दृष्टिकोण जो अक्सर ऐसी स्थितियों में बेहतर काम करता है, जिसे गिब्स नमूनाकरण के रूप में जाना जाता है, इसमें ही बार में सभी आयामों के लिए नमूना चुनने के बजाय, प्रत्येक आयाम के लिए दूसरों से अलग नया नमूना चुनना शामिल है। इस तरह, संभावित उच्च-आयामी स्थान से नमूना लेने की समस्या छोटी आयामीता से नमूना लेने के लिए समस्याओं के संग्रह में कम हो जाएगी।^[10] यह विशेष रूप से तब लागू होता है जब बहुभिन्नरूपी वितरण व्यक्तिगत यादृच्छिक चर के सेट से बना होता है जिसमें प्रत्येक चर केवल अन्य चर की छोटी संख्या पर आधारित होता है, जैसा कि अधिकांश विशिष्ट पदानुक्रमित बायेसियन मॉडल में होता है। फिर अलग-अलग चर का एक-एक करके नमूना लिया जाता है, प्रत्येक चर को अन्य सभी के नवीनतम मूल्यों पर आधारित किया जाता है। बहुभिन्नरूपी वितरण के सटीक रूप के आधार पर, इन व्यक्तिगत नमूनों को चुनने के लिए विभिन्न एल्गोरिदम का उपयोग किया जा सकता है: कुछ संभावनाएं अनुकूली अस्वीकृति नमूनाकरण विधियां हैं,^[8]अनुकूली अस्वीकृति मेट्रोपोलिस नमूनाकरण एल्गोरिदम,^[11] सरल एक-आयामी मेट्रोपोलिस-हेस्टिंग्स चरण, या स्लाइस नमूनाकरण।

औपचारिक व्युत्पत्ति

मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का उद्देश्य वांछित वितरण के अनुसार राज्यों का संग्रह उत्पन्न करना है $P(x)$ . इसे पूरा करने के लिए, एल्गोरिदम मार्कोव प्रक्रिया का उपयोग करता है, जो असम्बद्ध रूप से अद्वितीय मार्कोव श्रृंखला # स्थिर-राज्य विश्लेषण और सीमित वितरण तक पहुंचता है $\pi (x)$ ऐसा है कि $\pi (x)=P(x)$ .^[12]

एक मार्कोव प्रक्रिया को उसकी संक्रमण संभावनाओं द्वारा विशिष्ट रूप से परिभाषित किया गया है $P(x'\mid x)$ , किसी दिए गए राज्य से संक्रमण की संभावना $x$ किसी अन्य दिए गए राज्य के लिए $x'$ . इसका अद्वितीय स्टेशनरी वितरण है $\pi (x)$ जब निम्नलिखित दो शर्तें पूरी हों:^[12]# स्थिर वितरण का अस्तित्व: स्थिर वितरण का अस्तित्व होना चाहिए $\pi (x)$ . पर्याप्त लेकिन आवश्यक शर्त विस्तृत संतुलन नहीं है, जिसके लिए प्रत्येक संक्रमण की आवश्यकता होती है $x\to x'$ प्रतिवर्ती है: राज्यों की प्रत्येक जोड़ी के लिए $x,x'$ , राज्य में होने की संभावना $x$ और राज्य में परिवर्तन $x'$ राज्य में होने की संभावना के बराबर होना चाहिए $x'$ और राज्य में परिवर्तन $x$ , $\pi (x)P(x'\mid x)=\pi (x')P(x\mid x')$ .

स्थिर वितरण की विशिष्टता: स्थिर वितरण $\pi (x)$ अद्वितीय होना चाहिए। इसकी गारंटी मार्कोव प्रक्रिया की मार्कोव चेन#एर्गोडिसिटी द्वारा दी गई है, जिसके लिए आवश्यक है कि प्रत्येक राज्य को (1) एपेरियोडिक होना चाहिए - सिस्टम निश्चित अंतराल पर उसी स्थिति में वापस नहीं आता है; और (2) सकारात्मक आवर्ती होना - उसी स्थिति में लौटने के लिए चरणों की अपेक्षित संख्या सीमित है।

मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम में मार्कोव प्रक्रिया (संक्रमण संभावनाओं का निर्माण करके) को डिजाइन करना शामिल है जो उपरोक्त दो शर्तों को पूरा करता है, जैसे कि इसका स्थिर वितरण $\pi (x)$ होना चुना गया है $P(x)$ . एल्गोरिदम की व्युत्पत्ति विस्तृत संतुलन की स्थिति से शुरू होती है:

P(x'\mid x)P(x)=P(x\mid x')P(x'),

जिसे पुनः इस रूप में लिखा गया है

{\frac {P(x'\mid x)}{P(x\mid x')}}={\frac {P(x')}{P(x)}}.

दृष्टिकोण संक्रमण को दो उप-चरणों में अलग करना है; प्रस्ताव और स्वीकृति-अस्वीकृति. प्रस्ताव वितरण $g(x'\mid x)$ किसी राज्य को प्रस्तावित करने की सशर्त संभावना है $x'$ दिया गया $x$ , और स्वीकृति वितरण $A(x',x)$ प्रस्तावित राज्य को स्वीकार करने की संभावना है $x'$ . संक्रमण संभाव्यता को उनके उत्पाद के रूप में लिखा जा सकता है:

P(x'\mid x)=g(x'\mid x)A(x',x).

इस संबंध को पिछले समीकरण में डालने पर, हमारे पास है

{\frac {A(x',x)}{A(x,x')}}={\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}.

व्युत्पत्ति में अगला कदम स्वीकृति अनुपात चुनना है जो उपरोक्त शर्त को पूरा करता है। सामान्य विकल्प मेट्रोपोलिस विकल्प है:

A(x',x)=\min \left(1,{\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}\right).

इसके लिए मेट्रोपोलिस स्वीकृति अनुपात $A$ , दोनों में से $A(x',x)=1$ या $A(x,x')=1$ और, किसी भी तरह, शर्त पूरी होती है।

मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम को इस प्रकार लिखा जा सकता है:

आरंभ करें
1. एक प्रारंभिक अवस्था चुनें $x_{0}$ .
2. तय करना $t=0$ .
पुनरावृति
1. एक यादृच्छिक उम्मीदवार राज्य उत्पन्न करें $x'$ के अनुसार $g(x'\mid x_{t})$ .
2. स्वीकृति संभावना की गणना करें $A(x',x_{t})=\min \left(1,{\frac {P(x')}{P(x_{t})}}{\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}\right)$ .
3. स्वीकार करें या अस्वीकार करें:
  1. एक समान यादृच्छिक संख्या उत्पन्न करें $u\in [0,1]$ ;
  2. अगर $u\leq A(x',x_{t})$ , फिर नए राज्य को स्वीकार करें और सेट करें $x_{t+1}=x'$ ;
  3. अगर $u>A(x',x_{t})$ , फिर नए राज्य को अस्वीकार करें, और पुराने राज्य को आगे कॉपी करें $x_{t+1}=x_{t}$ .
4. वृद्धि: सेट $t=t+1$ .

बशर्ते कि निर्दिष्ट शर्तें पूरी हों, सहेजे गए राज्यों का अनुभवजन्य वितरण $x_{0},\ldots ,x_{T}$ संपर्क करेंगे $P(x)$ . पुनरावृत्तियों की संख्या ( $T$ ) प्रभावी ढंग से अनुमान लगाने की आवश्यकता है $P(x)$ कारकों की संख्या पर निर्भर करता है, जिसमें बीच का संबंध भी शामिल है $P(x)$ और प्रस्ताव वितरण और अनुमान की वांछित सटीकता।^[13] असतत राज्य स्थानों पर वितरण के लिए, इसे मार्कोव प्रक्रिया के स्वत: सहसंबंध समय के क्रम का होना चाहिए।^[14]

यह ध्यान रखना महत्वपूर्ण है कि सामान्य समस्या में यह स्पष्ट नहीं है कि कौन सा वितरण $g(x'\mid x)$ किसी को उचित अनुमान के लिए आवश्यक पुनरावृत्तियों की संख्या का उपयोग करना चाहिए; दोनों विधि के निःशुल्क पैरामीटर हैं, जिन्हें मौजूदा विशेष समस्या के अनुसार समायोजित किया जाना चाहिए।

संख्यात्मक एकीकरण में उपयोग

मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का सामान्य उपयोग अभिन्न की गणना करना है। विशेष रूप से, स्थान पर विचार करें $\Omega \subset \mathbb {R}$ और संभाव्यता वितरण $P(x)$ ऊपर $\Omega$ , $x\in \Omega$ . मेट्रोपोलिस-हेस्टिंग्स के रूप का अभिन्न अंग का अनुमान लगा सकते हैं

P(E)=\int _{\Omega }A(x)P(x)\,dx,

कहाँ $A(x)$ रुचि का (मापने योग्य) कार्य है।

उदाहरण के लिए, आँकड़े पर विचार करें $E(x)$ और इसकी संभाव्यता वितरण $P(E)$ , जो सीमांत वितरण है। मान लीजिए कि लक्ष्य अनुमान लगाना है $P(E)$ के लिए $E$ की पूँछ पर $P(E)$ . औपचारिक रूप से, $P(E)$ के रूप में लिखा जा सकता है

P(E)=\int _{\Omega }P(E\mid x)P(x)\,dx=\int _{\Omega }\delta {\big (}E-E(x){\big )}P(x)\,dx=E{\big (}P(E\mid X){\big )}

और, इस प्रकार, अनुमान लगाना $P(E)$ सूचक फ़ंक्शन के अपेक्षित मूल्य का अनुमान लगाकर पूरा किया जा सकता है $A_{E}(x)\equiv \mathbf {1} _{E}(x)$ , जो 1 है जब $E(x)\in [E,E+\Delta E]$ और अन्यथा शून्य. क्योंकि $E$ की पूँछ पर है $P(E)$ , राज्य बनाने की संभावना $x$ साथ $E(x)$ की पूँछ पर $P(E)$ के लिए आनुपातिक है $P(E)$ , जो परिभाषा के अनुसार छोटा है। मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का उपयोग यहां (दुर्लभ) राज्यों का नमूना लेने के लिए किया जा सकता है और इस प्रकार अनुमान लगाने के लिए उपयोग किए जाने वाले नमूनों की संख्या में वृद्धि हो सकती है $P(E)$ पूँछ पर. यह किया जा सकता है उदा. नमूना वितरण का उपयोग करके $\pi (x)$ उन राज्यों का पक्ष लेना (उदा. $\pi (x)\propto e^{aE}$ साथ $a>0$ ).

चरण-दर-चरण निर्देश

मान लीजिए कि नमूना लिया गया सबसे हालिया मूल्य है $x_{t}$ . मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का पालन करने के लिए, हम आगे नया प्रस्ताव राज्य बनाते हैं $x'$ संभाव्यता घनत्व के साथ $g(x'\mid x_{t})$ और मान की गणना करें

a=a_{1}a_{2},

कहाँ

a_{1}={\frac {P(x')}{P(x_{t})}}

प्रस्तावित नमूने के बीच संभाव्यता (जैसे, बायेसियन पोस्टीरियर) अनुपात है $x'$ और पिछला नमूना $x_{t}$ , और

a_{2}={\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}

दो दिशाओं में प्रस्ताव घनत्व का अनुपात है (से $x_{t}$ को $x'$ और इसके विपरीत)। यदि प्रस्ताव घनत्व सममित है तो यह 1 के बराबर है। फिर नया राज्य $x_{t+1}$ निम्नलिखित नियमों के अनुसार चुना जाता है।

अगर

a\geq 1{:}

x_{t+1}=x',

अन्य:

x_{t+1}={\begin{cases}x'&{\text{with probability }}a,\\x_{t}&{\text{with probability }}1-a.\end{cases}}

मार्कोव श्रृंखला मनमाने प्रारंभिक मूल्य से शुरू की गई है $x_{0}$ , और एल्गोरिथ्म को कई पुनरावृत्तियों तक चलाया जाता है जब तक कि यह प्रारंभिक स्थिति भूल न जाए। ये नमूने, जिन्हें त्याग दिया जाता है, बर्न-इन के रूप में जाने जाते हैं। के स्वीकृत मूल्यों का शेष सेट $x$ वितरण से नमूना (सांख्यिकी) प्रस्तुत करें $P(x)$ .

यदि प्रस्ताव घनत्व लक्ष्य वितरण के आकार से मेल खाता है तो एल्गोरिदम सबसे अच्छा काम करता है $P(x)$ , जिससे सीधा नमूना लेना कठिन है, अर्थात $g(x'\mid x_{t})\approx P(x')$ . यदि गाऊसी प्रस्ताव घनत्व $g$ विचरण पैरामीटर का उपयोग किया जाता है $\sigma ^{2}$ बर्न-इन अवधि के दौरान ट्यून करना होगा। यह आमतौर पर स्वीकृति दर की गणना करके किया जाता है, जो प्रस्तावित नमूनों का वह अंश है जिसे अंतिम विंडो में स्वीकार किया जाता है $N$ नमूने. वांछित स्वीकृति दर लक्ष्य वितरण पर निर्भर करती है, हालांकि यह सैद्धांतिक रूप से दिखाया गया है कि एक-आयामी गॉसियन वितरण के लिए आदर्श स्वीकृति दर लगभग 50% है, जो घटकर लगभग 23% हो जाती है। $N$ -आयामी गाऊसी लक्ष्य वितरण.^[15]पर्याप्त रूप से नियमित बायेसियन पोस्टीरियर से नमूना लेने पर ये दिशानिर्देश अच्छी तरह से काम कर सकते हैं क्योंकि वे अक्सर बहुभिन्नरूपी सामान्य वितरण का पालन करते हैं जैसा कि बर्नस्टीन-वॉन मिज़ प्रमेय का उपयोग करके स्थापित किया जा सकता है।^[16] अगर $\sigma ^{2}$ बहुत छोटा है, श्रृंखला धीरे-धीरे मिश्रित होगी (यानी, स्वीकृति दर अधिक होगी, लेकिन क्रमिक नमूने धीरे-धीरे अंतरिक्ष में घूमेंगे, और श्रृंखला केवल धीरे-धीरे ही परिवर्तित होगी) $P(x)$ ). वहीं दूसरी ओर, अगर $\sigma ^{2}$ बहुत बड़ा है, स्वीकृति दर बहुत कम होगी क्योंकि प्रस्तावों के बहुत कम संभावना घनत्व वाले क्षेत्रों में आने की संभावना है, इसलिए $a_{1}$ बहुत छोटा होगा, और फिर से श्रृंखला बहुत धीरे-धीरे एकत्रित होगी। आम तौर पर प्रस्ताव वितरण को ट्यून किया जाता है ताकि एल्गोरिदम सभी नमूनों के 30% के क्रम पर स्वीकार कर सके - पिछले पैराग्राफ में उल्लिखित सैद्धांतिक अनुमानों के अनुरूप।

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

बायेसियन अनुमान

मार्कोव चेन मोंटे कार्लो (एमसीएमसी) दृष्टिकोण का उपयोग करके पैरामीटर अनुमान के लिए मेट्रोपोलिस-हेस्टिंग्स (एम-एच) एल्गोरिदम का फ़्लोचार्ट।

एमसीएमसी का उपयोग सांख्यिकीय मॉडल के पिछले वितरण से नमूने लेने के लिए किया जा सकता है।

स्वीकृति की संभावना इस प्रकार दी गई है: $P_{acc}(\theta _{i}\to \theta ^{*})=\min \left(1,{\frac {{\mathcal {L}}(y|\theta ^{*})P(\theta ^{*})}{{\mathcal {L}}(y|\theta _{i})P(\theta _{i})}}{\frac {Q(\theta _{i}|\theta ^{*})}{Q(\theta ^{*}|\theta _{i})}}\right),$ कहाँ ${\mathcal {L}}$ संभावना है, $P(\theta )$ पूर्व संभाव्यता घनत्व और $Q$ (सशर्त) प्रस्ताव संभावना।

यह भी देखें

विस्तृत संतुलन
आनुवंशिक एल्गोरिदम
गिब्स नमूनाकरण
हैमिल्टनियन मोंटे कार्लो
माध्य-क्षेत्र कण विधियाँ
मेट्रोपोलिस-समायोजित लैंग्विन एल्गोरिदम
महानगर प्रकाश परिवहन
बहु-प्रयास महानगर
समानांतर तड़का
पूर्वनिर्धारित क्रैंक-निकोलसन एल्गोरिदम
कण फिल्टर
तैयार किए हुयी धातु पे पानी चढाने की कला

संदर्भ

↑ Kalos, Malvin H.; Whitlock, Paula A. (1986). Monte Carlo Methods Volume I: Basics. New York: Wiley. pp. 78–88.
↑ Tierney, Luke (1994). "पश्च वितरणों की खोज के लिए मार्कोव श्रृंखलाएँ". The Annals of Statistics. 22 (4): 1701–1762.
↑ Hastings, W.K. (1970). "Monte Carlo Sampling Methods Using Markov Chains and Their Applications". Biometrika. 57 (1): 97–109. Bibcode:1970Bimka..57...97H. doi:10.1093/biomet/57.1.97. JSTOR 2334940. Zbl 0219.65008.
↑ M.N. Rosenbluth (2003). "Genesis of the Monte Carlo Algorithm for Statistical Mechanics". AIP Conference Proceedings. 690: 22–30. Bibcode:2003AIPC..690...22R. doi:10.1063/1.1632112.
↑ J.E. Gubernatis (2005). "Marshall Rosenbluth and the Metropolis Algorithm". Physics of Plasmas. 12 (5): 057303. Bibcode:2005PhPl...12e7303G. doi:10.1063/1.1887186.
↑ Teller, Edward. Memoirs: A Twentieth-Century Journey in Science and Politics. Perseus Publishing, 2001, p. 328
↑ Rosenbluth, Marshall. "Oral History Transcript". American Institute of Physics
↑ ^8.0 ^8.1 Gilks, W. R.; Wild, P. (1992-01-01). "गिब्स सैम्पलिंग के लिए अनुकूली अस्वीकृति सैम्पलिंग". Journal of the Royal Statistical Society. Series C (Applied Statistics). 41 (2): 337–348. doi:10.2307/2347565. JSTOR 2347565.
↑ बायेसियन डेटा विश्लेषण. Gelman, Andrew (2nd ed.). Boca Raton, Fla.: Chapman & Hall / CRC. 2004. ISBN 978-1584883883. OCLC 51991499.{{cite book}}: CS1 maint: others (link)
↑ Lee, Se Yoon (2021). "Gibbs sampler and coordinate ascent variational inference: A set-theoretical review". Communications in Statistics - Theory and Methods. 51 (6): 1549–1568. arXiv:2008.01006. doi:10.1080/03610926.2021.1921214. S2CID 220935477.
↑ Gilks, W. R.; Best, N. G.; Tan, K. K. C. (1995-01-01). "गिब्स सैम्पलिंग के भीतर अनुकूली अस्वीकृति मेट्रोपोलिस सैम्पलिंग". Journal of the Royal Statistical Society. Series C (Applied Statistics). 44 (4): 455–472. doi:10.2307/2986138. JSTOR 2986138.
↑ ^12.0 ^12.1 Robert, Christian; Casella, George (2004). Monte Carlo Statistical Methods. Springer. ISBN 978-0387212395.
↑ Raftery, Adrian E., and Steven Lewis. "How Many Iterations in the Gibbs Sampler?" In Bayesian Statistics 4. 1992.
↑ Newman, M. E. J.; Barkema, G. T. (1999). Monte Carlo Methods in Statistical Physics. USA: Oxford University Press. ISBN 978-0198517979.
↑ Roberts, G.O.; Gelman, A.; Gilks, W.R. (1997). "Weak convergence and optimal scaling of random walk Metropolis algorithms". Ann. Appl. Probab. 7 (1): 110–120. CiteSeerX 10.1.1.717.2582. doi:10.1214/aoap/1034625254.
↑ Schmon, Sebastian M.; Gagnon, Philippe (2022-04-15). "बायेसियन लार्ज-सैंपल एसिम्प्टोटिक्स का उपयोग करके रैंडम वॉक मेट्रोपोलिस एल्गोरिदम की इष्टतम स्केलिंग". Statistics and Computing (in English). 32 (2): 28. doi:10.1007/s11222-022-10080-8. ISSN 0960-3174. PMC 8924149. PMID 35310543.

↑ In the original paper by Metropolis et al. (1953), $f$ was taken to be the Boltzmann distribution as the specific application considered was Monte Carlo integration of equations of state in physical chemistry; the extension by Hastings generalized to an arbitrary distribution $f$ .
↑ In the original paper by Metropolis et al. (1953), $g(x\mid y)$ was suggested to be a random translation with uniform density over some prescribed range.
↑ In the original paper by Metropolis et al. (1953), $f$ was actually the Boltzmann distribution, as it was applied to physical systems in the context of statistical mechanics (e.g., a maximal-entropy distribution of microstates for a given temperature at thermal equilibrium). Consequently, the acceptance ratio was itself an exponential of the difference in the parameters of the numerator and denominator of this ratio.

अग्रिम पठन

Bernd A. Berg. Markov Chain Monte Carlo Simulations and Their Statistical Analysis. Singapore, World Scientific, 2004.
Siddhartha Chib and Edward Greenberg: "Understanding the Metropolis–Hastings Algorithm". American Statistician, 49(4), 327–335, 1995
David D. L. Minh and Do Le Minh. "Understanding the Hastings Algorithm." Communications in Statistics - Simulation and Computation, 44:2 332-349, 2015
Bolstad, William M. (2010) Understanding Computational Bayesian Statistics, John Wiley & Sons ISBN 0-470-04609-0

[1] Kalos, Malvin H.; Whitlock, Paula A. (1986). Monte Carlo Methods Volume I: Basics. New York: Wiley. pp. 78–88.

[2] Tierney, Luke (1994). "पश्च वितरणों की खोज के लिए मार्कोव श्रृंखलाएँ". The Annals of Statistics. 22 (4): 1701–1762.

[Hastings-3] Hastings, W.K. (1970). "Monte Carlo Sampling Methods Using Markov Chains and Their Applications". Biometrika. 57 (1): 97–109. Bibcode:1970Bimka..57...97H. doi:10.1093/biomet/57.1.97. JSTOR 2334940. Zbl 0219.65008.

[Rosenbluth-4] M.N. Rosenbluth (2003). "Genesis of the Monte Carlo Algorithm for Statistical Mechanics". AIP Conference Proceedings. 690: 22–30. Bibcode:2003AIPC..690...22R. doi:10.1063/1.1632112.

[Gubernatis-5] J.E. Gubernatis (2005). "Marshall Rosenbluth and the Metropolis Algorithm". Physics of Plasmas. 12 (5): 057303. Bibcode:2005PhPl...12e7303G. doi:10.1063/1.1887186.

[Teller-6] Teller, Edward. Memoirs: A Twentieth-Century Journey in Science and Politics. Perseus Publishing, 2001, p. 328

[Barth-7] Rosenbluth, Marshall. "Oral History Transcript". American Institute of Physics

[:0-11] 8.0 ^8.1 Gilks, W. R.; Wild, P. (1992-01-01). "गिब्स सैम्पलिंग के लिए अनुकूली अस्वीकृति सैम्पलिंग". Journal of the Royal Statistical Society. Series C (Applied Statistics). 41 (2): 337–348. doi:10.2307/2347565. JSTOR 2347565.

[12] बायेसियन डेटा विश्लेषण. Gelman, Andrew (2nd ed.). Boca Raton, Fla.: Chapman & Hall / CRC. 2004. ISBN 978-1584883883. OCLC 51991499.{{cite book}}: CS1 maint: others (link)

[13] Lee, Se Yoon (2021). "Gibbs sampler and coordinate ascent variational inference: A set-theoretical review". Communications in Statistics - Theory and Methods. 51 (6): 1549–1568. arXiv:2008.01006. doi:10.1080/03610926.2021.1921214. S2CID 220935477.

[14] Gilks, W. R.; Best, N. G.; Tan, K. K. C. (1995-01-01). "गिब्स सैम्पलिंग के भीतर अनुकूली अस्वीकृति मेट्रोपोलिस सैम्पलिंग". Journal of the Royal Statistical Society. Series C (Applied Statistics). 44 (4): 455–472. doi:10.2307/2986138. JSTOR 2986138.

[Roberts_Casella-15] 12.0 ^12.1 Robert, Christian; Casella, George (2004). Monte Carlo Statistical Methods. Springer. ISBN 978-0387212395.

[16] Raftery, Adrian E., and Steven Lewis. "How Many Iterations in the Gibbs Sampler?" In Bayesian Statistics 4. 1992.

[Newman_Barkema-17] Newman, M. E. J.; Barkema, G. T. (1999). Monte Carlo Methods in Statistical Physics. USA: Oxford University Press. ISBN 978-0198517979.

[Roberts-18] Roberts, G.O.; Gelman, A.; Gilks, W.R. (1997). "Weak convergence and optimal scaling of random walk Metropolis algorithms". Ann. Appl. Probab. 7 (1): 110–120. CiteSeerX 10.1.1.717.2582. doi:10.1214/aoap/1034625254.

[19] Schmon, Sebastian M.; Gagnon, Philippe (2022-04-15). "बायेसियन लार्ज-सैंपल एसिम्प्टोटिक्स का उपयोग करके रैंडम वॉक मेट्रोपोलिस एल्गोरिदम की इष्टतम स्केलिंग". Statistics and Computing (in English). 32 (2): 28. doi:10.1007/s11222-022-10080-8. ISSN 0960-3174. PMC 8924149. PMID 35310543.

[8] In the original paper by Metropolis et al. (1953), $f$ was taken to be the Boltzmann distribution as the specific application considered was Monte Carlo integration of equations of state in physical chemistry; the extension by Hastings generalized to an arbitrary distribution $f$ .

[9] In the original paper by Metropolis et al. (1953), $g(x\mid y)$ was suggested to be a random translation with uniform density over some prescribed range.

[10] In the original paper by Metropolis et al. (1953), $f$ was actually the Boltzmann distribution, as it was applied to physical systems in the context of statistical mechanics (e.g., a maximal-entropy distribution of microstates for a given temperature at thermal equilibrium). Consequently, the acceptance ratio was itself an exponential of the difference in the parameters of the numerator and denominator of this ratio.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[lower-alpha 1]

[lower-alpha 2]

[lower-alpha 3]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

@@ Line 1: / Line 1: @@
 {{short description|Monte Carlo algorithm}}
-[[Image:Metropolis hastings algorithm.png|thumb|450px|प्रस्ताव संभाव्यता वितरण Q अगले बिंदु का प्रस्ताव करता है जिस पर [[यादृच्छिक चाल]] चल सकती है।]]सांख्यिकी और [[सांख्यिकीय भौतिकी]] में, मेट्रोपोलिस-हेस्टिंग्स एल्गोरिथ्म एक संभाव्यता वितरण से छद्म-यादृच्छिक संख्या नमूने का अनुक्रम प्राप्त करने के लिए एक [[मार्कोव श्रृंखला मोंटे कार्लो]] (एमसीएमसी) विधि है, जहां से प्रत्यक्ष नमूनाकरण मुश्किल है। इस अनुक्रम का उपयोग वितरण का अनुमान लगाने के लिए (उदाहरण के लिए [[हिस्टोग्राम]] उत्पन्न करने के लिए) या [[मोंटे कार्लो एकीकरण]] (उदाहरण के लिए [[अपेक्षित मूल्य]]) के लिए किया जा सकता है। मेट्रोपोलिस-हेस्टिंग्स और अन्य एमसीएमसी एल्गोरिदम का उपयोग आम तौर पर बहु-आयामी वितरण से नमूना लेने के लिए किया जाता है, खासकर जब आयामों की संख्या अधिक होती है। एकल-आयामी वितरण के लिए, आमतौर पर अन्य विधियां होती हैं (उदाहरण के लिए [[अनुकूली अस्वीकृति नमूनाकरण]]) जो सीधे वितरण से स्वतंत्र नमूने वापस कर सकती हैं, और ये एमसीएमसी विधियों में निहित ऑटोसहसंबंध नमूनों की समस्या से मुक्त हैं।
+[[Image:Metropolis hastings algorithm.png|thumb|450px|प्रस्ताव संभाव्यता वितरण Q अगले बिंदु का प्रस्ताव करता है जिस पर [[यादृच्छिक चाल]] चल सकती है।]]सांख्यिकी और [[सांख्यिकीय भौतिकी]] में, '''मेट्रोपोलिस-हेस्टिंग्स एल्गोरिथ्म''' संभाव्यता वितरण से छद्म-यादृच्छिक संख्या नमूने का अनुक्रम प्राप्त करने के लिए [[मार्कोव श्रृंखला मोंटे कार्लो]] (एमसीएमसी) विधि है, जहां से प्रत्यक्ष नमूनाकरण मुश्किल है। इस अनुक्रम का उपयोग वितरण का अनुमान लगाने के लिए (उदाहरण के लिए [[हिस्टोग्राम]] उत्पन्न करने के लिए) या [[मोंटे कार्लो एकीकरण]] (उदाहरण के लिए [[अपेक्षित मूल्य]]) के लिए किया जा सकता है। मेट्रोपोलिस-हेस्टिंग्स और अन्य एमसीएमसी एल्गोरिदम का उपयोग आम तौर पर बहु-आयामी वितरण से नमूना लेने के लिए किया जाता है, खासकर जब आयामों की संख्या अधिक होती है। एकल-आयामी वितरण के लिए, आमतौर पर अन्य विधियां होती हैं (उदाहरण के लिए [[अनुकूली अस्वीकृति नमूनाकरण]]) जो सीधे वितरण से स्वतंत्र नमूने वापस कर सकती हैं, और ये एमसीएमसी विधियों में निहित ऑटोसहसंबंध नमूनों की समस्या से मुक्त हैं।
 ==इतिहास==
 एल्गोरिथम का नाम आंशिक रूप से [[निकोलस मेट्रोपोलिस]] के नाम पर रखा गया है, जो 1953 के पेपर के पहले सह-लेखक थे, जिसका शीर्षक एरियाना डब्ल्यू. रोसेनब्लुथ, [[मार्शल रोसेनब्लथ]], ऑगस्टा एच. टेलर और [[एडवर्ड टेलर]] के साथ फास्ट कंप्यूटिंग मशीनों द्वारा राज्य की गणना का समीकरण था। कई वर्षों तक एल्गोरिथम को केवल मेट्रोपोलिस एल्गोरिथम के रूप में जाना जाता था।<ref>{{Cite book |last=Kalos |first=Malvin H. |title=Monte Carlo Methods Volume I: Basics |last2=Whitlock |first2=Paula A. |publisher=Wiley |year=1986 |location=New York |pages=78-88}}</ref><ref>{{Cite journal |last=Tierney |first=Luke |date=1994 |title=पश्च वितरणों की खोज के लिए मार्कोव श्रृंखलाएँ|url=https://projecteuclid.org/journals/annals-of-statistics/volume-22/issue-4/Markov-Chains-for-Exploring-Posterior-Distributions/10.1214/aos/1176325750.full |journal=The Annals of Statistics |volume=22 |issue=4 |pages=1701-1762}}</ref> पेपर ने सममित प्रस्ताव वितरण के मामले के लिए एल्गोरिदम का प्रस्ताव दिया, लेकिन 1970 में, डब्ल्यू.के. हेस्टिंग्स ने इसे अधिक सामान्य मामले तक विस्तारित किया।<ref name=Hastings/>सामान्यीकृत विधि को अंततः दोनों नामों से पहचाना गया, हालांकि मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम शब्द का पहला उपयोग अस्पष्ट है।
-मेट्रोपोलिस एल्गोरिथम के विकास के श्रेय के संबंध में कुछ विवाद मौजूद हैं। मेट्रोपोलिस, जो विधि के कम्प्यूटेशनल पहलुओं से परिचित थे, ने स्टैनिस्लाव उलम के साथ एक पुराने लेख में मोंटे कार्लो शब्द गढ़ा था, और सैद्धांतिक प्रभाग में उस समूह का नेतृत्व किया था जिसने 1952 में प्रयोगों में उपयोग किए गए [[MANIAC I]] कंप्यूटर को डिजाइन और निर्मित किया था। हालाँकि, 2003 से पहले एल्गोरिथम के विकास का कोई विस्तृत विवरण नहीं था। अपनी मृत्यु से कुछ समय पहले, मार्शल रोसेनब्लुथ ने 1953 के प्रकाशन की 50वीं वर्षगांठ के अवसर पर LANL में 2003 के एक सम्मेलन में भाग लिया। इस सम्मेलन में, रोसेनब्लुथ ने सांख्यिकीय यांत्रिकी के लिए मोंटे कार्लो एल्गोरिदम की उत्पत्ति नामक एक प्रस्तुति में एल्गोरिदम और उसके विकास का वर्णन किया।<ref name=Rosenbluth/>  2005 के एक जर्नल लेख में गुबर्नैटिस द्वारा और अधिक ऐतिहासिक स्पष्टीकरण दिया गया है<ref name=Gubernatis/>50वीं वर्षगांठ सम्मेलन का पुनर्गणना। रोसेनब्लुथ ने यह स्पष्ट किया कि उन्होंने और उनकी पत्नी एरियाना ने यह काम किया, और मेट्रोपोलिस ने कंप्यूटर समय प्रदान करने के अलावा विकास में कोई भूमिका नहीं निभाई।
+मेट्रोपोलिस एल्गोरिथम के विकास के श्रेय के संबंध में कुछ विवाद मौजूद हैं। मेट्रोपोलिस, जो विधि के कम्प्यूटेशनल पहलुओं से परिचित थे, ने स्टैनिस्लाव उलम के साथ पुराने लेख में मोंटे कार्लो शब्द गढ़ा था, और सैद्धांतिक प्रभाग में उस समूह का नेतृत्व किया था जिसने 1952 में प्रयोगों में उपयोग किए गए [[MANIAC I]] कंप्यूटर को डिजाइन और निर्मित किया था। हालाँकि, 2003 से पहले एल्गोरिथम के विकास का कोई विस्तृत विवरण नहीं था। अपनी मृत्यु से कुछ समय पहले, मार्शल रोसेनब्लुथ ने 1953 के प्रकाशन की 50वीं वर्षगांठ के अवसर पर LANL में 2003 के सम्मेलन में भाग लिया। इस सम्मेलन में, रोसेनब्लुथ ने सांख्यिकीय यांत्रिकी के लिए मोंटे कार्लो एल्गोरिदम की उत्पत्ति नामक प्रस्तुति में एल्गोरिदम और उसके विकास का वर्णन किया।<ref name=Rosenbluth/>  2005 के जर्नल लेख में गुबर्नैटिस द्वारा और अधिक ऐतिहासिक स्पष्टीकरण दिया गया है<ref name=Gubernatis/>50वीं वर्षगांठ सम्मेलन का पुनर्गणना। रोसेनब्लुथ ने यह स्पष्ट किया कि उन्होंने और उनकी पत्नी एरियाना ने यह काम किया, और मेट्रोपोलिस ने कंप्यूटर समय प्रदान करने के अलावा विकास में कोई भूमिका नहीं निभाई।
-यह एडवर्ड टेलर के एक लेख का खंडन करता है, जिन्होंने अपने संस्मरणों में कहा है कि 1953 के लेख के पांच लेखकों ने दिनों (और रातों) के लिए एक साथ काम किया।<ref name=Teller/>इसके विपरीत, रोसेनब्लुथ का विस्तृत विवरण टेलर को [[सांख्यिकीय यांत्रिकी]] का लाभ उठाने और विस्तृत [[गतिकी]] का पालन करने के बजाय समग्र औसत लेने के लिए एक महत्वपूर्ण लेकिन प्रारंभिक सुझाव का श्रेय देता है। रोसेनब्लुथ कहते हैं, इसने उन्हें सामान्यीकृत मोंटे कार्लो दृष्टिकोण के बारे में सोचना शुरू कर दिया - एक विषय जिसके बारे में उनका कहना है कि उन्होंने [[जॉन वॉन न्यूमैन]] के साथ अक्सर चर्चा की थी। एरियाना रोसेनब्लुथ ने बताया (2003 में गुबर्नैटिस को) कि ऑगस्टा टेलर ने कंप्यूटर का काम शुरू किया था, लेकिन एरियाना ने खुद इसे अपने हाथ में ले लिया और स्क्रैच से कोड लिखा। उनकी मृत्यु से कुछ समय पहले दर्ज मौखिक इतिहास में,<ref name=Barth/>रोसेनब्लुथ ने फिर से टेलर को मूल समस्या प्रस्तुत करने, स्वयं इसे हल करने और एरियाना को कंप्यूटर प्रोग्रामिंग करने का श्रेय दिया।
+यह एडवर्ड टेलर के लेख का खंडन करता है, जिन्होंने अपने संस्मरणों में कहा है कि 1953 के लेख के पांच लेखकों ने दिनों (और रातों) के लिए साथ काम किया।<ref name=Teller/>इसके विपरीत, रोसेनब्लुथ का विस्तृत विवरण टेलर को [[सांख्यिकीय यांत्रिकी]] का लाभ उठाने और विस्तृत [[गतिकी]] का पालन करने के बजाय समग्र औसत लेने के लिए महत्वपूर्ण लेकिन प्रारंभिक सुझाव का श्रेय देता है। रोसेनब्लुथ कहते हैं, इसने उन्हें सामान्यीकृत मोंटे कार्लो दृष्टिकोण के बारे में सोचना शुरू कर दिया - विषय जिसके बारे में उनका कहना है कि उन्होंने [[जॉन वॉन न्यूमैन]] के साथ अक्सर चर्चा की थी। एरियाना रोसेनब्लुथ ने बताया (2003 में गुबर्नैटिस को) कि ऑगस्टा टेलर ने कंप्यूटर का काम शुरू किया था, लेकिन एरियाना ने खुद इसे अपने हाथ में ले लिया और स्क्रैच से कोड लिखा। उनकी मृत्यु से कुछ समय पहले दर्ज मौखिक इतिहास में,<ref name=Barth/>रोसेनब्लुथ ने फिर से टेलर को मूल समस्या प्रस्तुत करने, स्वयं इसे हल करने और एरियाना को कंप्यूटर प्रोग्रामिंग करने का श्रेय दिया।
 ==अंतर्ज्ञान==
-मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम संभाव्यता घनत्व के साथ किसी भी संभाव्यता वितरण से नमूने खींच सकता है <math>P(x)</math>, बशर्ते कि हम एक फ़ंक्शन जानते हों <math>f(x)</math> संभाव्यता घनत्व फ़ंक्शन के आनुपातिक <math>P</math> और के मूल्य <math>f(x)</math> गणना की जा सकती है. आवश्यकता यह है कि <math>f(x)</math> घनत्व के बिल्कुल बराबर होने के बजाय केवल आनुपातिक होना चाहिए, जो मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम को विशेष रूप से उपयोगी बनाता है, क्योंकि आवश्यक सामान्यीकरण कारक की गणना करना व्यवहार में अक्सर बेहद कठिन होता है।
+मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम संभाव्यता घनत्व के साथ किसी भी संभाव्यता वितरण से नमूने खींच सकता है <math>P(x)</math>, बशर्ते कि हम फ़ंक्शन जानते हों <math>f(x)</math> संभाव्यता घनत्व फ़ंक्शन के आनुपातिक <math>P</math> और के मूल्य <math>f(x)</math> गणना की जा सकती है. आवश्यकता यह है कि <math>f(x)</math> घनत्व के बिल्कुल बराबर होने के बजाय केवल आनुपातिक होना चाहिए, जो मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम को विशेष रूप से उपयोगी बनाता है, क्योंकि आवश्यक सामान्यीकरण कारक की गणना करना व्यवहार में अक्सर बेहद कठिन होता है।
-मेट्रोपोलिस-हेस्टिंग्स एल्गोरिथ्म नमूना मूल्यों का एक क्रम इस तरह से उत्पन्न करता है कि, जैसे-जैसे अधिक से अधिक नमूना मूल्य उत्पन्न होते हैं, मूल्यों का वितरण वांछित वितरण के अधिक करीब होता है। ये नमूना मान पुनरावृत्त रूप से उत्पन्न होते हैं, अगले नमूने का वितरण केवल वर्तमान नमूना मूल्य पर निर्भर होता है, इस प्रकार नमूनों का अनुक्रम [[मार्कोव श्रृंखला]] में बन जाता है। विशेष रूप से, प्रत्येक पुनरावृत्ति पर, एल्गोरिदम वर्तमान नमूना मूल्य के आधार पर अगले नमूना मूल्य के लिए एक उम्मीदवार चुनता है। फिर, कुछ संभावना के साथ, उम्मीदवार को या तो स्वीकार कर लिया जाता है, जिस स्थिति में उम्मीदवार मूल्य का उपयोग अगले पुनरावृत्ति में किया जाता है, या इसे अस्वीकार कर दिया जाता है, जिस स्थिति में उम्मीदवार मूल्य को खारिज कर दिया जाता है, और वर्तमान मूल्य को अगले पुनरावृत्ति में पुन: उपयोग किया जाता है। स्वीकृति की संभावना फ़ंक्शन के मूल्यों की तुलना करके निर्धारित की जाती है <math>f(x)</math> वांछित वितरण के संबंध में वर्तमान और उम्मीदवार नमूना मूल्यों का।
+मेट्रोपोलिस-हेस्टिंग्स एल्गोरिथ्म नमूना मूल्यों का क्रम इस तरह से उत्पन्न करता है कि, जैसे-जैसे अधिक से अधिक नमूना मूल्य उत्पन्न होते हैं, मूल्यों का वितरण वांछित वितरण के अधिक करीब होता है। ये नमूना मान पुनरावृत्त रूप से उत्पन्न होते हैं, अगले नमूने का वितरण केवल वर्तमान नमूना मूल्य पर निर्भर होता है, इस प्रकार नमूनों का अनुक्रम [[मार्कोव श्रृंखला]] में बन जाता है। विशेष रूप से, प्रत्येक पुनरावृत्ति पर, एल्गोरिदम वर्तमान नमूना मूल्य के आधार पर अगले नमूना मूल्य के लिए उम्मीदवार चुनता है। फिर, कुछ संभावना के साथ, उम्मीदवार को या तो स्वीकार कर लिया जाता है, जिस स्थिति में उम्मीदवार मूल्य का उपयोग अगले पुनरावृत्ति में किया जाता है, या इसे अस्वीकार कर दिया जाता है, जिस स्थिति में उम्मीदवार मूल्य को खारिज कर दिया जाता है, और वर्तमान मूल्य को अगले पुनरावृत्ति में पुन: उपयोग किया जाता है। स्वीकृति की संभावना फ़ंक्शन के मूल्यों की तुलना करके निर्धारित की जाती है <math>f(x)</math> वांछित वितरण के संबंध में वर्तमान और उम्मीदवार नमूना मूल्यों का।
+चित्रण के प्रयोजन के लिए, मेट्रोपोलिस एल्गोरिदम, मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का विशेष मामला जहां प्रस्ताव फ़ंक्शन सममित है, नीचे वर्णित है।
-चित्रण के प्रयोजन के लिए, मेट्रोपोलिस एल्गोरिदम, मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का एक विशेष मामला जहां प्रस्ताव फ़ंक्शन सममित है, नीचे वर्णित है।
-<!---The sample values are linked in a [[Markov chain]], which means that the probability of each sample is conditionally independent of any earlier sample, given the sample immediately before it. In other words,
-general idea is to generate a sequence of samples which are linked in a [[Markov chain]]; in other words, where each sample in the sequence is conditionally independent of any earlier sample, given the sample immediately before it. The procedure for choosing successive samples guarantees that the distribution of sample values will match the desired distribution after a long time.!-->
 ;मेट्रोपोलिस एल्गोरिदम (सममित प्रस्ताव वितरण):
-होने देना <math>f(x)</math> एक ऐसा फ़ंक्शन बनें जो वांछित संभाव्यता घनत्व फ़ंक्शन के समानुपाती हो <math>P(x)</math> (उर्फ लक्ष्य वितरण){{efn|In the original paper by Metropolis et al. (1953), <math>f</math> was taken to be the [[Boltzmann distribution]] as the specific application considered was [[Monte Carlo integration]] of [[equation of state|equations of state]] in [[physical chemistry]]; the extension by Hastings generalized to an arbitrary distribution <math>f</math>.}}.
+होने देना <math>f(x)</math> ऐसा फ़ंक्शन बनें जो वांछित संभाव्यता घनत्व फ़ंक्शन के समानुपाती हो <math>P(x)</math> (उर्फ लक्ष्य वितरण){{efn|In the original paper by Metropolis et al. (1953), <math>f</math> was taken to be the [[Boltzmann distribution]] as the specific application considered was [[Monte Carlo integration]] of [[equation of state|equations of state]] in [[physical chemistry]]; the extension by Hastings generalized to an arbitrary distribution <math>f</math>.}}.
-# आरंभीकरण: एक मनमाना बिंदु चुनें <math>x_t</math> नमूने में पहला अवलोकन होना और एक मनमाना संभाव्यता घनत्व चुनना <math>g(x\mid y)</math> (कभी-कभी लिखा जाता है <math>Q(x\mid y)</math>) जो अगले नमूना मूल्य के लिए एक उम्मीदवार का सुझाव देता है <math>x</math>, पिछला नमूना मान दिया गया है <math>y</math>. इस खंड में, <math>g</math> सममित माना जाता है; दूसरे शब्दों में, इसे संतुष्ट करना होगा <math>g(x\mid y) = g(y\mid x)</math>. एक सामान्य विकल्प है जाने देना <math>g(x\mid y)</math> [[गाऊसी वितरण]] पर केन्द्रित होना <math>y</math>, तो यह करीब इंगित करता है <math>y</math> अगले दौरे पर जाने की अधिक संभावना है, जिससे नमूनों का क्रम यादृच्छिक चलन में बदल जाता है{{efn|In the original paper by Metropolis et al. (1953), <math>g(x\mid y)</math> was suggested to be a random translation with uniform density over some prescribed range.}}. कार्यक्रम <math>g</math> प्रस्ताव घनत्व या जम्पिंग वितरण के रूप में जाना जाता है।
+# आरंभीकरण: मनमाना बिंदु चुनें <math>x_t</math> नमूने में पहला अवलोकन होना और मनमाना संभाव्यता घनत्व चुनना <math>g(x\mid y)</math> (कभी-कभी लिखा जाता है <math>Q(x\mid y)</math>) जो अगले नमूना मूल्य के लिए उम्मीदवार का सुझाव देता है <math>x</math>, पिछला नमूना मान दिया गया है <math>y</math>. इस खंड में, <math>g</math> सममित माना जाता है; दूसरे शब्दों में, इसे संतुष्ट करना होगा <math>g(x\mid y) = g(y\mid x)</math>. सामान्य विकल्प है जाने देना <math>g(x\mid y)</math> [[गाऊसी वितरण]] पर केन्द्रित होना <math>y</math>, तो यह करीब इंगित करता है <math>y</math> अगले दौरे पर जाने की अधिक संभावना है, जिससे नमूनों का क्रम यादृच्छिक चलन में बदल जाता है{{efn|In the original paper by Metropolis et al. (1953), <math>g(x\mid y)</math> was suggested to be a random translation with uniform density over some prescribed range.}}. कार्यक्रम <math>g</math> प्रस्ताव घनत्व या जम्पिंग वितरण के रूप में जाना जाता है।
 # प्रत्येक पुनरावृत्ति के लिए t:
 #* एक उम्मीदवार तैयार करें <math>x'</math> वितरण से चुनकर अगले नमूने के लिए <math>g(x'\mid x_t)</math>.
@@ Line 28: / Line 27: @@
 #** अगर <math>u > \alpha</math>, फिर उम्मीदवार को अस्वीकार करें और सेट करें <math>x_{t+1} = x_t</math> बजाय।
-यह एल्गोरिदम नमूना स्थान के बारे में बेतरतीब ढंग से आगे बढ़ने का प्रयास करके आगे बढ़ता है, कभी-कभी चालों को स्वीकार करता है और कभी-कभी जगह पर बना रहता है। ध्यान दें कि स्वीकृति अनुपात <math>\alpha</math> यह इंगित करता है कि नया प्रस्तावित नमूना वर्तमान नमूने के संबंध में कितना संभावित है, वितरण के अनुसार जिसका घनत्व है <math>P(x)</math>. यदि हम किसी ऐसे बिंदु पर जाने का प्रयास करते हैं जो मौजूदा बिंदु से अधिक संभावित है (अर्थात उच्च-घनत्व वाले क्षेत्र में एक बिंदु) <math>P(x)</math> एक के अनुरूप <math>\alpha > 1 \ge u</math>), हम इस कदम को हमेशा स्वीकार करेंगे। हालाँकि, यदि हम कम संभावित बिंदु पर जाने का प्रयास करते हैं, तो हम कभी-कभी इस कदम को अस्वीकार कर देंगे, और संभावना में सापेक्ष गिरावट जितनी अधिक होगी, उतनी अधिक संभावना है कि हम नए बिंदु को अस्वीकार कर देंगे। इस प्रकार, हम उच्च-घनत्व वाले क्षेत्रों में बने रहेंगे (और वहां से बड़ी संख्या में नमूने वापस लाएंगे)। <math>P(x)</math>, जबकि केवल कभी-कभार ही कम घनत्व वाले क्षेत्रों का दौरा करते हैं। सहज रूप से, यही कारण है कि यह एल्गोरिदम काम करता है और नमूने लौटाता है जो घनत्व के साथ वांछित वितरण का पालन करते हैं <math>P(x)</math>.
+यह एल्गोरिदम नमूना स्थान के बारे में बेतरतीब ढंग से आगे बढ़ने का प्रयास करके आगे बढ़ता है, कभी-कभी चालों को स्वीकार करता है और कभी-कभी जगह पर बना रहता है। ध्यान दें कि स्वीकृति अनुपात <math>\alpha</math> यह इंगित करता है कि नया प्रस्तावित नमूना वर्तमान नमूने के संबंध में कितना संभावित है, वितरण के अनुसार जिसका घनत्व है <math>P(x)</math>. यदि हम किसी ऐसे बिंदु पर जाने का प्रयास करते हैं जो मौजूदा बिंदु से अधिक संभावित है (अर्थात उच्च-घनत्व वाले क्षेत्र में बिंदु) <math>P(x)</math> के अनुरूप <math>\alpha > 1 \ge u</math>), हम इस कदम को हमेशा स्वीकार करेंगे। हालाँकि, यदि हम कम संभावित बिंदु पर जाने का प्रयास करते हैं, तो हम कभी-कभी इस कदम को अस्वीकार कर देंगे, और संभावना में सापेक्ष गिरावट जितनी अधिक होगी, उतनी अधिक संभावना है कि हम नए बिंदु को अस्वीकार कर देंगे। इस प्रकार, हम उच्च-घनत्व वाले क्षेत्रों में बने रहेंगे (और वहां से बड़ी संख्या में नमूने वापस लाएंगे)। <math>P(x)</math>, जबकि केवल कभी-कभार ही कम घनत्व वाले क्षेत्रों का दौरा करते हैं। सहज रूप से, यही कारण है कि यह एल्गोरिदम काम करता है और नमूने लौटाता है जो घनत्व के साथ वांछित वितरण का पालन करते हैं <math>P(x)</math>.
 अनुकूली अस्वीकृति नमूनाकरण जैसे एल्गोरिदम की तुलना में<ref name=":0">{{Cite journal |last=Gilks |first=W. R. |last2=Wild |first2=P. |date=1992-01-01 |title=गिब्स सैम्पलिंग के लिए अनुकूली अस्वीकृति सैम्पलिंग|journal=Journal of the Royal Statistical Society. Series C (Applied Statistics) |volume=41 |issue=2 |pages=337–348 |doi=10.2307/2347565 |jstor=2347565}}</ref> जो सीधे वितरण से स्वतंत्र नमूने उत्पन्न करता है, मेट्रोपोलिस-हेस्टिंग्स और अन्य एमसीएमसी एल्गोरिदम के कई नुकसान हैं:
-* नमूने सहसंबद्ध हैं। हालांकि लंबी अवधि में वे सही ढंग से पालन करते हैं <math>P(x)</math>, आस-पास के नमूनों का एक सेट एक दूसरे के साथ सहसंबद्ध होगा और वितरण को सही ढंग से प्रतिबिंबित नहीं करेगा। इसका मतलब यह है कि प्रभावी नमूना आकार वास्तव में लिए गए नमूनों की संख्या से काफी कम हो सकता है, जिससे बड़ी त्रुटियां हो सकती हैं।
+* नमूने सहसंबद्ध हैं। हालांकि लंबी अवधि में वे सही ढंग से पालन करते हैं <math>P(x)</math>, आस-पास के नमूनों का सेट दूसरे के साथ सहसंबद्ध होगा और वितरण को सही ढंग से प्रतिबिंबित नहीं करेगा। इसका मतलब यह है कि प्रभावी नमूना आकार वास्तव में लिए गए नमूनों की संख्या से काफी कम हो सकता है, जिससे बड़ी त्रुटियां हो सकती हैं।
 * यद्यपि मार्कोव श्रृंखला अंततः वांछित वितरण में परिवर्तित हो जाती है, प्रारंभिक नमूने बहुत अलग वितरण का पालन कर सकते हैं, खासकर यदि शुरुआती बिंदु कम घनत्व वाले क्षेत्र में है। परिणामस्वरूप, बर्न-इन अवधि आम तौर पर आवश्यक होती है,<ref>{{Cite book |title=बायेसियन डेटा विश्लेषण|date=2004 |publisher=Chapman & Hall / CRC |others=Gelman, Andrew |isbn=978-1584883883 |edition=2nd |location=Boca Raton, Fla. |oclc=51991499}}</ref> जहां शुरुआती संख्या में नमूने फेंके जाते हैं।
 दूसरी ओर, अधिकांश सरल [[अस्वीकृति नमूनाकरण]] विधियां आयामीता के अभिशाप से ग्रस्त हैं, जहां आयामों की संख्या के फलन के रूप में अस्वीकृति की संभावना तेजी से बढ़ जाती है। मेट्रोपोलिस-हेस्टिंग्स, अन्य एमसीएमसी विधियों के साथ, इस हद तक यह समस्या नहीं है, और इस प्रकार अक्सर एकमात्र समाधान उपलब्ध होता है जब नमूना किए जाने वाले वितरण के आयामों की संख्या अधिक होती है। परिणामस्वरूप, आजकल कई विषयों में उपयोग किए जाने वाले [[पदानुक्रमित बायेसियन मॉडल]] और अन्य उच्च-आयामी सांख्यिकीय मॉडल से नमूने तैयार करने के लिए एमसीएमसी विधियां अक्सर पसंद की विधियां होती हैं।
-[[बहुभिन्नरूपी वितरण]] वितरण में, जैसा कि ऊपर वर्णित है, क्लासिक मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम में एक नया बहु-आयामी नमूना बिंदु चुनना शामिल है। जब आयामों की संख्या अधिक होती है, तो उपयोग करने के लिए उपयुक्त जंपिंग वितरण ढूंढना मुश्किल हो सकता है, क्योंकि अलग-अलग व्यक्तिगत आयाम बहुत अलग-अलग तरीकों से व्यवहार करते हैं, और अत्यधिक से बचने के लिए जंपिंग चौड़ाई (ऊपर देखें) एक ही बार में सभी आयामों के लिए बिल्कुल सही होनी चाहिए। धीमी गति से मिश्रण. एक वैकल्पिक दृष्टिकोण जो अक्सर ऐसी स्थितियों में बेहतर काम करता है, जिसे [[ गिब्स नमूनाकरण ]] के रूप में जाना जाता है, इसमें एक ही बार में सभी आयामों के लिए एक नमूना चुनने के बजाय, प्रत्येक आयाम के लिए दूसरों से अलग एक नया नमूना चुनना शामिल है। इस तरह, संभावित उच्च-आयामी स्थान से नमूना लेने की समस्या छोटी आयामीता से नमूना लेने के लिए समस्याओं के संग्रह में कम हो जाएगी।<ref>{{Cite journal |last=Lee |first=Se Yoon |year=2021 |title=Gibbs sampler and coordinate ascent variational inference: A set-theoretical review |journal=Communications in Statistics - Theory and Methods |volume=51 |issue=6 |pages=1549–1568 |arxiv=2008.01006 |doi=10.1080/03610926.2021.1921214 |s2cid=220935477}}</ref> यह विशेष रूप से तब लागू होता है जब बहुभिन्नरूपी वितरण व्यक्तिगत यादृच्छिक चर के एक सेट से बना होता है जिसमें प्रत्येक चर केवल अन्य चर की एक छोटी संख्या पर आधारित होता है, जैसा कि अधिकांश विशिष्ट पदानुक्रमित बायेसियन मॉडल में होता है। फिर अलग-अलग चर का एक-एक करके नमूना लिया जाता है, प्रत्येक चर को अन्य सभी के नवीनतम मूल्यों पर आधारित किया जाता है। बहुभिन्नरूपी वितरण के सटीक रूप के आधार पर, इन व्यक्तिगत नमूनों को चुनने के लिए विभिन्न एल्गोरिदम का उपयोग किया जा सकता है: कुछ संभावनाएं अनुकूली अस्वीकृति नमूनाकरण विधियां हैं,<ref name=":0" />अनुकूली अस्वीकृति मेट्रोपोलिस नमूनाकरण एल्गोरिदम,<ref>{{Cite journal |last=Gilks |first=W. R. |last2=Best |first2=N. G. |author-link2=Nicky Best |last3=Tan |first3=K. K. C. |date=1995-01-01 |title=गिब्स सैम्पलिंग के भीतर अनुकूली अस्वीकृति मेट्रोपोलिस सैम्पलिंग|journal=Journal of the Royal Statistical Society. Series C (Applied Statistics) |volume=44 |issue=4 |pages=455–472 |doi=10.2307/2986138 |jstor=2986138}}</ref> एक सरल एक-आयामी मेट्रोपोलिस-हेस्टिंग्स चरण, या स्लाइस नमूनाकरण।
+[[बहुभिन्नरूपी वितरण]] वितरण में, जैसा कि ऊपर वर्णित है, क्लासिक मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम में नया बहु-आयामी नमूना बिंदु चुनना शामिल है। जब आयामों की संख्या अधिक होती है, तो उपयोग करने के लिए उपयुक्त जंपिंग वितरण ढूंढना मुश्किल हो सकता है, क्योंकि अलग-अलग व्यक्तिगत आयाम बहुत अलग-अलग तरीकों से व्यवहार करते हैं, और अत्यधिक से बचने के लिए जंपिंग चौड़ाई (ऊपर देखें) ही बार में सभी आयामों के लिए बिल्कुल सही होनी चाहिए। धीमी गति से मिश्रण. वैकल्पिक दृष्टिकोण जो अक्सर ऐसी स्थितियों में बेहतर काम करता है, जिसे [[ गिब्स नमूनाकरण ]] के रूप में जाना जाता है, इसमें ही बार में सभी आयामों के लिए नमूना चुनने के बजाय, प्रत्येक आयाम के लिए दूसरों से अलग नया नमूना चुनना शामिल है। इस तरह, संभावित उच्च-आयामी स्थान से नमूना लेने की समस्या छोटी आयामीता से नमूना लेने के लिए समस्याओं के संग्रह में कम हो जाएगी।<ref>{{Cite journal |last=Lee |first=Se Yoon |year=2021 |title=Gibbs sampler and coordinate ascent variational inference: A set-theoretical review |journal=Communications in Statistics - Theory and Methods |volume=51 |issue=6 |pages=1549–1568 |arxiv=2008.01006 |doi=10.1080/03610926.2021.1921214 |s2cid=220935477}}</ref> यह विशेष रूप से तब लागू होता है जब बहुभिन्नरूपी वितरण व्यक्तिगत यादृच्छिक चर के सेट से बना होता है जिसमें प्रत्येक चर केवल अन्य चर की छोटी संख्या पर आधारित होता है, जैसा कि अधिकांश विशिष्ट पदानुक्रमित बायेसियन मॉडल में होता है। फिर अलग-अलग चर का एक-एक करके नमूना लिया जाता है, प्रत्येक चर को अन्य सभी के नवीनतम मूल्यों पर आधारित किया जाता है। बहुभिन्नरूपी वितरण के सटीक रूप के आधार पर, इन व्यक्तिगत नमूनों को चुनने के लिए विभिन्न एल्गोरिदम का उपयोग किया जा सकता है: कुछ संभावनाएं अनुकूली अस्वीकृति नमूनाकरण विधियां हैं,<ref name=":0" />अनुकूली अस्वीकृति मेट्रोपोलिस नमूनाकरण एल्गोरिदम,<ref>{{Cite journal |last=Gilks |first=W. R. |last2=Best |first2=N. G. |author-link2=Nicky Best |last3=Tan |first3=K. K. C. |date=1995-01-01 |title=गिब्स सैम्पलिंग के भीतर अनुकूली अस्वीकृति मेट्रोपोलिस सैम्पलिंग|journal=Journal of the Royal Statistical Society. Series C (Applied Statistics) |volume=44 |issue=4 |pages=455–472 |doi=10.2307/2986138 |jstor=2986138}}</ref> सरल एक-आयामी मेट्रोपोलिस-हेस्टिंग्स चरण, या स्लाइस नमूनाकरण।
 ==औपचारिक व्युत्पत्ति==
-मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का उद्देश्य वांछित वितरण के अनुसार राज्यों का संग्रह उत्पन्न करना है <math>P(x)</math>. इसे पूरा करने के लिए, एल्गोरिदम एक [[मार्कोव प्रक्रिया]] का उपयोग करता है, जो असम्बद्ध रूप से एक अद्वितीय मार्कोव श्रृंखला # स्थिर-राज्य विश्लेषण और सीमित वितरण तक पहुंचता है <math>\pi(x)</math> ऐसा है कि <math>\pi(x) = P(x)</math>.<ref name=Roberts_Casella/>
+मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का उद्देश्य वांछित वितरण के अनुसार राज्यों का संग्रह उत्पन्न करना है <math>P(x)</math>. इसे पूरा करने के लिए, एल्गोरिदम [[मार्कोव प्रक्रिया]] का उपयोग करता है, जो असम्बद्ध रूप से अद्वितीय मार्कोव श्रृंखला # स्थिर-राज्य विश्लेषण और सीमित वितरण तक पहुंचता है <math>\pi(x)</math> ऐसा है कि <math>\pi(x) = P(x)</math>.<ref name=Roberts_Casella/>
-एक मार्कोव प्रक्रिया को उसकी संक्रमण संभावनाओं द्वारा विशिष्ट रूप से परिभाषित किया गया है <math>P(x' \mid x)</math>, किसी दिए गए राज्य से संक्रमण की संभावना <math>x</math> किसी अन्य दिए गए राज्य के लिए <math>x'</math>. इसका एक अद्वितीय स्टेशनरी वितरण है <math>\pi(x)</math> जब निम्नलिखित दो शर्तें पूरी हों:<ref name=Roberts_Casella/># स्थिर वितरण का अस्तित्व: एक स्थिर वितरण का अस्तित्व होना चाहिए <math>\pi(x)</math>. एक पर्याप्त लेकिन आवश्यक शर्त [[विस्तृत संतुलन]] नहीं है, जिसके लिए प्रत्येक संक्रमण की आवश्यकता होती है <math>x \to x'</math> प्रतिवर्ती है: राज्यों की प्रत्येक जोड़ी के लिए <math>x, x'</math>, राज्य में होने की संभावना <math>x</math> और राज्य में परिवर्तन <math>x'</math> राज्य में होने की संभावना के बराबर होना चाहिए <math>x'</math> और राज्य में परिवर्तन <math>x</math>, <math>\pi(x) P(x' \mid x) = \pi(x') P(x \mid x')</math>.
+एक मार्कोव प्रक्रिया को उसकी संक्रमण संभावनाओं द्वारा विशिष्ट रूप से परिभाषित किया गया है <math>P(x' \mid x)</math>, किसी दिए गए राज्य से संक्रमण की संभावना <math>x</math> किसी अन्य दिए गए राज्य के लिए <math>x'</math>. इसका अद्वितीय स्टेशनरी वितरण है <math>\pi(x)</math> जब निम्नलिखित दो शर्तें पूरी हों:<ref name=Roberts_Casella/># स्थिर वितरण का अस्तित्व: स्थिर वितरण का अस्तित्व होना चाहिए <math>\pi(x)</math>. पर्याप्त लेकिन आवश्यक शर्त [[विस्तृत संतुलन]] नहीं है, जिसके लिए प्रत्येक संक्रमण की आवश्यकता होती है <math>x \to x'</math> प्रतिवर्ती है: राज्यों की प्रत्येक जोड़ी के लिए <math>x, x'</math>, राज्य में होने की संभावना <math>x</math> और राज्य में परिवर्तन <math>x'</math> राज्य में होने की संभावना के बराबर होना चाहिए <math>x'</math> और राज्य में परिवर्तन <math>x</math>, <math>\pi(x) P(x' \mid x) = \pi(x') P(x \mid x')</math>.
 # स्थिर वितरण की विशिष्टता: स्थिर वितरण <math>\pi(x)</math> अद्वितीय होना चाहिए। इसकी गारंटी मार्कोव प्रक्रिया की मार्कोव चेन#एर्गोडिसिटी द्वारा दी गई है, जिसके लिए आवश्यक है कि प्रत्येक राज्य को (1) एपेरियोडिक होना चाहिए - सिस्टम निश्चित अंतराल पर उसी स्थिति में वापस नहीं आता है; और (2) सकारात्मक आवर्ती होना - उसी स्थिति में लौटने के लिए चरणों की अपेक्षित संख्या सीमित है।
-मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम में एक मार्कोव प्रक्रिया (संक्रमण संभावनाओं का निर्माण करके) को डिजाइन करना शामिल है जो उपरोक्त दो शर्तों को पूरा करता है, जैसे कि इसका स्थिर वितरण <math>\pi(x)</math> होना चुना गया है <math>P(x)</math>. एल्गोरिदम की व्युत्पत्ति विस्तृत संतुलन की स्थिति से शुरू होती है:
+मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम में मार्कोव प्रक्रिया (संक्रमण संभावनाओं का निर्माण करके) को डिजाइन करना शामिल है जो उपरोक्त दो शर्तों को पूरा करता है, जैसे कि इसका स्थिर वितरण <math>\pi(x)</math> होना चुना गया है <math>P(x)</math>. एल्गोरिदम की व्युत्पत्ति विस्तृत संतुलन की स्थिति से शुरू होती है:
 : <math>P(x' \mid x) P(x) = P(x \mid x') P(x'),</math>
@@ Line 56: / Line 55: @@
 : <math>\frac{A(x', x)}{A(x, x')} = \frac{P(x')}{P(x)}\frac{g(x \mid x')}{g(x' \mid x)}.</math>
-व्युत्पत्ति में अगला कदम एक स्वीकृति अनुपात चुनना है जो उपरोक्त शर्त को पूरा करता है। एक सामान्य विकल्प मेट्रोपोलिस विकल्प है:
+व्युत्पत्ति में अगला कदम स्वीकृति अनुपात चुनना है जो उपरोक्त शर्त को पूरा करता है। सामान्य विकल्प मेट्रोपोलिस विकल्प है:
 : <math>A(x', x) = \min\left(1, \frac{P(x')}{P(x)} \frac{g(x \mid x')}{g(x' \mid x)}\right).</math>
-इसके लिए मेट्रोपोलिस स्वीकृति अनुपात <math>A</math>, दोनों में से एक <math>A(x', x) = 1</math> या <math>A(x, x') = 1</math> और, किसी भी तरह, शर्त पूरी होती है।
+इसके लिए मेट्रोपोलिस स्वीकृति अनुपात <math>A</math>, दोनों में से <math>A(x', x) = 1</math> या <math>A(x, x') = 1</math> और, किसी भी तरह, शर्त पूरी होती है।
 मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम को इस प्रकार लिखा जा सकता है:
@@ Line 81: / Line 80: @@
 {{main|Monte Carlo integration}}
-मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का एक सामान्य उपयोग एक अभिन्न की गणना करना है। विशेष रूप से, एक स्थान पर विचार करें <math>\Omega \subset \mathbb{R}</math> और एक संभाव्यता वितरण <math>P(x)</math> ऊपर <math>\Omega</math>, <math>x \in \Omega</math>. मेट्रोपोलिस-हेस्टिंग्स के रूप का एक अभिन्न अंग का अनुमान लगा सकते हैं
+मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का सामान्य उपयोग अभिन्न की गणना करना है। विशेष रूप से, स्थान पर विचार करें <math>\Omega \subset \mathbb{R}</math> और संभाव्यता वितरण <math>P(x)</math> ऊपर <math>\Omega</math>, <math>x \in \Omega</math>. मेट्रोपोलिस-हेस्टिंग्स के रूप का अभिन्न अंग का अनुमान लगा सकते हैं
 : <math>P(E) = \int_\Omega A(x) P(x) \,dx,</math>
-कहाँ <math>A(x)</math> रुचि का एक (मापने योग्य) कार्य है।
+कहाँ <math>A(x)</math> रुचि का (मापने योग्य) कार्य है।
-उदाहरण के लिए, एक आँकड़े पर विचार करें <math>E(x)</math> और इसकी संभाव्यता वितरण <math>P(E)</math>, जो [[सीमांत वितरण]] है। मान लीजिए कि लक्ष्य अनुमान लगाना है <math>P(E)</math> के लिए <math>E</math> की पूँछ पर <math>P(E)</math>. औपचारिक रूप से, <math>P(E)</math> के रूप में लिखा जा सकता है
+उदाहरण के लिए, आँकड़े पर विचार करें <math>E(x)</math> और इसकी संभाव्यता वितरण <math>P(E)</math>, जो [[सीमांत वितरण]] है। मान लीजिए कि लक्ष्य अनुमान लगाना है <math>P(E)</math> के लिए <math>E</math> की पूँछ पर <math>P(E)</math>. औपचारिक रूप से, <math>P(E)</math> के रूप में लिखा जा सकता है
 : <math>
@@ Line 92: / Line 91: @@
 </math>
 और, इस प्रकार, अनुमान लगाना <math>P(E)</math> सूचक फ़ंक्शन के अपेक्षित मूल्य का अनुमान लगाकर पूरा किया जा सकता है <math>A_E(x) \equiv \mathbf{1}_E(x)</math>, जो 1 है जब <math>E(x) \in [E, E + \Delta E]</math> और अन्यथा शून्य.
-क्योंकि <math>E</math> की पूँछ पर है <math>P(E)</math>, एक राज्य बनाने की संभावना <math>x</math> साथ <math>E(x)</math> की पूँछ पर <math>P(E)</math> के लिए आनुपातिक है <math>P(E)</math>, जो परिभाषा के अनुसार छोटा है। मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का उपयोग यहां (दुर्लभ) राज्यों का नमूना लेने के लिए किया जा सकता है और इस प्रकार अनुमान लगाने के लिए उपयोग किए जाने वाले नमूनों की संख्या में वृद्धि हो सकती है <math>P(E)</math> पूँछ पर. यह किया जा सकता है उदा. नमूना वितरण का उपयोग करके <math>\pi(x)</math> उन राज्यों का पक्ष लेना (उदा. <math>\pi(x) \propto e^{a E}</math> साथ <math>a > 0</math>).
+क्योंकि <math>E</math> की पूँछ पर है <math>P(E)</math>, राज्य बनाने की संभावना <math>x</math> साथ <math>E(x)</math> की पूँछ पर <math>P(E)</math> के लिए आनुपातिक है <math>P(E)</math>, जो परिभाषा के अनुसार छोटा है। मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का उपयोग यहां (दुर्लभ) राज्यों का नमूना लेने के लिए किया जा सकता है और इस प्रकार अनुमान लगाने के लिए उपयोग किए जाने वाले नमूनों की संख्या में वृद्धि हो सकती है <math>P(E)</math> पूँछ पर. यह किया जा सकता है उदा. नमूना वितरण का उपयोग करके <math>\pi(x)</math> उन राज्यों का पक्ष लेना (उदा. <math>\pi(x) \propto e^{a E}</math> साथ <math>a > 0</math>).
 ==चरण-दर-चरण निर्देश==
-मान लीजिए कि नमूना लिया गया सबसे हालिया मूल्य है <math>x_t</math>. मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का पालन करने के लिए, हम आगे एक नया प्रस्ताव राज्य बनाते हैं <math>x'</math> संभाव्यता घनत्व के साथ <math>g(x' \mid x_t)</math> और एक मान की गणना करें
+मान लीजिए कि नमूना लिया गया सबसे हालिया मूल्य है <math>x_t</math>. मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का पालन करने के लिए, हम आगे नया प्रस्ताव राज्य बनाते हैं <math>x'</math> संभाव्यता घनत्व के साथ <math>g(x' \mid x_t)</math> और मान की गणना करें
 : <math>a = a_1 a_2,</math>
@@ Line 117: / Line 116: @@
   \end{cases}
 </math>
-मार्कोव श्रृंखला एक मनमाने प्रारंभिक मूल्य से शुरू की गई है <math>x_0</math>, और एल्गोरिथ्म को कई पुनरावृत्तियों तक चलाया जाता है जब तक कि यह प्रारंभिक स्थिति भूल न जाए। ये नमूने, जिन्हें त्याग दिया जाता है, बर्न-इन के रूप में जाने जाते हैं। के स्वीकृत मूल्यों का शेष सेट <math>x</math> वितरण से एक [[नमूना (सांख्यिकी)]] प्रस्तुत करें <math>P(x)</math>.
+मार्कोव श्रृंखला मनमाने प्रारंभिक मूल्य से शुरू की गई है <math>x_0</math>, और एल्गोरिथ्म को कई पुनरावृत्तियों तक चलाया जाता है जब तक कि यह प्रारंभिक स्थिति भूल न जाए। ये नमूने, जिन्हें त्याग दिया जाता है, बर्न-इन के रूप में जाने जाते हैं। के स्वीकृत मूल्यों का शेष सेट <math>x</math> वितरण से [[नमूना (सांख्यिकी)]] प्रस्तुत करें <math>P(x)</math>.
 यदि प्रस्ताव घनत्व लक्ष्य वितरण के आकार से मेल खाता है तो एल्गोरिदम सबसे अच्छा काम करता है <math>P(x)</math>, जिससे सीधा नमूना लेना कठिन है, अर्थात <math>g(x' \mid x_t) \approx P(x')</math>.
-यदि एक गाऊसी प्रस्ताव घनत्व <math>g</math> विचरण पैरामीटर का उपयोग किया जाता है <math>\sigma^2</math> बर्न-इन अवधि के दौरान ट्यून करना होगा।
+यदि गाऊसी प्रस्ताव घनत्व <math>g</math> विचरण पैरामीटर का उपयोग किया जाता है <math>\sigma^2</math> बर्न-इन अवधि के दौरान ट्यून करना होगा।
 यह आमतौर पर स्वीकृति दर की गणना करके किया जाता है, जो प्रस्तावित नमूनों का वह अंश है जिसे अंतिम विंडो में स्वीकार किया जाता है <math>N</math> नमूने.
 वांछित स्वीकृति दर लक्ष्य वितरण पर निर्भर करती है, हालांकि यह सैद्धांतिक रूप से दिखाया गया है कि एक-आयामी गॉसियन वितरण के लिए आदर्श स्वीकृति दर लगभग 50% है, जो घटकर लगभग 23% हो जाती है। <math>N</math>-आयामी गाऊसी लक्ष्य वितरण.<ref name=Roberts/>पर्याप्त रूप से नियमित बायेसियन पोस्टीरियर से नमूना लेने पर ये दिशानिर्देश अच्छी तरह से काम कर सकते हैं क्योंकि वे अक्सर बहुभिन्नरूपी सामान्य वितरण का पालन करते हैं जैसा कि बर्नस्टीन-वॉन मिज़ प्रमेय का उपयोग करके स्थापित किया जा सकता है।<ref>{{Cite journal |last=Schmon |first=Sebastian M. |last2=Gagnon |first2=Philippe |date=2022-04-15 |title=बायेसियन लार्ज-सैंपल एसिम्प्टोटिक्स का उपयोग करके रैंडम वॉक मेट्रोपोलिस एल्गोरिदम की इष्टतम स्केलिंग|journal=Statistics and Computing |language=en |volume=32 |issue=2 |pages=28 |doi=10.1007/s11222-022-10080-8 |issn=0960-3174 |pmc=8924149 |pmid=35310543}}</ref>

Anonymous

Search

मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम: Difference between revisions

Namespaces

More

Page actions

Revision as of 18:37, 2 December 2023

Contents

इतिहास

अंतर्ज्ञान

औपचारिक व्युत्पत्ति

संख्यात्मक एकीकरण में उपयोग

चरण-दर-चरण निर्देश

बायेसियन अनुमान

यह भी देखें

संदर्भ

टिप्पणियाँ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम: Difference between revisions

Revision as of 18:37, 2 December 2023

इतिहास

अंतर्ज्ञान

औपचारिक व्युत्पत्ति

संख्यात्मक एकीकरण में उपयोग

चरण-दर-चरण निर्देश

बायेसियन अनुमान

यह भी देखें

संदर्भ

टिप्पणियाँ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories