Báo Cáo Hidden Markov Models Fundamentals [PDF]

Zitiervorschau

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG KHOA QUỐC TẾ VÀ ĐÀO TẠO SAU ĐẠI HỌC ---------o0o---------

TIỂU LUẬN CÔNG CỤ TOÁN CHO CÔNG NGHỆ THÔNG TIN

ĐỀ TÀI HIDDEN MARKOV MODELS FUNDAMENTALS

Giảng viên: TS. Vũ Văn Thỏa Nhóm thực hiện: Trần Xuân Hòa (C) Nguyễn Xuân Giang Nguyễn Tấn Hải Nguyễn Văn Hoàng Phạm Thành Hoan

HÀ NỘI - 09/2019

MỤC LỤC

PHẦN I: DỊCH BÀI BÁO SANG TIẾNG VIỆT ........................................................ 3 1

Mô hình Markov ....................................................................................................... 3 1.1

2

Hai vấn đề của mô hình Markov ........................................................................ 4

1.1.1

Xác suất của một chuỗi trạng thái ............................................................... 4

1.1.2

Thiết lập tham số khả năng tối đa ............................................................... 5

Mô hình Markov ẩn .................................................................................................. 7 2.1

Ba vấn đề của một mô hình Markov ẩn ............................................................. 7

2.2

Xác suất của một chuỗi quan sát: Thủ tục tiến .................................................. 8

2.3

Thiết lập trạng thái khả năng tối đa: Thuật toán Viterbi .................................... 9

2.4

Tham số học: EM cho HMMs.......................................................................... 10

2.5

Đọc thêm .......................................................................................................... 14

PHẦN II: PHÂN TÍCH VÀ ĐÁNH GIÁ ................................................................... 15 1

2

Các bài toán cơ bản trong HMM ............................................................................ 15 1.1

Bài toán 1 – Probability Evaluation ................................................................. 15

1.2

Bài toán 2 – “Optimal” State Sequence ........................................................... 18

1.3

Bài toán 3 – Parameter Estimation ................................................................... 20

Ví dụ cụ thể sử dụng thuật toán Viterbi .................................................................. 21 2.1

Xây dựng cấu trúc dữ liệu cho INPUT và OUTPUT ....................................... 24

2.2

Ưu - Nhược điểm của thuật toán Viterbi ......................................................... 24

2.3

Các lớp bài toán tương tự ................................................................................. 25

PHẦN I: DỊCH BÀI BÁO SANG TIẾNG VIỆT NHỮNG NGUYÊN TẮC CƠ BẢN VỀ MÔ HÌNH MARKOV ẨN Daniel Ramage CS229 Section Notes Ngày 01 tháng 12 năm 2007 LỜI GIỚI THIỆU Làm thế nào chúng ta có thể áp dụng phương pháp học máy (machine learning) cho các dữ liệu dạng chuỗi của các quan sát thay đổi theo thời gian? Ví dụ, chúng ta có thể quan tâm việc khám phá chuỗi các từ mà một người nào đó nói dựa trên bản ghi âm phần nói chuyện của họ. Hoặc chúng ta có thể muốn gán nhãn từ loại của bài nói chuyện. Ghi chú này cung cấp phần giới thiệu toán học toàn diện cho mô hình Markov - một phương thức lập luận về trạng thái theo thời gian, và mô hình Markov ẩn - áp dụng khi chúng ta muốn trích xuất một chuỗi trạng thái từ một chuỗi các quan sát. Phần cuối cùng bao gồm một số nguồn tham khảo thể hiện về mô hình này theo các góc độ khác. 1

Mô hình Markov

Cho tập trạng thái S = {s1, s2,… , s|S|} chúng ta có thể quan sát một chuỗi thời gian 𝒵⃗  ST. Ví dụ, chúng ta có các trạng thái thời tiết S = {sun,cloud, rain} với |S| = 3 và quan sát thời tiết trong một vài ngày {z1 = ssun; z2 = scloud; z3 = scloud; z4 = srain; z5 = scloud} với T = 5. Các trạng thái thời tiết được quan sát trong ví dụ đại diện cho kết quả đầu ra của quá trình ngẫu nhiên theo thời gian. Nếu không có thêm giả định nào, trạng thái sj tại thời điểm t có thể là một khả năng của bất kỳ biến nào, bao gồm tất cả các trạng thái từ thời điểm 1 đến t-1 và có thể là nhiều biến khác mà chúng ta thậm chí không mô hình chúng. Tuy nhiên, ta sẽ thực hiện hai giả định Markov nhằm giúp chúng ta dễ dàng xử lý chuỗi thời gian. The LIMITED HORIZON ASSUMPTION - Giả định phạm vi hạn chế là giả sử rằng xác suất của một trạng thái tại thời điểm t chỉ phụ thuộc vào trạng thái tại thời điểm t-1. Về mặt trực quan, giả định này chỉ ra rằng trạng thái tại thời điểm t biểu thị tóm tắt tương đối đầy đủ trạng thái trước đó để dự đoán khả năng sẽ có thể xảy ra trong tương lai. Công thức: P (zt|zt-1, zt-2,…, z1) = P(zt|zt-1) The STATIONARY PROCESS ASSUMPTION - Giả định tiến trình tĩnh, giả thiết rằng phân phối có điều kiện của trạng thái theo sau trạng thái hiện tại không thay đổi theo thời gian. Công thức: P (zt|zt-1) = P (z2|z1); t ∈ 2…T

3

Quy ước trạng thái ban đầu chính là quan sát đầu tiên z0 s0, với s0 thể hiện phân phối xác suất ban đầu của trạng thái tại thời điểm 0. Kí hiệu thuận tiện này cho phép chúng ta mã hóa một cách chính xác về tiền xác suất của quan sát trạng thái thực đầu tiên z1 là P(z1|z0). Lưu ý P(zt|zt-1,…, z1) = P(zt|zt-1,…, z1; z0) vì ta đã định nghĩa z0 = s0 cho chuỗi trạng thái bất kỳ nào. (Một số thể hiện khác của mô hình Markov ẩn - HMMs đôi khi biểu diễn tiền xác suất này bằng một véc tơ ℝ|𝑆| ) Ta tham số hóa những chuyển dịch này bằng cách xác định một ma trận chuyển trạng thái A∈ℝ(|S| + 1)x(|S| + 1). Giá trị Aij là xác suất chuyển từ trạng thái I đến trạng thái j tại thời điểm t bất kỳ. Với ví dụ về thời tiết ở trên, chúng ta có ma trận chuyển đổi sau:

Lưu ý rằng những con số mà tác giả đã thiết lập này biểu thị trực quan rằng các thời tiết có khả năng tự tương quan: nghĩa là nếu trời nắng nó sẽ có xu hướng tiếp tục nắng, nhiều mây sẽ tiếp tục nhiều mây,... Mô hình này phổ biến trong nhiều mô hình Markov và có thể được quan sát như là đường chéo chính trong ma trận chuyển đổi. Chú ý trong ví dụ này, xác suất chuyển đổi từ trạng thái khởi tạo s0 đến mỗi trạng thái còn lại là không thay đổi. 1.1 Hai vấn đề của mô hình Markov Kết hợp các giả định Markov với các tham số của ma trận chuyển trạng thái A, ta có thể trả lời hai vấn đề cơ bản về một chuỗi các trạng thái trong chuỗi Markov. Thứ nhất, xác suất của một chuỗi trạng thái cụ thể 𝒵⃗ là gì? Và, làm thế nào chúng ta ước lượng các tham số của ma trận A để có thể tối đa hóa khả năng của một chuỗi quan sát 𝒵⃗ ? 1.1.1 Xác suất của một chuỗi trạng thái Chúng ta có thể tính toán xác suất một chuỗi trạng thái cụ thể 𝒵⃗ bằng cách sử dụng quy tắc dây chuyền (chain rule) của xác suất: P(𝑧⃗) = P(zt, zt-1,…,z1; A) = P(zt, zt-1,…, z1, z0; A) = P(zt|zt-1, zt-2,…, z1; A)P(zt-1|zt-2,…,z1; A)…P(z1|z0; A) = P(zt|zt-1; A)P(zt-1|zt-2; A)…P(z2|z1; A)P(z1|z0; A) = ∏𝑇𝑡=1 𝑃(zt|zt-1; A) = ∏𝑇𝑡=1 𝐴zt-1 zt

4

Ở dòng thứ hai ta đặt z0 làm xác suất đầu mối ban đầu, vì ta đã định nghĩa z0 ở trên. Dòng thứ ba đúng với bất kỳ phân phối nối tiếp nào bởi quy tắc dây chuyền xác suất hoặc áp dụng lặp đi lặp lại các quy tắc Bayes. Dòng thứ tư dựa trên giả định Markov và dòng cuối cùng thể hiện các quy tắc như một yếu tố trong ma trận chuyển đổi A. Hãy tính xác suất của chuỗi thời gian trong ví dụ trước đó. Chúng ta tính P(z1 = ssun, z2 = scloud, z3 = srain, z4 = srain, z5 = scloud) như sau: P(ssun|s0) P(scloud|ssun) P(srain|scloud) P(srain|srain) P(scloud|srain) = .33 *.1 *.2* .7* .2. 1.1.2 Thiết lập tham số khả năng tối đa Từ một khía cạnh nghiên cứu, chúng ta có thể đi tìm cách để tìm ra các tham số của A để tối đa hóa khả năng xảy ra của chuỗi các quan sát 𝒵⃗ . Điều này tương ứng với tìm kiếm các khả năng chuyển từ sunny sang cloudy so với từ sunny sang sunny,… để tạo ra một tập các quan sát có khả năng nhất. Hãy xác định log-likelihood của một mô hình Markov.

Ở dòng cuối cùng, ta sử dụng một hàm chỉ thị có giá trị 1 khi điều kiện thỏa mãn và ngược lại có giá trị 0 để chọn ra chuyển dịch được quan sát tại mỗi bước thời gian. Khi giải quyết vấn đề tối ưu hóa này, điều quan trọng là phải đảm bảo rằng các thông số A được tìm ra vẫn tạo ra một ma trận chuyển đổi hợp lệ. Đặc biệt, cần phải tuân thủ rằng phân bố xác suất của các trạng thái i luôn luôn có tổng bằng 1 và tất cả các phần tử của A là không âm. Ta có thể giải quyết vấn đề tối ưu hóa này bằng phương pháp nhân tử Lagrange. max 𝑙(𝐴) 𝐴

|𝑆|

𝑠. 𝑡.

∑ 𝐴𝑖𝑗 = 1, 𝑖 = 1. . |𝑆| 𝑗=1

𝐴𝑖𝑗 ≥ 0, 𝑖, 𝑗 = 1. . |𝑆| Vấn đề tối ưu hóa ràng buộc này có thể được giải quyết dạng khép kín bằng phương pháp nhân tử Lagrange. Ta sẽ đưa các ràng buộc bình đẳng vào phương pháp Lagrange, nhưng ràng buộc bất bình đẳng có thể được bỏ qua, dù sao thì giải pháp tối ưu này sẽ vận dụng những giá trị dương cho Aij. Từ đó chúng ta xây dựng công thức Lagrange như sau:

5

Lấy đạo hàm từng phần và đặt chúng bằng không, ta có:

Thế trở lại và thiết lập αi bằng 0:

Thay thế giá trị này của αi vào biểu thức chúng ta đã khởi tạo cho Aij ta thu được giá trị tham số khả năng cực đại cuối cùng cho Âij.

Công thức này mã hóa một trực quan đơn giản: xác suất khả năng tối đa của sự chuyển đổi từ trạng thái i đến trạng thái j bằng số lần chuyển từ i sang j chia cho tổng số lần ở trạng thái i. Nói cách khác, tham số khả năng tối đa tương ứng với tỷ số của thời gian ở trong trạng thái i và chuyển sang trạng thái j.

6

2

Mô hình Markov ẩn

Mô hình Markov là một khái niệm trừu tượng hữu ích đối với các dữ liệu chuỗi thời gian, nhưng không nắm bắt một tình huống rất phổ biến. Làm thế nào chúng ta có thể suy luận về một loạt các trạng thái nếu chúng ta không thể quan sát các trạng thái đó, thay vì chỉ có một hàm xác suất trạng thái. Đây là tình huống gán nhãn từ loại khi các từ được quan sát nhưng không biết từ loại, và nhận dạng giọng nói khi chuỗi âm thanh được quan sát nhưng không phải là các từ tạo ra nó. Ví dụ đơn giản, chúng ta hãy mượn đề xuất được thiết lập bởi Jason Eisner vào năm 2002 [1], “Ice Cream Climatory”. Tình huống: Bạn là một nhà khí tượng trong năm 2799, nghiên cứu lịch sử của sự nóng lên toàn cầu. Bạn có thể không tìm ra bất cứ hồ sơ nào về thời tiết ở Baltimore, nhưng bạn tìm được nhật ký của Jason Eisner, trong đó ghi lại chi tiết tôi đã ăn bao nhiêu kem mỗi ngày. Dựa vào đây bạn có thể chỉ ra điều gì về thời tiết mùa hè? Mô hình Markov ẩn có thể được sử dụng để giải quyết tình huống này. Chúng ta không quan sát chuỗi trạng thái thực tế (thời tiết mỗi ngày). Thay vào đó, chúng ta chỉ có thể quan sát một số kết quả được tạo ra bởi mỗi trạng thái (bao nhiêu kem đã ăn ngày hôm đó). Về hình thức, một mô hình Markov là một mô hình Markov mà chúng ta có một chuỗi các kết quả đầu ra được quan sát 𝓍 ={𝓍1, 𝓍2, …, 𝓍T}rút ra từ tập đầu ra V = {v1, v2,…, v|V|}, nghĩa là 𝓍t V, t = 1..T. Trong phần trước, ta cũng thừa nhận sự tồn tại của các chuỗi trạng thái z = {z1, z2,…, zT} rút ra từ tập trạng thái S = {s1, s2,…, s|S|}, zt S, t = 1..T nhưng trong trường hợp này giá trị của các trạng thái không quan sát được. Sự chuyển dịch giữa các trạng thái i và j một lần nữa sẽ được thể hiện bởi các giá trị tương ứng trong ma trận chuyển dịch trạng thái Aij. Chúng ta cũng mô hình hóa xác suất tạo ra một quan sát đầu ra như một hàm của trạng thái ẩn. Để làm như vậy, chúng ta thực hiện giả định độc lập đầu ra - OUTPUT INDEPENDENCE ASSUMPTION và định nghĩa P(xt = vk|zt = sj)= P(xt = vk|x1,…, xT, z1,…, zT) = Bjk. Ma trận B mã hóa xác suất tạo ra trạng thái ẩn đầu ra vk được cho bởi trạng thái sj tại thời điểm tương ứng. Quay trở lại ví dụ về thời tiết, giả sử rằng bạn có một bản ghi chép về sự tiêu thụ kem trong giai đoạn bốn ngày: khi chỉ mã hóa số lượng kem tiêu thụ, nghĩa là: V={v1 = 1 ice cream, v2 = 2 ice creams, v3 = 3 ice creams}. Chúng ta phải giải quyết những vấn đề nào trong một HMM? 2.1 Ba vấn đề của một mô hình Markov ẩn Có ba vấn đề cơ bản của một HMM. Đó là: Xác suất của một chuỗi quan sát là gì (làm thế nào để chúng ta có khả năng biết được là 3, 2, 1, 2 cây kem đã được tiêu thụ)? Chuỗi các trạng thái có khả năng nhất tạo ra các quan sát là gì (thời tiết trong bốn ngày như thế nào)?

7

Và làm thế nào chúng ta có thể biết được cách giá trị các tham số A và B của một HMM đưa ra một vài dữ liệu? 2.2 Xác suất của một chuỗi quan sát: Thủ tục tiến Trong một HMM, chúng ta giả định rằng dữ liệu của chúng ta được tạo ra bởi quá trình như sau: thừa nhận sự tồn tại của một chuỗi trạng thái 𝒵⃗ dựa theo độ dài của chuỗi thời gian. Chuỗi trạng thái này được tạo ra bởi một mô hình Markov đã được tham số hóa bằng một ma trận chuyển đổi trạng thái A. Tại mỗi bước thời gian t, chúng ta chọn một đầu ra xt là một hàm trạng thái Zt. Vì vậy, để có được xác suất của một chuỗi các quan sát, chúng ta cần phải bổ sung thêm các khả năng của dữ liệu 𝓍⃗ cho mỗi chuỗi các trạng thái có thể.

Các công thức trên đúng cho bất kỳ phân phối xác suất nào. Tuy nhiên, các giả định HMM cho phép chúng ta giản lược các biểu thức như sau:

Tin tốt là, đây là một biểu thức đơn giản về các tham số. Biến đổi biểu thức theo các giả định HMM: giả định độc lập đầu ra, giả định Markov, và giả định quá trình tĩnh đều được sử dụng để có được dòng thứ hai. Tin xấu là tổng số vượt quá mỗi chỉ định có thể cho 𝒵⃗ . Bởi vì zt có thể lấy một trong những giá trị có thể của |S| tại từng bước thời gian, việc đánh giá trực tiếp tổng số này sẽ yêu cầu các phép tính O(|S|T). Thuật toán 1: Thủ tục tiến để tính αi(t) 1. Khởi tạo: αi(0) = A0i, i = 1..|S| 2. Đệ quy: May thay, một phương tiện nhanh hơn của máy tính P (𝑥⃗; A, B) là có thể thông qua một thuật toán lập trình động được gọi là thủ tục tiến. Đầu tiên, chúng ta hãy định nghĩa một lượng αi (t) = P(x1, x2,…, xt,zt = si; A, B). αi(t) biểu thị cho xác suất tổng của tất cả các quan sát theo thời gian t (bằng bất kỳ chỉ định trạng thái nào) và rằng chúng ta đang ở trong trạng thái si tại thời điểm t. Nếu chúng ta đã có một lượng như vậy, xác suất của loạt các quan sát đầy đủ P (𝑥⃗) có thể được biểu diễn như sau:

8

Thuật toán 2.2 biểu diễn một cách tính toán αi(t) hiệu quả. Tại mỗi bước thời gian chúng ta chỉ cần tính O(|S|), kết quả độ phức tạp thuật toán cuối cùng O(|S|.T) là tính xác suất tổng của một chuỗi trạng thái được quan sát P (𝑥⃗; A, B). Một thuật toán tương tự được gọi là thủ tục quay lui (BACKWARD PROCEDURE) có thể được sử dụng để tính toán xác suất tương tự βi (t) = P (xT, xT-1,…, xt + 1,zt = si; A, B). 2.3 Thiết lập trạng thái khả năng tối đa: Thuật toán Viterbi Một trong những vấn đề phổ biến nhất của một mô hình Markov ẩn là những gì mà chuỗi các trạng thái có khả năng nhất 𝒵⃗  ST đưa ra một chuỗi các kết quả đầu rađược quan sát 𝑥⃗ VT. Ta có:

Sự đơn giản hóa đầu tiên theo qui tắc Bayes và lần thứ hai dựa trên sự quan sát rằng mẫu số không phụ thuộc vào 𝒵⃗ . Một cách đơn giản, chúng ta có thể thử chỉ định mỗi khả năng có thể cho 𝒵⃗ và gán với một xác suất cao nhất trong mô hình của chúng ta. Tuy nhiên, điều này sẽ yêu cầu tính O(|S|T) để liệt kê một loạt các chỉ định có thể. Tại điểm này, bạn có thể cho rằng giải pháp lập trình động giống như thủ tục tiến có thể lưu giữ ngày. Chú ý rằng nếu bạn thay thế bởi giống với biểu thức đã được đưa ra ở thủ tục tiến.

thì nhiệm vụ hiện tại của chúng ta

Thuật toán 2: Ứng dụng Naive của EM cho HMMs Lặp lại cho đến khi hội tụ { (Bước E) Đối với mỗi gán nhãn có thể 𝒵⃗  ST , đặt Q(𝒵⃗ ) := p(𝒵⃗ |𝑥⃗; A,B) (Bước M) đặt:

9

Thuật toán Viterbi cũng giống như thủ tục tiến ngoại trừ việc thay vì theo dõi xác suất tổng tạo ra các quan sát cho đến bây giờ, chúng ta chỉ cần theo dõi xác suất cực đại và ghi nhận chuỗi trạng thái tương ứng của nó. 2.4 Tham số học: EM cho HMMs Vấn đề cuối cùng của một HMM là: đưa ra một tập hợp các quan sát, giá trị của xác suất chuyển đổi trạng thái A và xác suất phát sinh đầu ra B làm cho dữ liệu có khả năng nhất là gì? Ví dụ, giải quyết các tham số khả năng tối đa dựa trên một tập dữ liệu nhận dạng giọng nói sẽ cho phép chúng ta huấn luyện HMM một cách hiệu quả trước khi yêu cầu chỉ định các trạng thái khả năng tối đa của một tín hiệu phát biểu được đề cử. Trong phần này, chúng tôi trình bày cách áp dụng thuật toán tối đa kỳ vọng đối với các mô hình Markov ẩn. Bằng chứng này dựa theo công thức chung của EM đã được trình bày trong CS229. Thuật toán 2.4 đưa ra thuật toán EM cơ bản. Chú ý rằng vấn đề tối ưu hóa ở bước M bị hạn chế để A và B duy trì các xác suất hợp lệ. Giống giải pháp khả năng tối ưu chúng ta tìm ra trong mô hình Markov (không ẩn), chúng ta cũng có thể giải quyết vấn đề tối ưu hóa này với phương pháp nhân tử Lagrange. Chú ý rằng cả bước E và bước M đều yêu cầu liệt kê tất cả các |S|Tcó thể gán cho 𝒵⃗ . Chúng ta sẽ sử dụng các thuật toán tiến và lui đã đề cập trước đó để tính toán một tập hợp các số liệu thống kê đầy đủ cho bước E và bước M một cách dễ dàng. Đầu tiên, hãy viết lại hàm mục tiêu sử dụng các giả định Markov.

Ở dòng đầu tiên ta chia log thành một phép trừ và lưu ý rằng số hạng của mẫu số không phụ thuộc vào các tham số của A và B. Các giả định Markov được áp dụng ở dòng thứ 3. Dòng 5 sử dụng các hàm chỉ thị để đánh dấu cho A và B bằng trạng thái. Cũng như đối với các tham số khả năng tối ưu trong mô hình Markov không ẩn, sẽ không có vấn đề gì nếu ta bỏ qua các ràng buộc bất bình đẳng bởi vì dạng giải này tự đưa ra kết quả với các số dương. Xây dựng công thức Lagrange:

10

Lấy đạo hàm từng phần và đặt biểu thức bằng không:

Lấy đạo hàm từng phần giữ nguyên các nhân tử Lagrange và thay thế các giá trị của Aij và Bjk ở trên:

Thế trở lại vào biểu thức ở trên, ta sẽ tìm ra các tham số 𝐴̂ và 𝐵̂ mà tối đa hóa số lượng dự đoán của chúng ta đối với các bộ dữ liệu là:

11

Thật không may, mỗi một tổng số này vượt quá mọi nhãn có thể 𝒵⃗  ST. Nhưng nhớ lại rằng Q(𝒵⃗ ) đã được xác định ở bước E là P(𝒵⃗ |𝓍⃗; A,B) cho các tham số của A và B tại bước thời gian cuối. Hãy xem xét làm thế nào để biểu diễn tử số đầu tiên của Âij dưới dạng xác xuất tiến và lùi, αi (t) và βj(t).

Trong hai bước đầu tiên ta đảo vị trí các số hạng và thay thế giá trị đã định nghĩa của Q. Sau đó, ta sử dụng quy tắc Bayes và có được trong dòng thứ tư, và ở dòng 5 ta sử dụng các định nghĩa của α, β, A, và B. Tương tự như vậy, mẫu số có thể được biểu diễn bằng cách tính tổng tất cả giá trị của tử số thông qua j.

12

Kết hợp các biểu thức này, chúng ta có thể mô tả đầy đủ các chuyển đổi trạng thái khả năng tối đa Âij mà không cần phải liệt kê tất cả tử số có thể là:

Tương tự như vậy, chúng ta có thể biểu diễn cho tử số cho

jk

như sau:

Thuật toán 3: thuật toán Forward-Backward về nghiên cứu tham số HMM Khởi tạo: Đặt A và B là các ma trận xác suất hợp lệ ngẫu nhiên với Ai0 = 0 và B0k = 0 vài = 1..|S|; k = 1 ..|V|. Lặp lại cho đến khi hội tụ { (Bước E) Chạy thuật toán tiến và lùi để tính toán αi và βi, với i = 1..|S|. Sau đó đặt: (M-Step) ước tính lại các thông số khả năng tối đa:

Và triển khai

jk:

13

Kết hợp các biểu thức lại, ta thu được biểu thức cho các xác suất phát sinh khả năng tối đa như sau:

Thuật toán 2.4 cho thấy một biến thể của thuật toán Forward-Backward, hay thuật toán Baum-Welch cho tham số học trong HMMs. Trong bước E, thay vì đánh giá một cách minh bạch Q(𝒵⃗ ) cho tất cả các 𝒵⃗  ST, ta tính toán các thống kê đầy đủ 𝛾 t(i,j) = 𝛼i(t)AijBjxt𝛽 j(t+1) để cân đối xác suất chuyển đổi giữa trạng thái si và sj tại thời điểm t cho tất cả các quan sát 𝓍⃗. Các biểu thức gốc của Aij và Bjk tương đối là trực quan. Aij được tính bằng số chuyển đổi kỳ vọng từ si đến sj chia cho số lượng kỳ vọng xuất hiện của si. Tương tự như vậy, Bjk được tính bằng số phát sinh kỳ vọng của vk từ sj bị chia bởi số lượng xuất hiện kỳ vọng của sj. Giống như nhiều ứng dụng của EM, tham số học trong HMMs là một vấn đề non-convex với nhiều local maxima. EM sẽ hội tụ để đạt cực đại dựa trên tham số ban đầu của nó, vì vậy số hạng có thể được xếp theo thứ tự. Ngoài ra, nó còn có vai trò quan trọng trong việc làm mịn các phân phối xác suất được biểu diễn bởi A và B để cho không có một chuyển đổi hoặc phát sinh nào có xác xuất bằng 0. 2.5 Đọc thêm Có rất nhiều nguồn tài liệu tốt cho việc nghiên cứu về các mô hình Markov ẩn. Đối với các ứng dụng trong xử lý ngôn ngữ tự nhiên, tôi đề xuất dự thảo ấn bản thứ hai Speech and Language Processing1 của Jurafsky và Martin hoặc Foundations of Statistical Natural Language Processing của Manning và Schütze. Ngoài ra, HMM-in-a-spreadsheet [1] của Eisner là một cách tương tác khá dễ dàng để áp dụng một HMM chỉ cần đến ứng dụng bảng tính. Tài liệu tham khảo [1] Jason Eisner. An interactive spreadsheet for teaching the forward-backward algorithm. In Dragomir Radev and Chris Brew, editors, Proceedings of the ACL Workshop on Effective Tools and Methodologies for Teaching NLP and CL, pages 10-18, 2002.

14

PHẦN II: PHÂN TÍCH VÀ ĐÁNH GIÁ Nhiều bài toán thực tế được biểu diễn dưới mối quan hệ nhân - quả, nhưng chỉ quan sát được phần “quả” còn phần “nhân” thì lại là ẩn số. HMM là một mô hình cho phép các thuật toán giải quyết được các bài toán xác lập mối quan hệ nhân quả cục bộ nói trên. Mô hình Markov ẩn (Hidden Markov Model - HMM) là mô hình thống kê mà trong đó hệ thống đã được mô hình hóa được cho là một quá trình Markov với các tham số không biết trước. Nhiệm vụ là ta phải đi xác định các tham số ẩn dựa trên các tham số quan sát được. Theo đó, các tham số của mô hình được rút ra sau này có thể được sử dụng để thực hiện các phân tích kế tiếp. Để có thể áp dụng được mô hình HMM vào các ứng dụng phức tạp trong thực tế, trước hết cần có lời giải thỏa đáng cho 3 bài toán cơ bản của HMM: 1

Các bài toán cơ bản trong HMM  Bài toán 1: cho trước chuỗi tín hiệu quan sát O = {O1, O2, …, OT} và mô hình HMM đại diện bởi bộ tham số 𝜆 = (𝐴, 𝐵, 𝜋) Làm sao để tính toán một cách hiệu quả 𝑝(𝑂|𝜆) – xác suất phát sinh O từ mô hình 𝜆.  Bài toán 2: cho trước chuỗi tín hiệu quan sát O = {O1, O2, …, OT} và mô hình HMM đại diện bởi bộ tham số 𝜆 = (𝐴, 𝐵, 𝜋). Cần tìm ra chuỗi trạng thái tối ưu nhất Q = {q1, q2, …, qT} đã phát sinh ra O.  Bài toán 3: cho trước chuỗi tín hiệu quan sát O = {O1, O2, …, OT}. Làm thế nào để xác định các tham số mô hình 𝜆 = (𝐴, 𝐵, 𝜋) sao cho cực đại hóa xác suất 𝑝(𝑂|𝜆)? Đây chính là bài toán học / huấn luyện mô hình. Bài toán này đem lại một khả năng rất quan trọng của HMM: khả năng mô hình hóa một đối tượng cụ thể trong thực tế, mô hình hóa dữ liệu học.

1.1 Bài toán 1 – Probability Evaluation Mục tiêu của bài toán thứ nhất là tính 𝑝(𝑂|𝜆) – xác suất phát sinh O từ mô hình 𝜆. Một giải pháp đơn giản cho vấn đề này là trực tiếp duyệt qua tất cả các chuỗi trạng thái Q làm phát sinh ra O. Khi đó, xác suất 𝑝(𝑂|𝜆) sẽ là tổng các xác suất phát sinh O từ tất cả các chuỗi Q khác nhau: 𝑃(𝑂|𝜆) = ∑ 𝑃(𝑄 |𝑄, 𝜆). 𝑃(𝑄 |𝜆) 𝑎𝑙𝑙 𝑄

=

∑

𝜋𝑞1 𝑏𝑞1 (𝑂1 )𝑎𝑞1𝑞2 𝑏𝑞2 (𝑂2 ) . … . 𝑎𝑞𝑇−1𝑞𝑇 𝑏𝑞𝑇 (𝑂𝑇 )

𝑞1 ,𝑞2 ,…,𝑞𝑡

Để xác định 𝑝(𝑂|𝜆) theo cách trực tiếp như trên, ta cần thực hiện 2T(N)T phép tính. Điều này là không khả thi ngay cả với các giá trị nhỏ của N (số trạng thái của mô hình) và T (chiều dài của chuỗi tín hiệu quan sát); chẳng hạn với N = 5 và T = 100, tổng số phép tính cần

15

phải thực hiện là 2.100. 5100 ≈ 1072 . Rõ ràng chi phí tính toán là quá lớn, ta không thể tính 𝑝(𝑂|𝜆) theo cách như trên. Một giải pháp khả thi hơn để tính 𝑝(𝑂|𝜆) là là thông qua thủ tục forward backward. Trước tiên, ta định nghĩa biến forward 𝛼𝑡 (𝑖) là xác suất trạng thái Si tại thời điểm t và đã quan sát được đoạn O = {O1, O2, …, OT} từ mô hình 𝜆 cho trước: 𝛼𝑡 (𝑖) = 𝑝(𝑂1 𝑂2 … 𝑂𝑡 , 𝑞𝑡 = 𝑆𝑖 |𝜆)

16

Các biến 𝛼𝑡 (𝑖) có thể được tính theo quy nạp từng bước sau:  Bước 1 – Khởi tạo: đặt t = 1 𝛼1 (𝑖) = 𝜋𝑖 𝑏𝑖 (𝑂1 ), 1 ≤ 𝑖 ≤ 𝑁  Bước 2 – Quy nạp: 𝑁

𝛼𝑡+1 (𝑗) = 𝑏𝑗 (𝑂𝑡+1 ) ∑ 𝛼𝑡 (𝑖)𝑎𝑖𝑗 , 1 ≤ 𝑗 ≤ 𝑁 𝑖=1

 Bước 3 – Cập nhật thời gian t: Gán t = t + 1 Quay lại bước 2 nếu t < T, nếu không thì tiến tới bước 4  Bước 4 – Kết thúc: 𝑁

𝑃(𝑂|𝜆) = ∑ 𝛼 𝑇 (𝑖) 𝑖=1

Diễn tả thủ tục forward:

Về độ phức tạp tính toán, để tính được tất cả các biến forward 𝛼𝑡 (𝑖), ta cần thực hiện N T phép tính, nhỏ hơn rất nhiều so với 2T(N)T của phương pháp tính trực tiếp. 2

Tương tự như trong thủ tục forward, thủ tục backward trước hết định nghĩa biến backward 𝛽𝑡 (𝑖) là xác suất quan sát được đoạn O = {Ot+1, Ot+2, …, OT}. Cho trước trạng thái Si và mô hình 𝜆: 𝛽𝑡 (𝑖) = 𝑝(𝑂𝑡+1 𝑂𝑡+2 … 𝑂𝑇 , 𝑞𝑡 = 𝑆𝑖 |𝜆) Các biến backward cũng được tính quy nạp theo các bước sau:  Bước 1 – Khởi tạo: đặt t = T - 1 𝛽𝑡 (𝑖) = 1, 1 ≤ 𝑖 ≤ 𝑁  Bước 2 – Quy nạp: 𝑁

𝛽𝑡 (𝑖) = ∑ 𝛽𝑡+1 (𝑖)𝑎𝑖𝑗 𝑏𝑗 (𝑂𝑡+1 ) , 1 ≤ 𝑗 ≤ 𝑁 𝑗=1

17

 Bước 3 – Cập nhật thời gian t: Gán t = t - 1 Quay lại bước 2 nếu t > 0, nếu không thì tiến tới bước 4  Bước 4 – Kết thúc: 𝑁

𝑃(𝑂|𝜆) = ∑ 𝛽𝑇 (𝑖) 𝑖=1

Diễn tã thuật toán backward:

Cũng giống như các biến forward, việc tính tất cả các biến backward cần thực hiện N T phép tính. Như vậy, thủ tục forward-backward là khả thi với chi phí tính toán hoàn toàn có thể chấp nhận được. 2

Đối với việc tìm lời giải cho bài toán 1, ta chỉ cần đến phần forward trong thủ tục forward-backward. Tuy nhiên, phần backward giúp tìm lời giải cho bài toán 2 và 3. 1.2 Bài toán 2 – “Optimal” State Sequence Mục tiêu của bài toán 2 là tìm ra chuỗi trạng thái “tối ưu” nhất Q = { q1, q2, …, qT } đã phát sinh ra O. Một điều đáng lưu ý là có rất nhiều các tiêu chí “tối ưu” khác nhau cho việc xác định Q, nên lời giải cho bài toán này phụ thuộc vào tiêu chí ‘tối ưu” được chọn. Một trong những tiêu chí đó là chọn ra từng qt có độ khả thi cao nhất ở từng thời điểm t thông qua độ đo xác suất 𝑝(𝑞𝑡 = 𝑆𝑖 |𝑂, 𝜆) – xác suất ở trạng thái Si vào thời điểm t cho trước chuỗi tín hiệu quan sát O và mô hình 𝜆. Ta gọi độ đo này là 𝛾𝑡 (𝑖): 𝛾𝑡 (𝑖) = 𝑝(𝑞𝑡 = 𝑆𝑖 |𝑂, 𝜆) Biến 𝛾𝑡 (𝑖) có thể được tính thông qua các biến 𝛼𝑡 (𝑖) và 𝛽𝑡 (𝑖) theo biểu thức: 𝛾𝑡 (𝑖) =

𝛼𝑡 (𝑖) 𝛽𝑡 (𝑖) 𝛼𝑡 (𝑖) 𝛽𝑡 (𝑖) = 𝑁 ∑𝑖=1 𝛼𝑡 (𝑖) 𝛽𝑡 (𝑖) 𝑃(𝑂|𝜆)

Thông qua biến 𝛾𝑡 (𝑖), ta hoàn toàn có thể xác định được trạng thái có khả năng cao nhất được đạt đến ở thời điểm t: 𝑞𝑡 = 𝑎𝑟𝑔 max [𝛾𝑡 (𝑖)], 1 ≤ 𝑡 ≤ 𝑇 1≤𝑖≤𝑁

Xâu kết các qt lại, ta sẽ có chuỗi trạng thái lời giải Q của bài toán như ví dụ sau:

18

Tuy nhiên, kết quả này chỉ mang tính cục bộ, nghĩa là đôi khi chuỗi Q tìm được không tồn tại trong thực tế nếu một số xác suất chuyển trạng thái bằng 0. Giả sử trong chuỗi kết quả Q tìm được có q5 = S1 và q6 = S2, nhưng trên thực tế xác suất chuyển trạng thái a12 = 0, như vậy lời giải là mâu thuẫn. Để tránh tình trạng mâu thuẫn như trên, ta có thể thay đổi tiêu chí “tối ưu” cho việc chọn Q. Tùy theo từng ứng dụng cụ thể mà tiêu chí này sẽ được chọn sao cho phù hợp, tuy nhiên tiêu chí phổ biến nhất được sử dụng là chọn cả chuỗi Q khả thi nhất, nghĩa là qui bài toán từ việc tìm Q để cực đại hóa 𝑝(𝑄|𝑂, 𝜆) sang việc tìm Q để cực đại hóa 𝑝(𝑄|𝑂, 𝜆). Giải pháp cho vấn đề này là thuật toán viterbi Thuật toán viterbi định nghĩa biến 𝛿𝑡 (𝑖) là xác suất cao nhất của đoạn chuỗi trạng thái dẫn đến Si ở thời điểm t và đã quan sát được đoạn O1, O2, …, Ot cho trước mô hình 𝜆: 𝛿𝑡 (𝑖) =

max 𝑝(𝑞1 , 𝑞2 , … , 𝑞𝑡 = 𝑆𝑖 , 𝑂1 𝑂2 … 𝑂𝑡 |𝜆)

𝑞1 ,𝑞2 ,…,𝑞𝑡

Biến 𝛿𝑡 (𝑖) được tính theo quy nạp với các bước sau đây (thuật toán viterbi):  Bước 1 – Khởi tạo: 𝛿𝑡 (𝑖) = 𝜋𝑖 𝑏𝑖 (𝑂1 ), 1 ≤ 𝑖 ≤ 𝑁 𝜓1 (𝑖) = 0 𝜓1 (𝑖) là mảng để lưu lại các tham số i làm cực đại hóa biểu thức  Bước 2 – Lặp quy nạp: 𝛿𝑡 (𝑗) = max [𝛿𝑡−1 (𝑖)𝑎𝑖𝑗 ]𝑏𝑗 (𝑂𝑡 ), 2 ≤ 𝑡 ≤ 𝑇, 1 ≤ 𝑗 ≤ 𝑁 1≤𝑖≤𝑁

𝜓𝑡 (𝑗) = max [𝛿𝑡−1 (𝑖)𝑎𝑖𝑗 ], 2 ≤ 𝑡 ≤ 𝑇, 1 ≤ 𝑗 ≤ 𝑁 1≤𝑖≤𝑁

 Bước 3 – Kết thúc lặp: 𝑝∗ = max [𝛿𝑇 (𝑖)] 1≤𝑖≤𝑁

𝑞𝑡∗ = 𝑎𝑟𝑔 max [𝛿𝑇 (𝑖)] 1≤𝑖≤𝑁

 Bước 4 – Quay lui (backtracking): ∗ ) 𝑞𝑡∗ = 𝜓𝑡+1 (𝑞𝑡+1 , 𝑡 = 𝑇 − 1, 𝑇 − 2, … , 1 Kết thúc thuật toán, chuỗi 𝑄 = 𝑞1∗ 𝑞2∗ … 𝑞𝑇∗ chính là lời giải đáp của bài toán 2.

19

1.3 Bài toán 3 – Parameter Estimation Mục tiêu của bài toán thứ 3, cũng là bài toán phức tạp nhất trong ba bài toán, là tìm cách cập nhật lại các tham số của mô hình 𝜆 = (𝐴, 𝐵, 𝜋) sao cho cực đại hóa xác suất (𝑂|𝜆) – xác suất quan sát được chuỗi tín hiệu O từ mô hình. Với một chuỗi tín hiệu quan sát hữu hạn bất kỳ O làm dữ liệu huấn luyện, chưa có một phương pháp tối ưu nào cho việc ước lượng các tham số 𝜆 = (𝐴, 𝐵, 𝜋) của mô hình theo hướng cực đại toàn cục. Tuy nhiên, bộ tham số 𝜆 có thể được chọn sao cho xác suất 𝑝(𝑂|𝜆) đạt cực đại cục bộ bằng thuật toán Baum-Welch hoặc sử dụng phương pháp giảm dốc Gradient. Phần này trình bày thuật toán Baum-Welch giải quyết bài toán 3. Trước tiên, ta định nghĩa 𝜉𝑡 (𝑖, 𝑗) là xác suất ở trạng thái Si tại thời điểm t và rơi vào trạng thái Sj ở thời điểm t+1 cho trước mô hình 𝜆 và chuỗi tín hiệu quan sát O: 𝜉𝑡 (𝑖, 𝑗) = 𝑝(𝑞𝑡 = 𝑆𝑖 , 𝑞𝑡+1 = 𝑆𝑗 |𝑄, 𝜆 ) Theo định nghĩa này, 𝜉𝑡 (𝑖, 𝑗) có thể được tính thông qua các biến 𝛼𝑡 (𝑖) và 𝛽𝑡 (𝑖) theo biểu thức: 𝜉𝑡 (𝑖, 𝑗) =

𝛼𝑡 (𝑖)𝑎𝑖𝑗 𝑏𝑗 (𝑂𝑡+1 )𝛽𝑡+1 (𝑗) 𝛼𝑡 (𝑖)𝑎𝑖𝑗 𝑏𝑗 (𝑂𝑡+1 )𝛽𝑡+1 (𝑗) = 𝑁 ∑𝑖=1 ∑𝑁 𝑝(𝑂|𝜆) 𝑗=1 𝛼𝑡 (𝑖) 𝑎𝑖𝑗 𝑏𝑗 (𝑂𝑡+1 )𝛽𝑡+1 (𝑗)

Nếu ta lấy tổng 𝛾𝑡 (𝑖) theo 𝑡 ∈ [1, 𝑇 − 1], kết quả nhận được là số lần kỳ vọng chuyển trạng thái từ Si. Tương tự, lấy tổng 𝜉𝑡 (𝑖, 𝑗) theo 𝑡 ∈ [1, 𝑇 − 1], ta sẽ có số lần kỳ vọng chuyển từ trạng thái Si sang Sj: 𝑇−1

∑ 𝛾𝑡 (𝑖) = 𝑠ố 𝑙ầ𝑛 𝑘ỳ 𝑣ọ𝑛𝑔 𝑐ℎ𝑢𝑦ể𝑛 𝑡𝑟ạ𝑛𝑔 𝑡ℎá𝑖 𝑡ừ 𝑆𝑖 𝑇−1

𝑡=1

∑ 𝜉𝑡 (𝑖, 𝑗) = 𝑠ố 𝑙ầ𝑛 𝑘ỳ 𝑣ọ𝑛𝑔 𝑐ℎ𝑢𝑦ể𝑛 𝑡𝑟ạ𝑛𝑔 𝑡ℎá𝑖 𝑡ừ 𝑆𝑖 𝑠𝑎𝑛𝑔 𝑆𝑗 𝑡=1

Với các đại lượng này, ta có các biểu thức cập nhật tham số của HMM như sau:

   

𝜋̅𝑖 = 𝑠ố 𝑙ầ𝑛 𝑘ỳ 𝑣ọ𝑛𝑔 ở 𝑡𝑟ạ𝑛𝑔 𝑡ℎá𝑖 𝑆𝑖 𝑣à𝑜 𝑡ℎờ𝑖 đ𝑖ể𝑚 (𝑡 = 1) = 𝛾1 (𝑖) (∗) ∑𝑇−1 𝑒𝑥𝑛𝑢𝑚(𝑆𝑖 , 𝑆𝑗 ) 𝑡=1 𝜉𝑡 (𝑖, 𝑗) 𝑎̅𝑖𝑗 = = (∗∗) ∑𝑇−1 𝑒𝑥𝑛𝑢𝑚(𝑆𝑖 ) 𝑡=1 𝛾𝑡 (𝑖) ∑𝑇 𝑡=1 𝛾𝑡 (𝑗) 𝑒𝑥𝑛𝑢𝑚_𝑖𝑛(𝑆𝑗 , 𝑣𝑘 ) 𝑠.𝑡.𝑂𝑡 = 𝑣𝑘 𝑏̅𝑗 (𝑘) = = (∗∗∗) ∑𝑇𝑡=1 𝛾𝑡 (𝑗) 𝑒𝑥𝑛𝑢𝑚_𝑖𝑛(𝑆𝑗 ) exnum(Si,Sj): số lần kỳ vọng chuyển từ trạng thái Si sang trạng thái Sj exnum(Si): số lần kỳ vọng chuyển trạng thái từ Si exnum_in(Sj,vk): số lần kỳ vọng ở trạng thái Sj và quan sát được tín hiệu vk exnum_in(Sj): số lần kỳ vọng ở trạng thái Sj

Từ mô hình ban đầu 𝜆 = (𝐴, 𝐵, 𝜋) và chuỗi tín hiệu quan sát O, ta tính được vế phải của các biểu thức (*)(**)(***),kết quả nhận được chính là các tham số mới của mô hình 𝜆̅ =

20

(𝐴̅, 𝐵̅, 𝜋̅). Theo Baum đã chứng minh, ta luôn có 𝑝(𝑂|𝜆̅) > 𝑝(𝑂|𝜆) trừ phi mô hình 𝜆 đã đạt đến điểm tối ưu cục bộ (khi đó 𝜆̅ = 𝜆). Như vậy, thuật toán Baum-Welch sẽ được áp dụng qua nhiều bước lặp để ước lượng và cập nhật các tham số mô hình cho đến khi hội tụ. Tuy nhiên, kết quả cuối cùng chỉ đạt được tối ưu cục bộ mà thôi. Thông thường, nếu các tham số được khởi tạo với các giá trị thích hợp, thì có một phần khả năng nào đó có thể giúp mô hình đạt được tối ưu toàn cục khi huấn luyện. 2

Ví dụ cụ thể sử dụng thuật toán Viterbi

Một vấn đề của HMMs là xác định được chuỗi trạng thái mà có khả năng đưa ra được chuỗi quan sát cho trước nhiều nhất. Và trong bài báo này, tác giả đã lựa chọn sử dụng thuật toán Viterbi như là một trong những giải pháp cho vấn đề này. Thuật toán Viterbi là một dạng khác của thuật toán biểu đồ mắt cáo, tương tự như thủ tục tiến Forward, ngoại trừ việc chọn các giá trị xác suất chuyển đổi lớn nhất tại mỗi bước, thay vì tính tổng của chúng. Sau đây ta xét một ví dụ về dự báo thời tiết để hiểu rõ hơn về thuật toán Viterbi: Tình huống: Có 3 loại thời tiết: nắng , mưa , và sương mù . Và ta giả thiết rằng 1 loại thời tiết sẽ xảy ra diễn ra trong cả ngày, không thay đổi vào một khoảng thời gian trong ngày. Bây giờ giả thiết rằng bạn bị nhốt trong một căn phòng trong nhiều ngày, và bạn được hỏi về thời tiết ở bên ngoài. Và chỉ có một vài bằng chứng bạn có là việc một người bạn đem bữa ăn đến cho bạn là có mang một cây dù hay không . Bạn không biết thời tiết như thế nào khi bạn bị khóa. Vào ba ngày đầu tiên bạn quan sát thấy người bạn như sau: . Tìm xác suất lớn nhất của chuỗi thời tiết sử dụng thuật toán Viterbi (giả thiết rằng xác suất ưu tiên là như nhau vào ngày 1).

21

Bước 1. Tính giá trị ban đầu (Initialisation):

Hình 1: Thuật toán Viterbi để tìm chuỗi thời tiết có thể xảy ra nhất. Ta tìm thấy đường dẫn đến trạng thái trời nắng ở thời điểm n= 2 Bước 2. Đệ quy (Recursion): Chúng ta tính khả năng tới trạng thái có thể xảy ra nhất với:

từ tất cả 3 trạng thái trước, và chọn khả năng

22

Tức là trong hình vẽ tìm đường dẫn mà dẫn đến likelihood lớn nhất xét về likelihood tốt nhất ở thời điểm trước và bước chuyển tiếp từ nó. Rồi nhân với likelihood hiện tại được cho bởi trạng thái hiện tại. Và kết quả là sẽ tìm thấy đường dẫn tốt nhất. Likelihood là được tính trong δ, và trạng thái trước đó có thể nhất là trong ψ (xem hình 1). Thực hiện tương tự với trạng thái trời

và

:

Với n=3:

Cuối cùng, chúng ta sẽ thu được đường dẫn kết thúc có thể xảy ra nhất ở mỗi trạng thái của mô hình (hình 2):

Thuật toán Viterbi để tìm chuỗi thời tiết có khả năng xảy ra nhất tại n= 3

23

Thuật toán Virtebi tìm ra chuỗi thời tiết có thể xảy ra nhất Bước 3. Termination: Con đường có thể xảy ra nhất đã được xác định, bắt đầu bằng cách tìm ra trạng thái cuối cùng của chuỗi có thể xảy ra nhất.

Bước 4. Backtracking: Chuỗi trạng thái tốt nhất có thể đọc từ vector ψ. Xem hình 7

Theo cách đó thì chuỗi thời tiết có thể xảy ra nhất là:

2.1 Xây dựng cấu trúc dữ liệu cho INPUT và OUTPUT -

INPUT: Chuỗi quan sát: 𝑞1 , 𝑞2 … 𝑞𝑛 . OUTPUT: Chuỗi kết quả có thể xảy ra: 𝑄 ∗ = {𝑞1∗ , 𝑞2∗ … 𝑞𝑛∗ }

2.2 Ưu - Nhược điểm của thuật toán Viterbi  Ưu điểm: o Độ chính xác cao. o Tốc độ thực hiện cao.  Nhược điểm: o Yêu cầu nhiều dung lượng của bộ nhớ thiết bị.

24

2.3 Các lớp bài toán tương tự -

Bài toán gán nhãn từ loại (part-of-speech tagging - POS) trong xử lý ngôn ngữ tự nhiên (Natural Language Processing). Bài toán mã hóa dữ liệu trong hệ thống truyền dẫn số Bài toán nhận dạng tiếng nói Bài toán nhận diện khuôn mặt

25