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

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

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

इतिहास

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

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

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

अंतर्ज्ञान

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

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

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

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

मान लीजिए कि $f(x)$ ऐसा फलन है जो वांछित संभाव्यता घनत्व फलन $P(x)$ (ए.के.ए. लक्ष्य वितरण) के समानुपाती है।

1. आरंभीकरण: प्रतिरूप में प्रथम अवलोकन होने के लिए इच्छानुसार बिंदु $x_{t}$ चुनें और इच्छानुसार संभाव्यता घनत्व चुनें $g(x\mid y)$ (कभी-कभी $Q(x\mid y)$ लिखा जाता है) जो पूर्व प्रतिरूप मान $y$ को देखते हुए अगले प्रतिरूप मान $x$ के लिए प्रतियोगी का सुझाव देता है। इस खंड में, $g$ को सममित माना गया है; दूसरे शब्दों में, इसे $g(x\mid y)=g(y\mid x)$ को संतुष्ट करना होगा। सामान्य विकल्प यह है कि $g(x\mid y)$ को $y$ पर केन्द्रित गाऊसी वितरण बनाया जाए, जिससे कि $y$ के समीप के बिंदुओं पर अगली बार जाने की अधिक संभावना हो, जिससे प्रतिरूपों का क्रम यादृच्छिक रूप से चल सके। फलन $g$ को प्रस्ताव घनत्व या जंपिंग वितरण के रूप में जाना जाता है।
2. प्रत्येक पुनरावृत्ति के लिए t:
   • वितरण $g(x'\mid x_{t})$ से चुनकर अगले प्रतिरूप के लिए प्रतियोगी $x'$ उत्पन्न करें।
   • स्वीकृति अनुपात $\alpha =f(x')/f(x_{t})$ की गणना करें, जिसका उपयोग यह निश्चित करने के लिए किया जाएगा कि प्रतियोगी को स्वीकार करना है या अस्वीकार करना है . क्योंकि 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)$ के साथ वांछित वितरण का पालन करते हैं .

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

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

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

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

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

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

मार्कोव प्रक्रिया को उसकी संक्रमण संभावनाओं $P(x'\mid x)$ द्वारा विशिष्ट रूप से परिभाषित किया गया है, किसी भी दिए गए स्थान $x$ से किसी अन्य दिए गए स्थान $x'$ के लिए संक्रमण की संभावना होती हैं. निम्नलिखित दो निम्नलिखित दो नियमें पूर्ण होने पर इसका अद्वितीय स्थिर वितरण $\pi (x)$ होता हैं :

1. स्थिर वितरण का अस्तित्व: स्थिर वितरण $\pi (x)$ का अस्तित्व होना चाहिए . यह पर्याप्त किन्तु आवश्यक नियम विस्तृत संतुलन है जिसके लिए आवश्यक है कि प्रत्येक संक्रमण $x\to x'$ प्रतिवर्ती है: इसमें स्थानों की प्रत्येक जोड़ी के लिए $x,x'$, स्थान $x$ में होने और स्थान $x'$में संक्रमण की संभावना सामान्य होनी चाहिए | इस स्थान $x'$ में होने और स्थान $x$ में परिवर्तित होने की संभावना के लिए $\pi (x)P(x'\mid x)=\pi (x')P(x\mid x')$ आवश्यक हैं .
2. स्थिर वितरण की विशिष्टता: स्थिर वितरण $\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. आरंभ करें
   1. एक प्रारंभिक अवस्था $x_{0}$ चुनें .
   2. $t=0$ निश्चित करना .
2. पुनरावृति
   1. $g(x'\mid x_{t})$ के अनुसार यादृच्छिक प्रतियोगी स्थान $x'$ उत्पन्न करें.
   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)$ तक पहुंच जाएगा | प्रभावी विधि से अनुमान $P(x)$ लगाने के लिए आवश्यक पुनरावृत्तियों ($T$) की संख्या कारकों की संख्या पर निर्भर करती है, जिसमे $P(x)$ और प्रस्ताव वितरण के मध्य संबंध और अनुमान की वांछित स्पष्टता सम्मिलित है। असतत स्थान स्थानों पर वितरण के लिए, इसे मार्कोव प्रक्रिया के स्वत: सहसंबंध समय के क्रम का होना चाहिए।

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

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

Main article: मोंटे कार्लो एकीकरण

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

क्रमश: निर्देश

मान लीजिए कि प्रतिरूप लिया गया सबसे वर्तमान $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% है, जो $N$-आयामी गाऊसी लक्ष्य वितरण के लिए घटकर लगभग 23% हो जाती है। इसमें पर्याप्त रूप से नियमित बायेसियन पोस्टीरियर से प्रतिरूप लेने पर यह दिशानिर्देश सही प्रकार से कार्य कर सकते हैं क्योंकि वह प्रायः बहुभिन्नरूपी सामान्य वितरण का पालन करते हैं जैसे कि इसको बर्नस्टीन-वॉन मिसेस प्रमेय का उपयोग करके स्थापित किया जा सकता है।

यदि $\sigma ^{2}$ बहुत छोटा होता है, तब इसमें श्रृंखला धीरे-धीरे मिश्रित होती हैं (अर्थात, स्वीकृति दर अधिक होगी, किन्तु क्रमिक प्रतिरूप धीरे-धीरे स्पेस के चारों ओर परिवर्तित होगी, और श्रृंखला केवल धीरे-धीरे $P(x)$) में परिवर्तित होती हैं)। दूसरी ओर, यदि $\sigma ^{2}$ बहुत बड़ा है, तब स्वीकृति दर बहुत कम होगी क्योंकि प्रस्तावों के बहुत कम संभावना घनत्व वाले क्षेत्रों में आने की संभावना होती है, इसलिए $a_{1}$ बहुत छोटा होता हैं, और फिर से वह श्रृंखला बहुत धीरे-धीरे एकत्रित होते हैं। इसमें सामान्यतः प्रस्ताव वितरण को ट्यून किया जाता है जिससे एल्गोरिदम सभी प्रतिरूपों को 30% के क्रम पर स्वीकार कर सके - यह पूर्व पैराग्राफ में उल्लिखित सैद्धांतिक अनुमानों के अनुरूप होता हैं।

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

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

Main article: बायेसियन अनुमान

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

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

स्वीकृति की संभावना इस प्रकार दी गई है:$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$ (सशर्त) प्रस्ताव संभावना होती हैं।

यह भी देखें

• विस्तृत संतुलन
• आनुवंशिक ऐल्गरिदम
• गिब्स प्रतिरूपीकरण
• हैमिल्टनियन मोंटे कार्लो
• माध्य-क्षेत्र कण विधियाँ
• मेट्रोपोलिस-समायोजित लैंग्विन ऐल्गरिदम
• मेट्रोपोलिस लाइट ट्रांसपोर्ट
• मल्टीपल-ट्राई मेट्रोपोलिस
• समानांतर टेम्परिंग
• पूर्वनिर्धारित क्रैंक-निकोलसन ऐल्गरिदम
• अनुक्रमिक मोंटे कार्लो
• सिम्युलेटेड अनीलिंग

अग्रिम पठन

• 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