HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
BÀI TẬP LỚN MÔN
XỬ LÝ TÍN HIỆU NÂNG CAO
Đề tài: Tìm hiểu mô hình Markov ẩn

Người hướng dẫn: TS. NGUYỄN NGỌC MINH
Nhóm học viên : Nguyễn Hữu Hưng
Đinh Trọng Toàn
Nguyễn Nam Long
Lê Công Hòa
Lớp : M12CQDT02-B
HÀ NỘI, 4/2013
Mô hình Markov ẩn Xử lý tín hiệu số nâng
cao
MỤC LỤC
MỤC LỤC 2
DANH MỤC HÌNH 2
LỜI MỞ ĐẦU 3
I. Tổng quan về mô hình Markov ẩn 4
II. Các thuật toán sử dụng trong mô hình Markov ẩn 6
KẾT LUẬN 18
DANH MỤC HÌNH
Hình II-1 Sơ đồ khối hệ thống nhận dạng 7
Hình II-2 Minh họa ví dụ 1- a 7
Hình II-3 Minh họa ví dụ 1 - b 8
Hình II-4 Mô hình 2 –state và 3-state 9
Hình II-5 Mô hình Left – Righ 9
Hình II-6 Mô hình Bakis 10
Hình II-7 Mô hình tuyến tính 10
Hình II-8 Sự tiến hóa của mô hình Markov 10
Hình II-9 Biểu diễn trạng thái bằng sơ đồ mắt lưới 11

đượ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. Các tham số của mô hình
được rút ra sau đó có thể được sử dụng để thực hiện các phân tích kế tiếp, ví dụ ứng
dụng cho nhận dạng mẫu.
Trong một mô hình Markov điển hình, trạng thái được quan sát được từ người
quan sát, vì vậy các xác suất chuyển tiếp trạng thái là các tham số duy nhất. Mô hình
Markov ẩn thêm vào các đầu ra: mỗi trạng thái có xác suất phân bổ trên các biểu
hiện có thể. Vì vậy, nhìn vào dãy các biểu hiện được sinh ra bởi HMM không trực
tiếp chỉ ra dãy các trạng thái.
Nhắc lại Quá trình Markov:
Trong lí thuyết xác suất, quá trình Markov là một quá trình mang tính ngẫu
nhiên (stochastic process) với đặc tính như sau: trạng thái c
k
tại thời điểm k là một
giá trị trong tập hữu hạn {1,…,M}. Với giả thiết rằng quá trình chỉ diễn ra từ thời
điểm 0 đến thời điểm N và rằng trạng thái đầu tiên và trạng thái cuối cùng đã biết,
chuỗi trạng thái sẽ được biểu diễn bởi 1 vecto hữu hạn C={c
0
,…,c
N
}. Nếu P(c
k
|
c
0
,c
1
, ,c
(k − 1)
) biểu diễn xác suất (khả năng xảy ra) của trạng thái c

k
| c
0
,c
1
, ,c
(k − 1)
)= P(c
k
| c
k-n
,c
k-n-1
,…,c
(k − 1)
)
4
Mô hình Markov ẩn Xử lý tín hiệu số nâng
cao
Nói chung với giả thuật Viterbi quá trình xảy ra bên dưới được xem là một quá
trình Markov:
 Trạng thái hữu hạn nghĩa là số m là hữu hạn.
 Thời gian rời rạc, nghĩa là việc chuyển từ trạng thái này sang trạng thái
khác cùng mất một đơn vị thời gian.
 Quan sát không tốn bộ nhớ, nghĩa là chuỗi các quan sát có xác suất chỉ
phụ thuộc vào trạng thái ngay trước đó (nên không cần lưu bộ nhớ nhiều).
Mô hình Markov ẩn được ứng dụng trong nhiều lĩnh vực như:
• Nhận dạng tiếng nói.
• Nhận dạng chữ viết tay.
• Xử lý ngôn ngữ thống kê.

Nắng 0.1 0.9
Mưa 0.8 0.2
Mây mù 0.3 0.7
Ma trận trên gọi là ma trận quan sát, thường được ký hiệu là B, biểu diễn xác
suất quan sát trực tiếp được trong một quá trình Markov ẩn.
1.3 Các thông số của mô hình Markov ẩn
Một mô hình Markov ẩn bao gồm các thông số như:
• Số trạng thái ‘state’ N có trong mô hình và các trạng thái này là ẩn. Các
trạng thái này sẽ được biểu thị tương ứng với giá trị S=(S1, …., SN) gọi
là tập tất cả các trạng thái ẩn.
• M, Số symbol trên mỗi dãy quan sát trong một ‘State’. Các symbol này
sẽ được biểu thị tương ứng bởi các giá trị V=(V¬1, …, VM) gọi là tập
tất cả các ký hiệu quan sát được.
• A= [aij] xác suất chuyển trạng. Trong trường hợp đặc biệt, khi các trạng
thái là như nhau trong một bước đơn, ta có aij > 0 đối với tất cả các giá
trị i và j. Trong một vài loại hình khác của HMM, ta chi aij = 0 cho một
vài căp (i,j).
• B=[bij] xác suất nhả ký hiệu.
• p= [pi] xác suất khởi trạng
• qt - Trạng thái ở thời điểm t.
• Ot= (ký hiệu) Quan sát tại thời điểm t.
II. Các thuật toán sử dụng trong mô hình Markov ẩn
2.1 Mô hình Markov ẩn trong lý thuyết thông tin nhận dạng
Sơ đồ khối của hệ thống nhận dạng như hình 2-1.
6
Mô hình Markov ẩn Xử lý tín hiệu số nâng
cao
Hình II-1 Sơ đồ khối hệ thống nhận dạng
Nhận dạng là tìm cách xác định được khả năng xảy ra lớn nhất của chuỗi ngôn
ngữ,W, khi cho trước căn cứ âm A, Công thức:

, khi đó a
i1
+ a
i2
=1.
• Xét 2 bình, mỗi bình chứa các quả bóng đen, bóng trắng.
• Chia bình thứ i thành 2 phần tỉ lệ b
iB
, b
iW
, với
• b
iB
+ b
iW
=1
• Vecto tham số cho mô hình này là:
λ
= {a
01
,a
02
,a
11
,a
12
,a
21
,a
22

1
,v
2
,…,v
M
}
Kí hiệu quan sát ở thời điểm t, o
t
∈
v
• A= {a
ij
}: tập phân phối xác suất chuyển trạng thái
a
ij
= P(q
t+1
= s
j
|q
t
= s
i
), 1 ≤ i,j ≤ N
• B = {b
j
(k)}: phân bổ xác suất kí hiệu quan sát ở trạng thái j:
b
j
(k)= P(v





2221
1211
aa
aa
và B=






)()(
)()(
22
11
WbBb
WbBb
 Một số mô hình thông dụng:
Hình II-5 Mô hình Left – Righ
Hình 2-5: Mô hình Left – Righ
9
Hình II-4 Mô hình 2 –state và 3-state
Mô hình Markov ẩn Xử lý tín hiệu số nâng
cao
Hình II-6 Mô hình Bakis
Hình II-7 Mô hình tuyến tính

Mô hình Markov ẩn Xử lý tín hiệu số nâng
cao
Hình II-9 Biểu diễn trạng thái bằng sơ đồ mắt lưới
Vấn đề cơ bản của HMM:
Tính điểm (Scoring) : cho một chuỗi quan sát O = {o
1
,o
2
, ,o
T
} và một mô hình
λ = {A, B,π}, làm thế nào chúng ta có thể tính toán xác suất có điều kiện P(O | λ)
(khả năng xảy ra của chuỗi quan sát)?
 Dùng thuật toán tiến lùi (the forward-backwark algorithm)
So khớp (Matching): cho một chuỗi quan sát O = {o
1
,o
2
, ,o
T
}, làm thế nào
chúng ra có thể lựa chọn chuỗi trạng thái Q = {q
1
,q
2
, ,q
T
} để nó tối ưu theo một số
hướng.
 thuật toán Viterbi

q1
a
q1q2
a
q2q3
a
qT −1 qT
Vì vậy:
11
Mô hình Markov ẩn Xử lý tín hiệu số nâng
cao
P(O|λ)=
∑
Π
qT, , q2q1,
T12221111
) (o b a )(ob )a(ob
qT qTqT -q qqqq
Số phép tính cấn làm ≈ 2T.N
T
(có N
T
chuỗi như vậy)
Ví dụ: N=5, T=100  2.100.5
100
≈ 10
72
phép tính.
2.2 Thuật toán tiến – thuật toán lùi:
 Toán tử tiến α

=
N
1i
(i)
T
α
• Theo phương pháp quy nạp
α
t+1
(j)=[
∑
=
N
i
t
1
ij
a (i)
α
] b
j
(o
t+1
), 1≤ t≤ T-1, 1 ≤ j ≤ N
Số phép tính: N
2
T.
Ví dụ: N=5,T=100,  5
2
.100 phép tính,( thay vì 10

∑
=
Π
N
1i
11ii
(i))ß(ob
12
Mô hình Markov ẩn Xử lý tín hiệu số nâng
cao
o Theo phương pháp quy nạp
β
t
(i)=
∑
=
N
1j
1+t1+tj
(j))ß(oba
ij
(t=T−1,T−2, ,1; 1 ≤ i≤N)
 Diễn tả thủ tục lùi:
Hình II-11Thuật toán lùi
 Tìm chuỗi trạng thái tối ưu:
+ Một tiêu chuẩn để lựa chọn trạng thái tối ưu q
t
là cực đại hóa số
trạng thái đúng.
+ Toán tử

)(
λ
βα
γ
OP
ii
i
tt
t
=
+ Tuy nhiên với tiêu chuẩn tối ưu riêng phần thì xảy ra vấn đề là
chuỗi trạng thái tối ưu có thể không tuân theo những ràng buộc chuyển
tiếp trạng thái.
+ Một tiêu chuẩn tối ưu khác là cực đại hóa P(Q,O|
λ
). Điều này có
thể tìm thấy bằng thuật toán Viterbi.
+ Với
)(i
t
δ
là xác suất xảy ra cao nhất trên một đường dẫn tính với
t lần quan sát đầu tiên:
)| ,,, ,,(max)(
211121
, ,,
121
λδ
ttt
qqq

)()(
1 iii
obi
πδ
=
0)(
1
=
i
ψ
+ Đệ quy:
Ttobaiij
tjjt
Ni
t
≤≤=
−
≤≤
2),(])([max)(
1
1
δδ
Ttaij
ijt
Ni
t
≤≤=
−
≤≤
2],)([maxarg)(

*
−−==
+
+
tTt
qq
t
t
T
ψ
+ Số phép tính
TN
2
≈
+ Ví dụ thuật toán VIterbi:
 Ví dụ thuật toán
Viterbi(tt)
14
Mô hình Markov ẩn Xử lý tín hiệu số nâng
cao
  Ví dụ so khớp sử dụng thuật toán tiến-lùi:
 Ước lượng lại với thuật toán Baum-Welch
Ước lượng lại với thuật toán Baum-Welch sử dụng EM để xác định tham số ML:
Xét toán tử
)(i
t
ξ
là xác suất của hệ thống ở 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 điều kiện có chuỗi quan sát O và mô hình Markov ẩn
λ

N
j
tt
jii
1
),()(
ξγ
 Kết hợp
)(i
t
γ
và
),( ji
t
ξ
chúng ta được:

∑
−
=
1
1
)(
T
t
t
i
γ
= số chuyển tiếp từ trạng thái s
i

−
=
=
1
1
1
1
)(
),(
T
t
t
T
t
t
ij
i
ji
a
γ
ξ
•
∑
∑
=
==
=
T
t
t

xảy ra, trong trường hợp
λ
=
λ
. Hoặc:
o Mô hình
λ
thích hợp hơn
λ
trong điều kiện
)|()|(
λλ
OPOP
>
Chúng ta có thể tăng xác suất chuỗi quan sát O mà đã quan sát được từ mô hình
nếu sử dụng lặp lại
λ
trong không gian
λ
và lặp lại việc ước lượng lại cho đến khi
một số điểm tới hạn đạt được. Mô hình kết quả thu được gọi là mô hình Markov ẩn
có khả năng xảy ra lớn nhất.
17
Mô hình Markov ẩn Xử lý tín hiệu số nâng
cao
KẾT LUẬN
Mô hình Markov ẩn được ứng dụng nhiều trong lĩnh vực nhận dạng giọng nói,
trong nhiều lĩnh vực như sinh học, điện, điện tử, xử lý tín hệu số, vv vv
Đặc biệt trong khuôn khổ phạm vi lĩnh vực xử lý tín hiệu số, mô hình Markov ẩn
được ứng dụng nhiều trong việc xây dựng các hệ thống xử lý hình ảnh, âm thanh, trí