HMM——前向算法与后向算法
1. 前言
前向算法和后向算法主要還是針對HMM三大問題之一的評估問題的計算，即給定模型參數(shù)，計算觀察序列的概率。文章不介紹過多公式，主要看兩個例子
復(fù)習一下HMM的三大要素（以海藻（可觀測）和天氣（隱狀態(tài)）為例）：
①初始概率向量：當前時刻天氣的可能性，屬于先驗概率
②狀態(tài)轉(zhuǎn)移矩陣：從當前天氣轉(zhuǎn)移到下一個天氣的可能性，比如P(雨天|晴天)即為晴天轉(zhuǎn)移到雨天的概率
③混淆矩陣：當前天氣為某種天氣的時候，海藻狀態(tài)為某種狀態(tài)的可能性，比如P(干燥|晴天)即為晴天時候海藻干燥的概率
問題：給定HMM模型參數(shù)以及海藻的三天狀態(tài)：干燥、濕潤、濕透。
目的：求解海藻出現(xiàn)這三種狀態(tài)的概率。
2. 窮舉搜索直接計算
2.1 理論介紹
已知：給定HMM模型參數(shù)λ=(π，A，B)，和觀察序列
求解：觀測序列O出現(xiàn)的概率P(O|I,λ)
方法：列舉所有可能的狀態(tài)，分別求解各個狀態(tài)序列與觀測序列的聯(lián)合概率P(O,I | λ)，最后求和就得到了P(O|λ)
具體過程：
①狀態(tài)序列出現(xiàn)的概率是
②對于其中一種狀態(tài)序列，觀測序列的概率是
依據(jù)貝葉斯公式可以計算
③求和
?
2.2 實例推導(dǎo)
給定隱馬爾可夫模型，也就是在模型參數(shù)(π,A,B)已知的情況下，我們想找到觀察序列的概率。
最直接的方法是列舉出每種可能的轉(zhuǎn)移，如下圖所示(借用英文文獻中的那個例子)：
?
??
圖中展示了三天的海藻狀態(tài)，第一列對應(yīng)第一天海藻為dry時候三種可能的天氣隱狀態(tài)，第二列對應(yīng)第二天海藻為damp時候三種可能的天氣隱狀態(tài)，第三列對應(yīng)第三天海藻為soggy時候三種可能的天氣隱狀態(tài)；每個隱狀態(tài)都有一個概率指向當前可能的海藻狀態(tài)，由混淆矩陣給出；從第一天到第二天和第二天到第三天的天氣隱狀態(tài)之間都有轉(zhuǎn)移概率，由轉(zhuǎn)移概率矩陣給出。
計算觀察序列概率的方法是找到所有的可能路徑，因為每種海藻觀察情況都有三種可能天氣，所以共有33=27條路徑，即27種不同的天氣序列，然后將所有可能的觀察序列的概率加和起來:
不適用于大的模型和較長的序列。可以利用概率的時間不變性減少問題的復(fù)雜性。
?
3.前向算法
3.1 理論推導(dǎo)
前向概率：給定隱馬爾科夫模型λ，定義到時刻 t 部分觀測序列為,狀態(tài)的概率為前向概率：
說白了就是計算當給出模型參數(shù)的時候，計算一個觀測序列和第 t 時刻為狀態(tài)的聯(lián)合概率，這是一個遞推的過程，可以一層一層的計算，而不是像列舉法，直接一條路徑走到頭，然后再計算下一條路徑；最后能夠通過加和遞推得到P(O|λ)
已知：因馬爾科夫模型λ和觀測序列O
輸出：觀測序列概率P(O | λ )
方法：前向概率遞推得到P(O,I | λ)，加和得到P(O | λ)
具體過程：
① 初值,計算第一個時間點處于各隱狀態(tài)的概率
等式右邊表示最初第i個狀態(tài)出現(xiàn)的概率，乘以在這個狀態(tài)下，某個觀測狀態(tài)的概率。不懂沒關(guān)系，待會看天氣的實例解釋。
② 遞推?
中括號意思就是當前層的所有N個隱狀態(tài)與下一層的第i個狀態(tài)的連接，里面的 α 是到時刻t部分觀測序列為，且在 t 時刻處于狀態(tài) j 的概率（前向計算給出，第一層用的是過程①），a是 t 時刻第 j 個狀態(tài)到 t+1 時刻第 i 個狀態(tài)的轉(zhuǎn)移情況（轉(zhuǎn)移矩陣給出）；中括號外面乘以的b是當前狀態(tài)下，對應(yīng)觀測情況發(fā)生的概率，比如當前是晴天，那么晴天對應(yīng)海藻濕潤的概率是什么呢?就是b，由混淆矩陣給出。
③終止
其實就是求解在時刻t，所有狀態(tài)的概率求和。
前向算法的高效在于：利用路徑結(jié)構(gòu)將前向概率遞推到全局。在t=1時刻，計算每個狀態(tài)與觀測情況的聯(lián)合概率；t=2...T的時候，計算狀態(tài)與觀測情況的聯(lián)合概率時都用到了前一個時刻剛計算出來的聯(lián)合概率。
窮舉法時間復(fù)雜度：TNT
前向算法的時間復(fù)雜度：N2T其中T是指觀察序列的長度，N是指隱藏狀態(tài)數(shù)目。
【注】每次前向得到的均為隱狀態(tài)和觀測情況的聯(lián)合概率，因而最后一步需要來一次加法。
3.2 實例分解
將上述三步推廣到三天海藻觀察和天氣狀態(tài)中：
（1）計算t=1時的局部概率
局部概率的計算公式：
αt ( j )= Pr( t=1時刻的海藻觀察?|?隱藏狀態(tài)?j ) x Pr( t=1?時刻每個隱狀態(tài)可能發(fā)生的初始概率）
?
所以初始時刻狀態(tài) j 的局部概率依賴于此狀態(tài)的初始概率及相應(yīng)時刻我們所見的觀察概率。
（2）? 計算 t >1 時的局部概率
αt ( j )= Pr( t 時刻海藻的觀察情況 | 隱藏狀態(tài) j ) x Pr( t 時刻狀態(tài)到 t+1時刻狀態(tài)的轉(zhuǎn)移概率）
假設(shè)乘號左邊項Pr( 觀察情況 | 隱藏狀態(tài) )已經(jīng)有了，需要考慮右邊Pr( t?時刻所有指向?j?狀態(tài)的路徑）
計算到達某個狀態(tài)的所有路徑的概率。可以計算到達此狀態(tài)的每條路徑的概率并對它們求和。
計算α所需要的路徑數(shù)目隨著觀察序列的增加而指數(shù)級遞增。但是t-1時刻給出了所有到達此狀態(tài)的前一路徑概率。因此，我們可以通過t-1時刻的局部概率定義?t?時刻的局部概率。即：
我們計算的這個概率等于相應(yīng)的觀察概率?( t+1時在狀態(tài)?j 的觀察概率)與該時刻到達此狀態(tài)的概率總和（上一步每個局部概率的計算結(jié)果與相應(yīng)的狀態(tài)轉(zhuǎn)移概率乘積后再相加）的乘積。假設(shè)式子中t=1，拿上圖為例，第三列的中間節(jié)點代表的就是觀察海藻處于某種狀態(tài)時出現(xiàn)某種天氣的概率即b，后面的加和項就是第二列三個節(jié)點的概率與對應(yīng)轉(zhuǎn)移到第三排中間結(jié)點概率的乘積的和。
（3）將第（2）步按照下表j（所有狀態(tài)）加和起來即可
4. 后向算法
后向概率：給定隱馬爾可夫模型，定義在時刻t狀態(tài)為的條件下，從t+1時刻到T的部分觀測序列為后向概率
用遞推方法求后向概率，但是并非用簡單的加法得到P(O|λ)
具體過程(參考李航《統(tǒng)計學習方法》)：
輸入：隱馬爾可夫模型λ，觀測序列O
輸出：觀測序列概率P(O|λ)
①初始化后向概率，最終時刻的所有狀態(tài)規(guī)定
②對于t=T-1,T-2,...1遞推計算，時刻 t 狀態(tài)為條件下時刻t+1之后的觀測序列為的后向概率，其實就是第t+1 時刻的N個狀態(tài)到t 時刻狀態(tài)的轉(zhuǎn)移概率乘以t+1時刻每個隱狀態(tài)對應(yīng)的觀察情況為o(t+1)的概率，再乘以狀態(tài)j之后的觀測序列的后向概率,此項能夠遞推得到
③計算一種加和，但是與前向算法的加和還不一樣，它的含義是與步驟②一樣的，只不過初始概率 π 代替了轉(zhuǎn)移概率 a?
5. 統(tǒng)一寫法
《統(tǒng)計學習方法》中將前向算法和后向算法統(tǒng)一起來歸納了
6. 前向算法實例
6.1 海藻的實例
由馬爾可夫模型MM可知：由一個狀態(tài)轉(zhuǎn)移至另一個狀態(tài)中，存在著轉(zhuǎn)移概率，并對這種轉(zhuǎn)移概率可以依據(jù)其緊接的前一種狀態(tài)推算出來，與該系統(tǒng)原始狀態(tài)和此次轉(zhuǎn)移前的馬爾可夫過程無關(guān)。
隱馬爾可夫模型(Hidden Markov models ,HMM)是馬爾可夫鏈的一種，它的狀態(tài)不能直接觀察到，但能通過觀測向量序列觀察到，每個觀測向量都是通過某些概率密度分布表現(xiàn)為各種狀態(tài)，每一個觀測向量是由一個具有相應(yīng)概率密度分布的狀態(tài)序列產(chǎn)生的。
假設(shè)連續(xù)觀察三天的水藻濕度為(Dry，Damp，Soggy)，求出該觀察序列的概率。天氣狀態(tài)有三類(Sunny,Cloudy,Rainy)，而且海藻濕度和天氣有一定關(guān)系。
已知：
?1> 隱藏狀態(tài)：Sunny，Cloudy，Rainy
? ? ? ?海藻濕度有四類：{Dry，Dryish，Damp，Soggy}
?2>?觀察狀態(tài)序列：{Dry，Damp，Soggy}
?3>? 初始狀態(tài)序列：Sunny(0.63)，Cloudy(0.17)，Rainy(0.20)
?4>? 狀態(tài)轉(zhuǎn)移矩陣
| ? | Sunny | Cloudy | Rainy |
| Sunny | 0.5 | 0.375 | 0.125 |
| Cloudy | 0.25 | 0.125 | 0.625 |
| Rainy | 0.25 | 0.375 | 0.375 |
?
?
?
Cloudy(昨天)→Sunny(今天)的概率是0.25
Sunny(昨天)→Rainy(今天)的概率是0.125?
5>?混淆矩陣
| ? | Dry | Dryish | Damp | Soggy |
| Sunny | 0.6 | 0.2 | 0.15 | 0.05 |
| Cloudy | 0.25 | 0.25 | 0.25 | 0.25 |
| Rainy | 0.05 | 0.10 | 0.35 | 0.50 |
怎么計算觀察序列的概率？
即統(tǒng)計P(observation|Sunny,Sunny, Sunny)+P(observation| Sunny, Sunny, Cloudy)+ P(observation| Sunny,Sunny,Rainy)+ P(observation| Sunny, Cloudy, Sunny) + P(observation| Sunny, Cloudy,Cloudy)+ P(observation| Sunny, Cloudy, Rainy) + …總共33種可能性。
實際由于馬爾可夫模型，第二天的狀況只取決于第一天，第三天的只取決于第二天，與第一天的天氣沒關(guān)系。
①??先求第一天的P(Day1-Sunny),P(Day1-Cloudy),P(Day1-Rainy),Day1的海藻濕度是Dry
P(Day1-Sunny) =0.63*0.6;
P(Day1-Cloudy)=0.17*0.25;
P(Day1-Rain)=0.20*0.05;
②??再求第二天的P(Day2-Sunny),P(Day2-Cloudy),P(Day2-Rainy), Day2的海藻濕度是Damp
P(Day2-Sunny)=(P(Day1-Sunny)*0.5 + P(Day1-Cloudy)*0.25 +P(Day1-Rainy)*0.25)* 0.15
P(Day2-Cloudy) =(P(Day1-Sunny)*0.375+ P(Day1-Cloudy)*0.125 + P(Day1-Rainy)*0.375) * 0.25
P(Day2-Rainy) =(P(Day1-Sunny)*0.125+P(Day1-Cloudy)*0.625 + P(Day1-Rainy)*0.375)* 0.35
同理繼續(xù)求第三日的各天氣概率，Day3的海藻濕度是soggy。
P(Day3-Suny)=(P(Day2-Sunny)*0.5 + P(Day2-Cloudy)*0.25 +P(Day2-Rainy)*0.25)* 0.05
P(Day3-Cloudy) =(P(Day2-Sunny)*0.375+ P(Day2-Cloudy)*0.125 + P(Day2-Rainy)*0.375) * 0.25
P(Day3-Rainy)=(P(Day2-Sunny)*0.125+ P(Day2-Cloudy)*0.625 + P(Day2-Rainy)*0.375)* 0.50
推出：
P(observationlist) =P(Day3-Sunny)+P(Day3-Cloudy)+P(Day3-Rainy) = 0.030319
6.2 盒中取球的實例
已知HMM模型參數(shù)：
轉(zhuǎn)移概率矩陣A：
?
| 0.5 | 0.2 | 0.3 |
| 0.3 | 0.5 | 0.2 |
| 0.2 | 0.3 | 0.5 |
混淆矩陣B：
?
| 0.5 | 0.5 |
| 0.4 | 0.6 |
| 0.7 | 0.3 |
初始概率：
π=(0.2 , 0.4 , 0.4)
求解：三次取球顏色為（紅、白、紅）的概率P(O|λ)
提示：盒子相當于三種隱狀態(tài)，兩種顏色的球相當于觀測情況，觀測序列由（紅、白、紅）給出
（1）計算初值
（2）遞推計算
（3）終止條件
7. 后向算法實例
關(guān)于后向算法，直接以6.2盒子（隱）和球（觀測）的實例為例推導(dǎo)吧：
（1）初始化第三次取球為紅球時候，即最終時刻所有狀態(tài)的概率為1
式中下標為觀測情況，括號為隱狀態(tài)，比如第一個式子意思就是第一個隱狀態(tài)對應(yīng)的觀測到紅球的概率
（2）逆推迭代倒數(shù)第二次觀察情況為白球的情況
第一個式子表示的是第二次觀測，如果狀態(tài)為1，那么第二、三次觀測為（白、紅）的聯(lián)合概率分布，a是第二層隱狀態(tài)（第一個盒子）轉(zhuǎn)移到第三層隱狀態(tài)（三個盒子）的轉(zhuǎn)移概率，b表示第三層的三個隱狀態(tài)觀測到紅球的概率，β（等式右邊）表示已知模型參數(shù)和第三層隱狀態(tài)，求第三次觀測到紅球的概率，其實第（1）步計算是1
第二個式子表示的是第二次觀測，如果狀態(tài)為2，那么第二、三次觀測為（白、紅）的聯(lián)合概率分布，a是第二層隱狀態(tài)（第二個盒子）轉(zhuǎn)移到第三層隱狀態(tài)（三個盒子）的轉(zhuǎn)移概率，b表示第三層的三個隱狀態(tài)觀測到紅球的概率，β（等式右邊）表示已知模型參數(shù)和第三層隱狀態(tài)，求第三次觀測到紅球的概率，其實第（1）步計算是1
同理推導(dǎo)第一層的情況
（3）計算加和
可以發(fā)現(xiàn)前向算法和后向算法的結(jié)果相同
【注】前向算法中計算結(jié)果舍去了一位，結(jié)果應(yīng)該是0.035512
?
總結(jié)
以上是生活随笔為你收集整理的HMM——前向算法与后向算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 为什么实例没有prototype属性？什
- 下一篇： CSS——inline-block属性