本來想明天再把后面的部分寫好，可是睡覺今天是節日呢？一時情不自禁就有打開電腦..........
找到可能性最大的隱含狀態序列
崔曉源 翻譯
多數情況下，我們都希望能夠根據一個給定的HMM模型，根據觀察狀態序列找到產生這一序列的潛在的隱含狀態序列。
1、窮舉搜索方法
我們可以通過窮舉的方式列出所有可能隱含狀態序列，并算出每一種隱狀態序列組合對應的觀察狀態序列的概率。概率最大的那個組合對應的就是最可能的隱狀態序列組合。
Pr(observed sequence | hidden state combination).
比如說上圖中的trellis中，最有可能的隱狀態序列是使得概率：
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)
得到最大值的序列。
同樣這種窮舉法的計算量太大了。為了解決這個問題，我們可以利用和Forward algorithm一樣的原理--概率的時間不變性來減少計算量。
2.用遞歸方式減少復雜度
在給定的觀察序列和HMM模型下，我們用一種遞歸的方式找到最有可能的隱狀態序列。同樣我們滴定部分概率，即在trellis中到達某一中間狀態的概率。然后介紹如何在初始時刻t=1和t>1的時刻分別求解這個部分概率。但要注意，這里的部分概率是到達某一中間狀態的概率最大的路徑而不是所有概率之和。
2.1部分概率和部分最優路徑
看如下trellis
對于trellis中的每個中間狀態和結束狀態，都存在一條到達它的最優路徑。他可能是下圖這樣：
我們這些路徑為部分最優路徑，每一條 部分最優路徑都對應一個關聯概率--部分概率
2b. 計算 ‘s 在t = 1的初始值
由于在t=1不存在任何部分最優路徑，因此可以用初始狀態
這一點與Forward Algorithm相同
2c. 計算 ‘s 在t > 1 的部分概率
同樣我們只用t-1時刻的信息來得到t時刻的部分概率。
由此圖可以看出到達X的最優路徑是下面中的一條：
(sequence of states), . . ., A, X (sequence of states), . . ., B, X or (sequence of states), . . ., C, X
我們希望找到一條概率最大的。回想馬爾科夫一階模型的假設，一個狀態之和它前一時刻的狀態有關。
Pr (most probable path to A) . Pr (X | A) . Pr (observation | X)
因此到達X的最大概率就是：
其中第一部分由t-1時刻的部分概率得到，第二部分是狀態轉移概率，第三部分是混淆矩陣中對應的概率。
（Viterbi Algorithm 待續）
