Bài giảng Máy học và Mạng Neural: Bài 5

07/08/2013

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

Bài 05 – Mô hình Markov ẩn Hidden Markov Model

07/08/2013

Nội dung bài 04 – HMM

 Các khái niệm  Thuộc tính Markov  Ba bài toán cơ bản của HMM  Thuật toán lan truyền xuôi  Thuật toán lan truyền ngược  Thuật toán lan truyền xuôi-ngược  Thuật toán Viterbi  Thuật toán Baum-Welch  Một số thuật toán khác  Ví dụ ứng dụng tổng hợp và nhận dạng giọng nói

Định nghĩa

 Mô hình Markov ẩn (tiếng Anh là Hidden Markov Model - HMM) là mô hình thống kê trong đó hệ thống được mô hình hóa được cho là một quá trình Markov với các tham số không biết trước và nhiệm vụ là xác định các tham số ẩn từ các tham số quan sát được, dựa trên sự thừa nhận này. Các tham số của mô hình được rút ra sau đó có thể sử dụng để thực hiện các phân tích kế tiếp, ví dụ cho các ứng dụng nhận dạng mẫu.

07/08/2013

Tại sao dùng mô hình Markov ẩn?

• Nhiều bài toán thực tế được biểu diễn dưới mối quan hệ nhân quả, nhưng chỉ quan sát được phần quả còn phần nhân thì ẩn. • HMM dùng để giải quyết các bài toán xác lập mối nhân quả cục bộ (Fragmentation, Classification, Similarity Search).

1

2 K

…

Ứng dụng của mô hì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ự.

07/08/2013

Thuộc tính Markov

Một dãy trạng thái ngẫu nhiên gọi là có thuộc tính Markov nếu như xác suất chuyển sang trạng thái tiếp theo chỉ phụ thuộc vào trạng thái hiện tại và quá khứ. – Dãy chuyển trạng quan sát được → Xích Markov. – Dãy chuyển trạng không quan sát được → Mô hình Markov ẩn.

Chuỗi(Xích) Makov

- N là số lượng trạng thái trong chuỗi Makov (ở đây N=5), mỗi trạng thái được đánh số từ (1..N)

- St là trạng thái của hệ thống ở

thời điểm t

- aij là xác suất chuyển trạng thái với các tính chất sau : tổng tất cả a =1, aij >=0 - Aij=P[qt=j|qt-1=i]

07/08/2013

Ví dụ Mô hình biểu diễn thời tiết

- Mưa : Trạng thái 1 - Mây : Trạng thái 2 - Nắng : Trạng thái 3 - Ma trận xác suất chuyển trạng thái

Hỏi : Xá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 sá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)

Chuỗi(Xích) Makov

 Ví dụ: mô hình Markov bậc 1:

 Ví dụ: mô hình Markov bậc 2:

07/08/2013

Ví dụ một mô hình Makov ẩn

 Giả sử tôi có một người bạn sống ở rất xa.  Hàng ngày chúng tôi gọi điện thoại cho nhau và anh ta kể cho

tôi nghe anh ta đã làm gì trong ngày.

 Người bạn tôi chỉ có 3 công việc mà anh thích làm là 1) đi dạo,

2) đi chợ và 3) dọn phòng.

 Hiển nhiên là sự lựa chọn phải làm gì thì phụ 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 cụ thể về thời tiết nơi

anh bạn tôi sống nhưng tôi lạ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 có thể

đoán về thời tiết hôm đó.

Ví dụ một mô hình Makov ẩn

 Thời tiết được vận hành như một chuỗi Markov cụ thể  Có 2 trạng thái thời tiết, "Mưa" và "Nắng", nhưng tôi

không quan sát trực tiếp, do đó, chúng là ẩn đối với tôi  Dựa vào lời kể các hoạt động của anh bạn mà ta có thể dự đoán được thời tiết hôm đó là như thế nào. Toàn bộ quá trình này là một mô hình Makov ẩn. Lời kể các hoạt động của anh bạn là dữ liệu quan sát

07/08/2013

Ví dụ một mô hình Makov ẩn

'Mưa' : {'Mưa': 0.7, 'Nắng': 0.3}, 'Nắng' : {'Mưa': 0.4, 'Nắng': 0.6}, }

 trạng thái = ('Mưa', 'Nắng')  dữ liệu quan sát = ('đi dạo', 'đi chợ', 'dọn phòng')  khả_năng_ban_đầu = {'Mưa': 0.6, 'Nắng': 0.4}  khả_năng_chuyển_dịch = {  khả_năng_loại_bỏ = {

'Mưa' : {'đi dạo': 0.1, 'đi chợ': 0.4, 'dọn phòng': 0.5}, 'Nắng' : {'đi dạo': 0.6, 'đi chợ': 0.3, 'dọn phòng': 0.1}, }

Ví dụ một mô hình Makov ẩn

07/08/2013

Ví dụ: nhận dạng tiếng nói

07/08/2013

Mô hình Markov ẩn - HMM

• qt - Trạng thái ở thời điểm t. • S={1, 2,..., N} - Tập tất cả các trạng thái ẩn. • ot= (ký hiệu) Quan sát tại thời điểm t. • V={1,2, ...,M} Tập tất cả các ký hiệu quan sát được. • A= [aij] xác suất chuyển trạng thái.

• B=[bij] xác suất nhả ký hiệu.

= [i] xác suất khởi trạng

Tiến trình thực hiện của HMM

07/08/2013

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 xác định xác suất sinh dãy từ mô hình – P(O| ).

Ba bài toán cơ bản của HMM

b11

b23

b21

b12

b22

b13

07/08/2013

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 xác định dãy chuyển trạng Q=q1q2...qT cho xác suất sinh O lớn nhất (optimal path).

Ba bài toán cơ bản của HMM

b11

b23

b21

b12

b22

b13

Ví dụ bài toán 2: (Bài toán giải mã – nhận dạng) Giả sử ta có dãy quan sát O = Walk, Shop, Walk, Clean … và HMM -  hãy xác định dãy chuyển trạng Q = Rainy, Sunny, Rainny … nào đó mà nó cho xác suất sinh dãy quan sát O lớn nhất (optimal path).

07/08/2013

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 đại hoá xác suất sinh O – P(O| ) (tìm mô hình “khớp” dãy quan sát nhất.

Ba bài toán cơ bản của HMM

b11

b23

b21

b12

b22

b13

07/08/2013

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 trạng

Thuật toán lan truyền xuôi

07/08/2013

Thuật toán lan truyền xuôi

07/08/2013

Thuật toán lan truyền xuôi

Độ phức tạp thời gian: O(N2T) Độ phức tạp không gian: O(NT)

Ví dụ thuật toán lan truyền xuôi

b11

b23

b21

b22

b13

b12

Rain

a11

Sun

a12

a21 a22

walk

clean

shop

B = [Bik]I,k

07/08/2013

Thuật toán lan truyền ngược

Độ phức tạp thời gian: O(N2T) Độ phức tạp không gian: O(NT)

Thuật toán lan truyền xuôi-ngược

07/08/2013

Bài toán 2 - Thuật toán Viterbi

Thuật toán Viterbi – Giải quyết bài toán 2

• Ý tưởng chung: Nếu xác suất tốt nhất ở trạng thái cuối cùng qk=Sj có đi qua trạng thái qk-1=Si thì xác suất tại trạng thái qk-1=Si cũng phải tốt nhất

a1j

qk-1 qk s1

si

sj

aij

aNj

sN

• 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 chọn được xác suất tốt nhất ở vị trí cuối cùng qk=Sj thì quay lui lại để tìm được chuỗi Q cho ra xác suất sinh dãy quan sát O lớn nhất

07/08/2013

Thuật toán Viterbi

07/08/2013

Thuật toán Viterbi

07/08/2013

Thuật toán Viterbi

Ví dụ thuật toán Viterbi

Bước 1 : Tại thời điểm t = 1 Tính tất cả xác suất các q sinh ra o1. Ở đây ta tính:

b11

b23

P(q1|o1) hay là P (Rain|Walk) P(q2|o1) hay là P (Sun|Walk)

b21

b22

b13

b12

Sau đó chọn xác suất cao nhất. Ở đây giả sử P(Sun|Walk) là max.

Bước 2 : Cũng tính tất cả xác suất q sinh ra o2 nhưng chỉ dựa vào xác suất max của trạng thái ở bước 1.

Rain

a11

Tiếp theo, làm tương tự cho tới bước thứ T.

Sun

a12 MAX MAX

MAX a21 a22

B = [Bik]I,k

walk

clean

shop

Cuối cùng, tại trạng thái ở thời điểm T ta quay lui lại thì tìm được chuỗi Q có xác suât sinh ra O lớn nhất. Ở ví dụ này, chuỗi Q = Sun, Rain,… Sun có xác suất sinh ra chuỗi quan sát chuỗi O = Walk, Clean,… Shop là lớn nhất

07/08/2013

Thuật toán Baum-Welch- giải quyết bài toán 3

Thuật toán Baum-Welch

07/08/2013

Thuật toán Baum-Welch

07/08/2013

Thuật toán Baum-Welch

Ví dụ thuật toán Baum-Welch

b11

b23

b21

b22

b13

b12

Hôm nay Rain Sun Walk Shop Clean Rain 0.1 0.4 0.5 Rain 0.7 0.3 Hôm qua Sun 0.6 0.3 0.1 Sun 0.4 0.6

Start : P(Rain) = 0.6 ; P(Sun) = 0.4

07/08/2013

Ví dụ thuật toán Baum-Welch

Hôm nay Walk Shop Clean Rain Sun Rain 0.1 0.4 0.5 Rain 0.7 0.3 Hôm qua Sun 0.6 0.3 0.1 Sun 0.4 0.6

Start : P(Rain) = 0.6 ; P(Sun) = 0.4

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 trạng thá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

Ví dụ thuật toán Baum-Welch

Vậy Ma trận A Sẽ được chỉnh sửa các thông số lại sau khi quan sá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

Tổng số xác suất Max(qi|ok) của số lần xuất hiện trạng thái quan sát ok Tổng số xác suất Max(q|ok) của số lần xuất hiện trạng thái ok

Ma trận B được tính theo nguyên tắc chung như sau : b(ok)=

Ta tính thử thông số b của trạng thá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 trạng thái clean sinh ra bởi Rain : (0.048+0.084)/(0.048+0.084) = 1 Tính b23 của trạng thái clean sinh ra bởi Sun : (0.0144+0.0072)/(0.048+0.084) = ? Tương tự tính các thông số b của trạng thái walk, shop là ta sẽ thu được ma trận B hoàn chỉnh.

07/08/2013

Ví dụ thuật toán Baum-Welch

Một số thuật toán khác

• Thuật toán học Baldi-Chauvin (dùng Grandient Descent). • Thuật toán học Mamitsuka (kết hợp giữa Baum-Welch và Baldi-Chauvin cho phép học trên cả negative examples).

07/08/2013

HMM-based speech synthesis system

Training part

Speech signal

SPEECH DATABASE

Excitation Parameter extraction Spectral Parameter Extraction

Excitation parameters Spectral parameters Training HMMs Labels

TEXT

Text analysis Context-dependent HMMs & state duration models Parameter generation from HMMs

Synthesis part

Labels Excitation parameters Spectral parameters Excitation SYNTHESIZED SPEECH Excitation generation Synthesis filter

Câu hỏi và bài tập

07/08/2013

Bài tập mẫu

Cho HMM như hình vẽ, trong đó Rainy và Sunny là các trạng thái thuộc tập Q; Walk, Shop và Clean là các quan sát. Hãy xác định chuỗi chuyển trạng thái Q ẩn để có xác suất lớn nhất sinh ra chuỗi quan sát Shop  Clean  Walk Walk