HMM

Hidden Markov Models：隱馬爾可夫模型,。
隱馬爾可夫模型是一個(gè)包含隱變量的時(shí)序模型,，可以從馬爾可夫假設(shè)角度概率推導(dǎo)：

也可以從概率圖(簡(jiǎn)單緊湊的概率圖模型)角度理解依賴關(guān)系：

本文結(jié)合概率基礎(chǔ)，主要從概率圖角度理解HMM,。

如圖即為一個(gè)簡(jiǎn)單的貝葉斯網(wǎng)絡(luò),，O表示觀察值，Q表示隱變量,，經(jīng)常使用的符號(hào)還有O-S,、X-Y等。
HMM通過建模p(O, Q)預(yù)測(cè)p(Q|S),，屬于生成式模型,。

HMM主要包含以下幾點(diǎn)：

1. 三個(gè)基本問題
   評(píng)估、解碼及學(xué)習(xí),。
   模型的符號(hào)標(biāo)記為λ，指的也就是狀態(tài)轉(zhuǎn)移矩陣A,、發(fā)射概率B等參數(shù),。

Jurafsky & Martin 《Speech and Language Processing》

2. 兩個(gè)需要學(xué)習(xí)的矩陣
   狀態(tài)轉(zhuǎn)移概率矩陣及發(fā)射概率矩陣,。

Jurafsky & Martin 《Speech and Language Processing》

3. 四個(gè)動(dòng)態(tài)規(guī)劃算法
   前向算法(The Forward Algorithm)、后向算法(the backward probability),、前向后向算法(the forward-backward/Baum-Welch algorithm)及維特比算法(The Viterbi Algorithm),。
   需要注意的是動(dòng)態(tài)規(guī)劃算法只是遞歸形式的數(shù)學(xué)運(yùn)算，能夠有效減低計(jì)算復(fù)雜度,，但其本身和模型學(xué)習(xí)沒有必然聯(lián)系,。
   比如計(jì)算似然：

如果遍歷Q，計(jì)算復(fù)雜度將是O(N^T),，N表示Q的空間大小,，T表示序列長度；如果采用前向算法,，則時(shí)間復(fù)雜度降到O(N^2 * T),。

4. EM最優(yōu)化方法
   the Expectation-Maximization algorithm。

幾個(gè)重要的概率公式

d-分離

對(duì)于HMM來說,，關(guān)鍵點(diǎn)是X1->X2-> ··· ->Xn,，只要中間有一處阻塞，X1影響不到Xn,。

前向算法

The Forward Algorithm,，應(yīng)用于評(píng)估問題，求解p(O|λ),。

關(guān)于α的定義及遞歸關(guān)系,，在概率圖上，一目了然,。

Jurafsky & Martin 《Speech and Language Processing》

算法流程：

Jurafsky & Martin 《Speech and Language Processing》

維特比算法

The Viterbi Algorithm,，應(yīng)用于解碼問題，給定模型λ=(A,，B)及觀察值O=o1o2···ot,，求解最優(yōu)序列q1q2···qt。

與前向算法形式一致,，替換求和(Σ)為最大(max)即可,。

Jurafsky & Martin 《Speech and Language Processing》

算法流程：

Jurafsky & Martin 《Speech and Language Processing》

EM算法

一種最優(yōu)化方法：

1. 求解隱變量的期望
2. 已知隱變量，優(yōu)化最大似然

Daniel Ramage CS229 Hidden Markov Models Fundamentals

后向算法

the backward probability,，前向后向算法的一部分,，輔助解決學(xué)習(xí)問題。

算法流程：

Jurafsky & Martin 《Speech and Language Processing》

前向后向算法

the Baum-Welch algorithm,，解決模型學(xué)習(xí)問題,，給定觀察值序列O及隱狀態(tài)集合，學(xué)習(xí)矩陣A和B。

采用EM算法,，CS229 Daniel Ramage 給出了嚴(yán)謹(jǐn)?shù)淖C明,，假定隱變量期望給定，采用拉格朗日乘子法最優(yōu)化最大似然,，然后根據(jù)求解結(jié)果,，確定實(shí)際需要求解的隱變量期望。

Daniel Ramage CS229 Hidden Markov Models Fundamentals

期望示意圖：

Jurafsky & Martin 《Speech and Language Processing》

監(jiān)督學(xué)習(xí) vs 非監(jiān)督學(xué)習(xí)

對(duì)HMM模型來說：

• 監(jiān)督學(xué)習(xí)是指數(shù)據(jù)有隱變量Q的標(biāo)簽,，此時(shí)只需要求解最大似然確定A,、B。
• 非監(jiān)督學(xué)習(xí)是指只有隱變量的取值集合,，數(shù)據(jù)本身沒有隱變量標(biāo)簽,，此時(shí)需要通過上文中的前向后向/EM算法學(xué)習(xí)A、B,；注意此時(shí)的狀態(tài)轉(zhuǎn)移矩陣對(duì)機(jī)器來說只是一個(gè)編號(hào),，并不能直接對(duì)應(yīng)真實(shí)的狀態(tài)標(biāo)簽，類似聚類出的類別,，只代表有這些類但不知道具體是什么類,。

應(yīng)用案例

詞性標(biāo)注：

Jurafsky & Martin 《Speech and Language Processing》

GMM-HMM：

A Learning-Based Approach for Lane Departure Warning Systems With a Personalized Driver Model

DNN-HMM：

總結(jié)

HMM是一個(gè)有向概率圖/貝葉斯網(wǎng)絡(luò)模型，能夠通過序列觀察值,，推測(cè)更能表達(dá)事物本質(zhì)的隱狀態(tài),。
HMM是通過對(duì)p(O,Q)建模推測(cè)P(Q|O)，是生成式模型,，當(dāng)前狀態(tài)只和上一時(shí)刻狀態(tài)有關(guān)的馬爾可夫假設(shè),，使模型捕捉上下文信息有所欠缺。
HMM是機(jī)器學(xué)習(xí)非常經(jīng)典的算法,，深度學(xué)習(xí)時(shí)代,，對(duì)序列建模，采用更多的是RNN,、LSTM等,。