Bài giảng Máy học và mạng Neural - Bài 5: Mô hình Markov ẩn - Vũ Đức Lung

07/08/2013 1 Máy học và mạng neural (Machine Learning and Neural Network) Giảng viên: TS. Vũ Đức Lung Email: lungvd@uit.edu.vn 1 2 Bài 05 – Mô hình Markov ẩn Hidden Markov Model 07/08/2013 2 Nội dung bài 04 – HMM  Các khái niệm  Thuộc tính Markov  Ba bài toán cơ bản của HMM  Thuật toán lan truyền xuôi  Thuật toán lan truyền ngược  Thuật toán lan truyền xuôi-ngược  Thuật toán Viterbi  Thuật toán Baum-Welch  Một số thuật toán khác  Ví dụ ứng dụng tổng hợp và nhận dạng giọng nói 3 Định nghĩa Mô hình Markov ẩn (tiếng Anh là Hidden Markov Model - HMM) là mô hình thống kê 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 và nhiệm vụ là xác định các tham số ẩn từ các tham số quan sát được, dựa trên sự thừa nhận này. Các tham số của mô hình được rút ra sau đó có thể sử dụng để thực hiện các phân tích kế tiếp, ví dụ cho các ứng dụng nhận dạng mẫu. 4 07/08/2013 3 Tại sao dùng mô hình Markov ẩn? • 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ì ẩn. • HMM dùng để giải quyết các bài toán xác lập mối nhân quả cục bộ (Fragmentation, Classification, Similarity Search). K 1 2 5 Ứng dụng của mô hình Markov ẩn • Nhận dạng tiếng nói. • Nhận dạng chữ viết tay. • Xử lý ngôn ngữ thống kê. • Dịch máy. • Tin sinh học: – Khớp xấp xỉ nhiều chuỗi. – Tìm Motif. – Tìm kiếm tương tự. 6 07/08/2013 4 Thuộc tính Markov Một dãy trạng thái ngẫu nhiên gọi là có thuộc tính Markov nếu như xác suất chuyển sang trạng thái tiếp theo chỉ phụ thuộc vào trạng thái hiện tại và quá khứ. – Dãy chuyển trạng quan sát được → Xích Markov. – Dãy chuyển trạng không quan sát được → Mô hình Markov ẩn. 7 Chuỗi(Xích) Makov - N là số lượng trạng thái trong chuỗi Makov (ở đây N=5), mỗi trạng thái được đánh số từ (1..N) - St là trạng thái của hệ thống ở thời điểm t - aij là xác suất chuyển trạng thái với các tính chất sau : tổng tất cả a =1, aij >=0 - Aij=P[qt=j|qt-1=i] 8 07/08/2013 5 Ví dụ Mô hình biểu diễn thời tiết - Mưa : Trạng thái 1 - Mây : Trạng thái 2 - Nắng : Trạng thái 3 - Ma trận xác suất chuyển trạng thái Hỏi : Xác suất để thời tiết 4 ngày liên tiếp : Nắng, Mưa, Mây, Nắng là bao nhiêu? Trả lời : Dãy quan sát O là : (Nắng, Mưa, Mây, Nắng) P(O) = P[3,1,2,3] =P[3]. P[1|3]. P[2,1]. P[3,2] =1 * a31 * a12 * a23 (P[j|i]=aij) 9 Chuỗi(Xích) Makov  Ví dụ: mô hình Markov bậc 1:  Ví dụ: mô hình Markov bậc 2: 10 07/08/2013 6 Ví dụ một mô hình Makov ẩn  Giả sử tôi có một người bạn sống ở rất xa.  Hàng ngày chúng tôi gọi điện thoại cho nhau và anh ta kể cho tôi nghe anh ta đã làm gì trong ngày.  Người bạn tôi chỉ có 3 công việc mà anh thích làm là 1) đi dạo, 2) đi chợ và 3) dọn phòng.  Hiển nhiên là sự lựa chọn phải làm gì thì phụ thuộc trực tiếp vào thời tiết hôm đấy thế nào.  Như vậy, tôi không nhận được thông tin cụ thể về thời tiết nơi anh bạn tôi sống nhưng tôi lại biết về xu hướng chung.  Dựa vào lời kể của công việc hàng ngày của anh ta, tôi có thể đoán về thời tiết hôm đó. 11 Ví dụ một mô hình Makov ẩn  Thời tiết được vận hành như một chuỗi Markov cụ thể  Có 2 trạng thái thời tiết, "Mưa" và "Nắng", nhưng tôi không quan sát trực tiếp, do đó, chúng là ẩn đối với tôi  Dựa vào lời kể các hoạt động của anh bạn mà ta có thể dự đoán được thời tiết hôm đó là như thế nào. Toàn bộ quá trình này là một mô hình Makov ẩn. Lời kể các hoạt động của anh bạn là dữ liệu quan sát 12 07/08/2013 7 Ví dụ một mô hình Makov ẩn  trạng thái = ('Mưa', 'Nắng')  dữ liệu quan sát = ('đi dạo', 'đi chợ', 'dọn phòng')  khả_năng_ban_đầu = {'Mưa': 0.6, 'Nắng': 0.4}  khả_năng_chuyển_dịch = { 'Mưa' : {'Mưa': 0.7, 'Nắng': 0.3}, 'Nắng' : {'Mưa': 0.4, 'Nắng': 0.6}, }  khả_năng_loại_bỏ = { 'Mưa' : {'đi dạo': 0.1, 'đi chợ': 0.4, 'dọn phòng': 0.5}, 'Nắng' : {'đi dạo': 0.6, 'đi chợ': 0.3, 'dọn phòng': 0.1}, } 13 Ví dụ một mô hình Makov ẩn 14 07/08/2013 8 Ví dụ: nhận dạng tiếng nói 15 Ví dụ: nhận dạng tiếng nói 16 07/08/2013 9 Mô hình Markov ẩn - HMM • qt - Trạng thái ở thời điểm t. • S={1, 2,..., N} - Tập tất cả các trạng thái ẩn. • ot= (ký hiệu) Quan sát tại thời điểm t. • V={1,2, ...,M} Tập tất cả các ký hiệu quan sát được. • A= [aij] xác suất chuyển trạng thái. • B=[bij] xác suất nhả ký hiệu. = [i] xác suất khởi trạng 17 Tiến trình thực hiện của HMM 18 07/08/2013 10 Ba bài toán cơ bản của HMM Bài toán 1: (Evaluation problem) Cho dãy quan sát O=o1o2...oT và HMM -  hãy xác định xác suất sinh dãy từ mô hình – P(O| ). 19 Ba bài toán cơ bản của HMM b11 b12 b13 b23 b22 b21 q1 q2 o1 o2 o3 07/08/2013 11 Ba bài toán cơ bản của HMM Bài toán 2: (Decoding problem) Cho dãy quan sát O=o1o2...oT và HMM -  hãy xác định dãy chuyển trạng Q=q1q2...qT cho xác suất sinh O lớn nhất (optimal path). 21 Ba bài toán cơ bản của HMM Ví dụ bài toán 2: (Bài toán giải mã – nhận dạng) Giả sử ta có dãy quan sát O = Walk, Shop, Walk, Clean và HMM -  hãy xác định dãy chuyển trạng Q = Rainy, Sunny, Rainny nào đó mà nó cho xác suất sinh dãy quan sát O lớn nhất (optimal path). b11 b12 b13 b23 b22 b21 q1 q2 o1 o2 o3 07/08/2013 12 Ba bài toán cơ bản của HMM Bài toán 3: (Learning problem) Hiệu chỉnh HMM -  để cực đại hoá xác suất sinh O – P(O| ) (tìm mô hình “khớp” dãy quan sát nhất. 23 Ba bài toán cơ bản của HMM b11 b12 b13 b23 b22 b21 q1 q2 o1 o2 o3 07/08/2013 13 Ba bài toán cơ bản của HMM Bài toán 1: (Evaluation problem) Tuy nhiên có NT dãy chuyển trạng 25 Thuật toán lan truyền xuôi 26 07/08/2013 14 Thuật toán lan truyền xuôi 27 Thuật toán lan truyền xuôi 28 07/08/2013 15 Thuật toán lan truyền xuôi Độ phức tạp thời gian: O(N2T) Độ phức tạp không gian: O(NT) 29 Ví dụ thuật toán lan truyền xuôi b11 b12 b13 b23 b22 b21 q1 q2 o1 o2 o3 Rain Sun Rain Sun Rain Sun walk clean a11 a22 a12 a21 B = [Bik]I,k shop 07/08/2013 16 Thuật toán lan truyền ngược Độ phức tạp thời gian: O(N2T) Độ phức tạp không gian: O(NT) 31 Thuật toán lan truyền xuôi-ngược 32 07/08/2013 17 Bài toán 2 - Thuật toán Viterbi 33 Thuật toán Viterbi – Giải quyết bài toán 2 • Ý tưởng chung: Nếu xác suất tốt nhất ở trạng thái cuối cùng qk=Sj có đi qua trạng thái qk-1=Si thì xác suất tại trạng thái qk-1=Si cũng phải tốt nhất s1 si sN sj aij aNj a1j qk-1 qk • k(i) = max P(q1 qk-1 , qk= sj , o1 o2 ... ok) = maxi [ aij bj (ok ) max P(q1 qk-1= si , o1 o2 ... ok-1) ] • Sau khi chọn được xác suất tốt nhất ở vị trí cuối cùng qk=Sj thì quay lui lại để tìm được chuỗi Q cho ra xác suất sinh dãy quan sát O lớn nhất 07/08/2013 18 Thuật toán Viterbi 35 Thuật toán Viterbi 36 07/08/2013 19 Thuật toán Viterbi 37 Thuật toán Viterbi 38 07/08/2013 20 Thuật toán Viterbi 39 Ví dụ thuật toán Viterbi b11 b12 b13 b23 b22 b21 q1 q2 o1 o2 o3 Rain Sun Rain Sun Rain Sun walk clean a11 a22 a12 a21 B = [Bik]I,k shop Bước 1 : Tại thời điểm t = 1 Tính tất cả xác suất các q sinh ra o1. Ở đây ta tính: P(q1|o1) hay là P (Rain|Walk) P(q2|o1) hay là P (Sun|Walk) Sau đó chọn xác suất cao nhất. Ở đây giả sử P(Sun|Walk) là max. Bước 2 : Cũng tính tất cả xác suất q sinh ra o2 nhưng chỉ dựa vào xác suất max của trạng thái ở bước 1. Tiếp theo, làm tương tự cho tới bước thứ T. Cuối cùng, tại trạng thái ở thời điểm T ta quay lui lại thì tìm được chuỗi Q có xác suât sinh ra O lớn nhất. Ở ví dụ này, chuỗi Q = Sun, Rain, Sun có xác suất sinh ra chuỗi quan sát chuỗi O = Walk, Clean, Shop là lớn nhất MAX MAX MAX 07/08/2013 21 Thuật toán Baum-Welch- giải quyết bài toán 3 41 Thuật toán Baum-Welch 42 07/08/2013 22 Thuật toán Baum-Welch 43 Thuật toán Baum-Welch 44 07/08/2013 23 Thuật toán Baum-Welch 45 Ví dụ thuật toán Baum-Welch b11 b12 b13 b23 b22 b21 q1 q2 o1 o2 o3 Rain Sun Rain 0.7 0.3 Sun 0.4 0.6 Walk Shop Clean Rain 0.1 0.4 0.5 Sun 0.6 0.3 0.1 Start : P(Rain) = 0.6 ; P(Sun) = 0.4 Hôm nay Hôm qua 07/08/2013 24 Ví dụ thuật toán Baum-Welch Rain Sun Rain 0.7 0.3 Sun 0.4 0.6 Walk Shop Clean Rain 0.1 0.4 0.5 Sun 0.6 0.3 0.1 Start : P(Rain) = 0.6 ; P(Sun) = 0.4 Hôm nay Hôm qua Ngày đầu tiên trạng thái quan sát được là từ walk sang walk( ký hiệu : walk walk). Giả sử dãy chuyển trạng thái ẩn sinh ra dãy quan sát trên là từ Rain chuyển sang Sun. Xác suất của walk walk nếu dãy Rain, Sun là : 0.6*0.1*0.3*0.6 Tức là P(Rain)*P(Rain|Walk)*P(Rain|Sun)*P(Sun|W alk) Ví dụ thuật toán Baum-Welch Ta có bảng thông số chuyển trạng thái tính cho 5 ngày như sau : Chuỗi O Best P(O) walk walk 0.0108 0.0042 0.0096 0.0864 walk walk 0.0108 0.0042 0.0096 0.0864 walk clean 0.0018 0.021 0.048 0.0144 clean shop 0.027 0.084 0.0064 0.0072 shop walk 0.0432 0.0168 0.0048 0.0432 Tổng 0.0936 0.1302 0.0784 0.2376 0.348 07/08/2013 25 Ví dụ thuật toán Baum-Welch Vậy Ma trận A Sẽ được chỉnh sửa các thông số lại sau khi quan sát 5 ngày liên tiếp như sau : Rain Sun Rain 0.374 0.269 Sun 0.225 0.683 Chuẩn hóa lại ??? Ví dụ thuật toán Baum-Welch Ma trận B được tính theo nguyên tắc chung như sau : Tổng số xác suất Max(qi|ok) của số lần xuất hiện trạng thái quan sát ok Tổng số xác suất Max(q|ok) của số lần xuất hiện trạng thái ok b(ok)= Ta tính thử thông số b của trạng thái clean được sinh ra bởi Rain, Sun : Chuỗi O Best P(O) walk clean 0.0018 0.021 0.048 0.0144 clean shop 0.027 0.084 0.0064 0.0072 Clean chỉ xuất hiện 2 lần nên ta liệt kê 2 dòng liên quan tới clean Tính b13 của trạng thái clean sinh ra bởi Rain : (0.048+0.084)/(0.048+0.084) = 1 Tính b23 của trạng thái clean sinh ra bởi Sun : (0.0144+0.0072)/(0.048+0.084) = ? Tương tự tính các thông số b của trạng thái walk, shop là ta sẽ thu được ma trận B hoàn chỉnh. 07/08/2013 26 Ví dụ thuật toán Baum-Welch Một số thuật toán khác • Thuật toán học Baldi-Chauvin (dùng Grandient Descent). • Thuật toán học Mamitsuka (kết hợp giữa Baum-Welch và Baldi-Chauvin cho phép học trên cả negative examples). 52 07/08/2013 27 HMM-based speech synthesis system SPEECH DATABASE Excitation Parameter extraction Spectral Parameter Extraction Excitation generation Synthesis filter TEXT Text analysis SYNTHESIZED SPEECH Parameter generation from HMMs Context-dependent HMMs & state duration models Labels Excitation parameters Excitation Spectral parameters Speech signal Training part Synthesis part Training HMMs Spectral parameters Excitation parameters Labels 53 Câu hỏi và bài tập 54 07/08/2013 28 Bài tập mẫu Cho HMM như hình vẽ, trong đó Rainy và Sunny là các trạng thái thuộc tập Q; Walk, Shop và Clean là các quan sát. Hãy xác định chuỗi chuyển trạng thái Q ẩn để có xác suất lớn nhất sinh ra chuỗi quan sát Shop  Clean  Walk Walk 55