Mô hình Markov ẩn
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (398.72 KB, 13 trang )
MÔ HÌNH MARKOV ẨN
5.1Giới thiệu
Mô hình Markov ẩn 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. 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.
Chú ý: 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
tại thời điểm k khi đã qua mọi trạng thái cho đến (k-1). Giả sử trong thời
điểm đó c
k
chỉ phụ thuộc vào trạng thái trước đó c
k-1
và độc lập với các trạng thái
trước khác. Quá trình đó gọi là quá trình Markov bậc một(first order Markov
process). Có nghĩa là xác suất để xảy ra trạng thái c
k
tại thời điểm k, khi biết
trước mọi trạng thái cho đến thời điểm k-1 chỉ phụ thuộc vào trạng thái trước, ví
dụ trạng thái ck-1 tại thời điểm k-1. Khi đó ta có công thức:
P(c
k
| c
0
,c
1
,...,c
(k − 1)
)= P(c
k
| c
(k − 1)
)
Nói tóm lại một hệ có thuộc tính Markov được gọi là quá trình Markov
(bậc1).
Như vậy, với quá trình Markov bậc n:
P(c
k
| c
0
,c
1
,...,c
(k − 1)
)= P(c
k
| c
k-n
,c
k-n-1
,…,c
(k − 1)
)
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).
5.2Trình bày vấn đề
• Phương pháp tiếp cận lí thuyết thông tin về nhận dạng
Hình 1
o 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:
)/(max)/( AWPAWP
W
=
∧
• Theo luật Bayes:
)(
)()/(
)/(
AP
WPWAP
AWP
=
• Mô hình HMM quan tâm đến P(W|A)
• Kí hiệu:
A O
W
λ
P(A/W) P(O/
λ
)
• Ví dụ1:
Hình 5.2
o Xét 3 chén, mỗi chén trộn giữa các các “đá trạng thái” 1 và 2.
o Phân nhỏ chén thứ i thành 2 phần tỉ lệ a
i1
, a
i2
, khi đó a
i1
+
a
i2
=1.
o Xét 2 bình, mỗi bình chứa các quả bóng đen, bóng trắng.
o Chia bình thứ i thành 2 phần tỉ lệ b
iB
, b
iW
, với
o b
iB
+ b
iW
=1
o Vecto tham số cho mô hình này là:
λ
= {a
01
,a
02
,a
11
,a
12
,a
21
,a
22
,b
1
(B),b
1
(W ),b
2
(B),b
2
(W )}
Hình 5.3
Chuỗi quan sát : O={B,W,B,W,W,B}
Chuỗi trạng thái: Q={1,1,2,1,2,1}
Mục đích: cho mô hình λ và chuỗi quan sát O, có thể làm thể nào để
chuỗi trạng thái Q được xác định.
• Các yếu tố của mô hình Markov ẩn rời rạc
o N : số trạng thái trong mô hình
Các trạng thái, s= {s
1
,s
2
,…,s
N
}
Trạng thái ở thời điểm t, q
t
∈
s
o M: số kí hiệu quan sát (quan sát rời rạc)
Tập các kí hiệu quan sát v={v
1
,v
2
,…,v
M
}
Kí hiệu quan sát ở thời điểm t, o
t
∈
v
o 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
o 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
k
a
t
t|q
t
= s
j
), 1 ≤ j ≤ N, 1 ≤ k ≤ M
o π = {π
i
}: phân bổ xác suất trạng thái khởi đầu
π
i
= P(q
1
= s
i
), 1 ≤ i ≤ N
Một mô hình HMM được viết dưới dạng đặc trưng λ = {A, B,π}
• ví dụ 2:
o π={a
01
,a
02
} A=
2221
1211
aa
aa
và B=
)()(
)()(
22
11
WbBb
WbBb
o Sơ đồ trạng thái
• Một số mô hình thông dụng
Hình 5.4a: Mô hình 2 –state và 3-state
Hình 5.4b:Mô hình Left – Righ
Hình 5.4c:Mô hình Bakis
Hình 5.4d: Mô hình Tuyến tính
• Tạo chuỗi quan sát trong HMM
o Lựa chọn một trạng thái khởi đầu, q
1
=s
i
, dựa trên phân bổ trạng
thái khởi đầu, π.
o Cho t chạy từ 1 T:
Chọn o
t
=v
k
theo sự phân bổ xác suất kí hiệu trong trạng
thái s
i
, b
i
(k).
Chuyển tiếp đến trạng thái mới q
t+1
=s
j
theo sự phân bổ
xác suất sự chuyển tiếp trạng thái cho trạng thái s
i
, a
ij
.
o Tăng t lên 1, quay lại bước 2 nếu t≤T; ngược lại thì kết thúc.
