Python’da Markov Zincirleri: Başlangıç Eğitimi

Bir Markov zinciri, genellikle belirli olasılıksal kurallara göre bir durumdan diğerine geçen, rassal değişkenler koleksiyonu olarak tanımlanan matematiksel bir sistemdir. Bu geçiş kümesi, herhangi bir belirli duruma geçiş olasılığının yalnızca mevcut duruma ve geçen zamana bağlı olduğunu, ondan önce gelen durumların dizisine bağlı olmadığını belirten Markov Özelliğini sağlar. Markov süreçlerinin bu benzersiz özelliği onları hafızasız kılar.

Python ile daha fazla istatistik konusunu ele almak ister misiniz? DataCamp’in Statistical Thinking in Python kursuna göz atın!

Hadi geçiş yapalım...

Neden Markov Zincirleri?

Markov Zincirleri matematikte yaygın olarak kullanılır. Ekonomi, oyun teorisi, iletişim teorisi, genetik ve finansta geniş ölçüde uygulanırlar. Özellikle Bayesçi istatistik ve bilgi kuramsal bağlamlarda sıkça karşımıza çıkarlar. Gerçek dünya problemlerinde ise motorlu araçlardaki hız sabitleme sistemlerini, bir havaalanına gelen müşteri kuyruklarını, döviz kurlarını vb. incelemek için çözümler öne sürmede kullanılırlar. Aslen Google arama motoru için önerilen PageRank algoritması bir Markov sürecine dayanır. Reddit’in Subreddit Simulator’ı, Markov zincirlerini kullanarak rastgele gönderiler ve yorumlar üreten tamamen otomatik bir subreddit’tir, harika!

Markov Zinciri

Bir Markov zinciri, Markov özelliğine sahip bir rassal süreçtir. Rassal süreç (veya sıklıkla stokastik süreç) rassal değişkenler koleksiyonu olarak tanımlanan matematiksel bir nesnedir. Bir Markov zincirinin ya ayrık bir durum uzayı (rassal değişkenlerin alabileceği değerler kümesi) ya da ayrık bir indeks kümesi (çoğunlukla zamanı temsil eder) vardır — bu nedenle Markov zincirinin birçok varyasyonu mevcuttur. Genellikle “Markov zinciri” terimi, ayrık zaman kümesine sahip bir süreci, yani Ayrık Zamanlı Markov zincirini (DTMC) ifade etmek için kullanılır.

Ayrık Zamanlı Markov Zinciri

Ayrık zamanlı bir Markov zinciri, her adımda belirli bir durumda bulunan ve adımlar arasında durumu rastgele değişen bir sistemi içerir. Adımlar genellikle zaman anları olarak düşünülür (ancak fiziksel mesafe ya da başka herhangi bir ayrık ölçüm de olabilir). Ayrık zamanlı bir Markov zinciri, Markov özelliğine sahip X₁, X₂, X₃, ... şeklinde bir rassal değişkenler dizisidir; öyle ki bir sonraki duruma geçiş olasılığı yalnızca mevcut duruma bağlıdır, önceki durumlara değil. Bunu olasılık formülüyle ifade edersek:

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

Görüldüğü gibi, X_n+1’in olasılığı sadece ondan bir önceki X_n’e bağlıdır. Bu da, önceki durum bilgisi olmadan yalnızca mevcut durumun mevcut durumun olasılık dağılımını belirlemek için yeterli olduğu anlamına gelir; koşullu bağımsızlık kuralını sağlar (başka bir deyişle: bir sonraki durumu belirlemek için yalnızca mevcut durumu bilmeniz gerekir).

X_i’nin alabileceği değerler, zincirin durum uzayı olarak adlandırılan sayılabilir bir küme S oluşturur. Durum uzayı; harfler, sayılar, basketbol skorları veya hava durumları gibi herhangi bir şey olabilir. Zaman parametresi genellikle ayrık olsa da, ayrık zamanlı bir Markov zincirinin durum uzayı için yaygın kabul görmüş kısıtlar yoktur ve keyfi bir durum uzayındaki sürece atıfta bulunur. Ancak, Markov zincirlerinin birçok uygulaması sonlu veya sayılabilir sonsuz durum uzaylarını kullanır; çünkü bunların istatistiksel analizi daha doğrudur.

Model

Bir Markov zinciri, olasılıksal bir otomat kullanılarak temsil edilir (Kulağa karmaşık gelse de!). Sistemin durum değişikliklerine geçiş denir. Çeşitli durum değişiklikleriyle ilişkili olasılıklara geçiş olasılıkları denir. Olasılıksal bir otomat, belirli bir geçişin olasılığını geçiş fonksiyonuna dahil ederek bunu bir geçiş matrisine dönüştürür.

Bunu yönlendirilmiş grafiklerin bir dizisi olarak düşünebilirsiniz; burada n. grafiğin kenarları, n anındaki bir durumdan n+1 anındaki diğer durumlara gitme olasılıklarıyla etiketlenmiştir, Pr(X_n+1 = x | X_n = x_n). Bunu, X_n durumunun değerine bağlı olarak X_n+1 durumuna gitme olasılığı şeklinde okuyabilirsiniz. Aynı bilgi, n anından n+1 anına geçiş matrisi tarafından temsil edilir. Durum uzayındaki her durum bir kez satır olarak ve tekrar sütun olarak yer alır; matristaki her hücre, satırındaki durumdan sütunundaki duruma geçiş olasılığını verir.

Markov zincirinin N olası durumu varsa, matris N x N boyutunda olur; (I, J) girdisi I durumundan J durumuna geçiş olasılığıdır. Ayrıca geçiş matrisi stokastik bir matris olmalıdır; yani her satırdaki girişlerin toplamı tam olarak 1 olmalıdır. Neden? Çünkü her satır kendi olasılık dağılımını temsil eder.

Dolayısıyla model; bir durum uzayı, belirli geçişlerin olasılıklarını açıklayan bir geçiş matrisi ve başlangıç dağılımında verilen, durum uzayı genelinde bir başlangıç durumu ile karakterize edilir.

Epeyce kelime oldu, değil mi?

Kavramları anlamak için basit bir örneğe bakalım:

Cj üzgün olduğunda, ki bu çok sık olmaz: ya koşuya çıkar, bir kâse dondurmayı mideye indirir ya da uyur.

Geçmiş verilere göre, üzgün bir günü uykuda geçirirse, ertesi gün koşuya çıkma olasılığı %60, ertesi gün de yatakta kalma olasılığı %20 ve dondurmaya abanma olasılığı %20’dir.

Üzgünken koşuya çıkarsa, ertesi gün yine koşma olasılığı %60, dondurmaya yüklenme olasılığı %30 ve ertesi günü uykuda geçirme olasılığı sadece %10’dur.

Son olarak, üzgün bir günde dondurmaya yönelirse, ertesi gün de dondurmaya devam etme olasılığı yalnızca %10, koşuya çıkma olasılığı %70 ve ertesi günü uykuda geçirme olasılığı %20’dir.

Durum diyagramında gösterilen Markov Zinciri 3 olası duruma sahiptir: uyku, koşu, dondurma. Dolayısıyla geçiş matrisi 3 x 3 boyutunda olacaktır. Bir durumdan çıkan okların toplamının her zaman tam 1 olduğuna dikkat edin; benzer şekilde geçiş matrisindeki her satırdaki girişlerin toplamı tam 1 olmalıdır — bu bir olasılık dağılımını temsil eder. Geçiş matrisindeki hücreler, durum diyagramındaki okların yaptığı işi yapar.

Artık örneği gördüğünüze göre, bir Markov zinciriyle ilgili farklı kavramlara dair bir fikir edinmiş olmalısınız. Peki bu kuramı gerçek hayatta nasıl ve nerede kullanabilirsiniz?

Gördüğünüz örnekle artık şu gibi soruları yanıtlayabilirsiniz: “Uyku durumundan başlayarak, üzgün geçen 2 günün sonunda Cj’nin koşuyor olma (durum: koşu) olasılığı nedir?”

Şunu birlikte hesaplayalım: Uyku durumundan koşu durumuna geçmek için Cj ya ilk hamlede (veya günde) uyku durumunda kalıp ikinci hamlede koşuya geçmelidir (0,2 $\cdot$ 0,6); ya ilk gün koşuya geçip ikinci gün orada kalmalıdır (0,6 $\cdot$ 0,6) ya da ilk hamlede dondurma durumuna, ikinci hamlede koşuya geçebilir (0,2 $\cdot$ 0,7). Dolayısıyla olasılık: ((0,2 $\cdot$ 0,6) + (0,6 $\cdot$ 0,6) + (0,2 $\cdot$ 0,7)) = 0,62. Yani, başlangıç durumu uyku ise, Cj’nin iki gün üzgün olduktan sonra koşu durumuna geçme olasılığı %62’dir diyebiliriz.

Umarız bu, bir Markov Zinciri ağı kullanarak yanıtlayabileceğiniz çeşitli sorulara dair bir fikir vermiştir.

Ayrıca bu noktalar netleştiğinde, Markov zincirlerinin bazı önemli özelliklerini anlamak da kolaylaşır:

• İndirgenemezlik: Bir Markov zinciri, herhangi bir durumdan herhangi bir duruma gitmenin mümkün olması halinde indirgenemez olarak adlandırılır. Başka bir deyişle, herhangi iki durum arasında pozitif olasılığa sahip bir adım zinciri varsa Markov zinciri indirgenemezdir.
• Periyodiklik: Bir Markov zincirindeki bir durum, zincirin yalnızca 1’den büyük bir tamsayının katlarında o duruma geri dönebilmesi halinde periyodiktir. Dolayısıyla, ‘i’ durumunda başlayınca, zincir yalnızca periyot ‘k’nın katlarında ‘i’ye dönebilir ve k bu özelliği sağlayan en büyük tamsayıdır. ‘i’ durumu k = 1 ise aperiyodiktir, k > 1 ise periyodiktir.
• Geçicilik ve Tekrarlılık: ‘i’ durumu, ‘i’de başladığımız verildiğinde bir daha asla ‘i’ye dönmeme olasılığı sıfırdan büyükse geçici (transient) olarak adlandırılır. i durumu geçici değilse tekrarlayan (veya kalıcı) olarak adlandırılır. Bir tekrarlayan durum, sonlu sayıda adım içinde geri dönmesi bekleniyorsa pozitif tekrarlayan, aksi halde sıfır tekrarlayan (null recurrent) olarak bilinir.
• Ergodiklik: ‘i’ durumu, aperiyodik ve pozitif tekrarlayan ise ergodiktir. İndirgenemez bir Markov zincirindeki tüm durumlar ergodikse, zincir ergodiktir denir.
• Soğurucu Durum: i durumu, bu durumdan çıkmanın imkânsız olması halinde soğurucu olarak adlandırılır. Dolayısıyla ‘i’ durumu, i ≠ j için p_ii = 1 ve p_ij = 0 ise soğurucudur. Her durum bir soğurucu duruma ulaşabiliyorsa Markov zinciri soğurucu bir Markov zinciridir.

İpucu: Markov zincirlerinin görsel bir açıklamasını da görmek isterseniz, mutlaka bu sayfayı ziyaret edin.

Python’da Markov Zincirleri

Yukarıdaki örneği Python’da kodlamayı deneyelim. Gerçek hayatta muhtemelen Markov Zincirlerini çok daha verimli bir şekilde kodlayan bir kütüphane kullanacak olsanız da, aşağıdaki kod başlamak için yardımcı olacaktır...

Önce kullanacağınız bazı kütüphaneleri içe aktaralım.

import numpy as np
import random as rm

Şimdi durumları ve bunların olasılıklarını, yani geçiş matrisini tanımlayalım. Üç durumunuz olduğuna göre matris 3 X 3 olacaktır. Ayrıca geçiş yollarını da tanımlamanız gerekir; bunu da matrisler kullanarak yapabilirsiniz.

# 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]]

Olasılıkların toplamının her zaman 1 ettiğinden emin olun. Ve en azından kod yazarken hata mesajları bırakmak zarar vermez!

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!! ;)

Şimdi esas kısmı kodlayalım. Olası geçiş kümesinden rastgele örnek üretmek için numpy.random.choice kullanacaksınız. Argümanlarının çoğu kendini açıklar niteliktedir; ancak p olmayabilir. Bu, örnekleme kümesi için olasılık dağılımını girmenizi sağlayan isteğe bağlı bir argümandır; bu örnekte geçiş matrisi.

# 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

Başlangıç durumu Uyku iken, olası geçişlerden rastgele bir küme ve bunun olma olasılığını elde edersiniz. Programı, aynı başlangıç durumuyla birkaç yüz kez yineleyecek şekilde genişletirseniz, herhangi bir belirli durumda bitmenin beklenen olasılığını ve değerini görebilirsiniz. Bunu yapmak için activity_forecast fonksiyonunu yeniden yazıp buna yeni döngüler ekleyelim...

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%

Hedeflenen %62’ye nasıl yaklaştık?

Not Bu, aslında “büyük sayılar yasası”dır. Aynı gerçekleşme olasılığına sahip olayların frekanslarının, yeterince çok deneme olduğunda dengeleneceğini söyleyen bir olasılık ilkesidir. Başka bir deyişle, deney sayısı arttıkça, gerçekleşen sonuçların gerçek oranı, teorik veya beklenen sonuç oranına yakınsar.

Markov Zihniyeti

Markov Zincirlerine ilişkin bu eğitim burada sona eriyor. Markov Zincirleriyle tanıştınız ve bazı özelliklerini gördünüz. Basit Markov zincirleri, Python ile veri bilimine başlamak için gereken temel konulardandır. Python’da istatistiğe başlamak için daha fazla kaynağa ihtiyacınız varsa, mutlaka bu sayfaya göz atın.

İstatistik ve Python ile daha fazla pratik vaka çalışmasını keşfetmek ister misiniz? DataCamp’in Case Studies in Statistical Thinking veya Network Analysis in Python kurslarını inceleyin.