Thuật toán Viterbi
Ở bài viết trước, chúng ta đã nắm được cấu trúc của một Hidden Markov Model, nhưng vẫn còn một câu hỏi chúng ta chưa giải quyết được ở cuối bài: Nếu bạn nhìn thấy một chuỗi biểu hiện của An trong 3 ngày liên tiếp là ☹️ -> 😃 -> 😃, thì chuỗi thời tiết nào là hợp lý nhất đã xảy ra ở chỗ bạn An?
Vậy bài viết này sẽ giúp bạn gỡ nút thắt đó thông qua thuật toán Viterbi. Trước khi đi vào thuật toán, chúng ta hãy đi qua một số khái niệm liên quan trước nhé.
Với câu hỏi ở đầu bài, chuỗi thời tiết nào có khả năng cao nhất đã tạo ra 3 quan sát đó? Có rất nhiều tổ hợp có thể xảy ra (Mưa-Nắng-Nắng, Mưa-Mây-Nắng, Nắng-Nắng-Nắng…) và nhiệm vụ chọn ra chuỗi trạng thái ẩn khớp nhất với chuỗi quan sát được gọi là bài toán Decoding (bài toán giải mã).
Nếu tính toán thủ công bằng cách liệt kê mọi tổ hợp, máy tính sẽ sớm quá tải khi chuỗi quan sát dài lên. Khi đó, thuật toán Viterbi giải quyết việc này bằng quy hoạch động (Dynamic Programming), tức là thay vì nhìn lại toàn bộ quá trình từ đầu, thì tại mỗi bước (mỗi ngày), thuật toán chỉ giữ lại con đường “tốt nhất” để đi đến trạng thái hiện tại.
Thuật toán Viterbi
Thuật toán Viterbi hoạt động bằng cách lặp lại việc tính toán xác suất lớn nhất của các đường đi dẫn đến từng trạng thái tại mỗi thời điểm, lưu trữ các giá trị này, sau đó truy vết ngược (backtracking) để xác định chuỗi trạng thái ẩn có xác suất cao nhất.
Bước 1: Khởi tạo (Initialization)
Bước này thiết lập các xác suất ban đầu cho các trạng thái khởi đầu, dựa trên xác suất trạng thái ban đầu và xác suất biểu hiện ứng với quan sát đầu tiên.
V1(j) = πj.bj (o1) ∀j ∈ {1, …, N}
Bước 2: Đệ quy (Recursion)
Để tìm điểm số cao nhất cho trạng thái j ở ngày hôm nay, thuật toán sẽ nhìn lại tất cả các trạng thái i của ngày hôm qua, nhân với xác suất chuyển đổi và xác suất biểu hiện
Vt(j) = maxi [Vt-1 (i).aij.bj (ot)] ∀j ∈ {1, …, N}
Bước 3: Truy vết ngược (Backtracking)
Sau khi đã tính đến ngày cuối cùng, chúng ta sẽ chọn trạng thái ẩn có xác suất cao nhất ở bước cuối. Từ đó, chúng ta men theo các dấu vết đã lưu ở Bước 2 để đi ngược lại từ cuối về đầu.
P* = maxjVT (j)
Ví dụ cụ thể
Xét lại ví dụ ở bài viết trước, chúng ta sẽ cùng giải quyết bài toán này bằng thuật toán Viterbi thông qua Trellis Diagram để dễ hình dung hơn. Trong Trellis Diagram, mỗi cột là một mốc thời gian, còn mỗi hàng là một trạng thái ẩn.
Ma trận xác suất chuyển trạng thái:
Ma trận xác suất biểu hiện:
Xác suất khởi tạo:
Bài toán cần giải quyết:
Bước 1: Khởi tạo xác suất cho các trạng thái ở quan sát đầu tiên (Buồn)
Bước 2: Đệ quy
Sau khi có xác suất ở cột đầu tiên, ta tiếp tục đi tính xác suất cho các cột tiếp theo bằng công thức đệ quy đã nêu ở trên:
Sau khi đã tính xong, ta nhận thấy vào ngày thứ hai, nếu trời mưa thì xác suất cao nhất cho thời tiết của ngày hôm trước là trời có nhiều mây, và ta cũng chỉ giữ lại đường đi có xác suất cao nhất này. Tương tự như trên, ta tiếp tục tính nếu ngày thứ hai trời mây hay nắng thì đâu là thời tiết của ngày hôm trước.
Tiếp tục tính theo công thức trên với ngày thứ ba, ta sẽ có được kết quả như bên dưới:
Bước 3: Truy vết ngược
Vào ngày cuối cùng, ta thấy xác suất trời mưa xảy ra cao nhất, khi đó ta xác định được trời mưa vào ngày này. Từ đó, ta truy vết lại thời tiết nào vào hôm thứ hai đã dẫn đến trời mưa. Lúc này, ta xác định được vào ngày thứ hai xác suất trời mưa là cao nhất. Tiếp tục truy vết như vậy, ta lại thấy vào ngày đầu tiên trời nhiều mây.
Khi đó, chúng ta giải quyết được câu hỏi ở đầu bài: Nếu biểu hiện của bạn An trong 3 ngày liên tiếp là Buồn -> Vui -> Vui thì khả năng cao nhất thời tiết 3 ngày ở chỗ bạn An sẽ là Mây -> Mưa -> Mưa.
Ứng dụng
Thuật toán Viterbi không chỉ là lý thuyết khô khan mà còn được ứng dụng nhiều trong thực tế. Ví dụ, trong bài toán nhận diện giọng nói (Speech Recognition), khi bạn nói “Hey Siri”, sóng âm thanh mà điện thoại thu được rất nhiễu và khó phân biệt. Khi đó, các quan sát sẽ là các tín hiệu âm thanh, còn các trạng thái ẩn là các âm tiết (phonemes) hoặc từ vựng, và thuật toán sẽ tính toán chuỗi các từ có khả năng cao nhất khớp với đoạn âm thanh đó dựa trên quy luật ngôn ngữ.
Ngoài ra, Viterbi còn được ứng dụng trong bài toán gán nhãn từ loại (POS Tagging), thông tin liên lạc và truyền tin (mạng 4G/5G), phân tích bản đồ gen người, hay trong các hệ thống định vị.
Kết luận
Vậy là chúng ta đã đi qua được cách hoạt động của thuật toán Viterbi và những ứng dụng của nó trong đời sống. Thông qua ví dụ cụ thể, bạn chắc đã không còn gặp rắc rối hay khó hiểu khi nhìn vào các công thức toán học khô khan của thuật toán này nữa. Và bạn hãy nhớ là dù bạn đang sử dụng Siri để điều khiển điện thoại, tra cứu bản đồ gen hay chỉ đơn giản là gõ một dòng tin nhắn đúng chính tả, thuật toán Viterbi vẫn đang âm thầm giúp bạn “giải mã” thế giới xung quanh của bạn.