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表示序列長(zhǎng)度；如果采用前向算法，則時(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等。