一、概述
計算機科學中所談的“模式”通常指按照一定順序發生的事件序列，比如機器翻譯和自然語言處理中的文字（詞）序列，程序設計中的指令序列，模式則體現了序列中事件的相關性。

舉一個簡單的例子，傳說可以通過觀察海草來預測天氣，比如濕潤（soggy）的海草意味著雨天（rainy），干燥（dry）的海草則意味著晴天（sunny）。可以再加入一個中間的狀態“潮濕（dump）”，同時引入陰天（cloudy）。當然，這種關系并不是永遠成立，因此他們之間存在著一個概率分布。

而預測天氣的另外一個線索是：先前的天氣，這很容易理解。那么，現在開始，我們將用這些已知條件來預測天氣。

首先，我們會引入一個通過上述的關系預測出天氣轉換模型。然后，我們將引入“隱”系統的概念，隱系統相對于觀察到的結果，在這個例子中，海草的干濕是觀察結果，而實際的天氣就是一個隱系統，因為我們看不到它。最后，我們會利用建立起來的整個系統模型去解決一些問題，比如通過海草來預測一周的天氣，甚至來判斷當時的季節（直覺上，夏天海草會干，而冬天會濕）。

二、轉換模型（Generateing Pattern，轉移網絡）

1）決定性的（Deterministic）

決定性的轉換模型，例如交通燈，紅－紅/黃－綠－黃（amber），狀態之間的轉換在滿足條件的狀態下只有一種可能性，顯然這不能應用在天氣的預測上。

2）非決定性的（Non-Deterministic）

在馬爾可夫假設（Markov Assumption）中，當前狀態只與前面的若干個狀態有關，這使得模型可以大大簡化。雖然這會導致預測的錯誤（顯然，在天氣的預測中，只考慮到前幾天是晴天還是雨天并不明智，還應當考慮氣流，氣壓，風速等等），但這種錯誤通常是可以接受的。

若馬爾可夫模型中，當前狀態只與前n個狀態有關，則稱之為n序模型（order n）。在本例中，假設當前天氣只與頭天天氣有關（n＝1），那么三種天氣狀態（M＝3）間存在3^2＝9種轉換。（表項的列和為1，是為了對應后面的條件概率計算）

?

Weather->	Sun	Cloud	Rain
Sun	0.5	0.25	0.25
Cloud	0.375	0.125	0.375
Rain	0.125	0.625	0.375

?

于是，我們有了一個簡單的一階馬爾可夫過程（first order Markov Process），它包括：

1）初始化向量（Π向量），代表系統的初始狀態

Sun	Cloud	Rain
1.0	0.0	0.0

2）狀態集：Sunny，Cloudy，Rainy

3）狀態轉移矩陣（表1）

三、隱模型（Hidden Patten）

通常，馬爾可夫過程是不夠的，因為它并沒有利用其他條件（如海草的干濕）。如果同時考慮海草的干濕，我們可以得到兩個狀態集，即觀察結果集（海草）和“隱”狀態集（天氣）。之后我們將利用這兩個狀態集，通過算法預測未來的天氣。

一個更實際的例子是語音識別，實際的語音序列是一系列隱狀態的組合，而系統識別出的語音序列則是觀察結果狀態。同時，觀察結果狀態的個數和隱狀態的個數不一定總相同，正如我們可以再給海草一個dryish狀態，而實際的80個語素對應的發音也很可能不止80個。

這種對應關系也是有一定概率的，為此，我們使用隱馬爾可夫模型來描述。

從上圖中可以看出，觀察狀態的變化之下隱藏著實際狀態的更改，而其中的概率關系可以用Pr(Obv|Weather)表示，其觀察狀態矩陣（confusion matrix）為：（我認為這個矩陣的值有問題，應當是列和為1，這樣更符合后面以觀察結果為依據計算天氣）

?	Dry	Dryish	Damp	Soggy
Sun	0.60	0.20	0.15	0.05
Cloud	0.25	0.25	0.25	0.25
Rain	0.05	0.10	0.35	0.50

可見，一個隱馬爾可夫模型由5部分組成：

?1）隱藏狀態；2）觀察狀態；3）Π向量；4）狀態轉移矩陣；5）狀態矩陣。

四、隱馬爾可夫模型（Hidden Markov Models）

隱馬爾可夫模型可以由一個三元組（Π，A，B）描述：

1）Π = (πi)是初始化向量；
2）A = (aij)是狀態轉移矩陣，元素為Pr(xj(t))|xi(t-1))，相當于頭天天氣xi，今天天氣是xj的概率；（這是一個條件概率，列和為1，因此以列（今天）為前置條件）
3）B = (bij)是觀察狀態矩陣，元素為Pr(yj|xi)，相當于海草狀態為yj時，天氣是xi時概率。

它主要有三個方面的用途：

1）評價（Evaluation），從多個隱馬爾可夫模型中選出一個最符合當前觀察結果的。比如海草與天氣的模型，在冬天和夏天應當是不同的。那么給出一個海草干濕狀態變化的序列，就可以評估出哪個模型更合適，同時也就可以推斷出這個序列出現在冬天還是夏天。

我們使用前向算法（Forward Algo）去計算一個序列在不同模型中的概率，從而取得最大可能的模型。語音識別中，同樣使用這種方法去計算一個發音在不同模型（每個模型針對不同的詞）中的概率，從而取得最大可能的詞。

2）解碼（Decoding），給定一個隱馬爾可夫模型和觀察結果序列，計算出可能性最大的隱狀態序列，也可以認為是預測。
我們使用維特比算法（Viterbi Algo）進行解碼計算，一個很大的用途就是自然語言處理中的詞性標注。這里，句子中的詞是觀察結果，而詞性則是隱狀態（因為一個詞可能對應多個詞性）。通過對整個句子（觀察結果序列）語法（隱狀態序列）的識別，就可以確定詞性。

3）學習（Learning），根據一系列的觀察結果構建隱馬爾可夫模型。
這也是最難的一種應用，我們使用前向-后向算法（Forward-Backward Algo）來進行計算。?

?

五、前向算法（Forward Algo）

評價（Evaluation）的基本方法就是計算隱馬爾可夫模型產生一個序列的概率（能力）。概率越大，這個序列就越可能是該隱馬爾可夫模型生成的。
比如我們給定一個海草變化的序列：dry，dump，soggy。在隱模型（狀態轉換模型）中，可能存在27（3^3）個對應的天氣變化序列，分別是sun，sun，sun；sun，cloud，sun；...；rain，rain，rain。
也就是說， Pr(dry,damp,soggy | HMM) = Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy | sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + . . . . Pr(dry,damp,soggy | rainy,rainy ,rainy)。
但是這個計算太復雜了，當序列長度增加時，運算復雜度呈指數增長。于是，我們要想辦法降低復雜度，可以考慮動態規劃的方法：
對于序列中的第 i 項，對應 3 種狀態（sun，cloud，rain）。

分別求出到達每種狀態的概率，于是

pr(dry, damp, soggy | HMM) = Pr(x, y, sun) + Pr(x, y, cloud) + Pr(x, y, rain)，Pr(x, y, sun)

???????????????????????????????????????? = Pr(x, sun, sun) + Pr(x, cloud, sun) + Pr(x, rain, sun)

?????????????????????????????????????????= Pr(x, sun) * Pr(sun, sun) + Pr(x, cloud) * Pr(cloud, sun) + Pr(x, rain) * Pr(rain, sun)。???? 注意，Pr(x, sun)在計算Pr(x, y, sun)，Pr(x, y, cloud)和Pr(x, y, rain)中都會用到，這樣就通過填表的方式降低了運算復雜度，計算量約為 k*n^2 ，k 為序列長度，n 為狀態個數。
對于每個時間 t 下的每個狀態 j ，公式為：x( t )( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)。需要說明的時，t = 1 時，Pr 為初始化向量對應的值。也可以描述為：x(t+1)(j) = b(j)(k(t+1)) * (Σx(t)(i)*a(i)(j))，k 為觀察狀態序列，t 為序列中的位置，i 從 1 到 n。
而總的概率為：Pr = Σx(T)(j)，j 從 1 到 n 。
原文給出了Π = <0.63, 0.17, 0.20>時的模擬計算（一個Java Applet），A和B矩陣則都已經在前文中給出。ttp://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg1.html

?

?六、維特比算法（Viterbi Algo）
解碼（Decoding）是指：給定一個隱馬爾可夫模型（HMM）和觀察序列，求得可能性最大（見下文說明）的狀態序列。其經典算法是維特比算法。
同樣，對于這樣一個海草變化的序列：dry，dump，soggy。在隱模型（狀態轉換模型）中，可能存在27（3^3）個對應的天氣變化序列，分別是sun，sun，sun；sun，cloud，sun；...；rain，rain，rain。
也就是求出Max( Pr(dry,damp,soggy | sunny,sunny,sunny), Pr(dry,damp,soggy | sunny,sunny,cloudy), Pr(dry,damp,soggy | sunny,sunny,rainy), . . . . , Pr(dry,damp,soggy | rainy,rainy,rainy))，這同樣是一個很復雜的計算過程。
維特比算法的思想在于動態規劃和剪枝：對于每個時間 t 下的狀態 i ，只保留概率最大的一枝：Pr(i at time t) = Max(Pr(j at time(t-1)) * Pr(i|j) * Pr(obv. at time t|i)，同時，記錄這個最大值對應的 x(i) = j （填表），再通過 n 個這樣的最大值計算 t+1 時的最大值。當 t = 1 時，Pr(i) = Max(Pr(obv. | i) * Π(i))。其復雜度和前向算法相同，都是 k*n^2。
說明，維特比算法是填一個 n*k 大小的表，每個表項由兩部分組成，第一部分為 t 時刻到達 i 狀態的概率 Pr ，另一部分為產生該概率的前序狀態 j 。
這樣，從Max(Pr(i at time T))求得產生該觀察序列的最大可能的狀態序列的最后一個狀態 i(T) ，再從這個狀態 i(T) 開始，在表中向前回溯，i(t-1) = x(i(t))，即可求得完整的序列。
維特比算法的優勢在于不僅僅考察前后兩個觀察狀態的關系，而是全面考察整個觀察序列，得出一個“最大似然”的結果。這在語音識別，通信領域有著巨大的意義——即使序列中有一兩個誤碼，還是能夠根據整個序列給出正確的解碼。
原文給出的模擬計算有問題，因此不再給出鏈接。

七、前向-后向算法（Forward-Backward Algo）
前向算法和維特比算法都是基于隱馬爾可夫模型的應用，前提是隱馬爾可夫模型已知。但是，在很多情況下，模型是未知的，這就是學習（Learning）問題。前項后向算法通過分析由觀察狀態集中的狀態組成的一系列的觀察序列和隱狀態集，給出隱馬爾可夫模型。
比如語音識別中，通常需要針對某個人的聲音進行訓練，才能更好地識別出這個人說的話。
但是，到目前為止，學習問題還沒有解析解法。傳統的方法是先給出一組初始化參數（也許完全是錯誤的），然后使用觀察序列進行訓練——修正其中的錯誤，或使錯誤最小化。
在前向-后向算法中，同樣要先給出一組初始化參數，其基本原理是同時計算達到某個狀態的概率（前向）和由這個狀態到終止狀態的概率（后向），并以此為依據對參數進行調整。

八、總結（Summary）
通常，模式不會孤立的存在，它往往以時間或空間為順序，和它前面或后面的模式相關。因此，可以利用模式間的關系進行模式識別。
我們假設模式間的關系不隨時間/空間的變化而變化，并假設第 n 個模式只與它前面的 k 個模式有關（最簡單的是 k=1 ），這就構成了 k 階馬爾可夫過程。
又，模式并不一定存在于表面，它很有可能存在于某種現象之下，但現象和模式間存在某種聯系，這就構成了隱馬爾可夫模型。
隱馬爾可夫模型主要解決三方面的問題：
1）給定觀察序列和模型，求該模型生成該觀察序列的概率：評估（Evaluation）;
2）給定觀察序列和模型，求該模型下最可能生成該觀察序列的狀態序列：解碼（Decoding）；
3）給定觀察狀態集和隱狀態集，以及若干觀察序列，求模型：學習（Learning）。

總結

以上是生活随笔為你收集整理的隐马尔可夫(HMM)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。