隐马尔科夫模型HMM自学 （2）
HMM 定義
崔曉源 翻譯
HMM是一個三元組 (,A,B).
?the vector of the initial state probabilities;
??the state transition matrix;?
??the confusion matrix;?
這其中，所有的狀態轉移概率和混淆概率在整個系統中都是一成不變的。這也是HMM中最不切實際的假設。
HMM的應用
有三個主要的應用：前兩個是模式識別后一個作為參數估計
(1) 評估
根據已知的HMM找出一個觀察序列的概率。
這類問題是假設我們有一系列的HMM模型，來描述不同的系統（比如夏天的天氣變化規律和冬天的天氣變化規律），我們想知道哪個系統生成觀察狀態序列的概率最大。反過來說，把不同季節的天氣系統應用到一個給定的觀察狀態序列上，得到概率最大的哪個系統所對應的季節就是最有可能出現的季節。（也就是根據觀察狀態序列，如何判斷季節）。在語音識別中也有同樣的應用。
我們會用forward algorithm?算法來得到觀察狀態序列對應于一個HMM的概率。
(2) 解碼
根據觀察序列找到最有可能出現的隱狀態序列
回想水藻和天氣的例子，一個盲人隱士只能通過感受水藻的狀態來判斷天氣狀況，這就顯得尤為重要。我們使用viterbi algorithm來解決這類問題。
viterbi算法也被廣泛的應用在自然語言處理領域。比如詞性標注。字面上的文字信息就是觀察狀態，而詞性就是隱狀態。通過HMM我們就可以找到一句話上下文中最有可能出現的句法結構。
(3) 學習
從觀察序列中得出HMM
這是最難的HMM應用。也就是根據觀察序列和其代表的隱狀態，生成一個三元組HMM (,A,B)。使這個三元組能夠最好的描述我們所見的一個現象規律。
我們用forward-backward algorithm來解決在現實中經常出現的問題--轉移矩陣和混淆矩陣不能直接得到的情況。
總結 HMM可以解決的三類問題
?
?
4-1）Forward Algorithm
找到觀察序列的概率
崔曉源 翻譯
Finding the probability of an observed sequence
1、窮舉搜索方法
對于水藻和天氣的關系，我們可以用窮舉搜索方法的到下面的狀態轉移圖（trellis）：?
圖中，每一列于相鄰列的連線由狀態轉移概率決定，而觀察狀態和每一列的隱狀態則由混淆矩陣決定。如果用窮舉的方法的到某一觀察狀態序列的概率，就要求所有可能的天氣狀態序列下的概率之和，這個trellis中共有3*3=27個可能的序列。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)
可見計算復雜度是很大，特別是當狀態空間很大，觀察序列很長時。我們可以利用概率的時間不變性解決復雜度。 2、采用遞歸方法降低復雜度 我們采用遞歸的方式計算觀察序列的概率，首先定義部分概率為到達trellis中某一中間狀態的概率。在后面的文章里，我們把長度為T的觀察狀態序列表示為： 2a. Partial probabilities, (‘s) 在計算trellis中某一中間狀態的概率時，用所有可能到達該狀態的路徑之和表示。 比如在t=2時間，狀態為cloudy的概率可以用下面的路徑計算： 用t ( j ) 表示在時間t時 狀態j的部分概率。計算方法如下： t ( j )= Pr( observation | hidden state is j )?* Pr(all paths to state j at time t) 最后的觀察狀態的部分概率表示，這些狀態所經過的所有可能路徑的概率。比如： 這表示最后的部分概率的和即為trellis中所有可能路徑的和，也就是當前HMM下觀察序列的概率。 Section 3? 會給出一個動態效果介紹如何計算概率。 2b.計算初始狀態的部分概率 我們計算部分概率的公式為: ?t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t) 但是在初始狀態，沒有路徑到達這些狀態。那么我們就用probability乘以associated observation probability計算： 這樣初始時刻的狀態的部分概率就只與其自身的概率和該時刻觀察狀態的概率有關。隱馬爾科夫模型HMM自學 （4-2）Forward Algorithm
崔曉源 翻譯
書接上文，前一話我們講到了Forward Algorithm中初始狀態的部分概率的計算方法。這次我們繼續介紹。
2c.如何計算t>1時刻的部分概率
回憶一下我們如何計算部分概率：
t ( j )= Pr( observation | hidden state is j )?* Pr(all paths to state j at time t)
我們可知（通過遞歸）乘積中第一項是可用的。那么如何得到Pr(all paths to state j at time t) 呢？
為了計算到達一個狀態的所有路徑的概率，就等于每一個到達這個狀態的路徑之和：
隨著序列數的增長，所要計算的路徑數呈指數增長。但是在t時刻我們已經計算出所有到達某一狀態的部分概率，因此在計算t+1時刻的某一狀態的部分概率時只和t時刻有關。 這個式子的含義就是恰當的觀察概率（狀態j下，時刻t+1所真正看到的觀察狀態的概率）乘以此時所有到達該狀態的概率和（前一時刻所有狀態的概率與相應的轉移概率的積）。因此，我們說在計算t+1時刻的概率時，只用到了t時刻的概率。這樣我們就可以計算出整個觀察序列的概率。 2d.復雜度比較 對于觀察序列長度T，窮舉法的復雜度為T的指數級；而Forward Algorithm的復雜度為T的線性。 ======================================================= 最后我們給出Forward Algorithm的完整定義 We use the forward algorithm to calculate the probability of a T long observation sequence;where each of the y is one of the observable set. Intermediate probabilities (‘s) are calculated recursively by first calculating??for all states at t=1.
Then for each time step, t = 2, ..., T, the partial probability??is calculated for each state; ??
that is, the product of the appropriate observation probability and the sum over all possible routes to that state, exploiting recursion by knowing these values already for the previous time step. Finally the sum of all partial probabilities gives the probability of the observation, given the HMM,?. ???=======================================================
我們還用天氣的例子來說明如何計算t=2時刻，狀態CLOUDY的部分概率 怎么樣？看到這里豁然開朗了吧。要是還不明白，我就.....................還有辦法，看個動畫效果： http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg3.html 參數定義： http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg4.html http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg5.html 最后記住我們使用這個算法的目的（沒有應用任何算法都是垃圾），從若干個HMM模型中選出一個最能夠體現給定的觀察狀態序列的模型（概率最大的那個）。 Forward Algorithm （Done）總結
以上是生活随笔為你收集整理的隐马尔科夫模型HMM自学 （2）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 隐马尔科夫模型HMM自学（1）
- 下一篇： 隐马尔科夫模型HMM自学 （3）