TÌM HIỂU MÔ HÌNH MARKOV ẨN - ỨNG DỤNG
ĐỂ NHẬN DẠNG CHỮ VIẾT TAY
Lê Đình Phúc
Phạm Xuân Thu
Trần Đình Hoàng Huy
Nguyễn Đức Hoàng Tùng
GI I THI U - HMMsỚ Ệ
MÔ HÌNH MARKOV
CÁC NG D NGỨ Ụ
NỘI DUNG
GIỚI THIỆU
GIỚI THIỆU

Hidden Markov Models (HMMs) là những mô hình thống kê có sức mạnh đối
với việc mô hình các dữ liệu tuần tự hay liên tục theo thời gian.

HMMs đã được giới thiệu từ cuối những năm 1960 và đầu những năm 1970
của thế kỉ trước.

Năm 1970, Baum và một vài người đã công bố phương pháp cực đại hoá mà
đã cung cấp giải pháp cho vấn đề huấn luyện mô hình với quan sát đơn.
3
GIỚI THIỆU
GIỚI THIỆU

Năm 1977, Dempster đã công bố phương pháp Expectation Maximization để
cho việc ước tính độ giống nhau cực đại từ dữ liệu.

Năm 1983, Levinsons đã giới thiệu phương pháp độ giống nhau cực
đại(maximun likelihood) cho huấn luyện HMMs nhiều chuỗi quan sát đều
độc lập với nhau

phụ thuộc vào q
n-1
(trạng thái thời tiết ngày thứ n-1), q
n-2,
vv…

Tìm xác suất có điều kiện
P(q
n
|q
n-1
, q
n-2
, …, q
1
) 
6
MÔ HÌNH MARKOV
MÔ HÌNH MARKOV

Dựa vào công thức  chúng ta có thể dự đoán xác suất của các trạng thái
thời tiết của ngày mai, ngày mốt, … dựa vào các trạng thái quan sát được
trong quá khứ.

Ví dụ:

Chúng ta biết thời tiết của ba ngày liên tiếp trước đó là
{N, N, S}

Xác suất để ngày mai trời mưa (M) được tính bởi công

P(q
n
|q
n-1
, q
n-2
, …, q
1
) = P(q
n
|q
n-1
) 
Gọi là giả thiết Markov bậc nhất (mô hình Markov).

Với dãy các trạng thái {q
1
, q
2
, …, q
n
} thì
P(q
n
|q
n-1
, q
n-2
, …, q
1

n-1
) 
Gọi là giả thiết Markov bậc nhất (mô hình Markov).
Chuỗi {q
i
} đầu ra được gọi là xích Markov.

Ta có thể biểu diễn xác suất của chuỗi {q
1
, q
2
, …, q
n
} bằng cách sử dụng
giả thiết Markov như sau:


Với giả thiết Markov, chúng ta chỉ cần biết xác suất để chuyển từ trạng thái
q
n-1
sang q
n,
tức là P(q
n
|q
n-1
).
∏
=
=…

0.20
0.80
0.50
0.05
0.20
0.20
0.60
0.30
MÔ HÌNH MARKOV
MÔ HÌNH MARKOV

Ví dụ 1:

Cho biết hôm nay trời nắng (N). Tính xác suất để ngày
mai trời nắng (N) và ngày mốt trời mưa (M).

Sử dụng giả thiết Markov và xác suất cho trong bảng trên,
ta có:
P(q
2
=N, q
3
=M|q
1
=N) = P(q
3
=M|q
2
=N,q
1

=S). Tính xác suất ngày mai trời
sẽ nắng (q
3
=N).

Sử dụng giả thiết Markov và xác suất cho trong bảng
trên, ta có:
P(q
3
=N| q
2
=S, q
1
=M)
= P(q
3
=N|q
2
=S) (Giả thiết Markov)
= 0.20
13
MÔ HÌNH MARKOV
MÔ HÌNH MARKOV

Ví dụ 3:

Cho biết hôm nay trời sương mù (q
1
=S). Tính xác suất
ngày mốt trời sẽ mưa (q

= P(q
3
=M|q
2
=N) * P(q
2
=N|q
1
=S) +
= P(q
3
=M|q
2
=M) * P(q
2
=M|q
1
=S) +
= P(q
3
=M|q
2
=S) * P(q
2
=S|q
1
=S)
= 0.05*0.20 +0.60*0.30+0.30*0.50 = 0.34
14
MÔ HÌNH MARKOV ẨN - HMMs

M
0.80
S
0.30
MÔ HÌNH MARKOV Ẩn - HMMs
MÔ HÌNH MARKOV Ẩn - HMMs
16

Như vậy, thời tiết bên ngoài sẽ là ẩn đối với chúng ta.

Bây giờ chúng ta phải tìm xác suất của các trạng thái thời tiết q
i
∈ {
N
,
M
,
S
}
thông qua các quan sát được o
i
, với o
i
=D, nếu người chăm sóc mang theo
dù, o
i
=K nếu người chăm sóc không mang theo dù. Nghĩa là chúng ta phải
tìm P(q
i
|o

21
212121
2121
n
nnn
nn
oooP
qqqPqqqoooP
oooqqqP =
MÔ HÌNH MARKOV Ẩn - HMMs
MÔ HÌNH MARKOV Ẩn - HMMs
17

Trong đó:

P(q
1
, q
2
, …, q
n
) là xác suất xảy ra chuỗi trạng thái thời
tiết
Q = {q
1
, q
2
, …, q
n
}, q

2121
∏
=
=
n
i
iinn
qoPqqqoooP
MÔ HÌNH MARKOV Ẩn - HMMs
MÔ HÌNH MARKOV Ẩn - HMMs
18

S là một tập trạng thái (ẩn) gồm N phần tử: S = {s
1
, s
2
, …, s
N
}

V là một tập tín hiệu (quan sát được) gồm M phần tử: V = {v
1
, v
2
, …, v
M
}

Q là một chuỗi tuần tự các trạng thái có chiều dài T, tương ứng với O là một chuỗi
tuần tự các tín hiệu:

=s
i
)

B là ma trận xác suất tín hiệu. Xác suất quan sát được tín
hiệu k từ trạng thái i, độc lập với t:
B = [b
i
(k)], b
i
(k) = P(o
t
=v
k
|q
t
=s
i
)

π là chuỗi xác suất khởi đầu: π = [π
i
], π
i
= P(q
1
=s
i
)
MÔ HÌNH MARKOV Ẩn - HMMs

, …, o
t
, q
t
, q
t-1
, …, q
1
) = P(o
t
|q
t
)
MÔ HÌNH MARKOV Ẩn - HMMs
MÔ HÌNH MARKOV Ẩn - HMMs
20

Dùng lược đồ mắt cáo để tính toán cho HMMs.
Trạng thái
1
Trạng thái
2
Trạng thái
3
b
1,k
b
2,k
b
3,k

Dãy tín hiệu quan
sát
a
1,1
a
1,2
a
1,3
thời gian
…….
…….
…….
…….
…….
…….
MÔ HÌNH MARKOV Ẩn - HMMs
MÔ HÌNH MARKOV Ẩn - HMMs
21

Ví dụ lược đồ mắt cáo cho mô hình dự báo thời tiết
N
M
S
b
N,K
=0.9
o
1
=K
t=1

suất xảy ra chuỗi tín hiệu O = {o
1
, o
2
, …, o
T
}.
2. Cho mô hình Markov ẩn λ = (A, B, π), tìm chuỗi trạng
thái
Q = {q
1
, q
2
, …, q
T
} sao cho xác suất tương ứng với
chuỗi
tín hiệu quan sát được O = {o
1
, o
2
, …, o
T
} lớn nhất, tức
là P(O,Q|λ) cực đại.
3. Xây dựng mô hình Markov ẩn λ = (A, B, π) sao cho P(O|
λ) hoặc P(O,Q|λ) đạt cực đại
Ba bài toán với mô hình Markov ẩn
Ba bài toán với mô hình Markov ẩn
23

)|(
−
=
πλ
∑∑
−
==
T
TTT
qq
Tqqqqqqqq
Q
oqqobaobQPQOPOP

21
1
122111
)() ()()|(),|()|(
πλλλ
Ba bài toán với mô hình Markov ẩn
Ba bài toán với mô hình Markov ẩn
24

Lời giải bài toán 2:

Thuật toán Viterbi

Lời giải bài toán 3:

Thuật toán phân đoạn K-Trung bình