Mô hình markov ẩn hợp gauss

30 Chương 3: MÔ HÌNH MARKOV ẨN HỢP GAUSS 3.1. Gaussian Mixture Model 3.1.1. Đặc tả mô hình Mô hình hợp Gauss (Gaussian Mixture Model - GMM) là một dạng mô hình thống kê được xây dựng từ việc huấn luyện các tham số thông qua dữ liệu học. Mô hình GMM còn có một số tên gọi khác như Weighted Normal Distribution Sums hay Radial Basis Function Approximations… Hình 3.1: Hàm mật độ Gauss. Về cơ bản, mô hình GMM xấp xỉ một hàm mật độ xác suất bằng hợp các hàm mật độ Gauss. Hình 3.1 minh họa hai hàm mật độ Gauss với các tham số khác nhau. Một cách hình thức, hàm mật độ xác suất của phân phối Gauss fN(x, µ, σ2) được cho bởi công thức: ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −−= 2 2 2 )(exp 2 1)( σ μ πσ xxp (3.1) trong đó, µ là giá trị trung bình, σ là độ lệch chuẩn. Trong trường hợp x là vector gồm D thành phần, hàm mật độ xác suất của phân phối Gauss fN(x, µ, Σ) được cho bởi công thức: 31 ⎟⎠ ⎞⎜⎝ ⎛ −∑−−∑= − )()'( 2 1exp )2( 1)( 12/12/ μμπ rrrrr xxxp D khi đó, µ là vector trung bình, Σ là ma trận hiệp phương sai. Nếu chọn µ=0 và σ=1, công thức (3.1) sẽ trở thành hàm mật độ chuẩn Gauss: ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛−= 2 exp 2 1)( 2xxp π Từ “Gauss” được đặt theo tên của nhà toán học người Đức Carl Friedrich Gauss. Ông đã định nghĩa hàm mật độ Gauss và áp dụng trong phân tích dữ liệu thiên văn. Hình 3.2: Mô hình GMM. Cho trước M phân phối Gauss p1, p2, …, pM, hàm mật độ xác suất của mô hình GMM được minh họa trong hình 3.2 chính là tổng trọng của M phân phối Gauss theo công thức: ∑ = = M i iiGMM xpwxp 1 )()( rr trong đó, wi là trọng số của phân phối Gauss thứ i, thỏa ràng buộc 0≤ wi ≤1 và ∑ = = M i iw 1 1. Các trọng số này thể hiện mức độ ảnh hưởng của mỗi phân phối Gauss đối với mô hình GMM. Như vậy, phân phối Gauss có phương sai và trọng số lớn wM w2 w1 pGMM . . . ∑ P1 P2 PM X 32 bao nhiêu thì có mức độ ảnh hưởng lớn bấy nhiêu đối với kết xuất của mô hình. Hình 3.3 cho thấy mức độ ảnh hưởng của từng phân phối Gauss lên GMM. Hình 3.3: Hàm mật độ của GMM có 3 phân phối Gauss. Như vậy, một mô hình GMM có M phân phối Gauss sẽ được đại diện bởi bộ tham số λ = { wi, µi, Σi }, i ∈ [1, M]. Trong hướng tiếp cận GMM giải quyết bài toàn định danh người nói, mỗi người nói sẽ được mô hình hóa bằng một mô hình GMM mà bộ tham số λ của nó sẽ được xác định thông qua việc huấn luyện trên tập mẫu học của người nói tương ứng. Tùy thuộc vào cách tổ chức của ma trận hiệp phương sai (covariance matrix), GMM có thể có một số biến thể khác nhau: - Nodal covariance matrices GMM: mỗi phân phối Gauss trong GMM có một ma trận hiệp phương sai riêng. - Grand covariance matrix GMM: mọi phân phối Gauss trong một GMM dùng chung một ma trận hiệp phương sai. - Global covariance matrix GMM: mọi phân phối Gauss trong tất cả các GMM dùng chung một ma trận hiệp phương sai. Ngoài ra, xét về dạng thức, ma trận hiệp phương sai gồm hai loại: full (dạng đầy đủ) và diagonal (dạng ma trận đường chéo). Thông thường, dạng nodal-diagonal covariance matrices GMM được sử dụng phổ biến nhất. 33 3.1.2. Ước lượng tham số Trong bộ phân loại dựa trên mô hình thống kê, việc ước lượng các tham số của mô hình được thực hiện thông qua huấn luyện trên một số lượng lớn các dữ liệu học. Mục tiêu của bước huấn luyện là nhằm tổng quát hóa, mô hình hóa những đặc điểm chung nhất của tập dữ liệu học. Đối với mô hình GMM, một trong những kỹ thuật xác định bộ tham số λ của nó được áp dụng khá phổ biến là thuật toán Expectation-Maximization (EM). Bản thân EM là một thuật toán tổng quát, đem lại các kết quả khác nhau đối với các mô hình khác nhau. Ngoài ra, có hai tiêu chí ước lượng khác nhau trong EM: - Maximum likelihood (ML): ước lượng tham số theo hướng cực đại hóa độ tương tự p(X | λ). - Maximum a posteriori probability (MAP): ước lượng tham số theo hướng cực đại hóa xác suất quyết định p(λ | X). Cho trước vector đặc trưng X trích được từ dữ liệu âm thanh, ta có thể dễ dàng tính được độ tương tự p(X | λ). Tuy nhiên, trong định danh người nói, vai trò quyết định lại nằm ở xác suất p(λ | X). Sử dụng công thức Bayes, ta có tương quan giữa p(X|λ) và p(λ|X): )( )()|()|( Xp pXpXp λλλ = trong đó, p(X) là xác suất xuất hiện của vector đặc trưng X, p(λ) là tần suất xuất hiện của người nói được mô hình hóa bởi GMM tương ứng. Trong luật quyết định Bayes, p(X) độc lập; như vậy nếu giả định p(λ) là đồng nhất cho mọi người nói, ta có thể quy vai trò quyết định từ p(λ | X) về p(X | λ) và áp dụng EM ước lượng λ theo hướng maximum likelihood: )|(maxarg* λλ λ Xp= 34 Các bước tính toán để rút ra công thức cập nhật bộ tham số λ của GMM ở mỗi bước lặp EM được trình bày chi tiết trong [2]. Như vậy, với tập dữ liệu huấn luyện X gồm T mẫu { }TxxxX rrr ...,,, 21= , các trọng số, trung bình và phương sai của GMM ở mỗi bước lặp sẽ là: trọng số: ∑ = = T t ti xipT w 1 ),|(1 λr trung bình: ∑ ∑ = == T t t T t tt i xip xxip 1 1 ),|( ),|( λ λ μ r rr r phương sai: 2 1 1 2 2 ),|( ),|( iT t t T t tt i xip xxip μ λ λ σ −= ∑ ∑ = = r r trong đó, iti x μσ ,,2 là các thành phần tương ứng trong các vector iti x μσ rrr ,,2 . Xác suất ),|( λtxip r cho bởi công thức: ∑ = = M k tkk tii t xpw xpwxip 1 )( )(),|( r rr λ Trong quá trình xây dựng GMM, có hai vấn đề phát sinh là: số phân phối Gauss M của mô hình, và bộ tham số khởi đầu λ0 trước khi tiến hành thuật toán EM. Hiện tại, vẫn chưa có giải pháp tối ưu trên lý thuyết cho việc chọn M và λ0. Thông thường, M sẽ được chọn qua thực nghiệm, còn λ0 sẽ được khởi tạo bằng thuật toán k-means nhằm đem lại khả năng cao hơn cho việc đạt tối ưu toàn cục, đồng thời đẩy nhanh tốc độ hội tụ trong huấn luyện. 3.2. Hidden Markov Model 3.2.1. Mô hình Markov 35 Xét một hệ thống gồm N trạng thái phân biệt S1, S2, …, SN như trong hình 3.4 (chọn N=3). Tại thời điểm t bất kỳ, hệ thống có thể chuyển từ trạng thái Si hiện hành sang một trong N-1 trạng thái còn lại hoặc chuyển trở lại chính trạng thái Si. Như vậy, ở thời điểm t, từ trạng thái Si có N nhánh cho thao tác chuyển trạng thái; mỗi nhánh này có một độ đo khả năng xảy ra, gọi là xác suất chuyển trạng thái. Hình 3.4: Mô hình Markov 3 trạng thái. Gọi qt là trạng thái đạt đến được ở thời điểm t, aij là xác suất chuyển từ trạng thái Si sang thái Sj, ta có: ( ) NjiSqSqpa itjtij ≤≤=== + ,1,|1 Với t tùy ý, xác suất chuyển trạng thái aij luôn độc lập với thời gian t và thỏa ràng buộc xác suất ∑ = =≥ N j ijij aa 1 1,0 . Kết xuất của hệ thống là một chuỗi các trạng thái tại các thời điểm t tương ứng. Ta biết được trạng thái nào ở thời điểm t nào, chính vì vậy mà hệ thống này được gọi là mô hình Markov “hiện” (Observable Markov Model). Xét một ví dụ cụ thể với mô hình Markov 3 trạng thái mô tả thời tiết [16]. Giả định rằng vào giữa trưa mỗi ngày, thời tiết quan sát được có thể thuộc một trong 3 trạng thái sau: a22 a23 a32 a12 a21 a31 a13 a33 a11 S2 S1 S3 36 - Trạng thái 1: mưa. - Trạng thái 2: mây. - Trạng thái 3: nắng. Ma trận xác suất chuyển trạng thái như sau: { } ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ == 8.01.01.0 2.06.02.0 3.03.04.0 ijaA Cho trước thời tiết của ngày thứ nhất (t = 1) là nắng (trạng thái 3), liệu ta có thể tính được xác suất xảy ra chuỗi thời tiết trong 7 ngày tiếp theo là “nắng, nắng, mưa, mưa, nắng, mây, nắng” thông qua mô hình hay không? Hình thức hóa lại vấn đề, gọi O là chuỗi thời tiết quan sát được trong 8 ngày O = { S3, S3, S3, S1, S1, S3, S2, S3 } tương ứng với t = 1, 2, …, 8, ta cần xác định xác suất p(O | Markov) – xác suất của O cho trước mô hình Markov: p(O | Markov) = p(S3, S3, S3, S1, S1, S3, S2, S3 | Markov) = p(S3) . p(S3|S3) . p(S3|S3) . p(S1|S3) . p(S1|S1) . p(S3|S1) . p(S2|S3) . p(S3|S2) = π3 . a33 . a33 . a31 . a11 . a13 . a32 . a23 = 1 * (0.8)(0.8)(0.1)(0.4)(0.3)(0.1)(0.2) = 1.536 * 10- 4 Với πi là xác suất khởi đầu của trạng thái Si – xác suất rơi vào trạng thái Si ở thời điểm t = 1: ( ) NiSqp ii ≤≤== 1,1π 3.2.2. Mô hình Markov ẩn Phần 3.2.1 đã trình bày về mô hình Markov và một ví dụ minh họa tương ứng. Trong mô hình Markov, mỗi trạng thái tương ứng với một sự kiện quan sát được. Với cấu trúc này, mô hình Markov còn gặp nhiều hạn chế trong việc mô hình hóa hay giải quyết các vấn đề phức tạp. 37 Phần này trình bày khái niệm về mô hình Markov ẩn – một dạng mở rộng của mô hình Markov. Trong mô hình Markov ẩn, các sự kiện quan sát được nằm trong mỗi trạng thái và phụ thuộc vào hàm mật độ xác suất trong các trạng thái đó. Hình 3.5: Mô hình Markov ẩn 3 trạng thái. Hình 3.5 minh họa một mô hình Markov ẩn 3 trạng thái với các sự kiện có thể quan sát được trong mỗi trạng thái là V = {v1, v2, v3, v4}. Khả năng quan sát được sự kiện vk trong trạng thái Sj phụ thuộc vào xác suất bj(k). Hàm b được gọi là hàm mật độ xác suất của các sự kiện được quan sát. Để dễ hình dung hơn về mô hình Markov ẩn, xét một ví dụ cụ thể về hệ thống bình- cầu (Urn and Ball model) [16] như trong hình 3.6. Giả sử trong một căn phòng có N cái bình, trong mỗi bình có M quả cầu với màu sắc khác nhau. Thoạt đầu, một bình sẽ được chọn ra ngẫu nhiên trong N bình, từ cái bình này chọn ra một quả cầu ngẫu nhiên bên trong, màu của quả cầu sẽ được ghi nhận lại và xem là sự kiện quan sát đầu tiên. Sau đó, quả cầu được trả về chổ cũ, và từ vị trí cái bình hiện tại ta chuyển sang chọn ngẫu nhiên một bình tiếp theo trong số N bình; một quả cầu khác lại b34 b33 b32 b31 b14 b13 b12 b11 b24 b23 b22 b21 v1 v2 v3 v4 v4 v3 v2 v1 v4 v3 v2 v1 a23 a32 a12 a21 a31 a13 a33 a22 a11 S2 S1 S3 38 được chọn ra từ chiếc bình đó và được ghi nhận lại màu như là sự kiện quan sát thứ hai. Cứ như thế, tiến trình chọn bình và cầu được lặp đi lặp lại. Với T lần lặp, ta sẽ có T sự kiện quan sát được, đó chính kết xuất của hệ thống bình-cầu. Hình 3.6: Hệ thống Urn-Ball. Hệ thống bình-cầu này minh họa điển hình cho hoạt động của một mô hình Markov ẩn có N trạng thái và M tín hiệu quan sát trong mỗi trạng thái. Các trạng thái ứng với các bình, các tín hiệu quan sát ứng với màu của các quả cầu trong mỗi bình. Khả năng chuyển từ một bình sang bình khác chính là xác suất chuyển trạng thái; còn việc chọn ngẫu nhiên quả cầu trong bình sẽ bị chi phối bởi hàm mật độ xác suất của các tín hiệu quan sát trong bình (trạng thái) đó. Trong chuỗi kết xuất của hệ thống bình-cầu, ta chỉ biết được thông tin về màu của các quả cầu được rút ra ở thời điểm tương ứng nhưng không biết được rằng quả cầu đó đã được rút ra từ bình (trạng thái) nào. Các bình (trạng thái) được xem là “ẩn” so với kết quả quan sát được. Chính vì vậy, mô hình này được gọi là mô hình Markov ẩn (hidden) – Hidden Markov Model (HMM). Ví dụ về hệ thống bình-cầu đã minh họa tổng quan khái niệm về HMM. Định nghĩa một cách hình thức, HMM gồm các thành phần sau đây: Bình 1 Bình 2 Bình N … p(đỏ) = b1(1) p(xanh) = b1(2) p(vàng) = b1(3) p(tím) = b1(4) . . . p(cam) = b1(M) p(đỏ) = b2(1) p(xanh) = b2(2) p(vàng) = b2(3) p(tím) = b2(4) . . . p(cam) = b2(M) p(đỏ) = bN(1) p(xanh) = bN(2) p(vàng) = bN(3) p(tím) = bN(4) . . . p(cam) = bN(M) 39 1) N – số lượng trạng thái của mô hình: mặc dù các trạng thái được xem là “ẩn” nhưng trong một số ứng dụng cụ thể, các trạng thái cũng đóng vai trò nhất định nào đó; chẳng hạn như trong hệ thống bình-cầu, các trạng thái ứng với các bình… Ta ký hiệu các trạng thái là S = {S1, S2, …, SN} và trạng thái ở thời điểm t là qt. 2) M – số lượng tín hiệu có thể quan sát được trong mỗi trạng thái. Các tín hiệu quan sát này là thành phần trong chuỗi kết xuất của mô hình. Trong hệ thống bình-cầu, các tín hiệu quan sát chính là màu sắc phân biệt của các quả cầu. Ta ký hiệu các tín hiệu quan sát này là V = {v1, v2, …, vM} và tín hiệu quan sát được ở thời điểm t là Ot. 3) Các xác suất chuyển trạng thái A = { aij } với ( ) NjiSqSqpa itjtij ≤≤=== + ,1,|1 thỏa ràng buộc ∑ = = N j ija 1 1 4) Các hàm mật độ xác suất trong mỗi trạng thái B = { bj(k) } với ( ) MkNjSqtatvpkb jtkj ≤≤≤≤== 1,1,|)( thỏa ràng buộc ∑ = = M k j kb 1 1)( 5) Xác suất khởi đầu của mỗi trạng thái π = { πi } với ( ) NiSqp ii ≤≤== 1,1π thỏa ràng buộc ∑ = = N i i 1 1π Để thuận tiện cho việc trình bày, ta quy ước mỗi mô hình HMM sẽ được đại diện bởi bộ tham số λ = (A, B, π). 3.2.3. Ba bài toán cơ bản của HMM 40 Để 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: - 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ố λ = (A, B, π). Làm sao để tính toán một cách hiệu quả p(O|λ) – 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ố λ = (A, B, π). 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 λ = (A, B, π) sao cho cực đại hóa xác suất p(O|λ)? Đâ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. Các tiểu mục tiếp theo sẽ lần lượt trình bày giải pháp cho ba bài toán này. 3.2.3.1. Bài toán 1 – evaluation problem Mục tiêu của bài toán thứ nhất là tính p(O|λ) – 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 p(O|λ) 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: ( ) ( ) ( ) ∑ ∑ −= = T TTT qqq Tqqqqqqqq Qall ObaObaOb QPQOPOP ,...,, 21 21 122111 )(...)()( |,|| π λλλ Để xác định p(O|λ) 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, 41 tổng số phép tính cần phải thực hiện là 72100 1051002 ≈⋅⋅ . Rõ ràng chi phí tính toán là quá lớn, ta không thể tính p(O|λ) theo cách trực tiếp như trên. Một giải pháp khả thi hơn để tính p(O|λ) là thông qua thủ tục forward-backward. Trước tiên, ta định nghĩa biến forward α t(i) là xác suất ở trạng thái Si tại thời điểm t và đã quan sát được đoạn O1, O2, ..., Ot từ mô hình λ cho trước: )|,...()( 21 λα ittt SqOOOpi == (3.2) Các biến α t(i) có thể được tính theo qui nạp từng bước như sau: 1) Khởi tạo: NiObi ii ≤≤= 1,)()( 11 πα 2) Qui nạp: NjTtObaij tj N i ijtt ≤≤−≤≤⎥⎦ ⎤⎢⎣ ⎡= + = + ∑ 1,11,)()()( 1 1 1 αα Như vậy, với qui nạp, ta hoàn toàn có thể tính được αT(i). Mà theo định nghĩa (3.2) thì )|,...()( 21 λα iTTT SqOOOpi == . Từ đây, dễ dàng có được: ∑ = = N i T iOp 1 )()|( αλ Về độ phức tạp tính toán, để tính được tất cả các biến forward α t(i), ta cần thực hiện N2T phép tính, nhỏ hơn rất nhiều so với con số 2T(N)T của phương pháp tính trực tiếp. Cụ thể, để tính p(O|λ) với N = 5 và T = 100, chỉ cần khoảng 3000 phép tính cho thủ tục forward trong khi phương pháp tính trực tiếp cần đến 1072 phép tính. Tương tự như trong thủ tục forward, thủ tục backward trước hết định nghĩa biến backward βt(i) là xác suất quan sát được đoạn Ot+1, Ot+2, ..., OT cho trước trạng thái Si ở thời điểm t và mô hình λ: ),|...()( 21 λβ itTttt SqOOOpi == ++ Các biến βt(i) cũng được tính theo qui nạp từng bước như sau: 42 1) Khởi tạo: NiiT ≤≤= 1,1)(β 2) Qui nạp: ∑ = ++= N j ttjijt jObai 1 11 )()()( ββ với 1...,,2,1 −−= TTt và Ni ≤≤1 Cũng giống như các biến forward α t(i), việc tính tất cả các biến backward βt(i) cần thực hiện N2T 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. Đố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. 3.2.3.2. Bài toán 2 – decoding problem 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 p(qt = Si | O, λ) – 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à γt(i): ),|()( λγ OSqpi itt == Biến γt(i) có thể được tính thông qua các biến α t(i) và βt(i) theo biểu thức: ∑ = == N i tt tttt t ii ii Op iii 1 )()( )()( )|( )()()( βα βα λ βαγ Thông qua biến γt(i), 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: 43 [ ] Ttiq t Ni t ≤≤= ≤≤ 1,)(maxarg1 γ 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ư một ví dụ trong hình 3.7. 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. Ví dụ, 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. Hình 3.7: Chuỗi Q tối ưu cục bộ. Để 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 p(Q|O, λ) sang việc tìm Q để cực đại hóa p(Q,O| λ). 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 δt(i) 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)( 2121,...,, 121 λδ titqqqt OOOSqqqpi t == − γ4(i) γ3(i) t = S3 S2 S1 γ2(i) γ1(i) 0 1 0 0.1 0.4 0.5 0 0.8 0.2 0.4 0.3 0.3 1 2 3 4 44 δt(i) có thể được tính theo qui nạp: )(])(max[)( 11 ++ ⋅= tjijtit Obaij δδ (3.3) tuy nhiên thuật toán viterbi còn cần đến mảng ψt(j) để lưu lại các tham số i làm cực đại hóa biểu thức (3.3). Chi tiết các bước của thuật toán viterbi như sau: 1) Khởi tạo: 0)( 1,)()( 1 11 = ≤≤= i NiObi ii ψ πδ 2) Lặp qui nạp: Nj TtObaij tjijtNit ≤≤ ≤≤= −≤≤ 1 2,)(])([max)( 11 δδ Nj Ttaij ijt Ni t ≤≤ ≤≤= −≤≤ 1 2,])([maxarg)( 1 1 δψ 3) Kết thúc lặp: )]([maxarg* )]([max* 1 1 iq ip T Ni T TNi δ δ ≤≤ ≤≤ = = 4) quay lui – backtracking: 1,...,2,1,*)(* 11 −−== ++ TTtqq ttt ψ Kết thúc thuật toán, chuỗi **2*1 ... TqqqQ = chính là lời giải thỏa đáng của bài toán 2. 3.2.3.3. Bài toán 3 – learning problem 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 λ = (A, B, π) sao cho cực đại hóa xác suất p(O|λ) – 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ố λ = (A, B, π) của mô 45 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 p(O|λ) đạt cực đại cục bộ bằng thuật toán Baum-Welch (tương đương EM [2]) 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 ξt(i,j) là xác suất ở trạng thái Si