🏥 👵🏻 🆚 मार्कोव श्रृंखला के साथ मोंटे कार्लो विधियों का सहज उपयोग ⏹️ 🐺 ♨️

क्या यह आसान है? मैंने कोशिश की

डॉल्किक, नेटोलॉजी में एक लेक्चरर, डेटा डेवलपमेंट और काम के निदेशक एलेक्सी कुज़मिन ने राहुल अग्रवाल द्वारा एक लेख का अनुवाद किया कि मोंटे कार्लो कैसे मार्कोव श्रृंखला के साथ काम करते हैं ताकि एक बड़े राज्य स्थान के साथ समस्याओं को हल किया जा सके।

डाटा साइंस से जुड़े हर किसी ने कभी भी मार्कोव चेन (MCMC) के साथ मोंटे कार्लो के तरीकों के बारे में सुना है। कभी-कभी बायसी के आंकड़ों का अध्ययन करते समय विषय को छुआ जाता है, कभी-कभी पैगंबर जैसे उपकरणों के साथ काम करते समय।

लेकिन एमसीएमसी को समझना मुश्किल है। जब भी मैं इन तरीकों के बारे में पढ़ता हूं, मैंने देखा कि एमसीएमसी का सार गणितीय शोर की गहरी परतों में छिपा है, और इस शोर के पीछे बनाना मुश्किल है। मुझे इस अवधारणा को समझने में कई घंटे बिताने पड़े।

इस लेख में, मोंटे कार्लो विधियों को मार्कोव श्रृंखलाओं के साथ समझाने का प्रयास उपलब्ध है, जिससे यह स्पष्ट हो जाता है कि उनका उपयोग किस लिए किया जाता है। मैं अपनी अगली पोस्ट में इन तरीकों का उपयोग करने के लिए कुछ और तरीकों पर ध्यान केंद्रित करूँगा।

तो चलिए शुरू करते हैं। MCMC में दो पद होते हैं: मोंटे कार्लो और मार्कोव श्रृंखला। आइए उनमें से प्रत्येक के बारे में बात करें।

मोंटे कार्लो

सरल शब्दों में , मोंटे कार्लो विधियों को सरल सिमुलेशन के रूप में परिभाषित किया जा सकता है।

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

मार्कोव चेन

चूंकि एमसीएमसी में दो भाग होते हैं, इसलिए आपको अभी भी यह समझने की जरूरत है कि मार्कोव चेन क्या हैं । लेकिन मार्कोव श्रृंखला पर आगे बढ़ने से पहले, चलो मार्कोव गुणों के बारे में थोड़ी बात करते हैं।

मान लीजिए कि एम-संभव राज्यों की एक प्रणाली है, और आप एक राज्य से दूसरे राज्य में जाते हैं। आप अभी तक कुछ भी भ्रमित न करें। ऐसी प्रणाली का एक विशिष्ट उदाहरण मौसम है, जो गर्म से ठंडे तक बदल जाता है। एक अन्य उदाहरण शेयर बाजार है, जो एक मंदी से तेजी और स्थिर स्थिति में कूद रहा है।

मार्कोव संपत्ति बताती है कि एक निश्चित प्रक्रिया के लिए, जो समय में किसी विशेष क्षण में राज्य X _n पर है, प्रायिकता X _{n + 1} = k (जहाँ k, M-राज्यों में से एक है जहाँ प्रक्रिया जा सकती है) पर निर्भर करता है फिलहाल यह क्या हालत है। और इस बारे में नहीं कि यह अपनी वर्तमान स्थिति तक कैसे पहुंचा।
गणितीय शब्दों में, हम इसे निम्नलिखित सूत्र के रूप में लिख सकते हैं:

स्पष्टता के लिए, आपको उन परिस्थितियों के अनुक्रम की परवाह नहीं है जो बाजार में तेजी लाने के लिए ले गए थे। अगले राज्य "मंदी" होने की संभावना केवल इस तथ्य से निर्धारित होती है कि बाजार वर्तमान में "तेजी" स्थिति में है। यह व्यवहार में भी समझ में आता है।

मार्कोव संपत्ति के साथ एक प्रक्रिया को मार्कोव प्रक्रिया कहा जाता है। मार्कोव श्रृंखला क्यों महत्वपूर्ण है? इसके स्थिर वितरण के कारण।

स्थिर वितरण क्या है?

मैं नीचे दिए गए उदाहरण के लिए गणना करके स्थिर वितरण की व्याख्या करने का प्रयास करूंगा। मान लीजिए कि आपके पास शेयर बाजार के लिए मार्कोव प्रक्रिया है, जैसा कि नीचे दिखाया गया है।

आपके पास एक संक्रमण संभावना मैट्रिक्स है जो राज्य X _i से X _{j में} संक्रमण की संभावना निर्धारित करता है।

संक्रमण संभावना मैट्रिक्स, क्यू

क्षणिक संभावना मैट्रिक्स क्यू में, संभावना है कि "बैल" की वर्तमान स्थिति को देखते हुए अगला राज्य "बैल" होगा; = 0.9; यदि वर्तमान स्थिति "बैल" = 0.075 है तो अगली स्थिति "मंदी" होगी। और इसी तरह।

ठीक है, चलो कुछ विशेष राज्य से शुरू करते हैं। हमारा राज्य वेक्टर [बैल, भालू, ठहराव] द्वारा निर्धारित किया जाएगा। यदि हम एक "मंदी" स्थिति से शुरू करते हैं, तो वेक्टर इस तरह होगा: [0,1,0]। हम संक्रमण की संभावना मैट्रिक्स द्वारा वर्तमान राज्य वेक्टर को गुणा करके अगले राज्य के लिए संभाव्यता वितरण की गणना कर सकते हैं।

ध्यान दें कि सम्भावनाएँ 1 तक हैं।

राज्यों का निम्नलिखित वितरण सूत्र द्वारा पाया जा सकता है:

और इसी तरह। अंत में, आप एक स्थिर स्थिति में पहुंच जाएंगे जिसमें राज्य स्थिर हो जाता है:

ऊपर वर्णित संक्रमण संभावना मैट्रिक्स क्यू के लिए, स्थिर वितरण एस है

आप निम्न कोड के साथ एक स्थिर वितरण प्राप्त कर सकते हैं:

Q = np.matrix([[0.9,0.075,0.025],[0.15,0.8,0.05],[0.25,0.25,0.5]]) init_s = np.matrix([[0, 1 , 0]]) epsilon =1 while epsilon>10e-9:    next_s = np.dot(init_s,Q)    epsilon = np.sqrt(np.sum(np.square(next_s - init_s)))    init_s = next_s print(init_s) ------------------------------------------------------------------ matrix([[0.62499998, 0.31250002, 0.0625  ]])

आप किसी अन्य राज्य से भी शुरू कर सकते हैं - एक ही स्थिर वितरण प्राप्त करें। यदि आप यह सुनिश्चित करना चाहते हैं तो कोड में प्रारंभिक स्थिति को बदलें।

अब हम इस प्रश्न का उत्तर दे सकते हैं कि स्थिर वितरण इतना महत्वपूर्ण क्यों है।

स्थिर वितरण महत्वपूर्ण है क्योंकि इसका उपयोग किसी निश्चित अवस्था में यादृच्छिक अवस्था में होने की संभावना को निर्धारित करने के लिए किया जा सकता है।

हमारे उदाहरण के लिए, हम कह सकते हैं कि 62.5% मामलों में बाजार "तेजी" स्थिति में, 31.25% "मंदी" की स्थिति में और 6.25% ठहराव में होगा।

सहज रूप से, आप इसे श्रृंखला के चारों ओर एक यादृच्छिक भटकने के रूप में देख सकते हैं।

बेतरतीब चलना

आप एक निश्चित बिंदु पर हैं और वर्तमान स्थिति को ध्यान में रखते हुए, अगले राज्य की संभावना वितरण को देखते हुए, अगले राज्य का चयन करें। हम इन नोड्स की संभावनाओं के आधार पर कुछ नोड्स को दूसरों की तुलना में अधिक बार देख सकते हैं।

इस तरह से Google ने इंटरनेट की भोर में खोज समस्या को हल किया। समस्या उनके महत्व के आधार पर, पृष्ठों को छांट रही थी। Google ने Pagerank एल्गोरिथ्म का उपयोग करके इस समस्या को हल किया। Google पेजरैंक एल्गोरिथ्म को राज्य को एक पृष्ठ के रूप में और स्थिर वितरण में एक पृष्ठ की संभावना को इसके सापेक्ष महत्व के रूप में माना जाना चाहिए।

अब हम सीधे MCMC तरीकों पर विचार करते हैं।

मार्को चेन (MCMC) के साथ मोंटे कार्लो तरीके क्या हैं

MCMC क्या है, इसका उत्तर देने से पहले, मुझे एक प्रश्न पूछना चाहिए। हम बीटा वितरण के बारे में जानते हैं। हम इसकी संभावना घनत्व फ़ंक्शन को जानते हैं। लेकिन क्या हम इस वितरण से एक नमूना ले सकते हैं? क्या आप ऐसा करने का तरीका लेकर आ सकते हैं?

सोचो ...

MCMC आपको किसी भी प्रायिकता वितरण से चुनने की अनुमति देता है। यह विशेष रूप से महत्वपूर्ण है जब आपको पीछे के वितरण से चयन करने की आवश्यकता होती है।

आंकड़ा बेयस प्रमेय को दर्शाता है।

उदाहरण के लिए, आपको पश्च वितरण से एक नमूना बनाने की आवश्यकता है। लेकिन क्या स्थिरांक स्थिर (प्रमाण) के साथ पीछे के घटक की गणना करना आसान है? ज्यादातर मामलों में, आप उन्हें संभावना के उत्पाद के रूप में पा सकते हैं और एक प्राथमिकता संभावना। लेकिन सामान्य करने वाली स्थिरांक की गणना करने के लिए (पी (डी)) काम नहीं करता है। क्यों? आइए एक नज़र डालें।

मान लीजिए एच केवल 3 मान लेता है:

p (D) = p (H = H1) .p (D | H = H1) + p (H = H2) .p (D। H = H2) + p (H = H3) .p (D | H =) H3)

इस मामले में, पी (डी) की गणना करना आसान है। लेकिन क्या होगा यदि एच का मूल्य निरंतर है? क्या यह आसानी से गणना करना संभव होगा, खासकर अगर एच ने अनंत मूल्यों पर लिया? ऐसा करने के लिए, एक जटिल अभिन्न हल करना होगा।

हम पोस्टीरियर डिस्ट्रीब्यूशन से रैंडम सेलेक्शन करना चाहते हैं, लेकिन साथ ही p (D) को एक कॉन्स्टेंट मानना चाहते हैं।

विकिपीडिया लिखते हैं :

मार्कोव श्रृंखलाओं के साथ मोंटे कार्लो विधियाँ मार्कोव श्रृंखला के निर्माण के आधार पर संभाव्यता वितरण से नमूने के लिए एल्गोरिदम का एक वर्ग है, जो एक स्थिर वितरण के रूप में वांछित है। चरणों की एक श्रृंखला के बाद श्रृंखला राज्य तब वांछित वितरण से चयन के रूप में उपयोग किया जाता है। नमूने की गुणवत्ता में सुधार कदमों की बढ़ती संख्या के साथ है।

आइए एक उदाहरण देखें। मान लें कि आपको बीटा वितरण से एक नमूना की आवश्यकता है। इसका घनत्व:

जहां C सामान्य स्थिर है। वास्तव में, यह α और this का कुछ कार्य है, लेकिन मैं यह बताना चाहता हूं कि बीटा वितरण से नमूने के लिए इसकी आवश्यकता नहीं है, इसलिए हम इसे निरंतर के रूप में लेंगे।

बीटा वितरण समस्या वास्तव में मुश्किल है, अगर व्यावहारिक रूप से अघुलनशील नहीं है। वास्तव में, आपको अधिक जटिल वितरण कार्यों के साथ काम करना पड़ सकता है, और कभी-कभी आपको सामान्यीकरण स्थिरांक नहीं पता होगा।

MCMC तरीके एल्गोरिदम प्रदान करके जीवन को आसान बनाते हैं जो एक मार्कोव श्रृंखला बना सकते हैं जिसमें एक स्थिर वितरण के रूप में बीटा वितरण होता है, जिसे देखते हुए हम एक समान वितरण (जो अपेक्षाकृत सरल है) से चुन सकते हैं।

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

इनमें से एक MCMC एल्गोरिदम मेट्रोपोलिस-हेस्टिंग्स एल्गोरिथम है।

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

अंतर्ज्ञान:

तो उद्देश्य क्या है?

सहज रूप से, हम सतह के कुछ टुकड़े (हमारी मार्कोव श्रृंखला) को इस तरह से चलना चाहते हैं कि हम प्रत्येक स्थान पर जितना समय बिताते हैं, उस स्थान पर सतह की ऊंचाई के लिए आनुपातिक होता है (वांछित संभावना घनत्व जिसमें से हम एक चयन करना चाहते हैं)।

उदाहरण के लिए, हम पड़ोसी 50 मीटर की पहाड़ी की तुलना में 100 मीटर ऊंची पहाड़ी पर दो बार बिताना चाहेंगे। यह अच्छा है कि हम ऐसा कर सकते हैं, भले ही हम सतह पर बिंदुओं की निरपेक्ष ऊंचाइयों को नहीं जानते हैं: आपको सभी को जानना आवश्यक है। उदाहरण के लिए, यदि पहाड़ी A की चोटी पहाड़ी B के शीर्ष से दो गुना अधिक है, तो हम B की तुलना में A में दो गुना अधिक समय बिताना चाहेंगे।

नई जगहों और उनके गोद लेने के नियमों को प्रस्तावित करने के लिए अधिक जटिल योजनाएं हैं, लेकिन मुख्य विचार इस प्रकार है:

एक नया "सुझाया गया" स्थान चुनें।
पता करें कि वर्तमान स्थान की तुलना में यह स्थान कितना ऊंचा या नीचा है।
जगह में बने रहना या एक नई जगह पर जाना संभव स्थानों के साथ आनुपातिक अनुपात के साथ।

एमसीएमसी का उद्देश्य किसी भी बिंदु पर इसकी सही ऊंचाई जानने के लिए कुछ संभावना वितरण से चयन करना है (सी जानने की कोई आवश्यकता नहीं है)।
यदि "भटकने" की प्रक्रिया को सही ढंग से सेट किया गया है, तो आप यह सुनिश्चित कर सकते हैं कि यह आनुपातिकता (खर्च किए गए समय और वितरण की ऊंचाई के बीच) हासिल की है ।

एल्गोरिथ्म:

अब हम कार्य को और अधिक औपचारिक शब्दों में परिभाषित करते हैं। आज्ञा देना = (s1, s2, ..., sM) वांछित स्थिर वितरण हो। हम इस तरह के स्थिर वितरण के साथ एक मार्कोव श्रृंखला बनाना चाहते हैं। हम संक्रमण मैट्रिक्स पी के साथ एम-राज्यों के साथ एक मनमानी मार्कोव श्रृंखला से शुरू करते हैं, ताकि पीआई राज्य i से j तक संक्रमण की संभावना का प्रतिनिधित्व करता है।

सहज रूप से, हम जानते हैं कि मार्कोव श्रृंखला को कैसे घूमना है, लेकिन मार्कोव श्रृंखला में आवश्यक स्थिर वितरण नहीं है। इस श्रृंखला में कुछ स्थिर वितरण हैं (जिनकी हमें आवश्यकता नहीं है)। हमारा लक्ष्य मार्कोव श्रृंखला के चारों ओर घूमने के तरीके को बदलना है ताकि श्रृंखला में वांछित वितरण हो।

ऐसा करने के लिए:

एक यादृच्छिक प्रारंभिक अवस्था के साथ शुरू करें।
संक्रमण मैट्रिक्स पी की ith पंक्ति में संक्रमण संभावनाओं को देखकर बेतरतीब ढंग से एक नई ग्रहण स्थिति का चयन करें।
निर्णय संभावना नामक एक उपाय की गणना करें, जिसे इस प्रकार परिभाषित किया गया है: aij = min (sj.pji / si.pij, 1)।
अब एक सिक्के को उछालें, जो ईगल की सतह पर संभावना अईज के साथ भूमि है। यदि कोई ईगल गिरता है, तो प्रस्ताव स्वीकार करें, अर्थात्, अगले राज्य पर जाएं, अन्यथा, प्रस्ताव को अस्वीकार करें, अर्थात वर्तमान स्थिति में रहें।
कई बार दोहराएं।

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

बीटा डिस्ट्रीब्यूशन का नमूना लेने के लिए, आपको केवल संभावना घनत्व का उपयोग करने का निर्णय लेने की संभावना की खोज करना है। ऐसा करने के लिए, sj को si से विभाजित करें (अर्थात, स्थिर C को सामान्य करना रद्द कर दिया जाता है)।

बीटा चयन

अब हम बीटा वितरण से नमूने की समस्या की ओर मुड़ते हैं।

एक बीटा वितरण [0,1] पर एक निरंतर वितरण है और [0,1] पर अनंत मूल्य हो सकते हैं। मान लीजिए कि [0,1] पर अनंत राज्यों के साथ एक मनमानी मार्कोव श्रृंखला पी में एक संक्रमण मैट्रिक्स पी है जैसे कि मैट्रिक्स में pij = pji = सभी तत्व।

हमें मैट्रिक्स पी की आवश्यकता नहीं है, जैसा कि हम बाद में देखेंगे, लेकिन मैं चाहता हूं कि समस्या का विवरण उस एल्गोरिथ्म के जितना संभव हो उतना करीब हो जो हमने प्रस्तावित किया था।

(0,1) पर एक समान वितरण से प्राप्त एक यादृच्छिक प्रारंभिक अवस्था से शुरू करें।
संक्रमण मैट्रिक्स पी की ith पंक्ति में संक्रमण संभावनाओं को देखते हुए बेतरतीब ढंग से एक नई ग्रहण स्थिति का चयन करें। मान लीजिए कि हम ग्रहण किए गए राज्य के रूप में एक और राज्य यूनिफ (0,1) चुनते हैं।
माप की गणना करें, जिसे निर्णय लेने की संभावना कहा जाता है:

जो सरल है:

चूंकि पीजी = पीज, और कहां

अब एक सिक्का उछालें। संभावना के साथ aij ईगल गिर जाएगा। यदि एक बाज गिरता है, तो आपको प्रस्ताव को स्वीकार करना चाहिए, अर्थात अगले राज्य में जाना चाहिए। अन्यथा, यह प्रस्ताव को अस्वीकार करने के लायक है, अर्थात, उसी स्थिति में शेष है।
कई बार परीक्षा दोहराएं।

कोड:

यह सिद्धांत से अभ्यास की ओर बढ़ने का समय है। हम अपने बीटा सैंपल को पायथन में लिखेंगे।

 impo rt rand om # Lets define our Beta Function to generate s for any particular state. We don't care for the normalizing constant here. def beta_s(w,a,b): return w**(a-1)*(1-w)**(b-1) # This Function returns True if the coin with probability P of heads comes heads when flipped. def random_coin(p): unif = random.uniform(0,1) if unif>=p: return False else: return True # This Function runs the MCMC chain for Beta Distribution. def beta_mcmc(N_hops,a,b): states = [] cur = random.uniform(0,1) for i in range(0,N_hops): states.append(cur) next = random.uniform(0,1) ap = min(beta_s(next,a,b)/beta_s(cur,a,b),1) # Calculate the acceptance probability if random_coin(ap): cur = next return states[-1000:] # Returns the last 100 states of the chain

वास्तविक बीटा वितरण के साथ परिणामों की तुलना करें।

 impo rt num py as np import pylab as pl import scipy.special as ss %matplotlib inline pl.rcParams['figure.figsize'] = (17.0, 4.0) # Actual Beta PDF. def beta(a, b, i): e1 = ss.gamma(a + b) e2 = ss.gamma(a) e3 = ss.gamma(b) e4 = i ** (a - 1) e5 = (1 - i) ** (b - 1) return (e1/(e2*e3)) * e4 * e5 # Create a function to plot Actual Beta PDF with the Beta Sampled from MCMC Chain. def plot_beta(a, b): Ly = [] Lx = [] i_list = np.mgrid[0:1:100j] for i in i_list: Lx.append(i) Ly.append(beta(a, b, i)) pl.plot(Lx, Ly, label="Real Distribution: a="+str(a)+", b="+str(b)) pl.hist(beta_mcmc(100000,a,b),normed=True,bins =25, histtype='step',label="Simulated_MCMC: a="+str(a)+", b="+str(b)) pl.legend() pl.show() plot_beta(0.1, 0.1) plot_beta(1, 1) plot_beta(2, 3)

जैसा कि आप देख सकते हैं, मान बीटा वितरण के समान हैं। इस प्रकार, MCMC नेटवर्क एक स्थिर स्थिति में पहुंच गया है

उपरोक्त कोड में, हमने एक बीटा सैंपलर बनाया है, लेकिन वही अवधारणा किसी अन्य वितरण पर लागू होती है जिससे हम एक चयन करना चाहते हैं।

निष्कर्ष

यह एक महान पद था। बधाई हो अगर आप इसे अंत तक पढ़ते हैं।

संक्षेप में, एमसीएमसी तरीके जटिल हो सकते हैं, लेकिन वे हमें बहुत लचीलापन प्रदान करते हैं। आप एमसीएमसी के माध्यम से चयन का उपयोग करके किसी भी वितरण फ़ंक्शन से चयन कर सकते हैं। आमतौर पर, इन विधियों का उपयोग पश्च वितरण से नमूना करने के लिए किया जाता है।

आप एक बड़े राज्य स्थान के साथ समस्याओं को हल करने के लिए MCMC का उपयोग कर सकते हैं। उदाहरण के लिए, बैकपैक समस्या में या डिक्रिप्शन के लिए। मैं आपको अगले पोस्ट में और अधिक दिलचस्प उदाहरण प्रदान करने का प्रयास करूंगा। देखते रहो।

संपादकों से

डेटा के साथ काम करने के लिए पायथन कोर्स
ऑनलाइन मशीन लर्निंग कोर्स
ऑनलाइन पाठ्यक्रम " खरोंच से बड़े आंकड़े "

मार्कोव श्रृंखला के साथ मोंटे कार्लो विधियों का सहज उपयोग