Chuỗi Markov trong Python: Hướng dẫn cho người mới bắt đầu

Một chuỗi Markov là hệ thống toán học thường được định nghĩa là một tập hợp các biến ngẫu nhiên, chuyển từ trạng thái này sang trạng thái khác theo các quy tắc xác suất nhất định. Tập các chuyển trạng thái này thỏa mãn Tính chất Markov, phát biểu rằng xác suất chuyển sang bất kỳ trạng thái cụ thể nào chỉ phụ thuộc vào trạng thái hiện tại và thời gian đã trôi qua, chứ không phụ thuộc vào chuỗi trạng thái trước đó. Đặc điểm độc đáo này khiến các quá trình Markov có tính không nhớ.

Muốn chinh phục thêm các chủ đề thống kê với Python? Hãy xem khóa học Statistical Thinking in Python của DataCamp!

Hãy chuyển trạng thái nào...

Vì sao là Chuỗi Markov?

Chuỗi Markov được sử dụng rộng rãi trong toán học. Chúng được áp dụng trong kinh tế học, lý thuyết trò chơi, lý thuyết truyền thông, di truyền học và tài chính. Chúng xuất hiện nhiều trong thống kê, đặc biệt là thống kê Bayes và các ngữ cảnh lý thuyết thông tin. Với các bài toán thực tế, chúng được dùng để đề xuất cách tiếp cận cho hệ thống kiểm soát hành trình trên xe, các hàng chờ của khách tại sân bay, tỷ giá hối đoái, v.v. Thuật toán PageRank, ban đầu được đề xuất cho công cụ tìm kiếm Google, dựa trên một quá trình Markov. Subreddit Simulator của Reddit là một subreddit tự động hoàn toàn tạo bài đăng và bình luận ngẫu nhiên bằng chuỗi Markov — thật thú vị!

Chuỗi Markov

Một chuỗi Markov là một quá trình ngẫu nhiên có tính chất Markov. Một quá trình ngẫu nhiên (hay quá trình ngẫu nhiên theo nghĩa rộng) là một đối tượng toán học được định nghĩa như một tập biến ngẫu nhiên. Chuỗi Markov có thể có không gian trạng thái rời rạc (tập giá trị có thể của các biến ngẫu nhiên) hoặc tập chỉ số rời rạc (thường biểu diễn thời gian) — vì vậy tồn tại nhiều biến thể của chuỗi Markov. Thông thường, thuật ngữ "chuỗi Markov" được dành cho quá trình có tập thời điểm rời rạc, tức Chuỗi Markov Thời gian Rời rạc (DTMC).

Chuỗi Markov Thời gian Rời rạc

Một chuỗi Markov thời gian rời rạc mô tả một hệ thống ở một trạng thái nào đó tại mỗi bước, với trạng thái thay đổi ngẫu nhiên giữa các bước. Các bước thường được xem là các thời điểm (nhưng bạn cũng có thể coi là khoảng cách vật lý hoặc bất kỳ đại lượng rời rạc nào khác). Một chuỗi Markov thời gian rời rạc là một dãy biến ngẫu nhiên X₁, X₂, X₃, ... có tính chất Markov, sao cho xác suất chuyển sang trạng thái tiếp theo chỉ phụ thuộc vào trạng thái hiện tại mà không phụ thuộc các trạng thái trước đó. Viết dưới dạng công thức xác suất:

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

Như bạn thấy, xác suất của X_n+1 chỉ phụ thuộc vào xác suất của X_n ngay trước đó. Điều này có nghĩa là biết trạng thái trước đó là đủ để xác định phân phối xác suất của trạng thái hiện tại, thỏa mãn quy tắc độc lập có điều kiện (nói cách khác: bạn chỉ cần biết trạng thái hiện tại để xác định trạng thái tiếp theo).

Các giá trị có thể của X_i tạo thành một tập đếm được S, gọi là không gian trạng thái của chuỗi. Không gian trạng thái có thể là bất cứ thứ gì: chữ cái, số, điểm số bóng rổ hoặc điều kiện thời tiết. Dù tham số thời gian thường là rời rạc, không gian trạng thái của chuỗi Markov thời gian rời rạc không có ràng buộc được đồng thuận rộng rãi, mà nói chung chỉ là một quá trình trên không gian trạng thái tùy ý. Tuy nhiên, nhiều ứng dụng của chuỗi Markov dùng không gian trạng thái hữu hạn hoặc đếm được vô hạn, vì chúng dễ phân tích thống kê hơn.

Mô hình

Một chuỗi Markov được biểu diễn bằng một tự động xác suất (nghe có vẻ phức tạp thôi!). Các thay đổi trạng thái của hệ thống được gọi là chuyển tiếp. Các xác suất gắn với những thay đổi trạng thái khác nhau được gọi là xác suất chuyển tiếp. Một tự động xác suất đưa xác suất của một chuyển tiếp nhất định vào hàm chuyển tiếp, biến nó thành một ma trận chuyển tiếp.

Bạn có thể hình dung nó như một chuỗi đồ thị có hướng, trong đó các cạnh của đồ thị n được gán nhãn bằng xác suất đi từ một trạng thái tại thời điểm n sang các trạng thái tại thời điểm n+1, Pr(X_n+1 = x | X_n = x_n). Bạn có thể đọc là xác suất đi tới trạng thái X_n+1 khi biết giá trị trạng thái X_n. Thông tin tương tự được biểu diễn bằng ma trận chuyển tiếp từ thời điểm n tới n+1. Mỗi trạng thái trong không gian trạng thái xuất hiện một lần làm hàng và một lần làm cột, và mỗi ô trong ma trận cho bạn biết xác suất chuyển từ trạng thái của hàng sang trạng thái của cột.

Nếu chuỗi Markov có N trạng thái khả dĩ, ma trận sẽ là ma trận N x N, trong đó phần tử (I, J) là xác suất chuyển từ trạng thái I sang trạng thái J. Ngoài ra, ma trận chuyển tiếp phải là ma trận ngẫu nhiên, tức tổng các phần tử trên mỗi hàng phải đúng bằng 1. Tại sao? Vì mỗi hàng biểu diễn một phân phối xác suất riêng.

Vậy, mô hình được đặc trưng bởi không gian trạng thái, một ma trận chuyển tiếp mô tả xác suất của các chuyển tiếp cụ thể, và trạng thái khởi đầu trên toàn không gian trạng thái, được cho bởi phân phối ban đầu.

Nhiều chữ quá phải không?

Hãy xem một ví dụ đơn giản để hiểu các khái niệm:

Khi Cj buồn, điều này không thường xuyên lắm: cô ấy hoặc đi chạy, ngốn kem, hoặc ngủ một giấc.

Từ dữ liệu lịch sử, nếu cô ấy dành cả ngày buồn để ngủ. Ngày hôm sau có 60% khả năng cô ấy sẽ đi chạy, 20% sẽ vẫn nằm trên giường và 20% khả năng sẽ ăn kem thỏa thích.

Khi cô ấy buồn và đi chạy, có 60% khả năng cô ấy sẽ tiếp tục chạy ngày hôm sau, 30% sẽ ăn kem và chỉ 10% khả năng cô ấy sẽ dành ngày hôm sau để ngủ.

Cuối cùng, khi cô ấy ăn kem vào một ngày buồn, chỉ có 10% khả năng cô ấy tiếp tục ăn kem vào ngày hôm sau, 70% khả năng sẽ đi chạy và 20% khả năng sẽ ngủ vào ngày kế tiếp.

Chuỗi Markov được thể hiện trong sơ đồ trạng thái có 3 trạng thái khả dĩ: ngủ, chạy, kem. Vì vậy, ma trận chuyển tiếp sẽ là ma trận 3 x 3. Lưu ý, các mũi tên đi ra từ một trạng thái luôn cộng lại đúng bằng 1, tương tự các phần tử ở mỗi hàng trong ma trận chuyển tiếp phải cộng lại đúng bằng 1 — biểu diễn phân phối xác suất. Trong ma trận chuyển tiếp, các ô thực hiện cùng chức năng như các mũi tên trong sơ đồ trạng thái.

Bây giờ bạn đã thấy ví dụ, điều này sẽ giúp bạn hình dung các khái niệm khác nhau liên quan đến chuỗi Markov. Nhưng, làm thế nào và ở đâu bạn có thể áp dụng lý thuyết này trong đời thực?

Với ví dụ trên, giờ bạn có thể trả lời các câu như: "Bắt đầu từ trạng thái: ngủ, xác suất để Cj sẽ chạy (trạng thái: chạy) vào cuối khoảng thời gian buồn kéo dài 2 ngày là bao nhiêu?"

Hãy giải bài này: Để chuyển từ trạng thái: ngủ sang trạng thái: chạy, Cj có thể hoặc ở trạng thái: ngủ trong nước đi (hay ngày) đầu tiên, rồi chuyển sang trạng thái: chạy ở nước đi (ngày) thứ hai (0,2 $\cdot$ 0,6); hoặc chuyển sang trạng thái: chạy ngay ngày đầu và ở lại đó ngày thứ hai (0,6 $\cdot$ 0,6) hoặc cô ấy có thể chuyển sang trạng thái: kem ở nước đi đầu và rồi sang trạng thái: chạy ở nước đi thứ hai (0,2 $\cdot$ 0,7). Vậy xác suất: ((0,2 $\cdot$ 0,6) + (0,6 $\cdot$ 0,6) + (0,2 $\cdot$ 0,7)) = 0,62. Do đó, chúng ta có thể nói có 62% khả năng Cj sẽ ở trạng thái: chạy sau hai ngày buồn, nếu cô ấy bắt đầu ở trạng thái: ngủ.

Hy vọng điều này đã cho bạn ý tưởng về các câu hỏi có thể trả lời bằng mạng Chuỗi Markov.

Với nền tảng này, sẽ dễ hiểu hơn một số tính chất quan trọng của chuỗi Markov:

• Tính khử được: một chuỗi Markov được gọi là bất khả khử nếu có thể đi tới bất kỳ trạng thái nào từ bất kỳ trạng thái nào. Nói cách khác, chuỗi Markov là bất khả khử nếu tồn tại một chuỗi bước giữa mọi cặp trạng thái có xác suất dương.
• Tính chu kỳ: một trạng thái trong chuỗi Markov là chu kỳ nếu chuỗi chỉ có thể quay lại trạng thái đó tại bội số của một số nguyên lớn hơn 1. Do đó, bắt đầu ở trạng thái 'i', chuỗi chỉ có thể quay lại 'i' tại các bội của chu kỳ 'k', và k là số nguyên lớn nhất như vậy. Trạng thái 'i' là vô chu kỳ nếu k = 1 và có chu kỳ nếu k > 1.
• Tính thoáng qua và tái diễn: Trạng thái 'i' được gọi là thoáng qua nếu, khi bắt đầu ở 'i', có xác suất khác 0 rằng ta sẽ không bao giờ quay lại 'i'. Trạng thái i là tái diễn (hay bền) nếu nó không thoáng qua. Một trạng thái tái diễn được gọi là tái diễn dương nếu kỳ vọng quay lại trong số bước hữu hạn và tái diễn bằng không nếu ngược lại.
• Tính ergodic: trạng thái 'i' được gọi là ergodic nếu nó vô chu kỳ và tái diễn dương. Nếu mọi trạng thái trong một chuỗi Markov bất khả khử đều ergodic, thì chuỗi được gọi là ergodic.
• Trạng thái hấp thụ: một trạng thái i được gọi là hấp thụ nếu không thể rời khỏi trạng thái này. Do đó, trạng thái 'i' là hấp thụ nếu p_ii = 1 và p_ij = 0 với i ≠ j. Nếu mọi trạng thái đều có thể đi tới một trạng thái hấp thụ, thì chuỗi Markov đó là chuỗi Markov hấp thụ.

Mẹo: nếu bạn muốn xem phần minh họa trực quan về chuỗi Markov, hãy ghé trang này.

Chuỗi Markov trong Python

Hãy thử viết mã ví dụ trên bằng Python. Dù trong thực tế, bạn có thể dùng thư viện hiện thực Chuỗi Markov hiệu quả hơn nhiều, đoạn mã sau sẽ giúp bạn bắt đầu...

Đầu tiên, import một số thư viện bạn sẽ dùng.

import numpy as np
import random as rm

Bây giờ hãy định nghĩa các trạng thái và xác suất của chúng: ma trận chuyển tiếp. Nhớ rằng ma trận sẽ là ma trận 3 X 3 vì bạn có ba trạng thái. Bạn cũng sẽ phải định nghĩa các đường chuyển tiếp; bạn có thể làm điều này bằng ma trận.

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

À, luôn đảm bảo các xác suất cộng lại thành 1. Và để lại thông báo lỗi cũng không thừa, ít nhất là khi viết code!

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

Giờ hãy viết phần chính. Bạn sẽ dùng numpy.random.choice để sinh mẫu ngẫu nhiên từ tập các chuyển tiếp khả dĩ. Hầu hết tham số của nó đều dễ hiểu, nhưng p thì có thể không. Đây là tham số tùy chọn cho phép bạn truyền phân phối xác suất cho tập lấy mẫu, trong trường hợp này chính là ma trận chuyển tiế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

Bạn nhận được một tập chuyển tiếp ngẫu nhiên khả dĩ kèm theo xác suất xảy ra của nó, bắt đầu từ trạng thái: Sleep. Mở rộng chương trình để lặp vài trăm lần với cùng trạng thái bắt đầu, khi đó bạn có thể thấy xác suất kỳ vọng kết thúc ở bất kỳ trạng thái cụ thể nào và xác suất tương ứng. Hãy viết lại hàm activity_forecast và thêm một vòng lặp mới để làm điều này...

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%

Làm sao chúng ta xấp xỉ về mức 62% mong muốn?

Lưu ý Đây chính là "luật số lớn", một nguyên lý xác suất phát biểu rằng tần suất của các sự kiện có khả năng xảy ra như nhau sẽ dần cân bằng, nhưng chỉ khi số phép thử đủ lớn. Nói cách khác, khi số thí nghiệm tăng lên, tỷ lệ kết quả thực tế sẽ hội tụ về tỷ lệ kết quả lý thuyết hoặc kỳ vọng.

Tư duy Markov

Đây là phần kết thúc hướng dẫn về Chuỗi Markov. Bạn đã được giới thiệu về Chuỗi Markov và một số tính chất của nó. Các chuỗi Markov đơn giản là một trong những chủ đề nền tảng cần thiết để bắt đầu với khoa học dữ liệu trong Python. Nếu bạn muốn có thêm tài nguyên để bắt đầu với thống kê trong Python, hãy xem trang này.

Bạn muốn khám phá thêm các nghiên cứu tình huống thực tiễn với thống kê trong Python? Hãy xem các khóa Case Studies in Statistical Thinking hoặc Network Analysis in Python của DataCamp.