點擊上方「智能與算法之路」，選擇「星標」公眾號
資源乾貨，第一時間送達
今天為大家介紹的是隱馬爾可夫模型（Hidden Markov Model），隱馬爾可夫模型最初是在20世紀60年代後半期Leonard E. Baum和其它一些作者在一系列的統計學論文中描述的。HMM最初的應用之一是開始於20世紀70年代中期的語音識別。
隱馬爾可夫模型
簡單介紹
隱馬爾可夫模型是關於時序（順序）的概率模型，描述由一個隱藏的馬爾可夫鏈隨機生成不可觀測的狀態隨機序列，再由各個狀態生成一個觀測而產生觀測隨機序列的過程。隱藏的馬爾可夫鏈隨機生成的狀態的序列，稱為狀態序列（state sequence);每個狀態生成一個觀測，而由此產生的觀測的隨機序列，稱為觀測序列（observation sequence)。序列的每一個位置又可以看作是一個時刻。
我們知道句子的表達不僅與其構成的詞語有關，還與詞的位置以及語法有關。因此對於語言來說，如果忽略語序進行理解，往往得不到句子正常的意思。（儘管如此，樸素貝葉斯在垃圾郵件分類上仍取得很好的效果）HMM在建立模型的時候可以考慮之前狀態對當前的影響。例如，我們要給以下句子做詞性標註
我(名詞)愛(動詞)學習(名詞/動詞？)
如果單獨去給『學習』這個詞標註的話，『學習』可能是名詞也可以是動詞。但在上面那句話裡『學習』顯然是名詞，因為學習前面的詞『愛』是動詞，後面應該接名詞，因此『學習』標註應該標註為名詞。這裡我們在標註的時候考慮前面詞語的詞性對當前詞的詞性的影響。HMM也是這樣去給詞語標註詞性的。只不過HMM是這麼看待以上問題，我 愛 學習 被看做長度為3的序列，這個序列為觀測序列。它們的詞性可以理解為詞語的某個狀態，由於我們現在是要給詞語做標註，因此我們是不知道每個觀測值（詞語）的狀態（詞性）的。並且我們知道句子的基本構成有主謂賓定狀補，詞語的詞性往往與該詞在句子充當的成分有關。例如謂語(愛)之後的詞(學習)很有可能名詞這麼一種轉態改變的規則。
用HMM的概念來說，我愛學習是觀測序列，詞語的詞性序列是一個狀態序列，詞性變化規則為狀態轉移矩陣（描述不同狀態相互轉換的概率）。在深入介紹隱馬爾可夫模型之前先引入一些基本概念。
馬爾可夫性
馬爾可夫性質是概率論中的一個概念。當一個隨機過程在給定現在狀態及所有過去狀態情況下，其未來狀態的條件概率分布僅依賴於當前狀態；換句話說，在給定現在狀態時，它與過去狀態（即該過程的歷史路徑）是條件獨立的，那麼此隨機過程即具有馬爾可夫性質。具有馬爾可夫性質的過程通常稱之為馬爾可夫過程。當前情況盡跟之前n個狀態有關的隨機過程稱為n階馬爾科夫過程。
例子
拿天氣和海藻的例子來說
假設海藻的溼度與天氣有某種關聯，為了簡易的去定義這個問題，定義海藻存在四種觀測值{dry,dryish,damo,soggy},天氣的狀態也只有三種狀態{sunny,cloudy,rainy}。
（這裡我們直接定義了觀測序列為一段時間內，海藻的溼度的一個序列，隱含狀態為同一段時間內，天氣的狀態序列，我們假設一個盲人只能通過觸摸判斷海藻溼度來推測天氣這麼一個情景）
在不同天氣下，觀測到海藻不同的溼度的概率是不同的
上面其實是一個觀測矩陣，表示在不同的隱含狀態下觀測到不同海藻溼度的概率，你會發現該矩陣每一行求和的結果都等於1。這個矩陣的數據是通過經驗獲得的，例如你統計了很多個晴天的狀態下，海藻有著不一樣的溼度，通過對大量數據的一個統計，我們就可以得到晴天狀態下，觀測到不同溼度的海藻的概率。
當然天氣之間也是存在互相轉化的，但令人頭疼的是，昨天的天氣或者更久以前的天氣會對今天的天氣有所影響，這樣考慮問題會使得問題變得格外複雜，因此隱馬爾可夫做了最基本的假設，即當前狀態只與前一個狀態有關（齊次馬爾可夫性假設）。同時也做觀測獨立性假設，所有的觀測之間是互相獨立的，某個觀測之和生成它的狀態有關係。
對應狀態轉移矩陣A
其中為狀態：i->j的概率，然後同樣你會發現每一行元素的求和等於1。
我們還需要序列的初始狀態π，這個初始狀態可以通過對多個樣本的初始狀態進行統計得出。
由此我們就已經定義了一個完整的隱馬爾可夫模型，該模型由觀測序列、狀態序列、以及初始狀態概率向量ππ、狀態轉移概率矩陣AA和觀測概率矩陣BB，其中後三個為隱馬爾可夫模型的參數一般用一個三元組表示。即
假設盲人連續記錄三天，得到觀察序列Q = {dry,damp,soggy},這三天的天氣為{sunny,cloudy,rainy}（儘管盲人無法觀測到，但可以通過馬爾可夫模型去估計這幾天的天氣）
隱馬爾可夫三個基本問題
概率計算問題：給定模型參數和觀測序列，計算出現某個觀測序列的概率
預測問題：給定模型參數和觀測序列，求最有可能的狀態序列
學習問題：給定觀測序列和狀態序列，得到模型參數
概率計算問題
給定模型參數和觀測序列計算觀測序列O的出現概率,直接計算即按照概率公式去計算。
如果直接去計算，通過列舉所有可能的長度為T的狀態序列I，求各個狀態序列I與觀測序列的聯合概率,然後對所有可能的狀態序列求和得到結果
對於給定的I序列,O,I同時出現的聯合概率為
然後，對所有可能的狀態序列I求和，得到觀測序列O的概率
利用上述公式計算量很大，因為所有可能的狀態序列有很多種，上述方法時間複雜度是的，這種算法在數據量大的情況下，是不可行的。因此我們用前向算法去計算其時間複雜度為。
前向算法
前向概率 ：給定隱馬爾可夫模型參數λ 定義時刻t部分觀測序列為
，且狀態為的概率為前向概率，記作
每次計算利用了前一時刻Ｎ個狀態下的,避免了重複計算
前向算法其實是以空間換時間的一種方法。具體的第一項的前向概率為
後面的項的前向概率為
因此得出
同理我們可以導出後向概率與後向算法
後向算法的從序列後面開始計算概率，最後一項的後項概率為
其餘項的後向概率表示為
得出
利用前向概率和後向概率的定義可以將概率統一寫成
此式當t = 1 和 t = T -1時，則分別寫為原來的形式
學習問題
監督學習問題
如果訓練數據包含S個長度的長度的觀測序列和對隱狀態序列那麼我們可以直接用極大似然估計隱馬爾可夫模型的參數其中
π̂ 為需要統計S個樣本中初始狀態為的概率。
監督學習需要大量的數據，而且人工標註訓練數據的代價往往很高，故有時就會利用非監督學習的方法。
baum-welch算法
baum-welch算法又稱 前向-後向算法，由baum和welch，算法的本質其實就是用EM算法去估計P(O|λ)P(O|λ)的概率分布對應隱馬爾可夫模型的參數。
確定完全數據的對數似然函數
E步，求Q函數
去掉對λ而言的常數因子
M步
注意到滿足約束條件 ，利用拉格朗日乘子法，對其求偏導並令結果為0，得
對i求和得到γ
代入得
類似的求出
以上式子還可以寫成
預測問題
近似算法
近似算法實際是一種貪心的方法，在每一步選擇概率最大的狀態值作為結果，但這樣得到的結果有可能不是最佳的預測結果，但是近似算法的計算量非常的小。
維特比算法
維特比算法其實用了動態規劃的方法求解HMM的解碼問題。但在小的篇幅中很難把動態規劃講得淺顯易懂。因此有興趣的朋友可以去《數學之美》一書中去了解維特比算法。
資料來源:
《統計學習方法》 李航
以及網上各位大佬的博文
歡迎關注我們，收穫資源乾貨！