轉(zhuǎn)自：小象學(xué)院+自己總結(jié)
模型+策略+算法
隱馬爾可夫模型是用于標(biāo)注問題，描述由隱藏的馬爾科夫鏈隨機(jī)生成觀測序列的過程肠槽，屬于生成模型擎淤。在語音識(shí)別、自然語言處理秸仙、生物信息嘴拢、模式識(shí)別等領(lǐng)域有廣泛應(yīng)用。
是關(guān)于時(shí)序的概率模型寂纪，描述隱變量的隨機(jī)狀態(tài)席吴，以及隱藏狀態(tài)生成觀測序列。每個(gè)觀測序列又可以看作是一個(gè)時(shí)刻捞蛋。
模型由初始概率分布抢腐、狀態(tài)轉(zhuǎn)移概率分布以及觀測概率分布確定。Q為所有可能狀態(tài)的集合襟交，V是所有可能觀測的序列迈倍。
I是長度為T的狀態(tài)序列，O為其對(duì)應(yīng)的觀測序列捣域。
模型可以表示為：
其中包含兩個(gè)假設(shè)：
1）齊次馬爾科夫性假設(shè)啼染，任意時(shí)刻t的狀態(tài)只依賴于其前一時(shí)刻的狀態(tài)，與其他時(shí)刻的狀態(tài)和觀測無關(guān)焕梅，也與時(shí)刻t無關(guān)
2）觀測獨(dú)立性假設(shè)迹鹅，任意時(shí)刻的觀測只依賴于該時(shí)刻的隱馬爾可夫鏈的狀態(tài)，與其他觀測和狀態(tài)無關(guān)贞言。
三個(gè)基本問題：
1）概率計(jì)算問題：給定模型和觀測序列斜棚，計(jì)算在模型lambda下觀測序列O出現(xiàn)的概率P（O|lambda）
2）學(xué)習(xí)問題：已知觀測序列O，估計(jì)模型lambda的參數(shù)该窗，使得P（O|lambda）最大弟蚀，用極大似然估計(jì)的方法來估計(jì)參數(shù)
3）預(yù)測問題：也稱為解碼，已知模型lambda和觀測序列O求P（I|O）最大的I酗失，即最有可能的狀態(tài)序列义钉。
后續(xù)進(jìn)行中文分詞實(shí)踐
問題1：概率計(jì)算算法，計(jì)算觀測序列概率P（O|lambda）前向和后向算法
首先先介紹一下直接計(jì)算规肴。
最直接的方法是通過列舉所有可能長度為T的狀態(tài)序列捶闸，求各個(gè)狀態(tài)序列I與觀測序列O的聯(lián)合概率P(O,I|lambda)，然后對(duì)所有狀態(tài)序列求和得到P（O|lambda）
可以看出計(jì)算量非常大拖刃，是O（TN^T）階的删壮，因此不可行，需要引入前向后向算法
前向概率：
步驟1初始化前向概率兑牡，是初始時(shí)刻狀態(tài)i1=qi和觀測o1的聯(lián)合概率
步驟2是前向概率的遞推公式央碟，計(jì)算時(shí)刻r+1部分的觀測序列為o1,o2,...,ot,ot+1,且在時(shí)刻t+1處于狀態(tài)qi的前向概率。對(duì)于這個(gè)乘積在時(shí)刻t的所有可能的N個(gè)狀態(tài)qj求和发绢，其結(jié)果就是得到在時(shí)刻t+1達(dá)到狀態(tài)qi的聯(lián)合概率
可以看出前向算法實(shí)際是基于狀態(tài)序列的路徑結(jié)構(gòu)遞推計(jì)算硬耍，高效的關(guān)鍵在于局部計(jì)算前向概率垄琐。
這樣時(shí)間復(fù)雜度就降為了O（N^2T）
后向算法：
注意：前向概率計(jì)算出的是P（O,I|lambda），因此只需把所有狀態(tài)的概率相加即可
后向概率計(jì)算的是P（O|I经柴，lambda）狸窘，意思就是最后一個(gè)狀態(tài)已經(jīng)知道了，那么P（O,I|lambda）=P（O|I坯认，lambda）*P(O|I)再把所有狀態(tài)加起來
監(jiān)督學(xué)習(xí)（極大似然估計(jì)）和非監(jiān)督學(xué)習(xí)BW算法（EM）
監(jiān)督學(xué)習(xí)：
1. 轉(zhuǎn)移概率aij的估計(jì)
設(shè)樣本中時(shí)刻t處于狀態(tài)i時(shí)刻t+1轉(zhuǎn)移到狀態(tài)j的頻數(shù)為Aij那么aij的估計(jì)是
2. 觀測概率bj(k)的估計(jì)
設(shè)樣本中狀態(tài)為j并觀測為k的頻數(shù)是Bij翻擒，那么狀態(tài)為j觀測為k的概率bj(k)的估計(jì)是
3. 初始狀態(tài)概率pi的估計(jì)為初始狀態(tài)為qi的頻數(shù)
由于監(jiān)督學(xué)習(xí)需要使用訓(xùn)練數(shù)據(jù)，而人工標(biāo)注數(shù)據(jù)的代價(jià)很高牛哺，所以我們常用非監(jiān)督學(xué)習(xí)的方法
非監(jiān)督學(xué)習(xí)Baum-welch算法
隱馬爾可夫模型可以看作下面這個(gè)模型
它的參數(shù)學(xué)習(xí)可以由EM算法實(shí)現(xiàn)
1. 確定完全數(shù)據(jù)的對(duì)數(shù)似然函數(shù)logP（O陋气，I | lambda）
2. EM算法的E步：求Q函數(shù)Q（lambda，lambda^）
3. EM算法的M步：極大化Q函數(shù)引润，求模型中的A,B,PI
由于要極大化Q函數(shù)里的三項(xiàng)巩趁，可以對(duì)其進(jìn)行分別極大化
第二項(xiàng)式子可以寫成
第三項(xiàng)可以寫為：
問題3：解碼問題
可以用近似算法或者是維特比算法（viterbi）
近似算法：在每個(gè)時(shí)刻t選擇在該時(shí)刻最可能出現(xiàn)的狀態(tài)it。推廣到一個(gè)狀態(tài)序列
近似算法的優(yōu)點(diǎn)是計(jì)算簡單淳附，其缺點(diǎn)是不能保證預(yù)測狀態(tài)序列是整體最優(yōu)序列议慰，因?yàn)閺恼w的角度有可能不發(fā)生，存在轉(zhuǎn)移概率為0的情況
維特比算法：實(shí)際是用動(dòng)態(tài)規(guī)劃求解隱馬爾可夫模型預(yù)測問題奴曙，即用動(dòng)態(tài)規(guī)劃求得概率最大路徑（最優(yōu)路徑）
根據(jù)動(dòng)態(tài)規(guī)劃原理别凹，最優(yōu)路徑具有這樣的特性：如果最優(yōu)路徑在時(shí)刻t通過節(jié)點(diǎn)it，那么這條路徑從節(jié)點(diǎn)it到終點(diǎn)iT部分的路徑是最優(yōu)的洽糟。
因此我們只需要從t=1開始炉菲，遞推地計(jì)算在時(shí)刻t狀態(tài)為i的各條部分路徑的最大概率，直到t=T
注意前向概率和后項(xiàng)概率之間的關(guān)系
當(dāng)狀態(tài)為離散坤溃，觀測值為連續(xù)時(shí)拍霜，要使用高斯隱馬爾可夫
