Markov Models và Hidden Markov Models

Các Bayesian Network trước mô tả dependency giữa nhiều biến, nhưng chưa nhấn mạnh yếu tố thời gian.

Trong nhiều bài toán AI, dữ liệu đến theo chuỗi:

trạng thái mạng phút 1 -> phút 2 -> phút 3

thời tiết hôm nay -> ngày mai -> ngày kia

âm thanh frame 1 -> frame 2 -> frame 3

Markov Models là một cách mô hình hóa những chuỗi như vậy.

Mục tiêu

Sau bài này, bạn cần:

hiểu Markov assumption;
hiểu Markov Chain và transition model;
đọc được transition matrix;
sample được một Markov Chain đơn giản;
hiểu hidden state và observation;
hiểu cấu trúc Hidden Markov Model - HMM;
phân biệt transition model và emission/sensor model;
biết bốn bài toán cơ bản: filtering, prediction, smoothing, most likely explanation.

State theo thời gian

Ta ký hiệu:

X_1,X_2,\ldots,X_t,X_{t+1}

Ví dụ:

X_t = trạng thái Wi-Fi ở phút t

với:

WifiState ∈ {good, slow}

Một câu hỏi có thể là:

Nếu hiện tại Wi-Fi đang chậm, xác suất phút tiếp theo vẫn chậm là bao nhiêu?

Đây là xác suất chuyển trạng thái theo thời gian.

Markov Assumption - Giả định Markov

Về lý thuyết, trạng thái tương lai có thể phụ thuộc vào toàn bộ lịch sử:

P(X_{t+1}\mid X_t,X_{t-1},\ldots,X_1)

Nhưng lịch sử càng dài, mô hình càng phức tạp.

Markov assumption bậc 1 đơn giản hóa thành:

P(X_{t+1}\mid X_t,X_{t-1},\ldots,X_1) = P(X_{t+1}\mid X_t)

Nói bằng lời:

Khi đã biết state hiện tại, mô hình bỏ qua lịch sử xa hơn để dự đoán state tiếp theo.

Đây là giả định mô hình hóa, không phải một định luật nói rằng thế giới thật luôn như vậy.

Markov Chain - Chuỗi Markov

Một Markov Chain là chuỗi các random variables tuân theo Markov assumption.

Ví dụ trạng thái mạng Wi-Fi:

Giả sử transition model:

Hiện tại	Phút sau `good`	Phút sau `slow`
`good`	0.85	0.15
`slow`	0.35	0.65

Ví dụ:

P(X_{t+1}=slow\mid X_t=good)=0.15

và:

P(X_{t+1}=slow\mid X_t=slow)=0.65

Transition Matrix

Bảng trên có thể viết thành:

T= \begin{bmatrix} 0.85 & 0.15\\ 0.35 & 0.65 \end{bmatrix}

với thứ tự state:

[good, slow]

Mỗi hàng cộng bằng 1 vì nó là distribution của state tiếp theo khi state hiện tại đã cố định.

Hình công khai: Markov Chain hai trạng thái

Ví dụ Markov Chain với hai trạng thái

Hình: một Markov Chain hai trạng thái với xác suất chuyển trên các cạnh. Nguồn: Wikimedia Commons, tác giả Pmdusso, CC BY-SA 3.0.

Hình dùng Sunny và Rainy, nhưng cơ chế hoàn toàn giống ví dụ good và slow: cạnh nào cũng có xác suất chuyển trạng thái.

Sample một Markov Chain bằng Python

import random

transition = {
    "good": {"good": 0.85, "slow": 0.15},
    "slow": {"good": 0.35, "slow": 0.65},
}


def next_state(current):
    p_good = transition[current]["good"]
    return "good" if random.random() < p_good else "slow"


state = "good"
sequence = [state]

for _ in range(14):
    state = next_state(state)
    sequence.append(state)

print(sequence)

Một lần chạy có thể cho:

good -> good -> slow -> slow -> good -> ...

Chạy lại có thể cho chuỗi khác.

Markov Chain dùng ở đâu?

Ở mức ý tưởng, nó phù hợp với các hệ có state biến đổi theo bước thời gian và state tiếp theo phụ thuộc chủ yếu vào state gần nhất.

Ví dụ:

trạng thái thời tiết;
trạng thái tải server theo từng time slot;
hành vi người dùng theo phiên;
mô hình chuỗi ký tự hoặc từ đơn giản;
một số mô hình hàng đợi hoặc reliability.

Nhiều hệ hiện đại dùng mô hình mạnh hơn, nhưng Markov Chain vẫn là nền tảng quan trọng để hiểu probabilistic sequence models.

Hidden Markov Model - Khi state thật không quan sát trực tiếp

Markov Chain ở trên giả sử ta biết WifiState thật là good hay slow.

Nhưng trong thực tế, đôi khi state thật bị ẩn.

Ví dụ:

Hidden state:
NetworkLoad ∈ {low, high}

Observation:
Ping ∈ {fast, slow}

Ta không nhìn trực tiếp được “network load” tổng thể, nhưng ta đo được ping.

Ping chậm là evidence cho việc mạng đang tải cao, nhưng không đảm bảo 100% vì ping còn chịu nhiều yếu tố khác.

Đó là tình huống phù hợp với Hidden Markov Model - HMM.

Hai lớp của HMM

HMM có:

$X_t$ : hidden state ở thời điểm $t$ ;
$E_t$ : observation/evidence ở thời điểm $t$ .

Có hai loại probability quan trọng.

Transition Model

Transition model mô tả hidden state thay đổi theo thời gian:

P(X_t\mid X_{t-1})

Ví dụ:

`NetworkLoad_t`	`low` phút sau	`high` phút sau
`low`	0.80	0.20
`high`	0.30	0.70

Nếu mạng đang high load, mô hình giả định khả năng phút sau vẫn high là 70%.

Emission Model / Sensor Model

Emission model mô tả observation được sinh ra từ hidden state:

P(E_t\mid X_t)

Ví dụ:

`NetworkLoad`	`Ping=fast`	`Ping=slow`
`low`	0.90	0.10
`high`	0.25	0.75

Nếu load cao, ping slow có xác suất cao hơn. Nhưng vẫn có 25% trường hợp ping nhanh theo mô hình giả định.

Đây là điểm quan trọng:

Observation không phải hidden state. Observation chỉ cung cấp evidence về hidden state.

Hình công khai: cấu trúc HMM

Cấu trúc Hidden Markov Model

Hình: Hidden Markov Model với hidden states và outputs. Nguồn: Wikimedia Commons, tác giả Tdunning và bản vector hóa Razorbliss, CC BY 3.0.

Hình này giúp thấy hai loại cạnh khác nhau:

hidden state chuyển sang hidden state kế tiếp;
hidden state sinh ra observation.

Sensor Markov Assumption

HMM thường giả định observation tại thời điểm $t$ chỉ phụ thuộc trực tiếp vào hidden state cùng thời điểm:

P(E_t\mid X_t,X_{t-1},E_{t-1},\ldots) = P(E_t\mid X_t)

Nói đơn giản:

Khi đã biết hidden state hiện tại, mô hình không cần dùng toàn bộ lịch sử để giải thích observation hiện tại.

Đây cũng là một giả định đơn giản hóa.

Ví dụ gần sinh viên: đo Wi-Fi trong phòng học

Giả sử laptop ghi lại chuỗi ping:

fast, fast, slow, slow, slow, fast

Ta muốn suy luận chuỗi hidden network load có khả năng là:

low, low, high, high, high, low

Nhưng không thể chỉ map cứng:

fast -> low
slow -> high

vì emission model không deterministic.

Ví dụ:

P(Ping=slow\mid Load=low)=0.10

nên mạng low load vẫn có thể cho một lần ping chậm.

HMM kết hợp cả:

state trước ảnh hưởng state sau;
state hiện tại ảnh hưởng observation hiện tại.

Bốn bài toán điển hình với HMM

Filtering

Dùng observations từ đầu đến hiện tại để suy luận hidden state hiện tại:

P(X_t\mid e_1,\ldots,e_t)

Ví dụ:

Dựa trên chuỗi ping tới phút này, xác suất mạng hiện đang high load là bao nhiêu?

Prediction

Dùng observations đến hiện tại để dự đoán hidden state tương lai:

P(X_{t+k}\mid e_1,\ldots,e_t)

Ví dụ:

Với trạng thái ước lượng hiện tại, 5 phút nữa mạng còn high load không?

Smoothing

Dùng cả observations xuất hiện sau đó để cập nhật ước lượng về một hidden state trong quá khứ.

Ví dụ:

Sau khi xem thêm các ping ở phút 11-15, ta cập nhật lại nhận định mạng ở phút 10.

Most Likely Explanation

Tìm chuỗi hidden states có xác suất cao nhất giải thích toàn bộ observations.

Trong speech recognition cổ điển:

Observation: đặc trưng âm thanh
Hidden state: trạng thái âm vị / ngôn ngữ

Ta muốn tìm chuỗi hidden states phù hợp nhất với tín hiệu đã nghe.

Thuật toán kinh điển là Viterbi.

Filtering và “chỉ nhìn observation hiện tại” khác nhau thế nào?

Giả sử ping hiện tại là slow.

Nếu chỉ nhìn emission model, ta có evidence rằng load có thể high.

Nhưng HMM còn dùng state trước đó. Nếu nhiều phút trước đều cho evidence mạnh rằng load đang low, belief hiện tại có thể khác so với trường hợp trước đó đã high liên tục.

Đó là lợi ích của mô hình chuỗi:

Evidence hiện tại được kết hợp với belief truyền từ quá khứ.

HMM là Bayesian Network lặp theo thời gian

Có thể nhìn HMM như một Dynamic Bayesian Network rất đơn giản:

Joint distribution của một chuỗi ba bước có dạng:

P(X_1,X_2,X_3,E_1,E_2,E_3)

=P(X_1) P(E_1\mid X_1) P(X_2\mid X_1) P(E_2\mid X_2) P(X_3\mid X_2) P(E_3\mid X_3)

Công thức này chỉ là Bayesian Network factorization áp dụng cho cấu trúc lặp theo thời gian.

Markov assumption có luôn đúng không?

Không.

Ví dụ trạng thái mạng phút sau có thể phụ thuộc vào:

thời điểm trong ngày;
lịch học cả tòa nhà;
số người dùng 10 phút trước;
sự cố nhà mạng;
nhiều yếu tố khác.

Mô hình bậc 1 bỏ qua phần lớn lịch sử để đổi lấy tính đơn giản.

Trong machine learning, đây là trade-off rất phổ biến:

Mô hình đơn giản hơn
-> dễ tính hơn
-> nhưng có thể bỏ mất thông tin

Markov Models và mô hình AI hiện đại

RNN, LSTM, Transformers và các sequence models hiện đại mạnh hơn nhiều trong nhiều bài toán chuỗi. Tuy vậy, Markov Models vẫn đáng học vì:

giúp hiểu state và transition;
làm rõ hidden state và observation;
giải thích nền tảng của nhiều thuật toán xác suất chuỗi;
là mô hình đủ đơn giản để tính bằng tay và nhìn rõ toàn bộ cơ chế.

Không nên hiểu rằng “đã có deep learning thì Markov Models vô dụng”. Chúng vẫn xuất hiện trong signal processing, speech, bioinformatics, reliability, time-series modeling và nhiều hệ hybrid.

Tự kiểm tra

Câu 1

Giả định Markov bậc 1 nói gì?

Đáp án

Khi đã biết state hiện tại, distribution của state tiếp theo chỉ phụ thuộc vào state hiện tại, không cần toàn bộ lịch sử xa hơn.

Câu 2

Trong HMM Wi-Fi:

Hidden state: NetworkLoad
Observation: Ping

$P(Ping\mid NetworkLoad)$ thuộc loại model nào?

Đáp án

Emission model hoặc sensor model.

Câu 3

Bài toán “tìm chuỗi hidden states có khả năng nhất giải thích observations” gọi là gì?

Đáp án

Most likely explanation. Thuật toán kinh điển thường dùng là Viterbi.

Tóm tắt

Markov assumption giới hạn dependency vào một số state gần nhất.
Markov Chain mô tả chuỗi state bằng transition probabilities.
Transition matrix cho biết từ state hiện tại có thể đi sang state nào với xác suất bao nhiêu.
HMM thêm hidden state và observation.
Transition model: $P(X_t\mid X_{t-1})$ .
Emission model: $P(E_t\mid X_t)$ .
Bốn nhiệm vụ cơ bản là filtering, prediction, smoothing và most likely explanation.
Markov assumption là giả định đơn giản hóa, không phải chân lý tuyệt đối.

Tài liệu tham khảo

Bản tiếng Anh đang soạn.