盡量以最少的符號去詮釋模型，對公式推導的每個步驟也會詳細解讀，因為是按自己的思路理解的，所以符號應用上會與網(wǎng)上常見教程有出入。
一、定義模型
一個隱馬爾可夫模型（Hidden Markov Model, HMM）包含以下概念和參數(shù)：
- 按一定概率生成不可觀測的隱含狀態(tài)序列 H 鏈；
- 由各個隱含狀態(tài)生成一個可觀測結(jié)果序列 V 鏈；
- H 之間存在一個狀態(tài)轉(zhuǎn)換概率函數(shù)矩陣 A；
- H 到 V 存在一個映射概率函數(shù)矩陣 B；
- H 的初始狀態(tài)生成概率變量 C；
- S 為所有隱含狀態(tài)的集合，有 n 種可能的狀態(tài)；
- R 為所有可觀測結(jié)果的集合，有 m 種可能的結(jié)果；
下圖為包含以上參數(shù)的可視化模型：
用實際的例子套用的話，可以用自然語言處理里的詞性標注做例子，這也是 HMM 比較常見的應用。
在詞性標注中，把實際詞語序列（一個句子）看作 V 鏈，把對應的詞性標注序列看作 H 鏈。
比如
I watched the play last night.
是一條 V 鏈，對應的 H 鏈即為：
（代詞-動詞-限定詞-名詞-形容詞-名詞）
c(x1) 即為 “代詞出現(xiàn)的概率”；
b(x1y1) 即為 “在出現(xiàn)代詞的情況下，出現(xiàn)單詞 'I' 的概率”；
a(x1x2) 即為 “在出現(xiàn)代詞的情況下，下一個出現(xiàn)的單詞為動詞的概率”；
在沒給定句子的原始模型中，x 和 y 都是變量，分別有 n 種和 m 種可能。
另外，HMM 有以下幾個約束條件：
根據(jù)馬爾可夫性假設(shè)：H 鏈在任一時刻 t 的狀態(tài)只依賴于其前一個時刻的狀態(tài)?？傻?a 之間沒有依賴關(guān)系。
根據(jù)觀測獨立性假設(shè)：任意時刻 t 的觀測結(jié)果 v(t)，只依賴于該時刻的隱含狀態(tài) h(t)?？傻?b 之間沒有依賴關(guān)系。
-
所有的初始狀態(tài)概率和為1；
某時刻 t 的隱含狀態(tài)轉(zhuǎn)移到一下個所有可能的狀態(tài)的概率和為1；
某時刻 t 的隱含狀態(tài)觀測到的所有可能的觀測值的概率和為1。轉(zhuǎn)化為公式即：
二、HMM 解決的主要問題
- 給出觀測序列 V 和模型 μ=(A, B, C)，選擇出最好解釋 V 的對應的隱含狀態(tài)序列 H；（可應用于詞性標注）
- 給出模型 μ，算出某個觀測序列發(fā)生的概率 p(V)；
- 給定觀測序列 V，計算模型 μ 的參數(shù) (A, B, C) 以最好解釋 V。
問題一：給出觀測序列 V 和模型 μ，選擇出最好解釋 V 的對應的隱含狀態(tài)序列 H
回到詞語標注的例子，把實際詞語序列（一個句子）看作 V 鏈，把對應的詞性標注序列看作 H 鏈。一般實際情況為，有一個語料庫，包含很多需要標注詞性的句子。所以問題二可轉(zhuǎn)換成給一個句子的每個單詞計算出最有可能的詞性進行標注。
可以用 Viterbi 算法實現(xiàn)：
設(shè) δ(t) 表示在 t 時刻、狀態(tài) h(t)=s(xt) 的序列概率最大值
1. 初始值
2. 推導過程
解析：在確認 t-1 時刻的最大概率的基礎(chǔ)上，h(t-1) 會有 n 種可能狀態(tài)，取其中轉(zhuǎn)換到 ht 的概率最大的一項求積，再進行對應的 b 轉(zhuǎn)換。
當取到最大值時，記 h(t)* 為相應的狀態(tài)值。
3. 到最后一項，求得整條 V 鏈最佳路徑的概率
當取到最大值時，記 h(ed)* 為相應的狀態(tài)值。
4. 對最優(yōu)路徑 H 進行回溯，即為所求詞性序列
問題二：給出模型 μ=(A, B, C)，算出某個觀測序列發(fā)生的概率 p(V)
遍歷算法（蠻力算法）
基本思路，計算出每一條能生成對應 V 鏈的 H 鏈的概率，然后累加起來。有以下公式：
累加 n^t 次，是因為一條 H 鏈中，每個轉(zhuǎn)換的節(jié)點都有 n 種轉(zhuǎn)換組合，然后有 t 個節(jié)點。
這種算法非常耗時，計算復雜度是 O(tn^t) 指數(shù)冪級別，一般不采用。
前向算法（Forward Algorithm）
基本思路：運用動態(tài)規(guī)劃的思想，把每一個節(jié)點生成的概率先確定，然后再以此為基礎(chǔ)計算生成下一個節(jié)點的概率。
1. 初始概率
p(t) 表示在 t 時刻、狀態(tài) h(t)=s(xt) 的概率
2. 每次轉(zhuǎn)換的推導
p(t) 為得出前 (t-1) 個觀察值的概率，但對應的 h(t-1) 有 n 種可能，把 x(t-1) 視為變量。
對每一種 ht，h(t+1) 只取某一種對應的可能，最后乘對應的一種 b 轉(zhuǎn)換。一次轉(zhuǎn)換進行了 n^2 次運算。下圖為可視化解析：
3. 到最后一步，由于不需要再做轉(zhuǎn)換，只需要 把 n 種 h(ed) 的概率相加即可
每個節(jié)點都進行了 n*n 次運算，共有 t 個節(jié)點，所以計算復雜度為O(tn^2)，下面的后向算法同理。
后向算法（Backward Algorithm）
基本思路：與前向算法一樣采用動態(tài)規(guī)劃思想，從最后一項開始。
1. 初始概率
p(ed)=1
因為后向算法是由時刻 t+1 的概率值推算出時刻 t 的概率，最后一項沒有任何因素需要依賴，所以概率為1(100%)
2. 每次推導的轉(zhuǎn)換
這里的 p(t) 指得出從 (t+1) 項到最后一項觀察值的概率，h(t+1) 有 n 種可能，把 x(t+1) 視為變量，而 ht 取對應的1種可能，最后乘對應的一種 b 轉(zhuǎn)換。這一次轉(zhuǎn)換進行了 n^2 次運算。下圖為可視化解析：
3. 最后推導到最前
可以理解為 t=0 時，求得目標概率
問題三：給定觀測序列 V，計算模型 μ 的參數(shù) (A, B, C) 以最好解釋 V
這種應用屬于無監(jiān)督學習，可使用 Baum-Welch 算法（本質(zhì)上是 EM 算法），本質(zhì)上是要求對數(shù)似然函數(shù)：log p(V, H | μ)。
（到目前 EM 算法和拉格朗日乘子法還沒完全搞懂，所以直接寫下計算過程）
1. 根據(jù) EM 算法列出 Q 函數(shù)
其中 μ* 是模型當前估算值，一開始先預設(shè)一個，μ 是最終要求的模型最值
因為 p(V | μ*) 是可確定的值，等式中的分母可省略。
2. 解似然函數(shù)
3. 代入到 Q 函數(shù)
4. 上一步的3個加項拆開，三個部分分別滿足以下約束條件
- 最后分別對這三個部分根據(jù)約束依次利用 拉格朗日乘子法 求解，即可求解得到模型的參數(shù)。
最后一個小彩蛋
