Thuật toán Forward-Backward: Cơ sở định lượng trong Hidden Markov Model

Trong các hệ thống được mô hình hóa bằng Hidden Markov Model (HMM), chúng ta thường đối mặt với một lớp thông tin bị che khuất. Để hiểu rõ lớp ẩn này thông qua dữ liệu quan sát, thuật toán Forward-Backward đóng vai trò là công cụ tính toán hiệu quả nhất, giúp giải quyết bài toán định lượng và làm mịn dữ liệu.

Hệ tham số cơ bản của HMM: $\lambda = (A, B, \pi)$

Trước khi đi vào thuật toán, ta cần xác định bộ ba tham số $\lambda$ cấu thành nên một mô hình HMM:

• Ma trận chuyển trạng thái ẩn: $A = \{a_{ij}\}$, với $a_{ij} = P(q_{t+1} = s_j \mid q_t = s_i)$. Quản lý xác suất di chuyển giữa các trạng thái ẩn.

• Ma trận xác suất phát xạ: $B = \{b_j(k)\}$, với $b_j(k) = P(o_t = v_k \mid q_t = s_j)$. Quy định xác suất xuất hiện một quan sát khi hệ thống đang ở một trạng thái ẩn nhất định.

• Vector xác suất khởi tạo: $\pi = \{\pi_i\}$, với $\pi_i = P(q_1 = s_i)$. Xác định trạng thái bắt đầu của hệ thống tại $t=1$.

Phát biểu bài toán

Cho mô hình $\lambda$ và chuỗi quan sát $O = \{o_1, o_2, \dots, o_T\}$. Thuật toán Forward-Backward giúp tính toán:

• Đánh giá (Evaluation): Tổng xác suất chuỗi $O$ xảy ra: $P(O \mid \lambda)$. Nghĩa là để trả lời cho câu hỏi: "Khả năng mô hình này tạo ra chuỗi dữ liệu mà tôi đang thấy là bao nhiêu?". Đây là việc tính tổng xác suất của tất cả các kịch bản ẩn có thể xảy ra. Ví dụ: Bạn có 2 mô hình tiếng Việt và tiếng Anh. Khi nhận được một chuỗi âm thanh, mô hình nào cho kết quả "Đánh giá" (xác suất $P(O|\lambda)$) cao hơn thì chuỗi âm thanh đó thuộc về ngôn ngữ đó.

• Làm mịn (Smoothing): Xác suất hệ thống nằm ở trạng thái $s_i$ tại thời điểm $t$ bất kỳ, khi đã biết toàn bộ dữ liệu quan sát. Nghĩa là để trả lời cho câu hỏi: "Tại thời điểm $t$ trong quá khứ, hệ thống thực sự ở trạng thái nào? Bản chất của việc làm mịn khác với dự báo (chỉ dùng dữ liệu quá khứ đến hiện tại $t$), làm mịn dùng toàn bộ dữ liệu (cả trước và sau $t$) để hiệu chỉnh lại ước lượng tại $t$. Tại sao gọi là "Làm mịn"? Vì dữ liệu quan sát thường có nhiễu. Bằng cách nhìn vào các quan sát ở tương lai ($t+1, t+2...$), ta có thể loại bỏ các suy luận sai lầm tại $t$ do nhiễu gây ra.

Ví dụ minh họa

Xét bài toán dự báo tâm trạng đồng nghiệp: (Trạng thái ẩn: Vui - $S_1$, Buồn - $S_2$) qua hành động (Quan sát: Cười - $O_1$, Khóc - $O_2$).

• $\pi = [0.8, 0.2]$

• $A = \begin{pmatrix} 0.6 & 0.4 \\ 0.3 & 0.7 \end{pmatrix} ; B = \begin{pmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{pmatrix}$

• Chuỗi quan sát thực tế: Giả sử bạn quan sát thấy đồng nghiệp trong 2 ngày liên tiếp đều Cười ($O_1, O_1$)

Chúng ta cần tính:

• Yêu cầu 1 (Đánh giá): Tính xác suất để chuỗi quan sát "Cười - Cười" này xảy ra dựa trên mô hình tâm trạng đã thiết lập.

• Yêu cầu 2 (Làm mịn): Dựa trên toàn bộ chuỗi quan sát 2 ngày, hãy xác định xác suất thực sự người đó Vui ($S_1$) vào ngày đầu tiên.

Pha Forward (Xác suất tiến): Cơ chế tích lũy xác suất

Mục tiêu: Tính xác suất chuỗi quan sát $O = \{o_1, o_2, \dots, o_t\}$ xảy ra và tại thời điểm $t$, hệ thống đang dừng ở trạng thái ẩn $s_i$.

Ý tưởng cốt lõi: Thay vì tính toán độc lập từng kịch bản (đường đi) của trạng thái ẩn, Pha Forward sử dụng chiến lược quy hoạch động. Tại mỗi bước thời gian $t$, nó gom tất cả các khả năng từ quá khứ lại thành một giá trị duy nhất (gọi là biến Forward). Giá trị này sau đó được "đẩy" sang bước $t+1$.

Nói cách khác, xác suất ở hiện tại là tổng hợp của: (Xác suất đã tích lũy ở quá khứ) $\times$ (Xác suất chuyển trạng thái) $\times$ (Xác suất phát ra quan sát hiện tại).

Giải thích ký hiệu

Biến Forward $\alpha_t(i)$: là xác suất chúng ta nhìn thấy chuỗi quan sát từ đầu đến thời điểm $t$, và tại đúng thời điểm $t$ đó, hệ thống đang dừng ở trạng thái ẩn $i$.

• $q_t = s_i$: Trạng thái ẩn tại thời điểm $t$ là $s_i$.

• $o_1, \dots, o_t$: Các quan sát đã thu thập được từ bắt đầu đến hiện tại.

• $\lambda$: Bộ tham số mô hình $(A, B, \pi)$:

  • $\pi_i = P(q_1=s_i)$ Xác suất trạng thái đầu tiên là $s_i$.

  • $a_{ij} = P(q_{t+1} = s_j \mid q_t = s_i)$: Xác suất chuyển từ ẩn $i$ sang ẩn $j$.

  • $b_i(v_k) = P(o_t = v_k \mid q_t = s_i)$: Xác suất trạng thái ẩn $i$ phát ra biểu hiện $v_k$.

Quy trình tính toán

Bước 1: Khởi tạo - Tại $t=1$. Ta tính xác suất cho từng trạng thái ẩn tại thời điểm bắt đầu.

Giải thích: (Khả năng bắt đầu tại trạng thái $i$) $\times$ (Khả năng trạng thái $i$ đó phát ra quan sát đầu tiên $o_1$).

Bước 2: Đệ quy - Từ $t \to t+1$

Để tính được $\alpha_{t+1}(j)$ (xác suất tại bước tiếp theo), ta cần thu thập toàn bộ "di sản" từ tất cả các trạng thái $i$ ở bước trước đó.

• Phần Dự đoán: Tổng hợp xác suất từ mọi trạng thái $i$ trước, nhân với xác suất chuyển sang trạng thái $j$ hiện tại.

• Phần Đối chiếu: Sau khi dự đoán xong, ta nhân với xác suất trạng thái $j$ đó thực sự phát ra quan sát $o_{t+1}$ mà ta đang thấy.

Bước 3: Kết thúc (Termination) - Tại $t=T$

Tổng xác suất của toàn bộ chuỗi quan sát chính là tổng các $\alpha$ tại bước cuối cùng:

Forward - Tính toán cụ thể

Dựa trên ví dụ tâm trạng (Vui/Buồn) và hành động (Cười/Khóc):

• $\pi = [0.8, 0.2]$ (Vui: 0.8, Buồn: 0.2)

• $A = \begin{pmatrix} 0.6 & 0.4 \\ 0.3 & 0.7 \end{pmatrix}$: Nếu hôm nay vui thì xác suất mai vui là 60% và buồn 40%. Nếu hôm nay buồn thì xác suất mai vui là 30% và vẫn buồn là 70%.

• $B = \begin{pmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{pmatrix}$: Nếu đang vui, xác suất cười là 90%, xác suất khóc là 10%. Nếu đang buồn, xác xuất cười là 20%, khóc là 80%.

• Yêu cầu: Tính $\alpha$ cho chuỗi 2 ngày đều Cười ($O_1, O_1$).

Bước 1: Khởi tạo (Initialization) tại $t=1$

Tại thời điểm bắt đầu, xác suất chỉ phụ thuộc vào vector khởi tạo $\pi$ và khả năng phát xạ của trạng thái đó ra quan sát đầu tiên ($O_1$).

• $\alpha_1(Vui)$: Hôm nay khởi đầu vui (0.8) và người đó cười (0.9).

  $$\alpha_1(1) = \underbrace{P(q_1=Vui)}_{\pi_1}\times \underbrace{P( O_1=Cười |q_1=Vui)}_{b_1(o_1)}= 0.8 \times 0.9 = \mathbf{0.72}$$

• $\alpha_1(Buồn)$: Hôm nay khởi đầu buồn (0.2) và người đó cười (0.2), với các định nghĩa về $\pi_i$ và $b_i(o_j)$ như trên

  $$\alpha_1(2) = \pi_2 \times b_2(o_1) = 0.2 \times 0.2 = \mathbf{0.04}$$

Bước 2: Bước tiến đệ quy (Induction) tại $t=2$

Để tính xác suất cho ngày thứ 2, ta phải xét mọi con đường từ ngày 1 dẫn đến ngày 2.

Công thức tổng quát:

• Tính $\alpha_2(Vui)$: (Khả năng ngày 2 người đó Vui và Cười)

  • Đến từ ngày 1 Vui: $\alpha_1(Vui) \times a_{11} = 0.72 \times 0.6 = 0.432$

  • Đến từ ngày 1 Buồn: $\alpha_1(Buồn) \times a_{21} = 0.04 \times 0.3 = 0.012$

  • Tổng xác suất ẩn: $0.432 + 0.012 = 0.444$

  • Nhân với xác suất phát xạ (Ngày 2 Cười): $0.444 \times 0.9 = \mathbf{0.3996}$

• Tính $\alpha_2(Buồn)$: (Khả năng ngày 2 người đó Buồn và Cười)

  • Đến từ ngày 1 Vui: $\alpha_1(Vui) \times a_{12} = 0.72 \times 0.4 = 0.288$

  • Đến từ ngày 1 Buồn: $\alpha_1(Buồn) \times a_{22} = 0.04 \times 0.7 = 0.028$

  • Tổng xác suất ẩn: $0.288 + 0.028 = 0.316$

  • Nhân với xác suất phát xạ (Ngày 2 Cười): $0.316 \times 0.2 = \mathbf{0.0632}$

Bước 3: Kết thúc (Termination)

Tổng xác suất của toàn bộ chuỗi quan sát $P(O|\lambda)$ chính là tổng của tất cả các biến Forward tại bước thời gian cuối cùng ($T=2$).

Kết luận: Với mô hình này, xác suất để bạn bắt gặp chuỗi hành động "Cười - Cười" trong 2 ngày liên tiếp là 46.28%. Đây chính là kết quả của bài toán Đánh giá.

Pha Backward (Xác suất lùi): Cơ chế lan truyền ngược

Mục tiêu: Tính xác suất $\beta_t(i)$ – xác suất sẽ nhìn thấy phần còn lại của chuỗi quan sát từ thời điểm $t+1$ đến hết, với điều kiện hệ thống đang ở trạng thái ẩn $s_i$ tại thời điểm $t$.

Ý tưởng cốt lõi: Pha Backward bắt đầu từ điểm kết thúc của chuỗi thời gian và đi ngược về quá khứ. Nó trả lời câu hỏi: "Nếu bây giờ tôi đang ở trạng thái này, thì khả năng tôi sẽ thấy những quan sát sắp tới là bao nhiêu?" thông qua các bước:

• Chuyển đi: Thử nhảy sang tất cả các trạng thái $j$ có thể có vào ngày mai ($a_{ij}$).

• Phát xạ: Tại mỗi trạng thái $j$ đó, "phát" ra quan sát thực tế của ngày mai ($b_j(o_{t+1})$).

• Kế thừa: Nhân với niềm tin về tương lai xa hơn nữa mà trạng thái $j$ đó đang nắm giữ ($\beta_{t+1}(j)$).

Trong khi Forward cộng dồn mọi thứ đã qua, Backward chuẩn bị sẵn xác suất cho những gì chưa đến. Khi kết hợp cả hai tại cùng một thời điểm $t$, ta có cái nhìn toàn diện: Quá khứ dẫn đến $t$ (Forward) $\times$ Tương lai bắt đầu từ $t$ (Backward).

Giải thích ký hiệu

Nếu $\alpha$ là những gì đã tích lũy, thì $\beta_t(i)$ là một xác suất có điều kiện (Conditional Probability) dội ngược từ tương lai. Nó đại diện cho kịch bản:

"Giả sử tại thời điểm $t$, tôi đang ở trạng thái ẩn $s_i$, thì xác suất để tôi nhìn thấy toàn bộ chuỗi quan sát còn lại (từ $t+1$ đến hết) là bao nhiêu?"

• $q_t = s_i$: Giả thiết hệ thống đang ở trạng thái $s_i$ tại bước $t$.

• $o_{t+1}, \dots, o_T$: Chuỗi các quan sát xảy ra sau thời điểm $t$.

• Lưu ý: $\beta_t(i)$ không bao gồm quan sát tại chính thời điểm $t$ ($o_t$).

Quy trình tính toán

Bước 1: Khởi tạo - Tại thời điểm cuối cùng $T$

Tại bước cuối cùng, phía sau không còn quan sát nào nữa. Theo quy ước toán học để làm điểm tựa cho các bước nhân ngược phía sau:

Bước 2: Đệ quy ngược (Induction) - Từ $t+1$ về $t$

Để tính $\beta_t(i)$, ta thu thập thông tin từ tất cả các trạng thái $j$ ở bước kế tiếp:

Backward - Tính toán cụ thể

Tiếp tục với ví dụ: Vui ($S_1$) / Buồn ($S_2$) và chuỗi quan sát Cười ($O_1$) - Cười ($O_1$).

Thông số giữ nguyên:

• $A = \begin{pmatrix} 0.6 & 0.4 \\ 0.3 & 0.7 \end{pmatrix}$ ; $B = \begin{pmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{pmatrix}$

Bước 1: Khởi tạo tại $t=T$ (ngày 2)

Tại thời điểm cuối cùng của chuỗi, không còn quan sát nào ở tương lai để dự báo. Do đó, theo định nghĩa toán học, tất cả các trạng thái đều có xác suất kết thúc bằng 1.

• $\beta_2(Vui) = \mathbf{1.0}$

• $\beta_2(Buồn) = \mathbf{1.0}$

Bước 2: Bước lùi đệ quy (Induction) về $t=1$ (ngày 1)

Ta tính xác suất để từ trạng thái hiện tại (Ngày 1), hệ thống chuyển sang ngày 2, phát ra quan sát ngày 2 ($O_1$) và tiếp tục chuỗi tương lai.

Công thức tổng quát:

Tính $\beta_1(Vui)$: (Nếu ngày 1 Vui, khả năng ngày 2 thấy "Cười" là bao nhiêu?)

• Chuyển sang ngày 2 Vui: $a_{11} \times b_{Vui}(O_1) \times \beta_2(Vui) = 0.6 \times 0.9 \times 1 = 0.54$

• Chuyển sang ngày 2 Buồn: $a_{12} \times b_{Buồn}(O_1) \times \beta_2(Buồn) = 0.4 \times 0.2 \times 1 = 0.08$

• Tổng: $\beta_1(Vui) = 0.54 + 0.08 = \mathbf{0.62}$

Tính $\beta_1(Buồn)$: (Nếu ngày 1 Buồn, khả năng ngày 2 thấy "Cười" là bao nhiêu?)

• Chuyển sang ngày 2 Vui: $a_{21} \times b_{Vui}(O_1) \times \beta_2(Vui) = 0.3 \times 0.9 \times 1 = 0.27$

• Chuyển sang ngày 2 Buồn: $a_{22} \times b_{Buồn}(O_1) \times \beta_2(Buồn) = 0.7 \times 0.2 \times 1 = 0.14$

• Tổng: $\beta_1(Buồn) = 0.27 + 0.14 = \mathbf{0.41}$

Tại sao chúng ta cần Pha Backward?

Nếu chỉ dừng lại ở bài toán Đánh giá (xác suất toàn chuỗi), pha Forward là đủ. Tuy nhiên, pha Backward là bắt buộc cho bài toán Làm mịn:

Giả sử ta muốn biết xác suất người đó thực sự Vui vào Ngày 1.

• Theo Forward ($\alpha_1$): Ta chỉ biết thông tin "Ngày 1 Cười" $\implies$ $P \approx 94.7\%$.

• Kết hợp Backward ($\beta_1$): Ta có thêm thông tin "Ngày 2 cũng Cười". Vì xác suất lùi từ trạng thái Vui ($\beta_1=0.62$) cao hơn hẳn trạng thái Buồn ($\beta_1=0.41$), thông tin tương lai này "ủng hộ" giả thuyết người đó đang Vui ở ngày 1.

Kết quả sau khi làm mịn:

Kết luận: Pha Backward cho phép thuật toán "nhìn lại quá khứ bằng lăng kính của tương lai". Điều này cực kỳ quan trọng trong các bài toán như nhận dạng tiếng nói hoặc phân tích gen, nơi mà một tín hiệu tại thời điểm $t$ chỉ có thể được hiểu đúng nếu ta biết những tín hiệu xảy ra sau đó.

Kết luận

Thuật toán Forward-Backward là minh chứng cho việc tối ưu hóa tính toán thông qua lập trình động. Thay vì bùng nổ tổ hợp các nhánh xác suất, ta quản lý thông tin qua hai luồng thời gian đối nghịch. Đây là tiền đề không thể thiếu cho thuật toán Baum-Welch để huấn luyện các hệ thống máy học phức tạp dựa trên dữ liệu chuỗi thời gian.