Python में मार्कोव चेन: शुरुआती ट्यूटोरियल

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

Python के साथ और अधिक सांख्यिकी विषयों से निपटना चाहते हैं? DataCamp का Statistical Thinking in Python कोर्स देखें!

चलिए ट्रांज़िशन करते हैं...

मार्कोव चेन क्यों?

मार्कोव चेन का गणित में व्यापक उपयोग है। इन्हें अर्थशास्त्र, गेम थ्योरी, संचार सिद्धांत, जनेटिक्स और वित्त में बड़े पैमाने पर इस्तेमाल किया जाता है। ये सांख्यिकी, विशेषकर बेयज़ियन सांख्यिकी और सूचना-सैद्धांतिक संदर्भों में व्यापक रूप से प्रकट होते हैं। वास्तविक दुनिया की समस्याओं में, इनका उपयोग मोटर वाहनों में क्रूज़ कंट्रोल सिस्टम, हवाई अड्डे पर आने वाली कतारें या ग्राहकों की लाइनें, मुद्राओं के विनिमय दर आदि का अध्ययन करने के समाधान प्रस्तावित करने में किया जाता है। PageRank नामक एल्गोरिदम, जिसे मूल रूप से इंटरनेट सर्च इंजन Google के लिए प्रस्तावित किया गया था, एक मार्कोव प्रक्रिया पर आधारित है। Reddit का Subreddit Simulator एक पूर्णतः स्वचालित सबरेडिट है जो मार्कोव चेन का उपयोग करके रैंडम सबमिशन और टिप्पणियाँ बनाता है—काफी मज़ेदार!

मार्कोव चेन

एक मार्कोव चेन, मार्कोव गुण वाली एक यादृच्छिक प्रक्रिया है। एक यादृच्छिक प्रक्रिया, जिसे प्रायः स्टोकेस्टिक प्रक्रिया कहा जाता है, यादृच्छिक चरों के संग्रह के रूप में परिभाषित एक गणितीय वस्तु है। एक मार्कोव चेन का या तो डिस्क्रीट स्टेट स्पेस (यादृच्छिक चरों के संभावित मानों का समुच्चय) होता है या डिस्क्रीट इंडेक्स सेट (जो अक्सर समय का प्रतिनिधित्व करता है)—इस तथ्य के कारण, मार्कोव चेन की कई विविधताएँ मौजूद हैं। आमतौर पर "मार्कोव चेन" शब्द उस प्रक्रिया के लिए सुरक्षित रखा जाता है जिसमें समय के सेट डिस्क्रीट होते हैं, यानी डिस्क्रीट टाइम मार्कोव चेन (DTMC)।

डिस्क्रीट टाइम मार्कोव चेन

एक डिस्क्रीट-टाइम मार्कोव चेन एक ऐसे सिस्टम को शामिल करती है जो प्रत्येक चरण पर किसी न किसी अवस्था में होता है, और अवस्थाएँ चरणों के बीच यादृच्छिक रूप से बदलती हैं। चरणों को अक्सर समय के क्षणों के रूप में सोचा जाता है (लेकिन आप भौतिक दूरी या किसी अन्य डिस्क्रीट माप का भी संदर्भ दे सकते हैं)। एक डिस्क्रीट टाइम मार्कोव चेन यादृच्छिक चरों का अनुक्रम X₁, X₂, X₃, ... है, जिसमें मार्कोव गुण होता है, ताकि अगली अवस्था में जाने की प्रायिकता केवल वर्तमान अवस्था पर निर्भर करे, न कि पिछली अवस्थाओं पर। इसे गणितीय प्रायिकता सूत्र में ऐसे लिखा जा सकता है:

Pr( X_n+1 = x | X₁ = x₁, X₂ = x₂, …, X_n = x_n) = Pr( X_n+1 = x | X_n = x_n)

जैसा कि आप देख सकते हैं, X_n+1 की प्रायिकता केवल उससे ठीक पहले वाली X_n की प्रायिकता पर निर्भर करती है। इसका मतलब है कि वर्तमान अवस्था के प्रायिकता वितरण को निर्धारित करने के लिए पिछली अवस्था का ज्ञान ही पर्याप्त है, जो सशर्त स्वतंत्रता के नियम को संतुष्ट करता है (या दूसरे शब्दों में: अगली अवस्था निर्धारित करने के लिए आपको केवल वर्तमान अवस्था जाननी होती है)।

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

मॉडल

एक मार्कोव चेन को प्रायिकतामूलक ऑटोमेटन का उपयोग करके दर्शाया जाता है (सुनने में ही जटिल लगता है!)। सिस्टम की अवस्था में होने वाले परिवर्तन को ट्रांज़िशन कहा जाता है। विभिन्न अवस्था परिवर्तनों से संबंधित प्रायिकताओं को ट्रांज़िशन प्रायिकताएँ कहा जाता है। एक प्रायिकतामूलक ऑटोमेटन, दिए गए ट्रांज़िशन की प्रायिकता को ट्रांज़िशन फ़ंक्शन में शामिल करता है, जिससे वह ट्रांज़िशन मैट्रिक्स में बदल जाता है।

आप इसे निर्देशित ग्राफ़ों के अनुक्रम के रूप में सोच सकते हैं, जहाँ ग्राफ़ n की धाराएँ उन प्रायिकताओं के साथ लेबल की जाती हैं जो समय n पर एक अवस्था से समय n+1 पर अन्य अवस्थाओं में जाने की संभावना बताती हैं, Pr(X_n+1 = x | X_n = x_n)। आप इसे ऐसे पढ़ सकते हैं: अवस्था X_n के मान के दिए जाने पर X_n+1 अवस्था में जाने की प्रायिकता। यही जानकारी समय n से n+1 तक की ट्रांज़िशन मैट्रिक्स द्वारा दर्शाई जाती है। स्टेट स्पेस की हर अवस्था एक बार पंक्ति के रूप में और फिर स्तंभ के रूप में शामिल होती है, और मैट्रिक्स की प्रत्येक कोष्ठक आपको पंक्ति की अवस्था से स्तंभ की अवस्था में ट्रांज़िशन की प्रायिकता बताती है।

यदि मार्कोव चेन में N संभावित अवस्थाएँ हैं, तो मैट्रिक्स N x N का होगा, इस प्रकार प्रविष्टि (I, J) अवस्था I से अवस्था J में ट्रांज़िशन की प्रायिकता होगी। साथ ही, ट्रांज़िशन मैट्रिक्स एक स्टोकेस्टिक मैट्रिक्स होना चाहिए, यानी प्रत्येक पंक्ति की प्रविष्टियों का योग ठीक 1 होना चाहिए। क्यों? क्योंकि प्रत्येक पंक्ति अपना स्वयं का प्रायिकता वितरण दर्शाती है।

तो, मॉडल की विशेषताएँ हैं: एक स्टेट स्पेस, एक ट्रांज़िशन मैट्रिक्स जो विशिष्ट ट्रांज़िशनों की प्रायिकताओं का वर्णन करती है, और पूरे स्टेट स्पेस पर एक प्रारंभिक अवस्था, जो आरंभिक वितरण में दी जाती है।

बहुत सारे शब्द हो गए, है न?

आइए अवधारणाओं को समझने के लिए एक सरल उदाहरण देखें:

जब Cj उदास होती है, जो कि बहुत सामान्य नहीं है: तो वह या तो दौड़ने जाती है, आइसक्रीम खा लेती है या झपकी लेती है।

ऐतिहासिक डेटा से, यदि उसने उदासी का दिन सोते हुए बिताया है, तो अगले दिन 60% संभावना है कि वह दौड़ने जाएगी, 20% कि वह अगले दिन भी बिस्तर में रहेगी और 20% संभावना कि वह आइसक्रीम खा लेगी।

जब वह उदास होती है और दौड़ने जाती है, तो 60% संभावना है कि वह अगले दिन भी दौड़ने जाएगी, 30% कि वह आइसक्रीम का आनंद लेगी और केवल 10% संभावना कि वह अगला दिन सोते हुए बिताएगी।

अंत में, जब वह उदास दिन में आइसक्रीम खाती है, तो मात्र 10% संभावना है कि वह अगले दिन भी आइसक्रीम खाएगी, 70% संभावना कि वह दौड़ने जाएगी और 20% संभावना कि वह अगला दिन सोते हुए बिताएगी।

स्टेट डायग्राम में दर्शाई गई मार्कोव चेन में 3 संभावित अवस्थाएँ हैं: sleep, run, icecream। इसलिए, ट्रांज़िशन मैट्रिक्स 3 x 3 की होगी। ध्यान दें, किसी अवस्था से निकलने वाले तीरों का योग हमेशा ठीक 1 होता है, उसी तरह ट्रांज़िशन मैट्रिक्स की प्रत्येक पंक्ति की प्रविष्टियों का योग भी ठीक 1 होना चाहिए—जो प्रायिकता वितरण का प्रतिनिधित्व करता है। ट्रांज़िशन मैट्रिक्स में कोशिकाएँ वही काम करती हैं जो स्टेट डायग्राम में तीर करते हैं।

अब जब आपने उदाहरण देख लिया है, तो इससे आपको मार्कोव चेन से संबंधित विभिन्न अवधारणाओं का अंदाज़ा हो जाना चाहिए। लेकिन, इन सिद्धांतों का वास्तविक जीवन में कैसे और कहाँ उपयोग करें?

जिस उदाहरण को आपने देखा, उसके साथ अब आप ऐसे प्रश्नों के उत्तर दे सकते हैं: "अवस्था: sleep से शुरू करके, उदासी के 2-दिन के अंत में Cj के दौड़ने (अवस्था: run) की क्या प्रायिकता है?"

चलिए इसे हल करते हैं: अवस्था: sleep से अवस्था: run में जाने के लिए, Cj या तो पहले चाल (या दिन) में अवस्था: sleep पर ही रहे, फिर अगली (दूसरी) चाल में अवस्था: run में जाए (0.2 $\cdot$ 0.6); या पहले दिन अवस्था: run में जाए और दूसरे दिन वहीं रहे (0.6 $\cdot$ 0.6) या वह पहली चाल में अवस्था: icecream में जाए और दूसरी चाल में अवस्था: run में (0.2 $\cdot$ 0.7)। तो प्रायिकता: ((0.2 $\cdot$ 0.6) + (0.6 $\cdot$ 0.6) + (0.2 $\cdot$ 0.7)) = 0.62। तो, अब हम कह सकते हैं कि 62% संभावना है कि Cj, यदि वह अवस्था: sleep से शुरू करती है, तो उदास रहने के दो दिनों के बाद अवस्था: run में चली जाएगी।

उम्मीद है, इससे आपको उन तरह-तरह के प्रश्नों का अंदाज़ा लगा होगा जिनका उत्तर आप एक मार्कोव चेन नेटवर्क का उपयोग करके दे सकते हैं।

साथ ही, यह स्पष्ट होने पर, मार्कोव चेन की कुछ महत्वपूर्ण विशेषताओं को समझना आसान हो जाता है:

• रिड्यूसिबिलिटी: एक मार्कोव चेन को अवघटनीय (irreducible) कहा जाता है यदि किसी भी अवस्था से किसी भी अवस्था तक पहुँचना संभव हो। दूसरे शब्दों में, यदि किसी भी दो अवस्थाओं के बीच सकारात्मक प्रायिकता वाली चरणों की एक चेन मौजूद है, तो मार्कोव चेन अवघटनीय है।
• पिरियोडिसिटी: मार्कोव चेन में कोई अवस्था आवधिक (periodic) है यदि चेन केवल किसी 1 से बड़े पूर्णांक के गुणकों पर ही उस अवस्था में लौट सकती है। इस प्रकार, अवस्था 'i' से शुरू करते हुए, चेन केवल अवधि 'k' के गुणकों पर ही 'i' में लौट सकती है, और k ऐसा सबसे बड़ा पूर्णांक है। अवस्था 'i' एपीरियोडिक (aperiodic) है यदि k = 1 और आवधिक है यदि k > 1।
• ट्रांज़िएंस और रिकरेंस: यदि हम अवस्था 'i' से शुरू करते हैं, और एक गैर-शून्य प्रायिकता है कि हम कभी भी 'i' पर वापस नहीं आएँगे, तो अवस्था 'i' को क्षणिक (transient) कहा जाता है। अवस्था i पुनरावर्ती (recurrent या persistent) है यदि वह क्षणिक नहीं है। किसी पुनरावर्ती अवस्था को सकारात्मक पुनरावर्ती (positive recurrent) कहा जाता है यदि अपेक्षित है कि वह सीमित संख्या के चरणों में वापस आ जाएगी, अन्यथा शून्य पुनरावर्ती (null recurrent) कहलाती है।
• एरगोडिसिटी: अवस्था 'i' को एरगोडिक कहा जाता है यदि वह एपीरियोडिक और सकारात्मक पुनरावर्ती है। यदि किसी अवघटनीय मार्कोव चेन की सभी अवस्थाएँ एरगोडिक हैं, तो चेन को एरगोडिक कहा जाता है।
• एब्जॉर्बिंग स्टेट: अवस्था i को एब्जॉर्बिंग कहा जाता है यदि इस अवस्था को छोड़ना असंभव हो। इसलिए, अवस्था 'i' एब्जॉर्बिंग है यदि p_ii = 1 और i ≠ j होने पर p_ij = 0। यदि हर अवस्था किसी एब्जॉर्बिंग अवस्था तक पहुँच सकती है, तो मार्कोव चेन एब्जॉर्बिंग मार्कोव चेन है।

टिप: यदि आप मार्कोव चेन का दृश्यात्मक स्पष्टीकरण भी देखना चाहते हैं, तो यह पेज ज़रूर देखें।

Python में मार्कोव चेन

आइए ऊपर वाले उदाहरण को Python में कोड करने की कोशिश करें। और यद्यपि वास्तविक जीवन में, आप संभवतः कोई ऐसी लाइब्रेरी इस्तेमाल करेंगे जो मार्कोव चेन को अधिक दक्षता से एन्कोड करती हो, यह कोड आपको शुरुआत करने में मदद करेगा...

सबसे पहले, कुछ लाइब्रेरियाँ इम्पोर्ट करते हैं जिनका आप उपयोग करेंगे।

import numpy as np
import random as rm

अब अवस्थाओं और उनकी प्रायिकताओं को परिभाषित करते हैं: ट्रांज़िशन मैट्रिक्स। याद रखें, आपके पास तीन अवस्थाएँ हैं इसलिए मैट्रिक्स 3 X 3 की होगी। साथ ही, आपको ट्रांज़िशन पाथ भी परिभाषित करने होंगे, आप यह भी मैट्रिक्स का उपयोग करके कर सकते हैं।

# The statespace
states = ["Sleep","Icecream","Run"]

# Possible sequences of events
transitionName = [["SS","SR","SI"],["RS","RR","RI"],["IS","IR","II"]]

# Probabilities matrix (transition matrix)
transitionMatrix = [[0.2,0.6,0.2],[0.1,0.6,0.3],[0.2,0.7,0.1]]

ओह, हमेशा सुनिश्चित करें कि प्रायिकताओं का योग 1 हो। और त्रुटि संदेश छोड़ देना बुरा नहीं है, कम से कम कोडिंग करते समय!

if sum(transitionMatrix[0])+sum(transitionMatrix[1])+sum(transitionMatrix[1]) != 3:
    print("Somewhere, something went wrong. Transition matrix, perhaps?")
else: print("All is gonna be okay, you should move on!! ;)")

All is gonna be okay, you should move on!! ;)

अब असली काम कोड करते हैं। आप numpy.random.choice का उपयोग संभावित ट्रांज़िशनों के सेट से एक यादृच्छिक सैंपल बनाने के लिए करेंगे। इसके अधिकांश आर्ग्युमेंट स्व-स्पष्ट हैं, लेकिन p शायद न हो। यह एक वैकल्पिक आर्ग्युमेंट है जो आपको सैंपलिंग सेट के लिए प्रायिकता वितरण दर्ज करने देता है, जो इस केस में ट्रांज़िशन मैट्रिक्स है।

# A function that implements the Markov model to forecast the state/mood.
def activity_forecast(days):
    # Choose the starting state
    activityToday = "Sleep"
    print("Start state: " + activityToday)
    # Shall store the sequence of states taken. So, this only has the starting state for now.
    activityList = [activityToday]
    i = 0
    # To calculate the probability of the activityList
    prob = 1
    while i != days:
        if activityToday == "Sleep":
            change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
            if change == "SS":
                prob = prob * 0.2
                activityList.append("Sleep")
                pass
            elif change == "SR":
                prob = prob * 0.6
                activityToday = "Run"
                activityList.append("Run")
            else:
                prob = prob * 0.2
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Run":
            change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
            if change == "RR":
                prob = prob * 0.5
                activityList.append("Run")
                pass
            elif change == "RS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.3
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Icecream":
            change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
            if change == "II":
                prob = prob * 0.1
                activityList.append("Icecream")
                pass
            elif change == "IS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.7
                activityToday = "Run"
                activityList.append("Run")
        i += 1  
    print("Possible states: " + str(activityList))
    print("End state after "+ str(days) + " days: " + activityToday)
    print("Probability of the possible sequence of states: " + str(prob))

# Function that forecasts the possible state for the next 2 days
activity_forecast(2)

Start state: Sleep
Possible states: ['Sleep', 'Sleep', 'Run']
End state after 2 days: Run
Probability of the possible sequence of states: 0.12

आपको संभावित ट्रांज़िशनों का एक यादृच्छिक सेट मिलता है, साथ ही उसके होने की प्रायिकता भी, जो state: Sleep से शुरू होती है। प्रोग्राम को आगे बढ़ाएँ और शायद उसी प्रारंभिक अवस्था के साथ इसे कुछ सौ बार दोहराएँ, तब आप किसी विशेष अवस्था पर समाप्त होने की अपेक्षित प्रायिकता को उसकी प्रायिकता सहित देख सकेंगे। आइए फ़ंक्शन activity_forecast को फिर से लिखें और यह करने के लिए नए लूप जोड़ें...

def activity_forecast(days):
    # Choose the starting state
    activityToday = "Sleep"
    activityList = [activityToday]
    i = 0
    prob = 1
    while i != days:
        if activityToday == "Sleep":
            change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
            if change == "SS":
                prob = prob * 0.2
                activityList.append("Sleep")
                pass
            elif change == "SR":
                prob = prob * 0.6
                activityToday = "Run"
                activityList.append("Run")
            else:
                prob = prob * 0.2
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Run":
            change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
            if change == "RR":
                prob = prob * 0.5
                activityList.append("Run")
                pass
            elif change == "RS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.3
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Icecream":
            change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
            if change == "II":
                prob = prob * 0.1
                activityList.append("Icecream")
                pass
            elif change == "IS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.7
                activityToday = "Run"
                activityList.append("Run")
        i += 1    
    return activityList

# To save every activityList
list_activity = []
count = 0

# `Range` starts from the first count up until but excluding the last count
for iterations in range(1,10000):
        list_activity.append(activity_forecast(2))

# Check out all the `activityList` we collected    
#print(list_activity)

# Iterate through the list to get a count of all activities ending in state:'Run'
for smaller_list in list_activity:
    if(smaller_list[2] == "Run"):
        count += 1

# Calculate the probability of starting from state:'Sleep' and ending at state:'Run'
percentage = (count/10000) * 100
print("The probability of starting at state:'Sleep' and ending at state:'Run'= " + str(percentage) + "%")

The probability of starting at state:'Sleep' and ending at state:'Run'= 62.419999999999995%

हम वांछित 62% के करीब कैसे पहुँचे?

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

मार्कोव स्टेट ऑफ माइंड

यह मार्कोव चेन पर ट्यूटोरियल यहीं समाप्त होता है। आपने मार्कोव चेन और उनकी कुछ विशेषताओं का परिचय देखा। सरल मार्कोव चेन, Python में डेटा साइंस शुरू करने के लिए आवश्यक बुनियादी विषयों में से एक हैं। यदि आप Python में सांख्यिकी शुरू करने के लिए और संसाधन चाहते हैं, तो यह पेज ज़रूर देखें।

क्या आप Python में सांख्यिकी के साथ और अधिक व्यावहारिक केस स्टडीज़ का अन्वेषण करना चाहते हैं? DataCamp के Case Studies in Statistical Thinking या Network Analysis in Python कोर्स देखें।