作者 | 梁雲1991
來源 | Python與算法之美
HMM模型，韓梅梅的中文拼音的縮寫，所以又叫韓梅梅模型，由於這個模型的作者是韓梅梅的粉絲，所以給這個模型取名為HMM。開玩笑！
HMM模型，也叫做隱馬爾科夫模型，是一種經典的機器學習序列模型，實現簡單，計算快速，廣泛用於語音識別，中文分詞等序列標註領域。
下面通過一個村民看病的故事理解什麼是HMM模型。
想像一個鄉村診所，村民的身體狀況要麼健康要麼發燒，他們只有問診所的醫生才能知道是否發燒。
醫生通過詢問村民的感覺去診斷他們是否發燒。村民自身的感覺有正常、頭暈或冷。
假設一個村民每天來到診所並告訴醫生他的感覺。村民的感覺只由他當天的健康狀況決定。
村民的健康狀態有兩種：健康和發燒，但醫生不能直接觀察到，這意味著健康狀態對醫生是不可見的。
每天村民會告訴醫生自己有以下幾種由他的健康狀態決定的感覺的一種：正常、冷或頭暈。
於是醫生會得到一個村民的感覺的觀測序列，例如這樣：{正常，冷，冷，頭暈，冷，頭暈，冷，正常，正常}。
但是村民的健康狀態這個序列是需要由醫生根據模型來推斷的，是不可直接觀測的。
這個村民看病的故事中由村民的健康狀態序列和村民的感覺序列構成的系統就是一個隱馬爾科夫模型(HMM)。
其中村民的健康狀態序列構成一個馬爾科夫鏈。其每個序列值只和前一個值有關，和其它值無關。由於這個馬爾科夫鏈是隱藏的，不可以被直接觀測到，只能由其關聯的村民的感覺序列來進行推斷，因此叫做隱馬爾科夫模型(HMM)。
HMM模型的上帝視角
HMM模型是一個生成模型，描述了兩個相關序列的依賴關係。
這兩個相關序列稱為狀態序列 和 觀測序列 .
其中狀態序列在t時刻的值只和t-1時刻狀態序列的取值有關，觀測序列在t時刻的值只和t時刻觀測序列的取值有關。
其聯合概率函數如下：
如果能夠確定聯合概率函數中的各個參數，那麼HMM模型也就完全地確定了，我們就擁有了HMM模型描述的這個體系的上帝視角，可以用來計算任何關心的事件的概率，從而解決我們感興趣的問題。
HMM的三大假設
1，馬爾科夫性假設：t時刻的狀態出現的概率只和t-1時刻的狀態有關。
2，齊次性假設：可以理解為時間平移不變性
如
3，觀測獨立性假設：某個時刻t的觀測值只依賴於該時刻的狀態值，與任何其它時刻的觀測值和狀態值無關。
上述HMM的聯合概率函數中，實際上就用到了HMM的三大假設。
HMM的三要素
觀察HMM的聯合概率函數：
可以看到只依賴於三種概率值參數
, ,
分別是初始狀態概率，狀態值轉移概率，觀測值輸出概率(發射概率)
這就是HMM的三要素，也就是HMM的全部參數，確定了這三種概率，HMM模型就完全確定下來了。
對於狀態值取值和觀測值取值為離散值的情況下，這三種概率可以表示為矩陣。
假定狀態值可能的取值為 ，一共有M種可能取值。觀測值可能的取值為 ，一共有N種可能取值。
則HMM的全部參數可以表示為三個矩陣
其中 叫做初始概率矩陣，是一個M維向量，
叫做轉移概率矩陣，是一個M×M維矩陣，
叫做發射概率矩陣，是一個M×N維矩陣，
以上面村民看病的例子為例，假設這三個矩陣分別為：
pi = {'Healthy': 0.6, 'Fever': 0.4} #初始狀態矩陣A = { 'Healthy' : {'Healthy': 0.7, 'Fever': 0.3}, 'Fever' : {'Healthy': 0.4, 'Fever': 0.6}, } #狀態矩陣B = { 'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1}, 'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},} # 發射矩陣
HMM的三個基本問題
HMM模型相關的應用問題一般可以歸結為這三個基本問題中的一個：
1，評估問題：已知模型參數 ，和觀測序列 , 計算觀測序列出現的概率。以村民看病問題為例, 計算一個村民連續出現 {正常，冷，頭暈} 感覺的概率。評估問題一般使用前向算法或者後向算法進行解決，其中前向算法相對簡單，容易理解一些。後向算法較難理解。設想有兩個描述兩人語音的HMM模型，那麼給一個新的語音序列，利用前向算法或者後向算法就可以計算這個語音序列更可能是哪個人的。
2，預測問題：也叫做解碼問題。已知模型參數 ，和觀測序列 , 計算該觀測序列對應的最可能的狀態序列。以村民看病問題為例，假設一個病人連續出現 {正常，冷，頭暈} 的感覺，計算病人對應的最可能的健康狀態序列。預測問題一般使用貪心近似算法或者維特比算法解決。其中貪心近似算法相對簡單一些，但不一定能找到全局最優解。維特比算法可以找到全局最優，是一種動態規划算法。
3，學習問題：模型參數 未知，推斷模型參數。有兩種可能的場景，一種是監督學習的場景，已知諸多觀測序列和對應的狀態序列，推斷模型參數，第二種是非監督學習的場景，只知道諸多觀測序列，推斷模型參數。監督學習的場景，學習方法相對簡單。非監督學習的場景，一般使用EM期望最大化方法進行迭代求解。
三個基本問題的簡單解法
1，評估問題的簡單解法
已知模型參數 ，和觀測序列 , 計算觀測序列出現的概率。
評估問題一般使用前向算法或者後向算法進行解決，其中前向算法相對簡單。
如果暴力求解，這個概率可以計算如下:
計算複雜度大約為
前向算法是一種遞推算法，可以大大減少重複計算，降低計算複雜度。
構造序列
則初始值如下：
而：
不難發現存在遞推公式如下：
通過, 我們可以計算
計算複雜度已經降低為
2，預測問題的簡單解法
已知模型參數 ，和觀測序列 , 計算該觀測序列對應的最可能的狀態序列。
預測問題一般使用貪心近似算法或者維特比算法解決。較常用的是維特比算法。但貪心近似算法更加簡單，很多時候就已經足夠使用。
其基本思想是貪心思想，每一個步驟都取相應的, 使得對應輸出的概率最大。
3， 學習問題的簡單解法
模型參數 未知，推斷模型參數。監督學習的場景，學習方法相對簡單。已知諸多觀測序列和對應的狀態序列，推斷模型參數。
這種情況下可以統計相應的頻率作為, , 中各個概率的估計值。
三個基本問題的複雜解法
1，評估問題的複雜解法
已知模型參數 ，和觀測序列 , 計算觀測序列出現的概率。
除了前向算法，還有一種後向算法，功能和前向算法相當，也是使用遞推法實現的，但沒有前向算法那麼直觀。
構造序列
我們規定 對任何都成立。
類似地我們可以發現後向遞推關係：
通過, 我們可以計算
2，預測問題的複雜解法
已知模型參數 ，和觀測序列 , 計算該觀測序列對應的最可能的狀態序列。
解決這一預測問題較常用的方法是維特比算法，是一種動態規划算法，也可以理解成一種搜索空間的剪枝方法，可以保證找到全局最優路徑。
不同於貪心近似算法在每個步驟只保留一條當前最優路徑，維特比算法在每個步驟會保留若干條當前最優路徑，這些最優路徑和每個步驟的最後一個隱含狀態值的可能取值相對應，如果狀態值有M個可能取值，則每個步驟保留M條當前最優路徑。
由於HMM的馬爾科夫性質，之後的概率計算只和最後一個隱藏狀態取值相關，因此全局的最優路徑必定在這M條當前最優路徑中，如此遞推不斷向前尋找M個隱狀態值對應的M條當前最優路徑，最後取最終得到的M條當前最優路徑中概率最大的那條作為全局最優路徑。
3，學習問題的複雜解法
模型參數 未知，推斷模型參數。
這是一個存在隱變量的概率模型的參數估計問題，一般使用EM期望最大化算法進行求解。
原始問題可以定義為
根據期望最大化算法的算法原理，可以得到迭代條件如下：
於是可以得到三個參數 的 迭代條件：
其中 不含待優化參數，求導為0，考慮概率之和為1的約束，可以構造拉格朗日乘子法進行求解，過程較為繁瑣，從略。
參考文章：
《一站式解決：隱馬爾可夫模型（HMM）全過程推導及實現》：https://zhuanlan.zhihu.com/p/85454896
《機器學習：HMM原理及其實踐》：https://www.cnblogs.com/zhangxinying/p/12071061.html
《概率圖模型體系：HMM、MEMM、CRF》：https://zhuanlan.zhihu.com/p/33397147