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

Latest revision as of 10:22, 11 December 2023

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

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

इतिहास

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

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

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

अंतर्ज्ञान

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

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

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

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

मान लीजिए कि $f(x)$ ऐसा फलन है जो वांछित संभाव्यता घनत्व फलन $P(x)$ (ए.के.ए. लक्ष्य वितरण) के समानुपाती है।^{[lower-alpha 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$ के समीप के बिंदुओं पर अगली बार जाने की अधिक संभावना हो, जिससे प्रतिरूपों का क्रम यादृच्छिक रूप से चल सके। ^{[lower-alpha 2]} फलन $g$ को प्रस्ताव घनत्व या जंपिंग वितरण के रूप में जाना जाता है।
प्रत्येक पुनरावृत्ति के लिए t:
- वितरण $g(x'\mid x_{t})$ से चुनकर अगले प्रतिरूप के लिए प्रतियोगी $x'$ उत्पन्न करें।
- स्वीकृति अनुपात $\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. $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)$ और प्रस्ताव वितरण के मध्य संबंध और अनुमान की वांछित स्पष्टता सम्मिलित है।^[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)$ के अपेक्षित मान का अनुमान लगाकर पूर्ण किया जा सकता है, जो कि $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% हो जाती है। ^[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 2: / Line 2: @@
 [[Image:Metropolis hastings algorithm.png|thumb|450px|प्रस्ताव संभाव्यता वितरण Q अगले बिंदु का प्रस्ताव करता है जिस पर [[यादृच्छिक चाल]] चल सकती है।]]
-सांख्यिकी और [[सांख्यिकीय भौतिकी]] में, '''मेट्रोपोलिस-हेस्टिंग्स''' ऐल्गरिदम संभाव्यता वितरण से यादृच्छिक प्रतिरूप का अनुक्रम प्राप्त करने के लिए [[मार्कोव श्रृंखला मोंटे कार्लो]] (एमसीएमसी) विधि है, जहां से प्रत्यक्ष प्रतिरूपीकरण कठिन होता है। इस अनुक्रम का उपयोग वितरण का अनुमान लगाने के लिए किया जा सकता है| इसका उपयोग (उदाहरण के लिए [[हिस्टोग्राम]] उत्पन्न करने के लिए) या [[मोंटे कार्लो एकीकरण]] (उदाहरण के लिए [[अपेक्षित मूल्य]]) के अभिन्न अंग की गणना करने के लिए किया जा सकता हैं। मेट्रोपोलिस-हेस्टिंग्स और अन्य एमसीएमसी ऐल्गरिदम का उपयोग सामान्यतः बहु-आयामी वितरण से प्रतिरूप लेने के लिए किया जाता है, अधिकांश जब आयामों की संख्या अधिक होती है। तब एकल-आयामी वितरण के लिए, सामान्यतः अन्य विधियां होती हैं (उदाहरण के लिए [[अनुकूली अस्वीकृति नमूनाकरण|अनुकूली अस्वीकृति प्रतिरूपीकरण]]) जो सीधे वितरण से स्वतंत्र प्रतिरूप वापस कर सकती हैं, और जो एमसीएमसी विधियों में निहित स्वत: सहसंबद्ध प्रतिरूप की समस्या से मुक्त हैं।
+सांख्यिकी और [[सांख्यिकीय भौतिकी]] में, '''मेट्रोपोलिस-हेस्टिंग्स''' ऐल्गरिदम संभाव्यता वितरण से यादृच्छिक प्रतिरूप का अनुक्रम प्राप्त करने के लिए [[मार्कोव श्रृंखला मोंटे कार्लो]] (एमसीएमसी) विधि है, जहां से प्रत्यक्ष प्रतिरूपीकरण कठिन होता है। इस अनुक्रम का उपयोग वितरण का अनुमान लगाने के लिए किया जा सकता है| इसका उपयोग (उदाहरण के लिए [[हिस्टोग्राम]] उत्पन्न करने के लिए) या [[मोंटे कार्लो एकीकरण]] (उदाहरण के लिए [[अपेक्षित मूल्य|अपेक्षित मान]]) के अभिन्न अंग की गणना करने के लिए किया जा सकता हैं। मेट्रोपोलिस-हेस्टिंग्स और अन्य एमसीएमसी ऐल्गरिदम का उपयोग सामान्यतः बहु-आयामी वितरण से प्रतिरूप लेने के लिए किया जाता है, अधिकांश जब आयामों की संख्या अधिक होती है। तब एकल-आयामी वितरण के लिए, सामान्यतः अन्य विधियां होती हैं (उदाहरण के लिए [[अनुकूली अस्वीकृति नमूनाकरण|अनुकूली अस्वीकृति प्रतिरूपीकरण]]) जो सीधे वितरण से स्वतंत्र प्रतिरूप वापस कर सकती हैं, और जो एमसीएमसी विधियों में निहित स्वत: सहसंबद्ध प्रतिरूप की समस्या से मुक्त हैं।
 ==इतिहास==
@@ Line 9: / Line 9: @@
 मेट्रोपोलिस एल्गोरिथम के विकास के श्रेय के संबंध में कुछ तर्क उपस्तिथ हैं। मेट्रोपोलिस, जो विधि के कम्प्यूटेशनल पहलुओं से परिचित थे, इन्होने स्टैनिस्लाव उलम के साथ प्राचीन लेख में मोंटे कार्लो शब्दों को गढ़ा था, और सैद्धांतिक प्रभाग में उस समूह का नेतृत्व किया था जिसने 1952 में प्रयोगों में उपयोग किए गए [[MANIAC I|मनियाक आई]] कंप्यूटर को डिजाइन और निर्मित किया था। चूँकि, 2003 से पूर्व एल्गोरिथम के विकास का कोई विस्तृत विवरण नहीं था। अपनी मृत्यु से कुछ समय पहले, मार्शल रोसेनब्लुथ ने 1953 के प्रकाशन की 50वीं वर्षगांठ के अवसर पर लैनएल में 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>P                                                                                                                                                                                                                               </math> और मानों के आनुपातिक फ़ंक्शन<math>f(x)</math> को जानते हों। और <math>f(x)</math> की गणना की जा सकती है। यह आवश्यकता कि <math>f(x)</math> घनत्व के बिल्कुल समान्य होने केअतिरिक्त केवल आनुपातिक होना चाहिए, मेट्रोपोलिस-हेस्टिंग्स एल्गोरिथ्म को विशेष रूप से उपयोगी बनाता है, क्योंकि आवश्यक सामान्यीकरण कारक की गणना करना प्रायः वास्तव मेंअत्यधिक कठिन होता है।
+मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम संभाव्यता घनत्व <math>P(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>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>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>y</math> को देखते हुए अगले प्रतिरूप मान <math>x</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>.
+#*वितरण <math>g(x'\mid x_t)</math> से चुनकर अगले प्रतिरूप के लिए प्रतियोगी <math>x'</math> उत्पन्न करें।
-#* स्वीकृति अनुपात की गणना करें <math>\alpha = f(x')/f(x_t)</math>, जिसका उपयोग यह तय करने के लिए किया जाएगा कि प्रतियोगी को स्वीकार करना है या अस्वीकार करना है{{efn|In the original paper by Metropolis et al. (1953), <math>f</math> 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.}}. क्योंकि f, P के घनत्व के समानुपाती है, हमारे पास वह है <math>\alpha = f(x')/f(x_t) = P(x')/P(x_t)</math>.
+#* स्वीकृति अनुपात <math>\alpha = f(x')/f(x_t)</math> की गणना करें, जिसका उपयोग यह निश्चित करने के लिए किया जाएगा कि प्रतियोगी को स्वीकार करना है या अस्वीकार करना है {{efn|In the original paper by Metropolis et al. (1953), <math>f</math> 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.}}. क्योंकि f, P के घनत्व के समानुपाती है,और हमारे समीप वह <math>\alpha = f(x')/f(x_t) = P(x')/P(x_t)</math> है .
 #* स्वीकार करें या अस्वीकार करें:
-#** एक समान यादृच्छिक संख्या उत्पन्न करें <math>u \in [0, 1]</math>.
+#** इस समान यादृच्छिक संख्या <math>u \in [0, 1]</math> को उत्पन्न करें .
-#** अगर <math>u \le \alpha</math>, फिर सेटिंग करके प्रतियोगी को स्वीकार करें <math>x_{t+1} = x'</math>,
+#*यदि <math>u \le \alpha</math> है, तब <math>x_{t+1} = x'</math> समुच्चय करके प्रतियोगी को स्वीकार करें,
-#** अगर <math>u > \alpha</math>, फिर प्रतियोगी को अस्वीकार करें और सेट करें <math>x_{t+1} = x_t</math>अतिरिक्त।
+#*यदि <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> सरल एक-आयामी मेट्रोपोलिस-हेस्टिंग्स चरण, या स्लाइस प्रतिरूपीकरण होता हैं ।
 ==औपचारिक व्युत्पत्ति==
-मेट्रोपोलिस-हेस्टिंग्स ऐल्गरिदम का उद्देश्य वांछित वितरण के अनुसार स्थानों का संग्रह उत्पन्न करना है <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> अद्वितीय होना चाहिए। इसकी गारंटी मार्कोव प्रक्रिया की मार्कोव चेन#एर्गोडिसिटी द्वारा दी गई है, जिसके लिए आवश्यक है कि प्रत्येक स्थान को (1) एपेरियोडिक होना चाहिए - सिस्टम निश्चित अंतराल पर उसी स्थिति में वापस नहीं आता है; और (2) सकारात्मक आवर्ती होना - उसी स्थिति में लौटने के लिए चरणों की अपेक्षित संख्या सीमित है।
+# स्थिर वितरण का अस्तित्व: स्थिर वितरण <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 51: / Line 53: @@
 : <math>\frac{P(x' \mid x)}{P(x \mid x')} = \frac{P(x')}{P(x)}.</math>
-दृष्टिकोण संक्रमण को दो उप-चरणों में अलग करना है; प्रस्ताव और स्वीकृति-अस्वीकृति. प्रस्ताव वितरण <math>g(x' \mid x)</math> किसी स्थान को प्रस्तावित करने की सशर्त संभावना है <math>x'</math> दिया गया <math>x</math>, और स्वीकृति वितरण <math>A(x', x)</math> प्रस्तावित स्थान को स्वीकार करने की संभावना है <math>x'</math>. संक्रमण संभाव्यता को उनके उत्पाद के रूप में लिखा जा सकता है:
+इस दृष्टिकोण संक्रमण को दो उप-चरणों में भिन्न करना है; प्रस्ताव और स्वीकृति-अस्वीकृति. प्रस्ताव वितरण <math>g(x' \mid x)</math> दिए गए <math>x</math> किसी स्थान <math>x'</math> को प्रस्तावित करने की सनियम संभावना है, और स्वीकृति वितरण <math>A(x', x)</math> प्रस्तावित स्थान <math>x'</math> को स्वीकार करने की संभावना है. संक्रमण संभाव्यता को उनके उत्पाद के रूप में लिखा जा सकता है:
 : <math>P(x'\mid x) = g(x' \mid x) A(x', x).</math>
-इस संबंध को पिछले समीकरण में डालने पर, हमारे पास है
+इस संबंध को पूर्व समीकरण में डालने पर, हमारे समीप है
 : <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> और, किसी भी प्रकार, नियम पूर्ण होती है।
 मेट्रोपोलिस-हेस्टिंग्स ऐल्गरिदम को इस प्रकार लिखा जा सकता है:
 # आरंभ करें
-## एक प्रारंभिक अवस्था चुनें <math>x_0</math>.
+## एक प्रारंभिक अवस्था <math>x_0</math> चुनें .
-## तय करना <math>t = 0</math>.
+## <math>t = 0</math> निश्चित करना .
 # पुनरावृति
-## एक यादृच्छिक प्रतियोगी स्थान उत्पन्न करें <math>x'</math> के अनुसार <math>g(x' \mid x_t)</math>.
+## <math>g(x' \mid x_t)</math> के अनुसार यादृच्छिक प्रतियोगी स्थान <math>x'</math> उत्पन्न करें.
-## स्वीकृति संभावना की गणना करें <math>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)</math>.
+## स्वीकृति संभावना <math>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)</math> की गणना करें .
 ## स्वीकार करें या अस्वीकार करें:
-### एक समान यादृच्छिक संख्या उत्पन्न करें <math>u \in [0, 1]</math>;
+### एक समान यादृच्छिक संख्या <math>u \in [0, 1]</math> उत्पन्न करें ;
-### अगर <math>u \le A(x' , x_t)</math>, फिर नए स्थान को स्वीकार करें और सेट करें <math>x_{t+1} = x'</math>;
+### यदि <math>u \le A(x' , x_t)</math>, फिर नए स्थान को स्वीकार करें और <math>x_{t+1} = x'</math> समुच्चय करें ;
-### अगर <math>u >   A(x' , x_t)</math>, फिर नए स्थान को अस्वीकार करें, और प्राचीन स्थान को आगे कॉपी करें <math>x_{t+1} = x_{t}</math>.
+### यदि <math>u >   A(x' , x_t)</math>, फिर नए स्थान को अस्वीकार करें, और प्राचीन स्थान <math>x_{t+1} = x_{t}</math> को आगे कॉपी करें .
-## वृद्धि: सेट <math>t = t + 1</math>.
+## वृद्धि: समुच्चय <math>t = t + 1</math>.
-बशर्ते कि निर्दिष्ट शर्तें पूरी हों, सहेजे गए स्थानों का अनुभवजन्य वितरण <math>x_0, \ldots, x_T</math> संपर्क करेंगे <math>P(x)</math>. पुनरावृत्तियों की संख्या (<math>T</math>) प्रभावी ढंग से अनुमान लगाने की आवश्यकता है <math>P(x)</math> कारकों की संख्या पर निर्भर करता है, जिसमें बीच का संबंध भी शामिल है <math>P(x)</math> और प्रस्ताव वितरण और अनुमान की वांछित सटीकता।<ref>Raftery, Adrian E., and Steven Lewis. "How Many Iterations in the Gibbs Sampler?" ''In Bayesian Statistics 4''. 1992.</ref> असतत स्थान स्थानों पर वितरण के लिए, इसे मार्कोव प्रक्रिया के स्वत: सहसंबंध समय के क्रम का होना चाहिए।<ref name=Newman_Barkema/>
+परंतु कि निर्दिष्ट नियम पूर्ण हों, सहेजे गए स्थानों का अनुभवजन्य वितरण <math>x_0, \ldots, x_T</math>, <math>P(x)</math> तक पहुंच जाएगा | प्रभावी विधि से अनुमान <math>P(x)</math> लगाने के लिए आवश्यक पुनरावृत्तियों (<math>T</math>) की संख्या कारकों की संख्या पर निर्भर करती है, जिसमे <math>P(x)</math> और प्रस्ताव वितरण के मध्य संबंध और अनुमान की वांछित स्पष्टता सम्मिलित है।<ref>Raftery, Adrian E., and Steven Lewis. "How Many Iterations in the Gibbs Sampler?" ''In Bayesian Statistics 4''. 1992.</ref> असतत स्थान स्थानों पर वितरण के लिए, इसे मार्कोव प्रक्रिया के स्वत: सहसंबंध समय के क्रम का होना चाहिए।<ref name=Newman_Barkema/>
-यह ध्यान रखना महत्वपूर्ण है कि सामान्य समस्या में यह स्पष्ट नहीं है कि कौन सा वितरण <math>g(x' \mid x)</math> किसी को उचित अनुमान के लिए आवश्यक पुनरावृत्तियों की संख्या का उपयोग करना चाहिए; दोनों विधि के निःशुल्क पैरामीटर हैं, जिन्हें उपस्तिथा विशेष समस्या के अनुसार समायोजित किया जाना चाहिए।
+यह ध्यान रखना महत्वपूर्ण है कि यह स्पष्ट नहीं है, सामान्य समस्या में, किस वितरण <math>g(x' \mid x)</math> का उपयोग करना चाहिए या उचित अनुमान के लिए आवश्यक पुनरावृत्तियों की संख्या का उपयोग करना चाहिए; दोनों विधि के निःशुल्क पैरामीटर हैं, जिन्हें उपिस्थित विशेष समस्या के अनुसार समायोजित किया जाना चाहिए।
 ==संख्यात्मक एकीकरण में उपयोग==
-{{main|Monte Carlo integration}}
+{{main|मोंटे कार्लो एकीकरण}}
-मेट्रोपोलिस-हेस्टिंग्स ऐल्गरिदम का सामान्य उपयोग अभिन्न की गणना करना है। विशेष रूप से, स्थान पर विचार करें <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>
 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)
 </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>P(E)</math> का आकलन सूचक फलन <math>A_E(x) \equiv \mathbf{1}_E(x)</math> के अपेक्षित मान का अनुमान लगाकर पूर्ण किया जा सकता है, जो कि <math>E(x) \in [E, E + \Delta E]</math> होने पर 1 है और अन्यथा शून्य है। चूँकि <math>E</math>, <math>P(E)                                                                                                                                                                                                                                  </math> की टेल पर होता है, और <math>P(E)</math> की टेल पर <math>E(x)</math> के साथ अवस्था <math>x</math> बनाने की संभावना <math>P(E)</math> के समानुपाती होती है, जो परिभाषा के अनुसार छोटी होती है। मेट्रोपोलिस-हेस्टिंग्स एल्गोरिदम का उपयोग यहां (दुर्लभ) स्थितियों का अधिक संभावित प्रतिरूप लेने के लिए किया जा सकता है और इस प्रकार टेलों पर <math>P(E)</math> का अनुमान लगाने के लिए उपयोग किए जाने वाले प्रतिरूपों की संख्या में वृद्धि हो सकती है। यह कहाँ जा सकता है कि उदा. उन स्थानों का पक्ष लेने के लिए प्रतिरूप वितरण <math>\pi(x)</math> का उपयोग करके (उदाहरण के लिए <math>a > 0</math> के साथ <math>\pi(x) \propto e^{a 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>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>
-कहाँ
+जहाँ
 : <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>
-दो दिशाओं में प्रस्ताव घनत्व का अनुपात है (से <math>x_t</math> को <math>x'</math> और इसके विपरीत)।
+दो दिशाओं में प्रस्ताव घनत्व का अनुपात है (इससे <math>x_t</math> से <math>x'</math> और इसके विपरीत होते हैं)। यदि प्रस्ताव घनत्व सममित है तब यह 1 के समान्य है। उसके पश्चात् फिर निम्नलिखित नियमों के अनुसार स्थान <math>x_{t+1}</math>को चुना जाता है।
-यदि प्रस्ताव घनत्व सममित है तब यह 1 के समान्य है।
-फिर नया स्थान <math>x_{t+1}</math> निम्नलिखित नियमों के अनुसार चुना जाता है।
-: अगर <math>a \geq 1{:}</math>
+: यदि <math>a \geq 1{:}</math>
 :: <math>x_{t+1} = x',</math>
 : अन्य:
@@ Line 118: / Line 117: @@
   \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>N</math> प्रतिरूपों की विंडो में स्वीकार किया जाता है। इसकी वांछित स्वीकृति दर लक्ष्य वितरण पर निर्भर करती है, चूंकि यह सैद्धांतिक रूप से दिखाया गया है कि इस एक-आयामी गाऊसी वितरण के लिए आदर्श स्वीकृति दर लगभग 50% है, जो <math>N</math>-आयामी गाऊसी लक्ष्य वितरण के लिए घटकर लगभग 23% हो जाती है। <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>P(x)</math>, जिससे सीधा प्रतिरूप लेना कठिन है, अर्थात <math>g(x' \mid x_t) \approx P(x')</math>.
+यदि <math>\sigma^2</math> बहुत छोटा होता है, तब इसमें श्रृंखला धीरे-धीरे मिश्रित होती हैं (अर्थात, स्वीकृति दर अधिक होगी, किन्तु क्रमिक प्रतिरूप धीरे-धीरे स्पेस के चारों ओर परिवर्तित होगी, और श्रृंखला केवल धीरे-धीरे <math>P(x)</math>) में परिवर्तित होती हैं)। दूसरी ओर, यदि <math>\sigma^2</math> बहुत बड़ा है, तब स्वीकृति दर बहुत कम होगी क्योंकि प्रस्तावों के बहुत कम संभावना घनत्व वाले क्षेत्रों में आने की संभावना होती है, इसलिए <math>a_1</math> बहुत छोटा होता हैं, और फिर से वह श्रृंखला बहुत धीरे-धीरे एकत्रित होते हैं। इसमें सामान्यतः प्रस्ताव वितरण को ट्यून किया जाता है जिससे एल्गोरिदम सभी प्रतिरूपों को 30% के क्रम पर स्वीकार कर सके - यह पूर्व पैराग्राफ में उल्लिखित सैद्धांतिक अनुमानों के अनुरूप होता हैं।
-यदि गाऊसी प्रस्ताव घनत्व <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>
-अगर <math>\sigma^2</math> बहुत छोटा है, श्रृंखला धीरे-धीरे मिश्रित होगी (यानी, स्वीकृति दर अधिक होगी, किन्तु क्रमिक प्रतिरूप धीरे-धीरे अंतरिक्ष में घूमेंगे, और श्रृंखला केवल धीरे-धीरे ही परिवर्तित होगी) <math>P(x)</math>). वहीं दूसरी ओर,
-अगर <math>\sigma^2</math> बहुत बड़ा है, स्वीकृति दर बहुत कम होगी क्योंकि प्रस्तावों के बहुत कम संभावना घनत्व वाले क्षेत्रों में आने की संभावना है, इसलिए <math>a_1</math> बहुत छोटा होगा, और फिर से श्रृंखला बहुत धीरे-धीरे एकत्रित होगी। सामान्यतः प्रस्ताव वितरण को ट्यून किया जाता है ताकि ऐल्गरिदम सभी प्रतिरूप के 30% के क्रम पर स्वीकार कर सके - पिछले पैराग्राफ में उल्लिखित सैद्धांतिक अनुमानों के अनुरूप।
-[[Image:3dRosenbrock.png|thumb|मेट्रोपोलिस-हेस्टिंग्स एल्गोरिथम का उपयोग करके 3डी [[रोसेनब्रॉक फ़ंक्शन|रोसेनब्रॉक]] फ़ंक्शन पर चलने वाली तीन [[मार्कोव श्रृंखला]]ओं का परिणाम। ऐल्गरिदम उन क्षेत्रों से प्रतिरूप लेता है जहां पश्चवर्ती संभावना अधिक होती है, और इन क्षेत्रों में श्रृंखलाएं मिश्रित होने लगती हैं। अधिकतम की अनुमानित स्थिति पर प्रकाश डाला गया है। लाल बिंदु वे हैं जो बर्न-इन प्रक्रिया के बाद बने रहते हैं। पूर्व वालों को हटा दिया गया है.]]
+[[Image:3dRosenbrock.png|thumb|मेट्रोपोलिस-हेस्टिंग्स एल्गोरिथम का उपयोग करके 3डी [[रोसेनब्रॉक फ़ंक्शन|रोसेनब्रॉक]] फलन पर चलने वाली तीन [[मार्कोव श्रृंखला|मार्कोव श्रृंखलाओं]] का परिणाम हैं। ऐल्गरिदम उन क्षेत्रों से प्रतिरूप लेता है जहां पश्चवर्ती संभावना अधिक होती है, और इन क्षेत्रों में श्रृंखलाएं मिश्रित होने लगती हैं। अधिकतम की अनुमानित स्थिति पर प्रकाश डाला गया है। लाल बिंदु वह हैं जो बर्न-इन प्रक्रिया के पश्चात् बने रहते हैं।और इसमें पूर्व वालों को हटा दिया जाता है.]]
 == बायेसियन अनुमान ==
-{{main article|Bayesian Inference}}
+{{main article|बायेसियन अनुमान}}
-[[File:Flowchart-of-Metropolis-Hastings-M-H-algorithm-for-the-parameter-estimation-using-the.png|thumb|मार्कोव चेन मोंटे कार्लो (एमसीएमसी) दृष्टिकोण का उपयोग करके पैरामीटर अनुमान के लिए मेट्रोपोलिस-हेस्टिंग्स (एम-एच) ऐल्गरिदम का फ़्लोचार्ट।]]एमसीएमसी का उपयोग सांख्यिकीय मॉडल के पिछले वितरण से प्रतिरूप लेने के लिए किया जा सकता है।
+[[File:Flowchart-of-Metropolis-Hastings-M-H-algorithm-for-the-parameter-estimation-using-the.png|thumb|मार्कोव चेन मोंटे कार्लो (एमसीएमसी) दृष्टिकोण का उपयोग करके पैरामीटर अनुमान के लिए मेट्रोपोलिस-हेस्टिंग्स (एम-एच) ऐल्गरिदम का फ़्लोचार्ट।]]एमसीएमसी का उपयोग सांख्यिकीय मॉडल के पूर्व वितरण से प्रतिरूप लेने के लिए किया जा सकता है।
-स्वीकृति की संभावना इस प्रकार दी गई है:
+स्वीकृति की संभावना इस प्रकार दी गई है:<math>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),</math> जहाँ <math>\mathcal{L}</math> [[संभावना]] है, <math>P(\theta)</math> पूर्व संभाव्यता घनत्व और <math>Q</math> (सशर्त) प्रस्ताव संभावना होती हैं।
-<math>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),</math>
-कहाँ <math>\mathcal{L}</math> [[संभावना]] है, <math>P(\theta)</math> पूर्व संभाव्यता घनत्व और <math>Q</math> (सशर्त) प्रस्ताव संभावना।
 ==यह भी देखें==
@@ Line 143: / Line 137: @@
 * [[माध्य-क्षेत्र कण विधियाँ]]
 * [[मेट्रोपोलिस-समायोजित लैंग्विन एल्गोरिदम|मेट्रोपोलिस-समायोजित लैंग्विन ऐल्गरिदम]]
-* [[महानगर प्रकाश परिवहन]]
+* [[महानगर प्रकाश परिवहन|मेट्रोपोलिस लाइट ट्रांसपोर्ट]]
-* [[ बहु-प्रयास महानगर ]]
+* [[ बहु-प्रयास महानगर | मल्टीपल-ट्राई मेट्रोपोलिस]]
-* [[समानांतर तड़का]]
+* [[समानांतर तड़का|समानांतर टेम्परिंग]]
 * पूर्वनिर्धारित क्रैंक-निकोलसन ऐल्गरिदम
-* [[कण फिल्टर]]
+* [[कण फिल्टर|अनुक्रमिक मोंटे कार्लो]]
-* [[तैयार किए हुयी धातु पे पानी चढाने की कला]]
+* [[तैयार किए हुयी धातु पे पानी चढाने की कला|सिम्युलेटेड अनीलिंग]]
 ==संदर्भ==
@@ Line 181: / Line 175: @@
 [[Category: Machine Translated Page]]
 [[Category:Created On 28/11/2023]]
+[[Category:Vigyan Ready]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 10:22, 11 December 2023

Contents

इतिहास

अंतर्ज्ञान

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

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

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

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

यह भी देखें

संदर्भ

टिप्पणियाँ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 10:22, 11 December 2023

इतिहास

अंतर्ज्ञान

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

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

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

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

यह भी देखें

संदर्भ

टिप्पणियाँ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories