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

Revision as of 20:25, 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/>सामान्यीकृत विधि को अंततः दोनों नामों से पहचाना गया, हालांकि मेट्रोपोलिस-हेस्टिंग्स कलन शब्द का पहला उपयोग अस्पष्ट है।
+एल्गोरिथम का नाम आंशिक रूप से [[निकोलस मेट्रोपोलिस]] के नाम पर रखा गया है, जो 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/>रोसेनब्लुथ ने फिर से टेलर को मूल समस्या प्रस्तुत करने, स्वयं इसे हल करने और एरियाना को कंप्यूटर प्रोग्रामिंग करने का श्रेय दिया।
@@ Line 12: / Line 15: @@
 मेट्रोपोलिस-हेस्टिंग्स कलन संभाव्यता घनत्व के साथ किसी भी संभाव्यता वितरण से प्रतिरूप खींच सकता है <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> वांछित वितरण के संबंध में वर्तमान और उम्मीदवार प्रतिरूप मूल्यों का।
-चित्रण के प्रयोजन के लिए, मेट्रोपोलिस एल्गोरिदम, मेट्रोपोलिस-हेस्टिंग्स कलन का विशेष मामला जहां प्रस्ताव फ़ंक्शन सममित है, नीचे वर्णित है।
+चित्रण के प्रयोजन के लिए, मेट्रोपोलिस कलन, मेट्रोपोलिस-हेस्टिंग्स कलन का विशेष मामला जहां प्रस्ताव फ़ंक्शन सममित है, नीचे वर्णित है।
 ;मेट्रोपोलिस कलन (सममित प्रस्ताव वितरण):
 होने देना <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 27: / Line 30: @@
 #** अगर <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> जो सीधे वितरण से स्वतंत्र प्रतिरूप उत्पन्न करता है, मेट्रोपोलिस-हेस्टिंग्स और अन्य एमसीएमसी कलन के कई नुकसान हैं:
+अनुकूली अस्वीकृति प्रतिरूपीकरण जैसे कलन की तुलना में<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 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> सरल एक-आयामी मेट्रोपोलिस-हेस्टिंग्स चरण, या स्लाइस प्रतिरूपीकरण ।
 ==औपचारिक व्युत्पत्ति==
@@ Line 91: / Line 94: @@
 </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 100: / Line 103: @@
 : <math>a_1 = \frac{P(x')}{P(x_t)}</math>
-प्रस्तावित प्रतिरूप के बीच संभाव्यता (जैसे, बायेसियन पोस्टीरियर) अनुपात है <math>x'</math> और पिछला नमूना <math>x_t</math>, और
+प्रस्तावित प्रतिरूप के बीच संभाव्यता (जैसे, बायेसियन पोस्टीरियर) अनुपात है <math>x'</math> और पिछला प्रतिरूप <math>x_t</math>, और
 : <math>a_2 = \frac{g(x_t \mid x')}{g(x' \mid x_t)}</math>
@@ Line 116: / Line 119: @@
   \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>P(x)</math>, जिससे सीधा प्रतिरूप लेना कठिन है, अर्थात <math>g(x' \mid x_t) \approx P(x')</math>.
 यदि गाऊसी प्रस्ताव घनत्व <math>g</math> विचरण पैरामीटर का उपयोग किया जाता है <math>\sigma^2</math> बर्न-इन अवधि के दौरान ट्यून करना होगा।
-यह आमतौर पर स्वीकृति दर की गणना करके किया जाता है, जो प्रस्तावित नमूनों का वह अंश है जिसे अंतिम विंडो में स्वीकार किया जाता है <math>N</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>
+वांछित स्वीकृति दर लक्ष्य वितरण पर निर्भर करती है, हालांकि यह सैद्धांतिक रूप से दिखाया गया है कि एक-आयामी गॉसियन वितरण के लिए आदर्श स्वीकृति दर लगभग 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>
 अगर <math>\sigma^2</math> बहुत छोटा है, श्रृंखला धीरे-धीरे मिश्रित होगी (यानी, स्वीकृति दर अधिक होगी, लेकिन क्रमिक प्रतिरूप धीरे-धीरे अंतरिक्ष में घूमेंगे, और श्रृंखला केवल धीरे-धीरे ही परिवर्तित होगी) <math>P(x)</math>). वहीं दूसरी ओर,
-अगर <math>\sigma^2</math> बहुत बड़ा है, स्वीकृति दर बहुत कम होगी क्योंकि प्रस्तावों के बहुत कम संभावना घनत्व वाले क्षेत्रों में आने की संभावना है, इसलिए <math>a_1</math> बहुत छोटा होगा, और फिर से श्रृंखला बहुत धीरे-धीरे एकत्रित होगी। आम तौर पर प्रस्ताव वितरण को ट्यून किया जाता है ताकि कलन सभी नमूनों के 30% के क्रम पर स्वीकार कर सके - पिछले पैराग्राफ में उल्लिखित सैद्धांतिक अनुमानों के अनुरूप।
+अगर <math>\sigma^2</math> बहुत बड़ा है, स्वीकृति दर बहुत कम होगी क्योंकि प्रस्तावों के बहुत कम संभावना घनत्व वाले क्षेत्रों में आने की संभावना है, इसलिए <math>a_1</math> बहुत छोटा होगा, और फिर से श्रृंखला बहुत धीरे-धीरे एकत्रित होगी। सामान्यतः प्रस्ताव वितरण को ट्यून किया जाता है ताकि कलन सभी प्रतिरूप के 30% के क्रम पर स्वीकार कर सके - पिछले पैराग्राफ में उल्लिखित सैद्धांतिक अनुमानों के अनुरूप।
 [[Image:3dRosenbrock.png|thumb|मेट्रोपोलिस-हेस्टिंग्स एल्गोरिथम का उपयोग करके 3डी [[रोसेनब्रॉक फ़ंक्शन]] पर चलने वाली तीन [[मार्कोव श्रृंखला]]ओं का परिणाम। कलन उन क्षेत्रों से प्रतिरूप लेता है जहां पश्चवर्ती संभावना अधिक होती है, और इन क्षेत्रों में श्रृंखलाएं मिश्रित होने लगती हैं। अधिकतम की अनुमानित स्थिति पर प्रकाश डाला गया है। लाल बिंदु वे हैं जो बर्न-इन प्रक्रिया के बाद बने रहते हैं। पहले वालों को हटा दिया गया है.]]
@@ Line 136: / Line 139: @@
 ==यह भी देखें==
 * विस्तृत संतुलन
-* आनुवंशिक एल्गोरिदम
+* आनुवंशिक कलन
 * गिब्स प्रतिरूपीकरण
 * [[हैमिल्टनियन मोंटे कार्लो]]
 * [[माध्य-क्षेत्र कण विधियाँ]]
-* [[मेट्रोपोलिस-समायोजित लैंग्विन एल्गोरिदम]]
+* [[मेट्रोपोलिस-समायोजित लैंग्विन एल्गोरिदम|मेट्रोपोलिस-समायोजित लैंग्विन कलन]]
 * [[महानगर प्रकाश परिवहन]]
 * [[ बहु-प्रयास महानगर ]]
 * [[समानांतर तड़का]]
-* पूर्वनिर्धारित क्रैंक-निकोलसन एल्गोरिदम
+* पूर्वनिर्धारित क्रैंक-निकोलसन कलन
 * [[कण फिल्टर]]
 * [[तैयार किए हुयी धातु पे पानी चढाने की कला]]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 20:25, 2 December 2023

Contents

इतिहास

अंतर्ज्ञान

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

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

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

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

यह भी देखें

संदर्भ

टिप्पणियाँ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 20:25, 2 December 2023

इतिहास

अंतर्ज्ञान

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

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

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

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

यह भी देखें

संदर्भ

टिप्पणियाँ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories