HMM模型和Viterbi演算法

07-19

一、隱含馬爾可夫模型（Hidden Markov Model）1、簡介隱含馬爾可夫模型並不是俄羅斯數學家馬爾可夫發明的，而是美國數學家鮑姆提出的，隱含馬爾可夫模型的訓練方法（鮑姆-韋爾奇演算法）也是以他名字命名的。隱含馬爾可夫模型一直被認為是解決大多數自然語言處理問題最為快速、有效的方法。2、馬爾可夫假設隨機過程中各個狀態St的概率分布，只與它的前一個狀態St-1有關，即P(St|S1,S2,S3,…,St-1) = P(St|St-1)。比如，對於天氣預報，硬性假定今天的氣溫只與昨天有關而和前天無關。當然這種假設未必適合所有的應用，但是至少對以前很多不好解決的問題給出了近似解。3、馬爾可夫鏈符合馬爾可夫假設的隨機過程稱為馬爾可夫過程，也稱為馬爾可夫鏈。

圖：馬爾可夫鏈在這個馬爾可夫鏈中，四個圈表示四個狀態，每條邊表示一個可能的狀態轉換，邊上的權值是轉移概率。隱含馬爾可夫鏈是上述馬爾可夫鏈的一個擴展：任一時刻t的狀態St是不可見的。所以觀察者沒法通過觀察到一個狀態序列S1,S2,S3,…,ST來推測轉移概率等參數。但是隱含馬爾可夫模型在每個時刻t會輸出一個符號Ot，而且Ot和St相關且僅和St相關。這稱為獨立輸出假設。隱含馬爾可夫模型的結構如下圖，其中隱含的狀態S1,S2,S3,…是一個典型的馬爾可夫鏈。鮑姆把這種模型稱為「隱含」馬爾可夫模型。

圖：隱含馬爾可夫模型4、隱含馬爾可夫模型的三個基本問題（1）給定一個模型，如何計算某個特定的輸出序列的概率？Forward-Backward演算法（2）給定一個模型和某個特定的輸出序列，如何找到最可能產生這個輸出的狀態序列？維特比演算法（3）給定足夠量的觀測數據，如何估計隱含馬爾可夫模型的參數？訓練隱含馬爾可夫模型更實用的方式是僅僅通過大量觀測到的信號O1，O2，O3，….就能推算模型參數的P(St|St-1)和P(Ot|St)的方法（無監督訓練演算法），其中主要使用鮑姆-韋爾奇演算法。5、隱含馬爾可夫模型的五元組HMM是一個五元組（O , Q , O0，A , B）:O:{o1,o2,…,ot}是狀態集合，也稱為觀測序列。Q:{q1,q2,…,qv}是一組輸出結果，也稱為隱序列。Aij = P(qj|qi)：轉移概率分布Bij = P(oj|qi)：發射概率分布O0是初始狀態，有些還有終止狀態。二、維特比演算法（Viterbi）1、簡介維特比演算法是一個特殊但應用最廣的動態規劃演算法，它是針對籬笆網路的有向圖（Lattice）的最短路徑問題而提出的。凡是使用隱含馬爾可夫模型描述的問題都可以用維特比演算法來解碼，包括今天的數字通信、語音識別、機器翻譯、拼音轉漢字、分詞等。

圖：籬笆網路2、維特比演算法的基礎（1）如果概率最大的路徑P（或叫最短路徑）經過某個點，比如下圖中的X22，那麼這條路徑上從起始點S到X22的這一段子路徑Q，一定是S到X22之間的最短路徑。否則，用S到X22的最短路徑R替代Q，便構成了一條比P更短的路徑，這顯然是矛盾的。（2）從S到E的路徑必定經過第i時刻的某個狀態，假定第i時刻有k個狀態，那麼如果記錄了從S到第i個狀態的所有k個節點的最短路徑，最終的最短路徑必經過其中的一條。這樣，在任何時刻，只需要考慮非常有限條最短路徑即可。（3）結合上述兩點，假定當我們從狀態i進入狀態i+1時，從S到狀態i上各個節點的最短路徑已經找到，並且記錄在這些節點上，那麼在計算從起點S到前一個狀態i所有的k個結點的最短路徑，以及從這k個節點到Xi+1，j的距離即可。

3、維特比演算法總結（1）從點S出發，對於第一個狀態X1的各個節點，不妨假定有n1個，計算出S到它們的距離d(S,X1i)，其中X1i代表任意狀態1的節點。因為只有一步，所以這些距離都是S到它們各自的最短距離。（2）對於第二個狀態X2的所有節點，要計算出從S到它們的最短距離。對於特點的節點X2i，從S到它的路徑可以經過狀態1的n1中任何一個節點X1i，對應的路徑長度就是d(S,X2i) = d(S,X1i) + d(X1i,X2i)。由於j有n1種可能性，我們要一一計算，找出最小值。即：d(S,X2i) = minI=1，n1 d(S,X1i) + d(X1i,X2i)這樣對於第二個狀態的每個節點，需要n1次乘法計算。假定這個狀態有n2個節點，把S這些節點的距離都算一遍，就有O(n1·n2)次計算。（3）接下來，類似地按照上述方法從第二個狀態走到第三個狀態，一直走到最後一個狀態，就得到了整個網格從頭到尾的最短路徑。每一步計算的複雜度都和相鄰兩個狀態Si和Si+1各自的節點數目ni，ni+1的乘積成正比，即O(ni·ni+1)（4）假設這個隱含馬爾可夫鏈中節點最多的狀態有D個節點，也就是說整個網格的寬度為D，那麼任何一步的複雜度不超過O(D2)，由於網格長度是N，所以整個維特比演算法的複雜度是O(N·D2)。三、HMM模型+維特比演算法實例1、問題描述假設連續觀察3天的海藻濕度為(Dry,Damp,Soggy),求這三天最可能的天氣情況。2、已知信息①天氣只有三類(Sunny,Cloudy,Rainy)，海藻濕度有四類{Dry,Dryish, Damp,Soggy }，而且海藻濕度和天氣有一定的關係。②隱藏的狀態：Sunny, Cloudy, Rainy;③觀察狀態序列：{Dry, Damp, Soggy}④初始狀態序列：SunnyCloudyRainy0.630.170.20⑤狀態轉移矩陣：SunnyCloudyRainySunny0.50.3750.125Cloudy0.250.1250.625Rainy0.250.3750.375⑥發射矩陣：DryDryishDampSoggySunny0.60.20.150.05Cloudy0.250.250.250.25Rainy0.050.100.350.53、分析由一階HMM可知，Day2的天氣僅取決於Day1；Day3的天氣又只取決於Day2的天氣。4、計算過程（1）Day1由於是初始狀態，我們分別求P(Day1-Sunny)=0.63*0.6;P(Day1-Cloudy)=0.17*0.25;P(Day1-Rain)=0.20*0.05;Choose max{ P(Day1-Sunny) , P(Day1-Cloudy),P(Day1-Rainy)}, 得到P(Day1-Sunny)最大，得出第1天Sunny的概率最大。（2）Day2的天氣又取決於Day1的天氣狀況，同時也受Day2觀察的海藻情況影響。P(Day2-Sunny)= max{ P(Day1-Sunny)*0.5, P(Day1-Cloudy)*0.25, P(Day1-Rainy)*0.25} *0.15;P(Day2-Cloudy)= max{ P(Day1-Sunny)*0.375, P(Day1-Cloudy)*0.125, P(Day1-Rainy)*0.625} *0.25;P(Day2-Rainy)= max{ P(Day1-Sunny)*0.125, P(Day1-Cloudy)*0.625 , P(Day1-Rainy)*0.375} *0.35;Choosemax{ P(Day2-Sunny) , P(Day2-Cloudy), P(Day2-Rainy)},得到P(Day2-Rainy)最大，得出第2天Rainy的概率最大。故{Sunny,Rainy}是前兩天最大可能的天氣序列。（3）Day3的天氣又取決於Day2的天氣狀況，同時也受Day3觀察的海藻情況影響。P(Day3-Sunny)= max{ P(Day2-Sunny)*0.5, P(Day2-Cloudy)*0.25, P(Day2-Rainy)*0.25} *0.05;P(Day3-Cloudy)= max{ P(Day2-Sunny)*0.375, P(Day2-Cloudy)*0.125, P(Day2-Rainy)*0.625} *0.25;P(Day3-Rainy)= max{ P(Day2-Sunny)*0.125, P(Day2-Cloudy)*0.625, P(Day2-Rainy)*0.375} *0. 05;Choosemax{ P(Day3-Sunny) , P(Day3-Cloudy), P(Day3-Rainy)},得到P(Day3-Rainy)最大，得出第3天Rainy的概率最大。故{Sunny,Rainy,Rainy}是這三天最可能的天氣序列。---轉載請註明出處------聯繫方式---