隱含馬爾可夫模型與維特比演算法

隱含馬爾可夫模型與維特比演算法

4 人贊了文章這張圖片摘自吳軍的《數學之美》，畫的是一個籬笆網路，這裡的Xij表示狀態Xi的第j個可能的值。針對這張圖，一個有價值的問題是：如何求出籬笆網路(Lattice)（有向圖）的最短路徑？

規劃最短路徑，本質是一個動態規劃問題。針對籬笆網路的常用演算法是維特比演算法，它之所以重要是因為，凡是使用隱含馬爾科夫模型描述的問題都可以用它來解碼。

用維特比演算法，那上圖的複雜度為O(N·D^2)，這個複雜度表明，維特比演算法是和長度成正比的。無論是在通信領域，還是在語音識別、打字，輸入都是按照流(Stream)的方式進行的，這樣，只要處理每個狀態的時間比說話或者打字的速度快一點（而這是很容易實現的），就完全可以做到實時！這便是數學漂亮的地方！

viterbi演算法：通過已知的可以觀察到的狀態的序列，和一些已知的隱含狀態轉換之間的概率情況，通過綜合可觀察的狀態之間的轉移概率和前一個隱含狀態的情況計算出概率最大的隱含狀態轉換路徑，從而推斷出隱含狀態的序列的情況。

當又想不通時，回去讀數學之美，第26章！

隱含馬爾科夫模型：

到了19世紀，概率論的發展從對（相對靜態的）隨機變數的研究發展到對隨機變數的時間序列s1,s2,s3,s4,st...即隨機過程（動態的）的研究。馬爾科夫為了簡化問題，提出了一種簡化的假設，即隨機過程中各個狀態的概率分布只與它的前一個狀態有關。這一假設後來就被命名為馬爾可夫假設，而符合這一假設的隨機過程則稱為馬爾可夫過程（馬爾可夫鏈）。

轉換概率（transition probability）：是隱含狀態之間的相互轉化；

輸出概率（emission probability）：是指儘管可見狀態之間沒有轉化概率，但是在隱含狀態與可見狀態之間有一個概率；

有關hmm模型的假設：在狀態轉移矩陣及混淆矩陣中的每一個概率都是時間無關的——也就是說，當系統演化時這些矩陣並不隨時間改變。這是hmm模型關於真實世界最不現實的一個假設！！！

由一個向量和兩個矩陣(pi,A,B)描述的隱馬爾科夫模型對於實際系統有著巨大的價值，雖然經常只是一種近似，但它們卻是經得起分析的。隱馬爾科夫模型通常解決的問題包括：

　　1. 對於一個觀察序列匹配最可能的系統——評估，使用前向演算法（forward algorithm）解決；

　　2. 對於已生成的一個觀察序列，確定最可能的隱藏狀態序列——解碼，使用Viterbi 演算法（Viterbi algorithm）解決；

　　3. 對於已生成的觀察序列，決定最可能的模型參數——學習，使用前向-後向演算法（forward-backward algorithm）解決。

隱馬爾可夫模型（原文）（Hidden Markov Model，HMM）是統計模型，它用來描述一個含有隱含未知參數的馬爾可夫過程。其難點是從可觀察的參數中確定該過程的隱含參數。然後利用這些參數來作進一步的分析，例如模式識別。

下面用一個簡單的例子來闡述：

假設我手裡有三個不同的骰子。第一個骰子是我們平常見的骰子（稱這個骰子為D6），6個面，每個面（1，2，3，4，5，6）出現的概率是1/6。第二個骰子是個四面體（稱這個骰子為D4），每個面（1，2，3，4）出現的概率是1/4。第三個骰子有八個面（稱這個骰子為D8），每個面（1，2，3，4，5，6，7，8）出現的概率是1/8。

假設我們開始擲骰子，我們先從三個骰子里挑一個，挑到每一個骰子的概率都是1/3。然後我們擲骰子，得到一個數字，1，2，3，4，5，6，7，8中的一個。不停的重複上述過程，我們會得到一串數字，每個數字都是1，2，3，4，5，6，7，8中的一個。例如我們可能得到這麼一串數字（擲骰子10次）：1 6 3 5 2 7 3 5 2 4

這串數字叫做可見狀態鏈。但是在隱馬爾可夫模型中，我們不僅僅有這麼一串可見狀態鏈，還有一串隱含狀態鏈。在這個例子里，這串隱含狀態鏈就是你用的骰子的序列。比如，隱含狀態鏈有可能是：D6 D8 D8 D6 D4 D8 D6 D6 D4 D8

一般來說，HMM中說到的馬爾可夫鏈其實是指隱含狀態鏈，因為隱含狀態（骰子）之間存在轉換概率（transition probability）。在我們這個例子里，D6的下一個狀態是D4，D6，D8的概率都是1/3。D4，D8的下一個狀態是D4，D6，D8的轉換概率也都一樣是1/3。這樣設定是為了最開始容易說清楚，但是我們其實是可以隨意設定轉換概率的。比如，我們可以這樣定義，D6後面不能接D4，D6後面是D6的概率是0.9，是D8的概率是0.1。這樣就是一個新的HMM。

同樣的，儘管可見狀態之間沒有轉換概率，但是隱含狀態和可見狀態之間有一個概率叫做輸出概率（emission probability）。就我們的例子來說，六面骰（D6）產生1的輸出概率是1/6。產生2，3，4，5，6的概率也都是1/6。我們同樣可以對輸出概率進行其他定義。比如，我有一個被賭場動過手腳的六面骰子，擲出來是1的概率更大，是1/2，擲出來是2，3，4，5，6的概率是1/10。

其實對於HMM來說，如果提前知道所有隱含狀態之間的轉換概率和所有隱含狀態到所有可見狀態之間的輸出概率，做模擬是相當容易的。但是應用HMM模型時候呢，往往是缺失了一部分信息的，有時候你知道骰子有幾種，每種骰子是什麼，但是不知道擲出來的骰子序列；有時候你只是看到了很多次擲骰子的結果，剩下的什麼都不知道。如果應用演算法去估計這些缺失的信息，就成了一個很重要的問題。

以下是一個用隱含馬爾可夫模型來建立的案例，案例中我們通過社交網路知道了每一天一位女士的活動情況，在一些已知概率的基礎上，來預測隱含在其中的天氣的情況，原文在這裡，下面直接給出代碼：

# -*- coding:utf-8 -*-# Filename: viterbi.py# Author：hankcs&andreWu# Date: 2014-05-13 下午8:51 2017-3-10 下午8:42states = (Rainy, Sunny)observations = (walk, shop, clean) #已知的顯狀態時間序列start_probability = {Rainy: 0.6, Sunny: 0.4}transition_probability = { Rainy: {Rainy: 0.7, Sunny: 0.3}, Sunny: {Rainy: 0.4, Sunny: 0.6},}emission_probability = { Rainy: {walk: 0.1, shop: 0.4, clean: 0.5}, Sunny: {walk: 0.6, shop: 0.3, clean: 0.1},}# 列印路徑概率表def print_dptable(V): print " ", for i in range(len(V)): print "%7d" % i, print #此處print是另起一行的作用 #print V for y in V[0].keys(): print "%.5s: " % y, for t in range(len(V)): print "%.7s" % ("%f" % V[t][y]), printdef viterbi(obs, states, start_p, trans_p, emit_p): """ :param obs:觀測序列 :param states:隱狀態 :param start_p:初始概率（隱狀態） :param trans_p:轉移概率（隱狀態） :param emit_p: 發射概率 （隱狀態表現為顯狀態的概率） :return: """ # 路徑概率表 V[時間][隱狀態] = 概率 V = [{}] # 一個中間變數，代表當前狀態是哪個隱狀態 path = {} # 初始化初始狀態 (t == 0) for y in states: V[0][y] = start_p[y] * emit_p[y][obs[0]] print V path[y] = [y] print path # 對 t > 0 跑一遍維特比演算法 for t in range(1, len(obs)):#print(range(1,3)) 得到[1,2] V.append({}) # print V newpath = {} for y in states: # 概率 隱狀態 = 前狀態是y0的概率 * y0轉移到y的概率 * y表現為當前狀態的概率 (prob, state) = max([(V[t - 1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states]) print(prob, state) # 記錄最大概率 V[t][y] = prob # print V[t][y] # 記錄路徑 newpath[y] = path[state] + [y] print newpath # print [y] # 不需要保留舊路徑 path = newpath print_dptable(V) (prob, state) = max([(V[len(obs) - 1][y], y) for y in states]) return (prob, path[state])def example(): return viterbi(observations, states, start_probability, transition_probability, emission_probability)print example()

推薦閱讀：