Rantai Markov di Python: Tutorial Pemula

Rantai Markov adalah sistem matematis yang biasanya didefinisikan sebagai kumpulan variabel acak yang berpindah dari satu keadaan ke keadaan lain sesuai dengan aturan probabilistik tertentu. Kumpulan transisi ini memenuhi Sifat Markov, yang menyatakan bahwa probabilitas berpindah ke keadaan tertentu hanya bergantung pada keadaan saat ini dan waktu yang berlalu, bukan pada urutan keadaan sebelumnya. Karakteristik unik proses Markov ini membuatnya tanpa ingatan.

Ingin membahas lebih banyak topik statistik dengan Python? Lihat kursus DataCamp Statistical Thinking in Python!

Mari bertransisi...

Mengapa Rantai Markov?

Rantai Markov banyak digunakan dalam matematika. Rantai ini dipakai luas dalam ekonomi, teori permainan, teori komunikasi, genetika, dan keuangan. Rantai Markov juga muncul secara luas dalam konteks statistik—khususnya statistik Bayesian—dan teori informasi. Dalam masalah dunia nyata, rantai Markov digunakan untuk mengajukan solusi guna mengkaji sistem cruise control pada kendaraan bermotor, antrian atau barisan pelanggan yang datang di bandara, nilai tukar mata uang, dan sebagainya. Algoritma yang dikenal sebagai PageRank, yang awalnya diusulkan untuk mesin pencari Google, didasarkan pada proses Markov. Subreddit Simulator milik Reddit adalah subreddit sepenuhnya otomatis yang menghasilkan kiriman dan komentar acak menggunakan rantai Markov—keren!

Rantai Markov

Rantai Markov adalah proses acak dengan sifat Markov. Proses acak atau sering disebut properti stokastik adalah objek matematika yang didefinisikan sebagai kumpulan variabel acak. Rantai Markov memiliki ruang keadaan diskrit (himpunan nilai yang mungkin dari variabel acak) atau himpunan indeks diskrit (sering merepresentasikan waktu)—dengan demikian, banyak variasi rantai Markov yang ada. Biasanya istilah "rantai Markov" digunakan untuk proses dengan himpunan waktu diskrit, yaitu Discrete Time Markov Chain (DTMC).

Discrete Time Markov Chain

Rantai Markov waktu-diskrit melibatkan sistem yang berada dalam suatu keadaan pada setiap langkah, dengan keadaan yang berubah secara acak antar langkah. Langkah-langkah ini sering dianggap sebagai momen waktu (tetapi Anda juga bisa merujuk ke jarak fisik atau pengukuran diskrit lainnya). Rantai Markov waktu-diskrit adalah urutan variabel acak X₁, X₂, X₃, ... dengan sifat Markov, sehingga probabilitas berpindah ke keadaan berikutnya hanya bergantung pada keadaan saat ini dan bukan pada keadaan-keadaan sebelumnya. Jika dituliskan dalam rumus probabilitas matematis:

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

Seperti yang Anda lihat, probabilitas X_n+1 hanya bergantung pada probabilitas X_n yang mendahuluinya. Artinya, pengetahuan tentang keadaan sebelumnya sudah cukup untuk menentukan distribusi probabilitas dari keadaan saat ini, memenuhi aturan independensi bersyarat (atau dengan kata lain: Anda hanya perlu mengetahui keadaan saat ini untuk menentukan keadaan berikutnya).

Nilai-nilai yang mungkin dari X_i membentuk himpunan terhitung S yang disebut ruang keadaan dari rantai. Ruang keadaan bisa apa saja: huruf, angka, skor bola basket, atau kondisi cuaca. Meskipun parameter waktu biasanya diskrit, ruang keadaan dari rantai Markov waktu-diskrit tidak memiliki pembatasan yang disepakati secara luas, dan lebih merujuk pada proses pada ruang keadaan sebarang. Namun, banyak aplikasi rantai Markov memakai ruang keadaan berhingga atau terhitung tak berhingga, karena analisis statistiknya lebih lugas.

Model

Rantai Markov direpresentasikan menggunakan automaton probabilistik (kedengarannya rumit, tapi tidak!). Perubahan keadaan sistem disebut transisi. Probabilitas yang terkait dengan berbagai perubahan keadaan disebut probabilitas transisi. Automaton probabilistik memasukkan probabilitas suatu transisi ke dalam fungsi transisi, menjadikannya matriks transisi.

Anda dapat memandangnya sebagai urutan graf berarah, di mana sisi-sisi graf ke-n diberi label dengan probabilitas berpindah dari satu keadaan pada waktu n ke keadaan lain pada waktu n+1, Pr(X_n+1 = x | X_n = x_n). Anda dapat membacanya sebagai: probabilitas menuju keadaan X_n+1 dengan nilai keadaan X_n. Informasi yang sama direpresentasikan oleh matriks transisi dari waktu n ke waktu n+1. Setiap keadaan dalam ruang keadaan dicantumkan sekali sebagai baris dan sekali lagi sebagai kolom, dan setiap sel dalam matriks memberi tahu Anda probabilitas transisi dari keadaan pada barisnya ke keadaan pada kolomnya.

Jika rantai Markov memiliki N keadaan yang mungkin, matriksnya akan berukuran N x N, sehingga entri (I, J) adalah probabilitas transisi dari keadaan I ke keadaan J. Selain itu, matriks transisi harus berupa matriks stokastik, yaitu matriks yang jumlah entri pada setiap barisnya harus tepat 1. Mengapa? Karena setiap baris merepresentasikan distribusi probabilitasnya sendiri.

Jadi, model dicirikan oleh ruang keadaan, matriks transisi yang menggambarkan probabilitas transisi tertentu, dan keadaan awal di seluruh ruang keadaan yang diberikan dalam distribusi awal.

Banyak sekali istilah, ya?

Mari kita lihat contoh sederhana untuk memahami konsep-konsepnya:

Saat Cj sedih, yang tidak terlalu sering terjadi: ia akan lari, melahap es krim, atau tidur siang.

Dari data historis, jika ia menghabiskan hari sedihnya dengan tidur. Hari berikutnya ada kemungkinan 60% ia akan lari, 20% ia akan tetap di tempat tidur keesokan harinya, dan 20% kemungkinan ia akan melahap es krim.

Saat ia sedih dan berlari, ada peluang 60% ia akan lari lagi keesokan harinya, 30% ia akan melahap es krim, dan hanya 10% kemungkinan ia akan tidur keesokan harinya.

Terakhir, saat ia memanjakan diri dengan es krim pada hari yang sedih, hanya ada 10% kemungkinan ia akan terus makan es krim keesokan harinya, 70% kemungkinan ia akan lari, dan 20% kemungkinan ia akan tidur keesokan harinya.

Rantai Markov yang ditampilkan dalam diagram keadaan memiliki 3 keadaan yang mungkin: tidur, lari, es krim. Jadi, matriks transisinya akan berukuran 3 x 3. Perhatikan, panah yang keluar dari suatu keadaan selalu berjumlah tepat 1, demikian pula entri dalam setiap baris pada matriks transisi harus berjumlah tepat 1—merepresentasikan distribusi probabilitas. Pada matriks transisi, sel-selnya melakukan pekerjaan yang sama seperti panah pada diagram keadaan.

Sekarang setelah Anda melihat contohnya, ini seharusnya memberi gambaran tentang berbagai konsep terkait rantai Markov. Namun, bagaimana dan di mana Anda dapat menggunakan teori ini dalam kehidupan nyata?

Dengan contoh yang telah Anda lihat, kini Anda dapat menjawab pertanyaan seperti: "Mulai dari keadaan: tidur, berapa probabilitas bahwa Cj akan berlari (keadaan: lari) pada akhir durasi 2 hari yang sedih?"

Mari kita kerjakan: Untuk berpindah dari keadaan: tidur ke keadaan: lari, Cj harus tetap pada keadaan: tidur pada langkah (atau hari) pertama, lalu berpindah ke keadaan: lari pada langkah (kedua) berikutnya (0,2 $\cdot$ 0,6); atau berpindah ke keadaan: lari pada hari pertama lalu tetap di sana pada hari kedua (0,6 $\cdot$ 0,6); atau ia dapat bertransisi ke keadaan: es krim pada langkah pertama lalu ke keadaan: lari pada langkah kedua (0,2 $\cdot$ 0,7). Jadi probabilitasnya: ((0,2 $\cdot$ 0,6) + (0,6 $\cdot$ 0,6) + (0,2 $\cdot$ 0,7)) = 0,62. Jadi, kini kita dapat mengatakan ada peluang 62% bahwa Cj akan berpindah ke keadaan: lari setelah dua hari sedih, jika ia memulai dari keadaan: tidur.

Mudah-mudahan, ini memberi Anda gambaran tentang berbagai pertanyaan yang dapat dijawab menggunakan jaringan Rantai Markov.

Dengan ini jelas, menjadi lebih mudah untuk memahami beberapa sifat penting dari rantai Markov:

• Redusibilitas: suatu rantai Markov dikatakan ireduksibel jika memungkinkan untuk mencapai keadaan apa pun dari keadaan apa pun. Dengan kata lain, rantai Markov ireduksibel jika terdapat rangkaian langkah antara dua keadaan mana pun yang memiliki probabilitas positif.
• Periodisitas: suatu keadaan dalam rantai Markov bersifat periodik jika rantai hanya dapat kembali ke keadaan tersebut pada kelipatan suatu bilangan bulat lebih besar dari 1. Jadi, mulai dari keadaan 'i', rantai hanya dapat kembali ke 'i' pada kelipatan periode 'k', dan k adalah bilangan bulat terbesar tersebut. Keadaan 'i' adalah aperiodik jika k = 1 dan periodik jika k > 1.
• Transien dan Rekuren: Suatu keadaan 'i' dikatakan transien jika, dengan asumsi kita mulai di keadaan 'i', ada probabilitas non-nol bahwa kita tidak akan pernah kembali ke 'i'. Keadaan i adalah rekuren (atau persisten) jika tidak transien. Keadaan rekuren disebut rekuren positif jika diharapkan kembali dalam jumlah langkah terbatas dan rekuren nol jika sebaliknya.
• Ergoditas: suatu keadaan 'i' dikatakan ergodik jika ia aperiodik dan rekuren positif. Jika semua keadaan dalam rantai Markov yang ireduksibel bersifat ergodik, maka rantai tersebut dikatakan ergodik.
• Keadaan Menyerap: suatu keadaan i disebut menyerap jika tidak mungkin keluar dari keadaan ini. Karena itu, keadaan 'i' menyerap jika p_ii = 1 dan p_ij = 0 untuk i ≠ j. Jika setiap keadaan dapat mencapai keadaan menyerap, maka rantai Markov tersebut adalah rantai Markov menyerap.

Tip: jika Anda juga ingin melihat penjelasan visual tentang rantai Markov, pastikan untuk mengunjungi halaman ini.

Rantai Markov di Python

Mari coba menulis kode contoh di atas dalam Python. Dan meskipun dalam praktiknya Anda mungkin akan menggunakan pustaka yang mengenkode Rantai Markov dengan cara yang jauh lebih efisien, kode ini akan membantu Anda memulai...

Pertama, impor beberapa pustaka yang akan Anda gunakan.

import numpy as np
import random as rm

Sekarang definisikan keadaan dan probabilitasnya: matriks transisi. Ingat, matriksnya akan berukuran 3 X 3 karena Anda memiliki tiga keadaan. Selain itu, Anda perlu mendefinisikan jalur transisi, yang juga bisa dilakukan menggunakan matriks.

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

Oh, selalu pastikan probabilitasnya berjumlah 1. Dan tidak ada salahnya menambahkan pesan galat, setidaknya saat ngoding!

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

Sekarang mari tulis kodenya. Anda akan menggunakan numpy.random.choice untuk menghasilkan sampel acak dari himpunan transisi yang mungkin. Sebagian besar argumennya sudah jelas, namun p mungkin belum. Ini adalah argumen opsional yang memungkinkan Anda memasukkan distribusi probabilitas untuk himpunan sampel, yang dalam kasus ini adalah matriks transisi.

# 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

Anda mendapatkan sekumpulan transisi acak yang mungkin beserta probabilitas terjadinya, dimulai dari keadaan: Sleep. Kembangkan program lebih lanjut untuk mungkin menjalankannya ratusan kali dengan keadaan awal yang sama, maka Anda dapat melihat probabilitas ekspektasi untuk berakhir pada keadaan tertentu beserta probabilitasnya. Mari kita tulis ulang fungsi activity_forecast dan tambahkan serangkaian loop baru untuk melakukannya...

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%

Bagaimana kita dapat mendekati nilai 62% yang diharapkan?

Catatan Ini sebenarnya adalah "hukum bilangan besar", yaitu prinsip probabilitas yang menyatakan bahwa frekuensi kejadian dengan kemungkinan kejadian yang sama akan menyeimbangkan, tetapi hanya jika terdapat cukup banyak percobaan atau kejadian. Dengan kata lain, seiring meningkatnya jumlah eksperimen, rasio hasil aktual akan konvergen ke rasio hasil teoretis atau yang diharapkan.

Markov State of Mind

Ini mengakhiri tutorial tentang Rantai Markov. Anda telah diperkenalkan pada Rantai Markov dan melihat beberapa sifatnya. Rantai Markov yang sederhana adalah salah satu topik dasar yang diperlukan untuk memulai data science dengan Python. Jika Anda ingin lebih banyak sumber belajar untuk memulai statistik dengan Python, pastikan untuk melihat halaman ini.

Apakah Anda tertarik mengeksplorasi lebih banyak studi kasus praktis dengan statistik di Python? Lihat kursus DataCamp Case Studies in Statistical Thinking atau Network Analysis in Python.