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