मार्कोव चेन मोंटे कार्लो

मार्कोव चेन मोंटे कार्लो एक जटिल लक्ष्य वितरण (target distribution) से नमूने लेता है, जिसके लिए एक मार्कोव चेन का अनुकरण किया जाता है जिसे उस वितरण को अपनी अद्वितीय स्थिर नियम (unique stationary law) के रूप में रखने के लिए डिज़ाइन किया गया है।

Definition

मार्कोव चेन मोंटे कार्लो एल्गोरिदम का एक परिवार है जो एक लक्ष्य संभाव्यता वितरण (target probability distribution) के तहत अपेक्षाओं (expectations) का अनुमान लगाता है, जिसके लिए एक एर्गोडिक मार्कोव चेन (ergodic Markov chain) को चलाया जाता है जिसका स्थिर वितरण लक्ष्य होता है और चेन के पथ पर एक फ़ंक्शन का औसत निकाला जाता है।

Scope

यह विषय एक निर्धारित स्थिर वितरण के साथ संक्रमण कर्नेल (transition kernels) के डिजाइन, मेट्रोपोलिस-हेस्टिंग्स एल्गोरिथम और उसके स्वीकृति नियम (acceptance rule), सशर्त अपडेट के लिए गिब्स सैंपलर (Gibbs sampler), अभिसरण निदान (convergence diagnostics) और बर्न-इन (burn-in), अनुमानक विचरण (estimator variance) पर ऑटोकोरिलेशन (autocorrelation) के प्रभाव, और मिश्रण समय (mixing times) तथा सैंपलिंग की कम्प्यूटेशनल लागत के बीच के संबंध को शामिल करता है।

Core questions

• वांछित स्थिर वितरण प्राप्त करने के लिए मार्कोव चेन का निर्माण कैसे किया जाता है?
• मेट्रोपोलिस-हेस्टिंग्स स्वीकृति नियम सही स्थिर नियम क्यों उत्पन्न करता है?
• गिब्स सैंपलर सशर्त वितरणों का कैसे उपयोग करता है?
• चेन को कितने समय तक चलाना चाहिए ताकि उसके नमूने प्रयोग करने योग्य हों, और इसका मूल्यांकन कैसे किया जाता है?

Key theories

मेट्रोपोलिस-हेस्टिंग्स निर्माण

एक मनमाने कर्नेल से चालों का प्रस्ताव करना और लक्ष्य घनत्व अनुपात (target density ratio) से निर्मित संभाव्यता के साथ उन्हें स्वीकार करना एक प्रतिवर्ती चेन (reversible chain) उत्पन्न करता है जिसका स्थिर वितरण बिल्कुल लक्ष्य होता है, जिसके लिए केवल एक सामान्यीकरण स्थिरांक (normalising constant) तक लक्ष्य की आवश्यकता होती है।

एर्गोडिक औसत और मोंटे कार्लो अनुमान

क्योंकि चेन अपने स्थिर नियम के रूप में लक्ष्य के साथ एर्गोडिक है, चेन के साथ एक फ़ंक्शन के समय औसत लगभग निश्चित रूप से लक्ष्य अपेक्षा में परिवर्तित होते हैं, जो नमूने के रूप में सिम्युलेटेड पथों के उपयोग को उचित ठहराता है।

Clinical relevance

मार्कोव चेन मोंटे कार्लो आधुनिक बायेसियन सांख्यिकी, सांख्यिकीय भौतिकी और मशीन लर्निंग का मुख्य आधार है, जो उच्च-आयामी पश्च वितरण (high-dimensional posterior distributions), विभाजन कार्यों (partition functions) और ऊर्जा परिदृश्यों (energy landscapes) पर अनुमान लगाने में सक्षम बनाता है जिन्हें विश्लेषणात्मक रूप से एकीकृत नहीं किया जा सकता है; इसकी विश्वसनीयता अंतर्निहित चेन के पर्याप्त तेजी से मिश्रण पर निर्भर करती है।

History

स्वीकृति-अस्वीकृति चेन (acceptance-rejection chain) की उत्पत्ति 1953 के मेट्रोपोलिस एल्गोरिथम में सांख्यिकीय भौतिकी के लिए हुई थी, इसे 1970 में हेस्टिंग्स द्वारा सामान्यीकृत किया गया था, और 1984 में गेमन और गेमन के गिब्स सैंपलर और 1990 के आसपास गेल्फैंड और स्मिथ के प्रभावशाली बायेसियन अनुप्रयोगों के माध्यम से सांख्यिकी के लिए इसे फिर से तैयार किया गया, जिसने कम्प्यूटेशनल बायेसियन क्रांति की शुरुआत की।

Key figures

• Nicholas Metropolis
• W. Keith Hastings
• Stuart Geman
• Donald Geman

Seminal works

• robertCasella2004
• hastings1970

Frequently asked questions

नमूने लेने के लिए मार्कोव चेन का उपयोग क्यों करें?

उच्च-आयामी या असामान्यीकृत लक्ष्य वितरणों के लिए, प्रत्यक्ष नमूनाकरण अव्यावहारिक है; एक मार्कोव चेन जो लक्ष्य में परिवर्तित होती है, वह संतुलन तक पहुंचने के बाद आपको निर्भर लेकिन सही ढंग से वितरित नमूने उत्पन्न करने देती है।

बर्न-इन क्या है?

यह चेन का प्रारंभिक भाग है जिसे छोड़ दिया जाता है क्योंकि चेन अभी तक अपने स्थिर वितरण में परिवर्तित नहीं हुई है, इसलिए वे शुरुआती अवस्थाएँ अनुमानों को पक्षपाती कर सकती हैं।