找到觀察序列的概率
崔曉源 翻譯
Finding the probability of an observed sequence
1、窮舉搜索方法
對于水藻和天氣的關(guān)系，我們可以用窮舉搜索方法的到下面的狀態(tài)轉(zhuǎn)移圖（trellis）：
圖中，每一列于相鄰列的連線由狀態(tài)轉(zhuǎn)移概率決定，而觀察狀態(tài)和每一列的隱狀態(tài)則由混淆矩陣決定。如果用窮舉的方法的到某一觀察狀態(tài)序列的概率，就要求所有可能的天氣狀態(tài)序列下的概率之和，這個(gè)trellis中共有3*3=27個(gè)可能的序列。
Pr(dry,damp,soggy | HMM) = Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy | sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + . . . . Pr(dry,damp,soggy | rainy,rainy ,rainy)
可見計(jì)算復(fù)雜度是很大，特別是當(dāng)狀態(tài)空間很大，觀察序列很長時(shí)。我們可以利用概率的時(shí)間不變性解決復(fù)雜度。
2、采用遞歸方法降低復(fù)雜度
我們采用遞歸的方式計(jì)算觀察序列的概率，首先定義部分概率為到達(dá)trellis中某一中間狀態(tài)的概率。在后面的文章里，我們把長度為T的觀察狀態(tài)序列表示為：
2a. Partial probabilities, (
‘s)
在計(jì)算trellis中某一中間狀態(tài)的概率時(shí)，用所有可能到達(dá)該狀態(tài)的路徑之和表示。
比如在t=2時(shí)間，狀態(tài)為cloudy的概率可以用下面的路徑計(jì)算：
用
t ( j ) 表示在時(shí)間t時(shí) 狀態(tài)j的部分概率。計(jì)算方法如下：
t ( j )= Pr( observation | hidden state is j ) * Pr(all paths to state j at time t)
最后的觀察狀態(tài)的部分概率表示，這些狀態(tài)所經(jīng)過的所有可能路徑的概率。比如：
這表示最后的部分概率的和即為trellis中所有可能路徑的和，也就是當(dāng)前HMM下觀察序列的概率。
Section 3 會給出一個(gè)動(dòng)態(tài)效果介紹如何計(jì)算概率。
2b.計(jì)算初始狀態(tài)的部分概率
我們計(jì)算部分概率的公式為:
t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)
但是在初始狀態(tài)，沒有路徑到達(dá)這些狀態(tài)。那么我們就用probability乘以associated observation probability計(jì)算：
這樣初始時(shí)刻的狀態(tài)的部分概率就只與其自身的概率和該時(shí)刻觀察狀態(tài)的概率有關(guān)。
