Thuật toán Viterbi: Giải mã con đường tối ưu trong Hidden Markov Model

Trong các bài toán như nhận dạng tiếng nói, dịch máy hay phân tích gen, chúng ta không chỉ muốn biết xác suất của một chuỗi quan sát, mà quan trọng hơn, chúng ta cần biết: Chuỗi trạng thái ẩn nào có khả năng cao nhất đã tạo ra quan sát đó? Thuật toán Viterbi chính là câu trả lời tối ưu cho bài toán giải mã (Decoding) này.

Viterbi vs. Forward: Sự khác biệt về mục tiêu

Dễ nhầm lẫn giữa hai thuật toán này vì cả hai đều dùng kỹ thuật lập trình động trên lưới trellis, nhưng bản chất toán học lại khác nhau:

• Thuật toán Forward: Tính TỔNG xác suất của tất cả các con đường khả thi dẫn đến một trạng thái.

• Thuật toán Viterbi: Chỉ chọn con đường LỚN NHẤT (MAX) dẫn đến trạng thái đó.

Nếu Forward trả lời câu hỏi: "Xác suất là bao nhiêu?", thì Viterbi trả lời câu hỏi: "Kịch bản nào là đúng nhất?".

Ý tưởng cốt lõi

Giả sử ta có $N$ trạng thái ẩn và chuỗi quan sát dài $T$ bước.

• Số lượng con đường khả thi là $N^T$.

• Với $N=10$ và $T=100$, số con đường là $10^{100}$ (lớn hơn số nguyên tử trong vũ trụ). Việc kiểm tra từng con đường để tìm cái tốt nhất là bất khả thi.

Ý tưởng chủ đạo của Viterbi đến từ Nguyên lý tối ưu Bellman (The Bellman Optimality Principle):

Nếu con đường tối ưu đi qua trạng thái $s_i$ tại thời điểm $t$, thì phần con đường từ điểm bắt đầu đến $(s_i, t)$cũng phải là con đường tối ưu nhất để đến được đó.

Ví dụ: Nếu đường đi ngắn nhất từ Hà Nội đến TP.HCM đi qua Đà Nẵng, thì chắc chắn đoạn từ Hà Nội đến Đà Nẵng trong lộ trình đó cũng phải là đoạn đường ngắn nhất vì nếu có đường nào ngắn hơn đến Đà Nẵng, ta đã thay nó vào để tổng quãng đường ngắn hơn nữa rồi.

Tại mỗi thời điểm $t$, đối với mỗi trạng thái $s_j$:

• Có $N$ con đường từ các trạng thái ở bước $t-1$ dẫn đến nó.

• Viterbi sẽ tính toán xác suất của cả $N$ nhánh này.

• Quyết định quan trọng: Nó chỉ giữ lại duy nhất một nhánh có xác suất cao nhất (con đường "sống sót") và vứt bỏ hoàn toàn $N-1$ nhánh còn lại.

• Nó ghi chú lại: "Để đến $s_j$ lúc này một cách tốt nhất, tôi đã đi từ trạng thái $s_i$ ở bước trước" (đây chính là Backpointer).

Ý tưởng này biến một bài toán có độ phức tạp lũy thừa $O(N^T)$ trở thành bài toán có độ phức tạp tuyến tính theo thời gian $O(N^2 T)$.

• Tính cục bộ: Tại bất kỳ thời điểm nào, máy tính cũng chỉ cần lưu trữ $N$ giá trị xác suất tốt nhất và $N$ con đường dẫn đến chúng.

• Không nhìn lại: Một khi một nhánh đã bị loại bỏ ở bước $t$, nó sẽ không bao giờ được xem xét lại ở bước $t+1, t+2...$. Điều này giúp tiết kiệm tài nguyên khổng lồ.

Công thức & Bước thực hiện

Để tiện theo dõi, mình sẽ vẫn giữ hệ thống ký hiệu được sử dụng xuyên suốt qua các bài viết HMM và Forward-Backward algorithm

Mạng Trellis (Trellis Diagram)

Đây là một sơ đồ không gian - thời gian dùng để biểu diễn các trạng thái ẩn và các bước chuyển tiếp của chúng. Mạng này đóng vai trò làm bản đồ vẽ lại tất cả các con đường ta có thể đi trong mê cung trạng thái của HMM theo thời gian. Một mạng Trellis được xây dựng dựa trên hai trục:

• Trục tung (Vertical): Biểu diễn tập hợp các trạng thái ẩn ($s_1, s_2, \dots, s_N$). Mỗi trạng thái tại một thời điểm được vẽ như một nút (node).

• Trục hoành (Horizontal): Biểu diễn thời gian ($t=1, t=2, \dots, t=T$).

Tại mỗi mốc thời gian $t$, chúng ta vẽ lại toàn bộ các trạng thái ẩn có thể có. Các đường nối giữa các nút ở thời điểm $t$ và $t+1$ biểu diễn xác suất chuyển trạng thái ($a_{ij}$). Từ đó, ta đã biến một bài toán xác suất thành một bài toán tìm đường trên đồ thị. Để thực hiện thuật toán, chúng ta cần quản lý hai loại thông tin tại mỗi nút trên mạng Trellis: Trọng số tốt nhất và Dấu vết con đường.

Biến Viterbi $\delta_t(i)$

$\delta_t(i)$ đại diện cho xác suất của con đường "sáng giá" nhất kết thúc tại trạng thái $s_i$ ở thời điểm $t$. Công thức:

Ý nghĩa ở đây là trong số hàng nghìn kịch bản có thể dẫn đến việc đang ở trạng thái $s_i$ lúc này, $\delta_t(i)$ chỉ ghi lại điểm số của kịch bản có xác suất cao nhất.

Biến lưu vết: $\psi_t(i)$

$\psi_t(i)$ là "quyển sổ nhật ký" giúp chúng ta thực hiện việc truy hồi (Backtracking). Công thức:

Để ý ở đây $\psi_t(i)$ không lưu giá trị xác suất, mà lưu tên (chỉ số) của trạng thái ở bước $t-1$ đã dẫn đến kết quả Max cho trạng thái $i$ ở bước $t$.

Nôm na: "Nếu tôi đang ở trạng thái $i$ lúc này, thì ở bước trước đó, tôi đến từ đâu là tốt nhất?"

Ba bước của thuật toán

Thuật toán vận hành theo quy trình tịnh tiến từ trái sang phải trên mạng Trellis:

Bước 1: Khởi tạo - Tại $t=1$

Vì không có quá khứ, xác suất tốt nhất chính là xác suất bắt đầu:

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

Đây là bước chọn lọc xác suất tốt nhất chọn lọc:

• $\max$: Chọn ra giá trị xác suất lớn nhất từ các trạng thái bước trước.

• $\text{argmax}$: Ghi lại ID của trạng thái bước trước đã tạo ra cái $\max$ đó.

• Các thành phần của bộ tham số $\lambda = (A,B,\pi)$:

  • $a_{ij}$ : Phần tử của ma trận chuyển trạng thái $A$ đại diện cho xác suất nhảy từ trạng thái ẩn $i \to j$

  • $b_j(o_t)$: Xác suất trạng thái $i$) biểu hiện ra quan sát $o_t$

  • $\pi_i$: Xác suất bắt đầu trạng thái tại $i$

Bước 3: Kết thúc và Truy hồi

• Xác suất con đường tốt nhất: $P^* = \max_{1 \le i \le N} [\delta_T(i)]$

• Trạng thái cuối cùng tối ưu: $q_T^* = \text{argmax}_{1 \le i \le N} [\delta_T(i)]$

• Truy hồi ngược: $q_t^* = \psi_{t+1}(q_{t+1}^*)$ với $t = T-1, T-2, \dots, 1$.

Tính toán cụ thể

Mình vẫn sử dụng lại bài toán và các giá trị đã dùng trong series này từ các bài trước: HMM và Forward-Backward algorithm

Bài toán

Quan sát đồng nghiệp trong 2 ngày liên tiếp và cả 2 ngày họ đều Cười ($o_1, o_2$).

Hệ thống tham số $\lambda$:

• Trạng thái ẩn: $S = \{Vui, Buồn\}$

• Vector khởi tạo: $\pi = [0.8, 0.2]$ (80% khả năng họ bắt đầu ngày mới vui vẻ).

• Ma trận chuyển trạng thái: $A = \begin{pmatrix} 0.6 & 0.4 \\ 0.3 & 0.7 \end{pmatrix}$ (Vui dễ duy trì 60%, nhưng Buồn thì lỳ lợm hơn với 70%).

• Ma trận phát xạ: $B = \begin{pmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{pmatrix}$ (Vui thì 90% sẽ Cười, Buồn vẫn có thể Cười gượng 20%).

Mục tiêu giải toán: Tìm chuỗi tâm trạng ẩn $Q^* = \{q_1, q_2\}$ có khả năng cao nhất đã dẫn đến chuỗi hành động "Cười - Cười". Chúng ta không tìm tổng xác suất, chúng ta tìm kịch bản logic nhất.

Các bước tính toán chi tiết

Chúng ta sẽ triển khai thuật toán qua mạng Trellis 2 bước thời gian.

Bước 1: Khởi tạo (Ngày 1 - $t=1$)

Tại ngày đầu tiên, ta tính xác suất tốt nhất để dừng ở mỗi trạng thái khi thấy họ Cười.

• $\delta_1(Vui)$: $\pi_{Vui} \times b_{Vui}(Cười) = 0.8 \times 0.9 = \mathbf{0.72}$

• $\delta_1(Buồn)$: $\pi_{Buồn} \times b_{Buồn}(Cười) = 0.2 \times 0.2 = \mathbf{0.04}$

• Lưu vết: $\psi_1(Vui) = 0$; $\psi_1(Buồn) = 0$ (Gốc tọa độ).

Bước 2: Đệ quy (Ngày 2 - $t=2$)

Khi quan sát thấy nụ cười thứ hai, ta phải tìm con đường tối ưu để "đến" được trạng thái của ngày hôm nay.

Ta xét 2 con đường dẫn đến "Vui" ở ngày 2: $\delta_2(Vui)$

• Từ Ngày 1 Vui: $\delta_1(Vui) \times a_{11} = 0.72 \times 0.6 = 0.432$

• Từ Ngày 1 Buồn: $\delta_1(Buồn) \times a_{21} = 0.04 \times 0.3 = 0.012$

• Chọn Max: $0.432$ (Đến từ trạng thái Vui ngày 1).

• Nhân phát xạ: $\delta_2(Vui) = 0.432 \times b_{Vui}(Cười) = 0.432 \times 0.9 = \mathbf{0.3888}$

• Ghi nhật ký: $\psi_2(Vui) = Vui$.

Tương tự, ta xét 2 con đường dẫn đến "Buồn" ở ngày 2: $\delta_2(Buồn)$

• Từ Ngày 1 Vui: $\delta_1(Vui) \times a_{12} = 0.72 \times 0.4 = 0.288$

• Từ Ngày 1 Buồn: $\delta_1(Buồn) \times a_{22} = 0.04 \times 0.7 = 0.028$

• Chọn Max: $0.288$ (Đến từ trạng thái Vui ngày 1).

• Nhân phát xạ: $\delta_2(Buồn) = 0.288 \times b_{Buồn}(Cười) = 0.288 \times 0.2 = \mathbf{0.0576}$

• Ghi nhật ký: $\psi_2(Buồn) = Vui$.

Bước 3: Kết thúc và Truy hồi

Đây là bước thu hoạch kết quả từ "quyển sổ nhật ký" $\psi$.

• Tìm điểm kết thúc tốt nhất ($t=2$):

  • So sánh $\delta_2(Vui) = 0.3888$ và $\delta_2(Buồn) = 0.0576$.

  • => Giá trị lớn nhất là 0.3888. Vậy trạng thái ẩn của Ngày 2 chắc chắn nhất là Vui.

• Dò ngược về Ngày 1:

  • Bạn đang ở Ngày 2 là Vui. Hãy xem nhật ký $\psi_2(Vui)$ ghi gì?

  • => $\psi_2(Vui) = Vui$. Vậy Ngày 1 người đó cũng là Vui.

Như vậy, chuỗi trạng thái ẩn tối ưu (Viterbi Path) là: Vui $\to$ Vui. Xác suất của con đường này là: 0.3888.

Vấn đề Underflow

Trong HMM, các giá trị xác suất ($\pi, a_{ij}, b_i$) luôn nằm trong khoảng $[0, 1]$. Khi tính toán các biến $\delta$ hay $\alpha$, chúng ta thực hiện phép nhân liên tiếp các số thập phân này qua từng bước thời gian $t$.

Ví dụ:

• Giả sử mỗi bước $t$, xác suất giảm đi khoảng $0.1$ ($10^{-1}$).

• Sau 100 bước thời gian ($T=100$), xác suất sẽ là $0.1^{100} = 10^{-100}$.

• Sau 400 bước thời gian, con số này có thể là $10^{-400}$.

Vấn đề là máy tính lưu trữ số thực (kiểu float64) có giới hạn dưới. Khi một số trở nên quá nhỏ (thường là nhỏ hơn khoảng $10^{-308}$ đối với chuẩn IEEE 754), máy tính không thể biểu diễn nó được nữa và sẽ tự động làm tròn về 0. Nếu chuỗi quan sát chỉ dài 5-10 bước, có thể không thấy Underflow. Nhưng trong nhận dạng tiếng nói (với hàng nghìn frame ảnh mỗi giây) hoặc phân tích chuỗi DNA, hiện tượng Underflow chắc chắn sẽ xảy ra.

Để giải quyết vấn đề này, thay vì nhân các xác suất, chúng ta sẽ cộng các Logarit của chúng. Dựa trên tính chất toán học:

• Các số cực nhỏ như $10^{-400}$ khi lấy Log sẽ trở thành các số âm có độ lớn vừa phải (khoảng $-921$). Máy tính xử lý con số $-921$ cực kỳ dễ dàng và chính xác.

• Phép toán Max vẫn giữ nguyên tính chất: Nếu $x > y$ thì $\log(x) > \log(y)$. Do đó, kết quả tìm con đường tối ưu không bị thay đổi.

Ta biến đổi công thức Viterbi sang miền log. Thay vì dùng $\delta_t(i)$, chúng ta dùng $V_t(i) = \log(\delta_t(i))$.

• Khởi tạo:
  

  $$V_1(i) = \log(\pi_i) + \log(b_i(o_1))$$

• Đệ quy (Thay $\times$ bằng $+$ và giữ nguyên $\max$):
  

  $$V_{t+1}(j) = \left[ \max_{1 \le i \le N} (V_t(i) + \log(a_{ij})) \right] + \log(b_j(o_{t+1}))$$