Chuỗi Markov & Mô hình Markov ẩn: Khái niệm & Ứng dụng

Chuỗi Markov và Ma trận chuyển trạng thái

Chuỗi Markov (Markov Chain)

Chuỗi Markov (hay Xích Markov) là một quá trình ngẫu nhiên mô tả một hệ thống thay đổi giữa các trạng thái hữu hạn. Đặc điểm cốt lõi của nó là tính chất Markov: Trạng thái tương lai chỉ phụ thuộc vào trạng thái hiện tại, không phụ thuộc vào chuỗi các trạng thái trong quá khứ. Nói cách khác, nếu ta biết "bây giờ", thông tin về "ngày hôm qua" trở nên dư thừa trong việc dự báo "ngày mai".

Từ ví dụ thực tế đến dạng thức Ma trận

Xét một hệ thống thời tiết đơn giản với hai trạng thái: Nắng (N) và Mưa (M). Giả sử quy luật thay đổi được xác định như sau:

• Nếu hôm nay Nắng, xác suất ngày mai Nắng là 0.7 và Mưa là 0.3.

• Nếu hôm nay Mưa, xác suất ngày mai Nắng là 0.9 và Mưa là 0.1.

Như vậy, nếu hôm nay là Nắng, ngày mai sẽ có 70% khả năng Nắng. Vậy 2 ngày sau thì sao? Sẽ là Nắng hay Mưa?

Để tính thủ công, chúng ta phải liệt kê đầy đủ các nhánh nếu hôm nay là ngày Nắng, gồm có:

• Nắng (hôm nay) - Nắng - Nắng: $0.7 \times 0.7 = 0.49$

• Nắng (hôm nay) - Nắng - Mưa: $0.7 \times 0.3 = 0.21$

• Nắng (hôm nay) - Mưa - Nắng: $0.3 \times 0.9 = 0.27$

• Nắng (hôm nay) - Mưa - Mưa: $0.3 \times 0.1 = 0.03$

Như vậy 2 ngày sau thì xác suất Nắng là $0.49+0.27 = 0.76$ và Mưa là $0.21 + 0.03=0.24$. Điều này trở nên phức tạp khi số ngày tăng lên.

Để tối ưu hóa, ta biểu diễn quy luật trên bằng một Ma trận chuyển trạng thái (Transition Matrix) $P$:

Trong đó, hàng 1 biểu thị xác suất đi từ Nắng sang các trạng thái khác, hàng 2 biểu thị từ Mưa. Nếu trạng thái hiện tại là đang nắng (100% Nắng, 0% Mưa) thì vector biểu diễn sẽ là$v_0 = [1, 0]$, như vậy xác suất xảy ra năng mưa các ngày sau sẽ là:

• Ngày mai ($v_1$): $v_1^T = v_0^T P = [0.7, 0.3]$ (70% Nắng, 30% Mưa) đúng theo giả thiết.

• Và cho $n$ ngày sau ($v_n$): $v_n^T = v_0^T P^n$

Câu hỏi đặt ra là: Tại sao phép nhân $v_0^T P^n$ lại cho ra kết quả chính xác như việc ta ngồi cộng từng nhánh xác suất?

Bản chất của phép nhân ma trận chính là phép tính tổng các tích (dot product). Hãy nhìn vào phép tính $P^2$:

Kết quả tính toán chi tiết:

• Hàng 1, Cột 1 (Nắng $\to$ Nắng): $0.49 + 0.27 = 0.76$

• Hàng 1, Cột 2 (Nắng $\to$ Mưa): $0.21 + 0.03 = 0.24$

• Hàng 2, Cột 1 (Mưa $\to$ Nắng): $0.63 + 0.09 = 0.72$

• Hàng 2, Cột 2 (Mưa $\to$ Mưa): $0.27 + 0.01 = 0.28$

Ma trận kết quả cuối cùng:

Ý nghĩa các phần tử trong $P^2$:

• Phần tử $P^2_{11}$ (0.76): Tổng xác suất của các kịch bản bắt đầu từ Nắng và kết thúc tại Nắng sau 2 ngày (N-N-N và N-M-N).

• Phần tử $P^2_{12}$ (0.24): Tổng xác suất của các kịch bản bắt đầu từ Nắng và kết thúc tại Mưa sau 2 ngày (N-N-M và N-M-M).

• Phần tử $P^2_{21}$ (0.72): Tổng xác suất của các kịch bản bắt đầu từ Mưa và kết thúc tại Nắng sau 2 ngày (M-N-N và M-M-N).

• Phần tử $P^2_{22}$ (0.28): Tổng xác suất của các kịch bản bắt đầu từ Mưa và kết thúc tại Mưa sau 2 ngày (M-N-M và M-M-M).

Điều này nghĩa là khi ta tính $P^n$, mỗi phần tử trong ma trận kết quả thực chất là tổng của tất cả các kịch bản có thể xảy ra để đi từ trạng thái $i$ đến trạng thái $j$ sau đúng $n$ bước.

Quan sát khi ta nhân ma trận chuyển cho nhiều bước thời gian ($P^n$ với $n$ lớn), một hiện tượng toán học quan trọng xảy ra: ma trận sẽ hội tụ. Với ma trận $P$ ở trên, khi $n \to \infty$:

Lúc này, các hàng của ma trận trở nên giống hệt nhau. Điều này có nghĩa là dù trạng thái khởi đầu ($v_0$) là Nắng hay Mưa, thì sau một thời gian đủ dài, xác suất hệ thống nằm ở trạng thái Nắng luôn là 75% và Mưa là 25%. Trạng thái này được gọi là Trạng thái dừng ($\pi$).

Ý nghĩa của Trạng thái dừng

Việc hiểu sự hội tụ của ma trận chuyển trạng thái mang lại hai ý nghĩa thực tiễn:

• Phân tách giai đoạn dự báo: Trong ngắn hạn, ta cần ma trận $P$ và trạng thái hiện tại để có dự báo chính xác. Trong dài hạn, ta chỉ cần vector trạng thái dừng $\pi$ để biết đặc tính ổn định của hệ thống.

• Đánh giá tính bền vững: Trạng thái dừng cho phép ta trả lời các câu hỏi mang tính hệ thống như: "Trung bình một khách hàng sẽ ở lại website trong bao lâu?" hay "Tỉ lệ lỗi trung bình của hệ thống truyền tin là bao nhiêu?".

Mô hình Markov ẩn (Hidden Markov Model - HMM)

Khái niệm lớp "Ẩn" (Hidden)

Trong Chuỗi Markov ở Phần 1, ta giả định có thể nhìn thấy trực tiếp trạng thái (ví dụ: nhìn lên bầu trời biết ngay là Nắng hay Mưa). Tuy nhiên, trong nhiều bài toán, trạng thái thực sự bị che khuất, ta chỉ có thể thu thập được các quan sát (observations) có liên quan đến trạng thái đó.

Ví dụ: Bạn đang ở trong một căn phòng kín không cửa sổ và muốn biết thời tiết bên ngoài là Nắng ($N$) hay Mưa ($M$). Dữ liệu duy nhất bạn có là quan sát một người đồng nghiệp bước vào phòng: họ đang Cầm Ô ($U$) hay Không Cầm Ô ($F$).

• Thời tiết (Nắng/Mưa) là Trạng thái ẩn.

• Việc cầm ô (Có/Không) là Quan sát.

Các thành phần cấu tạo nên HMM

Một mô hình HMM được xác định bởi bộ ba tham số $\lambda = (A, B, \pi)$:

• Ma trận chuyển trạng thái ẩn ($A$): Giống như $P$ ở Phần 1, mô tả xác suất chuyển đổi giữa các trạng thái ẩn (ví dụ: xác suất từ Nắng sang Mưa).

• Ma trận xác suất phát xạ ($B$ - Emission Matrix): Đây là thành phần mới. Nó mô tả xác suất xuất hiện một quan sát cụ thể khi hệ thống đang ở một trạng thái ẩn nhất định. Ví dụ: Nếu trời Mưa, xác suất đồng nghiệp cầm ô là 0.9. Nếu trời Nắng, xác suất cầm ô chỉ là 0.2.

• Vector xác suất khởi tạo ($\pi$): Xác suất hệ thống bắt đầu ở một trạng thái ẩn nào đó tại thời điểm $t=0$

Ví dụ về Ma trận phát xạ $B$

Tiếp tục với ví dụ thời tiết, ma trận phát xạ $B$ có thể được trình bày như sau:

Dưới dạng ma trận

Sự phức tạp phát sinh từ việc một quan sát có thể đến từ nhiều trạng thái ẩn khác nhau.

• Nếu ta thấy đồng nghiệp cầm ô ($U$), ta không thể kết luận 100% là trời đang Mưa, vì vẫn có 20% khả năng họ cầm ô khi trời Nắng (để che nắng chẳng hạn).

• Để dự báo đúng nhất, ta phải kết hợp cả xác suất chuyển trạng thái (trời hôm qua thế nào) và xác suất phát xạ (hành động cầm ô có ý nghĩa gì)

Ba bài toán cốt lõi của HMM

Để vận hành một mô hình HMM, giới kỹ thuật tập trung giải quyết 3 bài toán sau:

• Bài toán Đánh giá (Evaluation): Cho trước mô hình và một chuỗi quan sát (ví dụ: 3 ngày liên tiếp thấy cầm ô), tính xác suất để chuỗi quan sát đó xảy ra. Giải quyết bằng Thuật toán Forward-Backward.

• Bài toán Giải mã (Decoding): Cho trước một chuỗi quan sát, tìm chuỗi trạng thái ẩn "khả dĩ nhất" đã tạo ra chúng. Giải quyết bằng Thuật toán Viterbi. Đây là bài toán phổ biến nhất (ví dụ: suy luận từ âm thanh ra văn bản).

• Bài toán Học máy (Learning): Nếu chỉ có chuỗi quan sát mà chưa có các ma trận $A$ và $B$, làm sao để ước lượng chúng? Giải quyết bằng Thuật toán Baum-Welch.

Tạm thời, chúng ta ngừng ở đây đã, các thuật toán liên quan chúng ta sẽ bàn luận ở các bài tiếp theo nhé.