隐马尔科夫模型HMM自学 （3）
Viterbi Algorithm
本來想明天再把后面的部分寫好，可是睡覺今天是節(jié)日呢？一時(shí)情不自禁就有打開電腦..........
找到可能性最大的隱含狀態(tài)序列
崔曉源 翻譯
多數(shù)情況下，我們都希望能夠根據(jù)一個(gè)給定的HMM模型，根據(jù)觀察狀態(tài)序列找到產(chǎn)生這一序列的潛在的隱含狀態(tài)序列。
1、窮舉搜索方法
?
我們可以通過窮舉的方式列出所有可能隱含狀態(tài)序列，并算出每一種隱狀態(tài)序列組合對(duì)應(yīng)的觀察狀態(tài)序列的概率。概率最大的那個(gè)組合對(duì)應(yīng)的就是最可能的隱狀態(tài)序列組合。
Pr(observed sequence | hidden state combination).
比如說上圖中的trellis中，最有可能的隱狀態(tài)序列是使得概率：
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ì)算量太大了。為了解決這個(gè)問題，我們可以利用和Forward algorithm一樣的原理--概率的時(shí)間不變性來減少計(jì)算量。
2.用遞歸方式減少復(fù)雜度
在給定的觀察序列和HMM模型下，我們用一種遞歸的方式找到最有可能的隱狀態(tài)序列。同樣我們滴定部分概率，即在trellis中到達(dá)某一中間狀態(tài)的概率。然后介紹如何在初始時(shí)刻t=1和t>1的時(shí)刻分別求解這個(gè)部分概率。但要注意，這里的部分概率是到達(dá)某一中間狀態(tài)的概率最大的路徑而不是所有概率之和。
2.1部分概率和部分最優(yōu)路徑
看如下trellis
?
對(duì)于trellis中的每個(gè)中間狀態(tài)和結(jié)束狀態(tài)，都存在一條到達(dá)它的最優(yōu)路徑。他可能是下圖這樣：
?
我們這些路徑為部分最優(yōu)路徑，每一條?部分最優(yōu)路徑都對(duì)應(yīng)一個(gè)關(guān)聯(lián)概率--部分概率。與Forward algorithm不同是最有可能到達(dá)該狀態(tài)的一條路徑的概率。
??(i,t)是所有序列中在t時(shí)刻以狀態(tài)i終止的最大概率。當(dāng)然它所對(duì)應(yīng)那條路徑就是部分最優(yōu)路徑。???(i,t)對(duì)于每個(gè)i,t都是存在的。這樣我們就可以在時(shí)間T（序列的最后一個(gè)狀態(tài)）找到整個(gè)序列的最優(yōu)路徑。
2b.?計(jì)算??‘s?在t = 1的初始值
由于在t=1不存在任何部分最優(yōu)路徑，因此可以用初始狀態(tài)?向量協(xié)助計(jì)算。
這一點(diǎn)與Forward Algorithm相同
2c.?計(jì)算??‘s?在t?> 1 的部分概率
同樣我們只用t-1時(shí)刻的信息來得到t時(shí)刻的部分概率。
由此圖可以看出到達(dá)X的最優(yōu)路徑是下面中的一條：
(sequence of states), . . ., A, X ?????????????????????????????? (sequence of states), . . ., B, X or (sequence of states), . . ., C, X
我們希望找到一條概率最大的。回想馬爾科夫一階模型的假設(shè)，一個(gè)狀態(tài)之和它前一時(shí)刻的狀態(tài)有關(guān)。
Pr (most probable path to A) . Pr (X | A) . Pr (observation | X)
因此到達(dá)X的最大概率就是：
?
其中第一部分由t-1時(shí)刻的部分概率得到，第二部分是狀態(tài)轉(zhuǎn)移概率，第三部分是混淆矩陣中對(duì)應(yīng)的概率。
（Viterbi Algorithm 待續(xù)）
書接前文，viterbi算法已經(jīng)基本成形......
崔曉源 翻譯
一般化上一篇最后得到的公式我們可以把概率的求解寫成：
2d.?反向指針,?‘s
考慮下面trellis
現(xiàn)在我們可以得到到達(dá)每一個(gè)中間或者終點(diǎn)狀態(tài)的概率最大的路徑。但是我們需要采取一些方法來記錄這條路徑。這就需要在每個(gè)狀態(tài)記錄得到該狀態(tài)最優(yōu)路徑的前一狀態(tài)。記為：
這樣argmax操作符就會(huì)選擇使得括號(hào)中式子最大的索引j。
如果有人問，為什么沒有乘以混淆矩陣中的觀察概率因子。這是因?yàn)槲覀冴P(guān)心的是在到達(dá)當(dāng)前狀態(tài)的最優(yōu)路徑中，前一狀態(tài)的信息，而與他對(duì)應(yīng)的觀察狀態(tài)無關(guān)。
2e. viterbi算法的兩個(gè)優(yōu)點(diǎn)
1）與Forward算法一樣，它極大的降低了計(jì)算復(fù)雜度
2）viterbi會(huì)根據(jù)輸入的觀察序列，“自左向右”的根據(jù)上下文給出最優(yōu)的理解。由于viterbi會(huì)在給出最終選擇前考慮所有的觀察序列因素，這樣就避免了由于突然的噪聲使得決策原理正確答案。這種情況在真實(shí)的數(shù)據(jù)中經(jīng)常出現(xiàn)。
==================================================
下面給出viterbi算法完整的定義1. Formal definition of algorithm
The algorithm may be summarised formally as:
For each i,, i = 1, ... , n, let :
- this intialises the probability calculations by taking the product of the intitial hidden state probabilities with the associated observation probabilities.
For t = 2, ..., T, and i = 1, ... , n let :
- thus determining the most probable route to the next state, and remembering how to get there. This is done by considering all products of transition probabilities with the maximal probabilities already derived for the preceding step. The largest such is remembered, together with what provoked it.
Let :
- thus determining which state at system completion (t=T) is the most probable.
For t = T - 1, ..., 1
Let :
- thus backtracking through the trellis, following the most probable route. On completion, the sequence i1 ... iT will hold the most probable sequence of hidden states for the observation sequence in hand.
==================================================?? 我們還用天氣的例子來說明如何計(jì)算狀態(tài)CLOUDY的部分概率，注意它與Forward算法的區(qū)別 還是那句話： 怎么樣？看到這里豁然開朗了吧。要是還不明白，我就.....................還有辦法，看個(gè)動(dòng)畫效果： http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/s3_pg3.html 參數(shù)定義： http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/s3_pg4.html http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/s3_pg5.html
隱馬爾科夫模型HMM自學(xué) （6）尾聲
崔曉源 翻譯
HMM 的第三個(gè)應(yīng)用就是learning，這個(gè)算法就不再這里詳述了，并不是因?yàn)樗y于理解，而是它比前兩個(gè)算法要復(fù)雜很多。這個(gè)方向在語音處理數(shù)據(jù)庫上有重要的地位。因?yàn)樗梢詭椭覀冊(cè)跔顟B(tài)空間很大，觀察序列很長的環(huán)境下找到合適HMM模型參數(shù)：初始狀態(tài)、轉(zhuǎn)移概率、混淆矩陣等。
好了，我們終于可以對(duì)HMM做一個(gè)階段性的總結(jié)了。通過這個(gè)系列的自學(xué)過程，我相信各位已經(jīng)和我一樣對(duì)HMM的概念和應(yīng)用有了一個(gè)初步的了解。這里我們考慮的都是一階馬爾科夫過程。HMM在語音識(shí)別和NLP方面都有很深入的應(yīng)用。
簡單說說我學(xué)習(xí)HMM的初衷，在科研過程中遇到了reranking的問題，候選一直都是別人為我生成的，處于好奇，終于決定自己也研究一下，大家都知道， reranking是需要產(chǎn)生N-best的候選，既然是N-best，那么viterbi算法就只能生成一條最好的路徑，其他的該怎么辦呢？原來在實(shí)際應(yīng)用過程中，通常是把viterbi decoding與另一種稱為stack decoding的算法聯(lián)合使用（當(dāng)然A*算法也可以）產(chǎn)生多個(gè)候選。前面我們已經(jīng)對(duì)A*算法作了介紹，在今后的日子里，如果我有時(shí)間也會(huì)把stack decoding向大家介紹。(希望不要等太長時(shí)間)
別忘了，viterbi算法的目的是根據(jù)給定的觀察狀態(tài)序列找出最有可能的隱含狀態(tài)序列，別忘了viterbi算法不會(huì)被中間的噪音所干擾。
總結(jié)
以上是生活随笔為你收集整理的隐马尔科夫模型HMM自学 （3）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 隐马尔科夫模型HMM自学 （2）
- 下一篇： Boosting for PRML