Đề tài Nhận dạng tiếng nói và ứng dụng tích hợp với các phần mềm máy tính

ước 1: Thiết kế codebook có một vector. Vector này là nhân của tập vector huấn luyện. Bước 2: Nhân đôi kích thước của codebook bằng cách tách mỗi một vector yn trong codebook theo luật sau: (2.77) giá trị của thường chọn trong khoảng [0.01,0.05]. Bước 3: Sử dụng giải thuật phân nhóm K trung bình ở trên để tìm ra tập nhân tốt nhất cho codebook vừa được tách ra. Bước 4: Lặp lại bước hai và bước ba cho đến khi xây dựng được codebook có kích thước theo yêu cầu. Sơ đồ khối của thuật toán tách nhị phân như sau: Tìm nhân ban đầu Bắt đầu Tách nhân D’ = 0 Phân lớp vector Tìm các nhân Tính độ méo D’ D-D’<d m< M D’ = D m= 2*m Kết thúc Y N N m = 1 Y Hình 24 Sơ đồ khối thuật toán tách nhị phân Chương này đã trình bày cơ sở lý thuyết của các thuật toán trong khâu tiền xử lý tiếng nói. Tín hiệu sau khi được thu nhận từ card âm thanh được đưa vào modul phát hiện tiếng nói nhằm lọc thông tin dư thừa ra khỏi tín hiệu tiếng nói. Sau đó, tín hiệu này được trích chọn lấy tín hiệu đặc trưng bằng một trong hai phương pháp là mã hóa dự đoán tuyến tính hoặc phân tích hệ số phổ tần Mel. Cuối cùng tín hiệu được lượng tử hóa vector để tối thiểu hóa lượng thông tin trước khi đưa vào khâu nhận dạng. MÔ HÌNH MARKOV ẨN Trong chương một đã đề cập đến các phương pháp thường được sử dụng trong nhận dạng tiếng nói. Trong ba phương pháp này thì phương pháp nhận dạng mẫu là phương pháp đơn giản và khá hiệu quả. Các hệ thống nhận dạng tiếng nói theo phương pháp nhận dạng mẫu thường gặp nhất là nhận dạng mẫu có sử dụng mô hình Markov ẩn. Đây là một mô hình thống kê có rất nhiều ưu điểm trong nhận dạng tiếng nói. Chương này sẽ trình bày lý thuyết về mô hình Markov ẩn và những vấn đề cần chú ý khi cài đặt mô hình Markov ẩn. Để cho dễ hiểu trước hết chúng ta hãy nghiêm cứu một chút về chuỗi Markov rời rạc sau đó mở rộng nó sang mô hình Markov ẩn [7] [9]. CÁC QUÁ TRÌNH MARKOV RỜI RẠC Xét một hệ thống mà ở đó tại bất kì thời điểm nào ta cũng có thể mô tả nó bởi một trong N trạng thái phân biệt S1, S2,…,SN. Với những khoảng thời gian rời rạc cách đều hệ thống thực hiện chuyển trạng thái (có thể vẫn ở trạng thái đó) theo một tập xác suất nào đó gắn với từng trạng thái. Gọi thời gian ứng với việc thay đổi trạng thái đó là t =1,2,3,…., và gọi trạng thái ở thời điểm t là qt. Trong trường hợp tổng quát thì xác xuất để hệ thống ở một trạng thái nào dó phải phụ thuộc vào tất cả các trạng thái trước nó, tuy nhiên đối với chuỗi Markov bậc một thì xác suất này chỉ phụ thuộc vào trạng thái liền trước nó mà thôi. P[qt = j | qt-1 = i, qt-2 = k, ...] = P[qt = j | qt-1 = i] ( 3.1) Hơn nữa chúng ta chỉ quan tâm tới những tiến trình mà ở đó vế phải của công thức (3.1) độc lập với thời gian. Khi đó ta có một ma trận chuyển trạng thái như sau: aij = P[at = j | qt-1 = i] 1 £ i, j £ N ( 3.2) với các hệ số chuyển trạng thái có các thuộc tính sau: ( 3.3) ( 3.4) Quá trình thống kê trên gọi là một mô hình Markov có thể quan sát được bởi đầu ra của tiến trình tại bất kì thời điểm nào chỉ là môt trong số N trạng thái, và mỗi trạng thái lại gắn với một sự kiện vất lý nào đó. Hãy xem xét ví dụ mo hình Markov ba trạng thái về thời tiết như sau: Giả định thời tiết trong một ngày t được mô tả bởi một trong ba trang thái. Trạng thái 1: Trời mưa. Trạng thái 2: Trời nhiều mây. Trạng thái 3: Trời nắng. Ma trận chuyển trạng thái A như sau: ( 3.5) với mô hình trên các câu hỏi thường đặt ra là: Cho trạng trạng thái ở ngày thứ nhất (t=1) là trời nắng, tính xác suất để 7 ngày tiếp sau sẽ là: “Nắng-Nắng-Mưa-Mưa-Nắng-Mây-Nắng”. Giải: Kí hiệu chuỗi quan sát O ứng với các trạng thái của mô hình là: O = {S3, S3, S3, S1, S1,S3, S2, S3} tương ứng với t=1, 2, 3, … ,8 khi đó ta có ( 3.6) ở đây là xác xuất để trạng thái thứ i là trạng thái khởi đầu của mô hình, do đó ta có. ( 3.7 Cho mô hình và trạng thái khởi tạo hãy tính xác suất để mô hình vẫn ở trạng thái đó đúng trong d ngày tiếp sau Giải: Từ giả thiết ta có chuỗi quan sát tương ứng là: ( 3.8) xác suất của chuỗi với mô hình là. ( 3.9) ở đây pi(d) là hàm xác suất rời rạc để mô hình ở trạng thái i trong d ngày. Dựa vào pi(d) chúng ta có thể tính được số lần mong đợi để hệ thống ở nguyên trạng thái đó trong một với điều kiện nó chính là trạng thái khởi đầu của mô hình đó. ( 3.10) do đó ngày mong đợi liên tiếp nhau để mô hình có trạng thái là trời nắng là: 1/(1-0.2) = 5 ngày, trời mưa là: 1/(1-0.6) = 2.5 ngày và nhiều mây là: 1/(1-0.4) = 1.67 ngày. MÔ HÌNH MARKOV ẨN Khái niệm Mô hình Markov mà chúng ta thảo luận ở phần trên là mô hình có thể quan sát được, mô hình này có rất nhiều hạn chế khi áp dụng nó vào giải quyết các vấn đề trong thực tế. Trong phần này chúng ta sẽ mở rộng nó để bao gồm cả trường hợp trong đó chuỗi quan sát là hàm xác suất của trạng thái, kết quả ta thu được mô hình là một quá trình ngẫu nhiên được nhúng hai lần với một quá trình ngẫu nhiên chính không thể quan sát được một cách trực tiếp mà chỉ có thể quan sát được thông qua một tập quá trình ngẫu nhiên khác – các quá trình ngẫu nhiên tạo ra các chuỗi quan sát. Để hiểu rõ hơn về khái niệm mô hình Markov ẩn chúng ta hãy nghiên cứu thí nghiệm tung đồng xu. Mô hình tung đồng xu: Giả sử bạn đang ngồi trong một căn phòng có một bức tường chắn do đó bạn không thể nhìn thấy được điều gì đang xảy ra ở phía bên kia của bức tường, ở đó một người đang thực hiện một thí nghiệm tung đồng xu. Người này sẽ không nói cho ban biết là anh ta tung đồng xu nào mà chỉ nói cho bạn biết kết quả tung đồng xu là xấp hay ngửa. Do đó một chuỗi các thí nghiệm tung đồng xu “ẩn” đã được thực hiện, với chuỗi quan sát là một dãy các mặt xấp, ngửa của các đồng xu. Thông thường chuỗi quan sát này có dạng như sau: O = {o1,o2,….,oT} = {H T H T… T} ( 3.11) với mô hình thí nghiệm này thì một vấn đề đặt ra là làm sao chúng ta có thể xây dựng nên một mô hình Markov ẩn (HMM) để giải thích cho các chuỗi quan sát được. Hai vấn đề mà ta cần phải giải quyết để có thể xây dựng nên một HMM là: Các trạng thái của mô hình tương ứng với cái gì. Mô hình cần bao nhiêu trạng thái. Đối với thí nghiệm trên chúng ta có thể có ba lựa chon sau: Giả định chỉ có một đồng xu được tung khi đó chúng ta có thể mô hình hoá thí nghiệm trên bằng mô hình có hai trạng thái với mỗi trạng thái của nó ứng với kết quả của lần tung đồng xu trước đó. Đây là mô hình Markov có thể quan sát được và chỉ có một vấn đề cần phải giả quyết là xác định giá trị tốt nhất cho từng tham số của mô hình (xác suất mặt xấp, ngửa). Mô hình được thể hiện trong hình 3.1.1. Mô hình thứ hai là một mô hình có hai trạng thái, trong đó mỗi trạng thái tương ứng với một mặt của đồng xu (Hình 3.1.2). Mỗi trạng thái của mô hình được đặc trưng bởi. Phân bố xác suất mặt sấp hay mặt ngửa. Xác xuất chuyển đổi giữa các trạng thái, được mô tả bởi ma trận chuyển trạng thái. Mô hình thứ ba ứng với trường hợp có ba đồng xu được sử dụng trong thí nghiệm. Việc lựa chọn đồng xu nào do một số sự kiện mang tính xác suất quyết định.(Hình 3.1.3). Hình 31 Ba mô hình Markov ẩn cho thí nghiệm tung đồng xu Với các mô hình trên thì câu hỏi đặt ra là mô hình nào giải thích tốt nhất cho chuỗi quan sát thu được. Với mô hình thứ nhất thì chỉ có một tham số ma ta chưa biết là P(H), với mô hình thứ hai có bốn tham số mà ta chưa biết là {a11, a22, P1,P2}, còn đối với mô hình thư ba thì có chín tham số mà ta chưa biết là (a11, a12, a21, a22, a31, a32, P1, P2, P3). Có thể thấy rằng những mô hình có bậc tự do lớn hơn dường như sẽ mô hình hóa thí nghiệm trên tốt hơn, điều này chỉ đúng về mặt lý thuyết còn trên thực tế có một số giới hạn về kích thước của mô hình cần phải quan tâm đến. Thành phần của mô hình Markov ẩn Một mô hình Markov ẩn được mô tả bởi 3 thành phần cơ bản: N-Số trạng thái của mô hình: Mặc dù số trạng thái của mô hình là ẩn nhưng trong các ứng dụng ở thực tế thì thường có một ý nghĩa vật lý nào đó gắn với các trạng thái của mô hình. Ta đánh nhãn các trạng thái riêng rẽ là {1,2,3,4,..,N} và kí hiệu trạng thái ở thời điểm t là qt. M- Số biểu tượng có thể quan sát được ứng với mỗi trạng thái: Các biểu tượng có thể quan sát được thường tương ứng với sự kiện vật lý đàu ra của một hệ thống đang được mô hình hoá. Trong thí nghiệm tung đồng xu thì số biểu tượng có thể quan sát được ứng với từng trạng thái chính là mặt sấp và mặt ngửa của đồng xu. Ta kí hiệu các biểu tượng đó là V = {v1,v2,…,vM}. Ma trận xác suất chuyển trạng thái A = {aij}:Với aij là xác suất để trạng thái ở thời điểm t là i và trạng thái ở thời điểm t+1 là j. Do đó ta có. ( 3.12) ( 3.13) trong trường hợp tổng quát thì aij>0 với mọi i,j nằm trong khoản từ 1 đến N tuy nhiên trong nhiều hệ thống aij lại có thể bằng không ứng với một số giá trị nào đó của i và j. Ma trận phân bố xác suất các kí hiệu quan sát B = {bi(k)}. Trong đó bj(k) là xác suất nhận được kí hiệu quan sát vk ở trạng thái j: bj(k) = P[ot=vk | qt=j] 1£k£M ( 3.14) ( 3.15) Ma trận phân bố xác suất trạng thái ban đầu p = {pi} Trong đó pi là xác suất mô hình ở trạng thái i tại thời điểm ban đầu t=1: p = P[q1=i] ( 3.16) ( 3.17) như vậy để đặc tả đầy đủ một mô hình Markov ẩn thì chúng ta cần các tham số là số trạng thái N, số biểu tượng quan sát M và các ma trạn xác suất A,B,p. Người ta thường kí hiệu một mô hình như trên dưới dạng: ( 3.18) Ba bài toán cơ bản của mô hình Markov ẩn Với mô hình Markov ẩn được mô tả như trên thì có ba bài toán cơ bản cần phải giải quyết để có thể áp dụng nó vào thực tế là: Bài toán một Vấn đề: Cho một chuỗi quan sát O = O1 O2 … OT, và một mô hình Markov ẩn , Tính xác suất của chuỗi quan sát O với mô hình một cách hiệu quả nhất. Giải pháp: Đây là bài toán đánh giá, nghĩa là cho trước mô hình và dãy quan sát, ta phải tính xác suất mô hình với dãy quan sát đã được tạo ra. Có thể xem đây là một kiểu đánh giá xem mô hình được cho có tốt với dãy quan sát đó hay không. Trong trường hợp ta phải chọn một trong số nhiều mô hình thì giải pháp cho bài toán 1 sẽ cho ta sự lựa chọn được mô hình thích hợp nhất đối với dãy quan sát. Cách tường minh nhất để tính được xác suất trên là thông qua việc đánh số mọi dãy trạng thái chiều dài T (T là số lượng quan sát trong dãy). Có NT dãy trạng thái như vậy. Xét một trong các dãy trạng thái đó: q = (q1q2...qT) ( 3.19) Trong đó q1 là trạng thái khởi đầu. Xác suất của dãy quan sát O cho bởi dãy trạng thái q ở trên sẽ là: ( 3.20) Giả sử rằng các quan sát là độc lập thống kê, ta có: ( 3.21) Xác suất của một dãy trạng thái q như vậy là: ( 3.22) Xác suất để O và q xảy ra đồng thời là: ( 3.23) Xác suất của O cho bởi mô hình chính là lấy tổng của xác suất trên tất cả các dãy trạng thái có thể có của q, tức là: ( 3.24) Việc tính toán P(O|l) theo định nghĩa trực tiếp của nó như trên bao gồm 2T.NT phép tính, do tại mọi thời điểm t=1,2,...T có N trạng thái có thể đạt được (có NT chuỗi trạng thái có thể), và với mỗi dãy trạng thái như vậy cần khoảng 2T phép tính cho mỗi toán hạng trong tổng ở công thức trên. Khối lượng tính toán nhiều như vậy trong thực tế là không thể thực hiện được (với những giá trị khá nhỏ của N và T, chẳng hạn N=5 và T=100 thì cũng cần phải thực hiện khoảng 1072 phép tính). Vì vậy, ta cần phải có một giải thuật đơn giản hơn để giải quyết vấn đề này. Dưới đây là hai thủ tục để giải quyết vấn để này. Cần phải chú ý là nếu chỉ để tính xác suất của một chuỗi quan sát với một mô hình thì ta chỉ cần sử dụng thủ tục tiến nhưng ở đây giới thiệu cả thủ tục lùi để do nó được sử dụng để giải quyết vấn đề thứ 3. Thủ tục tiến (Forward Procedure) Xét biến tiến at(i) được định nghĩa như sau: at(i) = P(o1o2...ot, qt=i|l) ( 3.25) Đó là xác suất của dãy quan sát bộ phận o1o2...ot và trạng thái i đạt được tại thời điểm t. Ta có thể dùng quy nạp để tính at(i) như sau: Khởi tạo: ( 3.26) Quy nạp: ( 3.27) Kết thúc: ( 3.28) Bước 1 khởi tạo các biến a1(i) là xác suất đồng thời trạng thái i và quan sát ban đầu o1. Bước quy nạp là cốt lõi của thủ tục, được minh họa trong hình 3.2 (a). Hình này cho thấy ta có thể đạt tới trạng thái j ở thời điểm t+1 từ N trạng thái i, , ở thời điểm t như thế nào. Vì at(i) là xác suất của biến cố o1o2 ... ot và trạng thái ở thời điểm t là i, nên tích at(i)aij là xác suất đồng thời của biến cố o1o2...ot và trạng thái j ở thời điểm t+1 qua trạng thái i ở thời điểm t. Lấy tổng tất cả các tích này theo tất cả các trạng thái i, , ở thời điểm t ta sẽ nhận được xác suất trạng thái j ở thời điểm t+1 với tất cả những quan sát từng phần ở trước thời điểm t+1. Do đó dễ dàng nhận thấy rằng at+1(j) bằng tổng trên nhân với bj(ot+1). Cuối cùng, bước 3 cho ta kết quả P(O|l) là tổng của những biến tiến cuối cùng aT(i), đó là do định nghĩa: aT(i) = P(o1o2...ot, qT=i|l) ( 3.29) Vì vậy P(O|l) chính là tổng của các aT(i), Ta có nhận xét rằng, việc tính toán theo thủ tục tiến cần khoảng N2T phép tính, cụ thể cần N(N+1)(T-1)+N phép tính nhân và N(N-1)(T-1) phép tính cộng. Chẳng hạn với N=5 và T=100 thì ta cần khoảng 3000 phép tính, nhỏ hơn rất nhiều so với phương pháp tính trực tiếp cần đến 1072 phép tính. Trong thực tế, để tính biến tiến at(i) cho hiệu quả người ta thường dùng cấu trúc lưới như ở hình 3.2 (b). Ý tưởng của cách làm này là : vì chỉ có N trạng thái nên tất cả dãy trạng thái có thể có đều được cấu thành từ N nút này cho dù dãy quan sát có chiều dài bao nhiêu. Ở thời điểm t=1 (mức thời gian đầu tiên trong lưới), ta cần tính những giá trị a1(i), . Ở những thời điểm t = 2, 3, ... T ta chỉ cần tính những giá trị at(j), 1£j£N, ở đó mỗi lần tính chỉ liên quan đến N giá trị trước at-1(i) bởi vì mỗi nút trong lưới có thể đạt tới từ N nút ở thời điểm trước đó. Hình 32 Chuỗi thao tác tính toán biến trạng thái. (a) Chuỗi thao tác để tính biến tiến (b) Tính dưới dạng một mạng lưới các quan sát t và trạng thái i Thủ tục lùi (Backward Procedure) Tương tự ta có thể xét biến lùi bt(i) được định nghĩa như sau: bt(i) = P(ot+1ot+2...oT, qt=i|l) ( 3.30) bt(i) là xác suất của dãy quan sát bộ phận từ thời điểm t+1 đến thời điểm cuối, căn cứ vào trạng thái i tại thời điểm t và mô hình l. Có thể tính bt(i) bằng quy nạp như sau: 1. Khởi đầu: ( 3.31) 2. Quy nạp: ( 3.32) 3. Kết thúc: ( 3.33) Hình 33 Thao tác tính Bài toán hai Vấn đề: Cho chuỗi quan sát O = O1 O2 … OT, và mô hình . Tìm chuỗi trạng thái tối ưu theo tương ứng với chuỗi quan sát một điều kiện nào đó. Giải pháp: Không giống như bài toán một chúng ta có thể tìm ra giải pháp chính xác, ở bài toán hai ta có nhiều cách giải quyết để tìm ra một dãy trạng thái tối ưu ứng với một chuỗi quan sát đã cho. Khó khăn nằm ở chỗ định nghĩa dãy trạng thái thế nào là tối ưu - đó là vì có nhiều tiêu chuẩn tối ưu. Chẳng hạn một tiêu chuẩn tối ưu là chọn ra trạng thái qt mà nó phù hợp nhất một cách riêng biệt tại thời điểm t. Tiêu chuẩn tối ưu này làm cực đại số kỳ vọng của từng trạng thái đúng riêng rẽ. Để thực hiện giải pháp cho vấn để này, ta định nghĩa một biến xác suất như sau: ( 3.34) Đó là xác suất để mô hình ở trạng thái Si tại thời điểm t với dãy quan sát O. có thể được tính theo biến tiến và biến lùi như sau: ( 3.35) ( 3.36) Ta thấy giải thích cho dãy quan sát bộ phận o1o2...ot và trạng thái i tại thời điểm t. Còn giải thích cho phần còn lại của dãy quan sát ot+1ot+2...oT với điều kiện trạng thái qt=i tại thời điểm t. Dễ ràng nhận thấy ( 3.37) Sử dụng ta có thể tính được trạng thái phù hợp nhất tại thời điểm t như sau: ( 3.38) Mặc dù biểu thức trên làm cực đại số lượng mong đợi các trạng thái đúng (bằng cách chọn trạng thái phù hợp nhất ứng với thời điểm t) nhưng vẫn có một vài vấn đề với dãy trạng thái nhận được. Ví dụ khi HMM có các xác suất chuyển đổi trạng thái là 0 (aij = 0 đối với một vài i,j) thì dãy trạng thái "tối ưu" nhận được trong thực tế có thể không phải là một dãy trạng thái hợp lệ. Đó là do phương pháp trên chỉ đơn giản là xác định trạng thái phù hợp nhất tại mỗi thời điểm mà không quan tâm đến xác suất xảy ra của các dãy trạng thái. Một giải pháp cho vấn đề này là thay đổi tiêu chuẩn tối ưu. Ví dụ, chúng ta có thể tính được dãy trạng thái mà làm cực đại số lượng mong đợi các cặp trạng thái đúng (qt, qt+1) hay bộ ba trạng thái đúng (qt, qt+1, qt+2),... Mặc dù tiêu chuẩn này có thể hợp lý đối với một số ứng dụng nhưng tiêu chuẩn được sử dụng rộng rãi nhất là tìm ra chuỗi trạng thái đơn tốt nhất, nghĩa là làm cực đại P(q|O,l) cũng là làm cực đại P(q,O|l). Phương pháp quy hoạch động để tìm chuỗi trạng thái đơn tốt nhất chính là giải thuật Viterbi sau đây. Thuật toán Viterbi Để tìm dãy trạng thái đơn tốt nhất q = (q1q2...qT) đối với dãy quan sát O = (o1o2...oT), ta định nghĩa đại lượng sau: ( 3.39) là xác suất lớn nhất dọc theo một đường đi đơn tại thời điểm t của t quan sát đầu tiên trong đó có quan sát cuối cùng là ở trạng thái i. Bằng quy nạp ta có: ( 3.40) Thuật toán: Ta sử dụng mảng để giữ lại các đối số làm cực đại biểu thức trên ứng với mỗi t và j. 1. Khởi tạo: ( 3.41) 2. Vòng lặp: ( 3.42a) ( 3.42b) 3. Kết thúc: ( 3.43a) ( 3.43b) 4. Quay ngược lại tìm đường đi (dãy trạng thái): ( 3.44) Ước lượng tham số của mô hình Đây là bài toán khó nhất trong ba bài toán mà mô hình Markov ẩn cần giải quyết. Vấn để ở đây là phải tìm ra một phương pháp để điều chỉnh các tham số của mô hình để cực đại hoá xác suất của chuỗi quan sát với mô hình đó. Trên thực tế thì không có một giải pháp tối ưu nào cho vấn đề này, tuy nhiên chúng ta có thể chọn mô hình để nó làm cực đại địa phương xác suất của chuỗi quan sát O với mô hình bằng cách sử dụng một thủ tục lặp giống như phương pháp của Baum-Welch hay là sử cụng kỹ thuật gradient. Trong phần này ta sẽ tìm hiểu phương pháp lặp do Baum và các đồng nghiệp của ông ta đưa ra. Để mô tả thủ tục ước lượng lại tham số mô hình, đầu tiên ta định nghĩa là xác suất có được trạng thái i tại thời điểm t và trạng thái j tại thời điểm t+1 với mô hình l và dãy quan sát O đã cho, tức là: ( 3.45) Từ định nghĩa các biến tiến và biến lùi ở phần trước, ta có thể viết lại dưới dạng như sau: ( 3.46) Ta đã định nghĩa ở phần trước là xác suất có được trạng thái i ở thời điểm t với dãy quan sát O và mô hình l, vì vậy ta có mối liên hệ giữa với như sau: ( 3.47) Nếu lấy tổng theo thời gian t, ta nhận được đại lượng chính là kỳ vọng số lần hệ thống ở trạng thái i, hay tương đương với kỳ vọng số chuyển đổi trạng thái được thực hiện từ trạng thái i (nếu bỏ qua t=T trong phép lấy tổng). Tương tự, lấy tổng theo t (từ t=1 đến t=T-1) là kỳ vọng số lần chuyển đổi từ trạng thái i sang trạng thái j, tức là: = kỳ vọng số chuyển trạng thái từ trạng thái i trong O ( 3.48) =kỳ vọng chuyển đổi từ trạng thái i sang trạng thái j trong O ( 3.49) Từ các công thức trên ta có thể đưa ra một phương pháp đánh giá lại tham số của một mô hình Markov ẩn như sau: Ước lượng p: = kỳ vọng số lần ở trạng thái i tại thời điểm t=1 = = (3.50) Ước lượng A: = = ( 3.51) Ước lượng B: = = ( 3.52) Nếu ta định nghĩa mô hình hiện thời là , sau khi áp dụng các công thức trên ta được mô hình . Baum và các đồng sự đã chứng minh được rằng: Hoặc l đạt trạng thái tới hạn của một hàm likelihood, tức là = l Hoặc là mô hình "tốt hơn" mô hình l theo nghĩa P(O|) > P(O|l), tức là đã tìm ra mô hình mới giải thích được dãy quan sát O tốt hơn so với mô hình cũ l. Dựa vào thủ tục trên, nếu ta lặp lại việc ước lượng bằng cách thay vào vị trí của l thì ta có thể cải tiến được xác suất của dãy quan sát O cho bởi mô hình đó cho đến khi đạt được trạng thái tới hạn. Các loại mô hình Markov ẩn Để phân loại mô hình Markov ẩn ta có thể dựa vào cấu trúc của ma trận chuyển trạng thái A. Trong trường hợp tổng quát ta có mô hình Markov ẩn kết nối đầy đủ, nghĩa là từ một trạng thái ta có thể chuyển tới bất kì trạng thái nào chỉ bằng một lần chuyển. Loại mô hình này có tính chất là các hệ số aij đều dương. Ví dụ về loại mô hình này được trình bày trong hình 3.4 (a) trong đó N = 4 trạng thái. Hình 34 Các loại mô hình Markov ẩn . (a) Mô hình liên kết đầy đủ 4 trạng thái. (b) Mô hình trái-phải (Bakis) 4 trạng thái. Đối với một số ứng dụng, đặc biệt là các ứng dụng xử lý tiếng nói, để mô hình hóa những đặc trưng của tín hiệu thì các mô hình kết nối đầy đủ như trên là không thích hợp. Ta phải cần đến những mô hình hiệu quả hơn, đó là các mô hình trái-phải hay còn gọi là mô hình Bakis. Sở dĩ mô hình có tên trái-phải là vì dãy trạng thái ẩn bên dưới mô hình có tính chất : khi thời gian tăng lên thì hoặc là chỉ số trạng thái cũng tăng lên, hoặc là giữ nguyên trạng thái cũ, tức là hệ thống chuyển trạng thái từ trái sang phải. Rõ ràng loại mô hình trái-phải này rất thích hợp khi mô hình hóa những tín hiệu mà thuộc tính của nó thay đổi theo thời gian, chẳng hạn như tín hiệu tiếng nói. Tính chất cơ bản của mô hình Markov ẩn trái-phải là các xác suất chuyển trạng thái đều thỏa mãn: ( 3.53) Tức là không cho phép chuyển sang trạng thái có chỉ số nhỏ hơn chỉ số trạng thái hiện tại. Hơn nữa, xác suất trạng thái ban đầu có tính chất: ( 3.54) Bởi vì dãy trạng thái phải bắt đầu ở trạng thái 1 và kết thúc ở trạng thái N. Thông thường mô hình trái-phải còn có thêm những ràng buộc nhằm đảm bảo không có sự thay đổi quá lớn về khoảng cách giữa các trạng thái. Các ràng buộc đó có dạng: ( 3.55) Trong ví dụ ở hình 3.4(b), Di = 2, tức là không được phép nhảy quá 2 trạng thái. Ma trận chuyển trạng thái có dạng: ( 3.56) Trạng thái cuối cùng trong mô hình trái-phải có các hệ số của ma trận vị trí là: ( 3.57) Một điểm lưu ý quan trọng là những ràng buộc trên mô hình trái-phải không ảnh hưởng đến thủ tục ước lượng lại tham số dùng trong quá trình huấn luyện HMM. Đó là vì những tham số có giá trị 0 lúc khởi tạo sẽ vẫn là 0 trong suốt thủ tục ước lượng lại. Những vấn đề cần thực hiện đối với mô hình Markov ẩn Trên đây chúng ta chỉ mới thảo luận về lý thuyết của mô hình Markov ẩn. Để có thể cài đặt được mô hình Markov ẩn trong các ứng dụng thực tế ta cần phải thực hiện một số vấn đề sau: Lấy tỷ lệ Tại sao ta cần phải lấy tỉ lệ khi cài đặt thủ tục ước lượng tham số cho mô hình Markov ẩn? Hãy xem lại định nghĩa at(i) ở phương trình (3.29). Có thể thấy rằng at(i) là tổng của một số lượng lớn các số hạng có dạng: Với qt=1. Vì các số hạng và nhỏ hơn 1 (nói chung là nhỏ hơn 1 rất nhiều), nên khi t lớn, mỗi số hạng của at(i) sẽ tiến dần về 0 theo tốc độ của hàm mũ. Với t đủ lớn, miền giá trị của at(i) sẽ vượt quá giới hạn dữ liệu cho phép của bất kì máy tính nào. Vì vậy trong thủ tục ước lượng ta cần phải lấy tỉ lệ thích hợp cho các tính toán để tránh bị tràn số. Ý tưởng cơ bản của thủ tục lấy tỉ lệ là nhân at(i) với một hệ số tỉ lệ, hệ số này phải độc lập với i (tức là chỉ phụ thuộc vào t) và có mục đích giữ cho giá trị at(i) sau khi lấy tỉ lệ không nằm ngoài khoảng cho phép của máy tính. Thủ tục lấy tỉ lệ này cũng được thực hiện tương tự cho các hệ số bt(i) (vì các hệ số này cũng có xu hướng tiến nhanh về 0), và ở cuối thủ tục ước lượng, các hệ số tỉ lệ này sẽ được loại bỏ một cách chính xác. Để hiểu rõ quá trình thực hiện của thủ tục lấy tỉ lệ, chúng ta hãy xem lại công thức ước lượng các hệ số aij của ma trận chuyển trạng thái ở phương trình (4.54): ( 3.58) Do : Nên : ( 3.59) Quá trình tính at(i) như sau. Ta dùng kí hiệu at(i) để chỉ giá trị khi chưa lấy tỉ lệ, để chỉ giá trị đã lấy tỉ lệ, để chỉ giá trị trung gian trước khi lấy tỉ lệ. Ban đầu, với t=1, ta tính at(i) theo phương trình (3.19) đồng thời đặt và với Với mỗi t (2£t£T), trước tiên ta tính theo công thức quy nạp ở phương trình (3.20) theo các giá trị đã lấy tỉ lệ trước đó, tức là : ( 3.60a) Ta đặt hệ số tỉ lệ như sau : (4.60b) Và gán : (4.60c) khi đó hệ số được tính như sau : ( 3.61) Bằng quy nạp ta có thể viết dưới dạng : ( 3.62) Vì vậy sẽ được viết như sau : ( 3.63) Tức là mỗi at(i) được lấy tỉ lệ theo hệ số là tổng tất cả các trạng thái của at(i). Tiếp theo chúng ta sẽ tính các số hạng bt(i) theo công thức đệ quy của thủ tục Backward. Lưu ý rằng ta dùng cùng một hệ số tỉ lệ ở mỗi thời điểm t cho các giá trị b như đã dùng cho các giá trị a. Các giá trị bt(i) được lấy tỉ lệ có dạng : ( 3.64) Theo các biến đã được lấy tỉ lệ, công thức ước lượng ở phương trình (3.61) trở thành : ( 3.65) trong đó mỗi có thể được viết dưới dạng: ( 3.66) v có dạng: ( 3.67) Phương trình (3.56) sẽ trở thành: ( 3.68) Ta nhận thấy CtDt+1 có dạng : ( 3.69) Rõ ràng CT là độc lập với t nên CtDt+1 có thể được loại bỏ khỏi tử số và mẫu số của phương trình (3.59) và ta nhận được phương trình ước lượng aij chính xác. Tương tự ta có thể áp dụng thủ tục lấy tỉ lệ cho các công thức ước lượng B. ( 3.70) Ta lưu ý rằng thủ tục lấy tỉ lệ ở phương trình (3.63) không nhất thiết phải được áp dụng ở mỗi thời điểm t, mà có thể được áp dụng khi nào muốn hay khi cần thiết để tránh tràn số. Nếu không áp dụng việc lấy tỉ lệ tại thời điểm t thì ta cần đặt ct=1 ở thời điểm đó. Do áp dụng thủ tục tính tỉ lệ nên thủ tục tính xác suất P(O|l) cũng phải thay đổi. Chúng ta không thể đơn giản chỉ lấy tổng các giá trị bởi vì các giá trị này đã được lấy tỉ lệ. Tu