分類(lèi) 隱馬爾科夫模型
隱馬爾科夫模型（HMM）依然是讀者訪(fǎng)問(wèn)“我愛(ài)自然語(yǔ)言處理”的一個(gè)熱門(mén)相關(guān)關(guān)鍵詞，我曾在《HMM學(xué)習最佳范例與崔曉源的博客》中介紹過(guò)國外的一個(gè)不錯的HMM學(xué)習教程，并且國內崔曉源師兄有一個(gè)相應的翻譯版本，不過(guò)這個(gè)版本比較簡(jiǎn)化和粗略，有些地方只是概況性的翻譯了一下，省去了一些內容，所以從今天開(kāi)始計劃在52nlp上系統的重新翻譯這個(gè)學(xué)習教程，希望對大家有點(diǎn)用。
一、介紹（Introduction）
我們通常都習慣尋找一個(gè)事物在一段時(shí)間里的變化模式（規律）。這些模式發(fā)生在很多領(lǐng)域，比如計算機中的指令序列，句子中的詞語(yǔ)順序和口語(yǔ)單詞中的音素序列等等，事實(shí)上任何領(lǐng)域中的一系列事件都有可能產(chǎn)生有用的模式。
考慮一個(gè)簡(jiǎn)單的例子，有人試圖通過(guò)一片海藻推斷天氣——民間傳說(shuō)告訴我們‘濕透的’海藻意味著(zhù)潮濕陰雨，而‘干燥的’海藻則意味著(zhù)陽(yáng)光燦爛。如果它處 于一個(gè)中間狀態(tài)（‘有濕氣’），我們就無(wú)法確定天氣如何。然而，天氣的狀態(tài)并沒(méi)有受限于海藻的狀態(tài)，所以我們可以在觀(guān)察的基礎上預測天氣是雨天或晴天的可 能性。另一個(gè)有用的線(xiàn)索是前一天的天氣狀態(tài)（或者，至少是它的可能狀態(tài)）——通過(guò)綜合昨天的天氣及相應觀(guān)察到的海藻狀態(tài)，我們有可能更好的預測今天的天 氣。
這是本教程中我們將考慮的一個(gè)典型的系統類(lèi)型。
首先，我們將介紹產(chǎn)生概率模式的系統，如晴天及雨天間的天氣波動(dòng)。
然后，我們將會(huì )看到這樣一個(gè)系統，我們希望預測的狀態(tài)并不是觀(guān)察到的——其底層系統是隱藏的。在上面的例子中，觀(guān)察到的序列將是海藻而隱藏的系統將是實(shí)際的天氣。
最后，我們會(huì )利用已經(jīng)建立的模型解決一些實(shí)際的問(wèn)題。對于上述例子，我們想知道：
1. 給出一個(gè)星期每天的海藻觀(guān)察狀態(tài)，之后的天氣將會(huì )是什么?
2. 給定一個(gè)海藻的觀(guān)察狀態(tài)序列，預測一下此時(shí)是冬季還是夏季？直觀(guān)地，如果一段時(shí)間內海藻都是干燥的，那么這段時(shí)間很可能是夏季，反之，如果一段時(shí)間內海藻都是潮濕的，那么這段時(shí)間可能是冬季。
分類(lèi) 隱馬爾科夫模型
二、生成模式（Generating Patterns）
1、確定性模式（Deterministic Patterns）
考慮一套交通信號燈，燈的顏色變化序列依次是紅色-紅色/黃色-綠色-黃色-紅色。這個(gè)序列可以作為一個(gè)狀態(tài)機器，交通信號燈的不同狀態(tài)都緊跟著(zhù)上一個(gè)狀態(tài)。
注意每一個(gè)狀態(tài)都是唯一的依賴(lài)于前一個(gè)狀態(tài)，所以，如果交通燈為綠色，那么下一個(gè)顏色狀態(tài)將始終是黃色——也就是說(shuō)，該系統是確定性的。確定性系統相對比較容易理解和分析，因為狀態(tài)間的轉移是完全已知的。
2、非確定性模式（Non-deterministic patterns）
為了使天氣那個(gè)例子更符合實(shí)際，加入第三個(gè)狀態(tài)——多云。與交通信號燈例子不同，我們并不期望這三個(gè)天氣狀態(tài)之間的變化是確定性的，但是我們依然希望對這個(gè)系統建模以便生成一個(gè)天氣變化模式（規律）。
一種做法是假設模型的當前狀態(tài)僅僅依賴(lài)于前面的幾個(gè)狀態(tài)，這被稱(chēng)為馬爾科夫假設，它極大地簡(jiǎn)化了問(wèn)題。顯然，這可能是一種粗糙的假設，并且因此可能將一些非常重要的信息丟失。
當考慮天氣問(wèn)題時(shí)，馬爾科夫假設假定今天的天氣只能通過(guò)過(guò)去幾天已知的天氣情況進(jìn)行預測——而對于其他因素，譬如風(fēng)力、氣壓等則沒(méi)有考慮。在這個(gè)例子以及其他相似的例子中，這樣的假設顯然是不現實(shí)的。然而，由于這樣經(jīng)過(guò)簡(jiǎn)化的系統可以用來(lái)分析，我們常常接受這樣的知識假設，雖然它產(chǎn)生的某些信息不完全 準確。
一個(gè)馬爾科夫過(guò)程是狀態(tài)間的轉移僅依賴(lài)于前n個(gè)狀態(tài)的過(guò)程。這個(gè)過(guò)程被稱(chēng)之為n階馬爾科夫模型，其中n是影響下一個(gè)狀態(tài)選擇的（前）n個(gè)狀態(tài)。最簡(jiǎn)單 的馬爾科夫過(guò)程是一階模型，它的狀態(tài)選擇僅與前一個(gè)狀態(tài)有關(guān)。這里要注意它與確定性系統并不相同，因為下一個(gè)狀態(tài)的選擇由相應的概率決定，并不是確定性的。
下圖是天氣例子中狀態(tài)間所有可能的一階狀態(tài)轉移情況：
對于有M個(gè)狀態(tài)的一階馬爾科夫模型，共有
下面的狀態(tài)轉移矩陣顯示的是天氣例子中可能的狀態(tài)轉移概率：
-也就是說(shuō)，如果昨天是晴天，那么今天是晴天的概率為0.5，是多云的概率為0.375。注意，每一行的概率之和為1。
要初始化這樣一個(gè)系統，我們需要確定起始日天氣的（或可能的）情況，定義其為一個(gè)初始概率向量，稱(chēng)為
-也就是說(shuō)，第一天為晴天的概率為1。
現在我們定義一個(gè)一階馬爾科夫過(guò)程如下：
狀態(tài)：三個(gè)狀態(tài)——晴天，多云，雨天。
狀態(tài)轉移矩陣：給定前一天天氣情況下的當前天氣概率。
任何一個(gè)可以用這種方式描述的系統都是一個(gè)馬爾科夫過(guò)程。
3、總結
我們嘗試識別時(shí)間變化中的模式，并且為了達到這個(gè)目我們試圖對這個(gè)過(guò)程建模以便產(chǎn)生這樣的模式。我們使用了離散時(shí)間點(diǎn)、離散狀態(tài)以及做了馬爾科夫假設。在采用了這些假設之后，系統產(chǎn)生了這個(gè)被描述為馬爾科夫過(guò)程的模式，它包含了一個(gè)
分類(lèi) 隱馬爾科夫模型
三、隱藏模式（Hidden Patterns）
1、馬爾科夫過(guò)程的局限性
在某些情況下，我們希望找到的模式用馬爾科夫過(guò)程描述還顯得不充分?；仡櫼幌绿鞖饽莻€(gè)例子，一個(gè)隱士也許不能夠直接獲取到天氣的觀(guān)察情況，但是他有一些水藻。民間傳說(shuō)告訴我們水藻的狀態(tài)與天氣狀態(tài)有一定的概率關(guān)系——天氣和水藻的狀態(tài)是緊密相關(guān)的。在這個(gè)例子中我們有兩組狀態(tài)，觀(guān)察的狀態(tài)（水藻的狀態(tài)）和隱藏的狀態(tài)（天氣的狀態(tài)）。我們希望為隱士設計一種算法，在不能夠直接觀(guān)察天氣的情況下，通過(guò)水藻和馬爾科夫假設來(lái)預測天氣。
一個(gè)更實(shí)際的問(wèn)題是語(yǔ)音識別，我們聽(tīng)到的聲音是來(lái)自于聲帶、喉嚨大小、舌頭位置以及其他一些東西的組合結果。所有這些因素相互作用產(chǎn)生一個(gè)單詞的聲音，一套語(yǔ)音識別系統檢測的聲音就是來(lái)自于個(gè)人發(fā)音時(shí)身體內部物理變化所引起的不斷改變的聲音。
一些語(yǔ)音識別裝置工作的原理是將內部的語(yǔ)音產(chǎn)出看作是隱藏的狀態(tài)，而將聲音結果作為一系列觀(guān)察的狀態(tài)，這些由語(yǔ)音過(guò)程生成并且最好的近似了實(shí)際（隱 藏）的狀態(tài)。在這兩個(gè)例子中，需要著(zhù)重指出的是，隱藏狀態(tài)的數目與觀(guān)察狀態(tài)的數目可以是不同的。一個(gè)包含三個(gè)狀態(tài)的天氣系統（晴天、多云、雨天）中，可以觀(guān)察到4個(gè)等級的海藻濕潤情況（干、稍干、潮濕、濕潤）；純粹的語(yǔ)音可以由80個(gè)音素描述，而身體的發(fā)音系統會(huì )產(chǎn)生出不同數目的聲音，或者比80多，或者 比80少。
在這種情況下，觀(guān)察到的狀態(tài)序列與隱藏過(guò)程有一定的概率關(guān)系。我們使用隱馬爾科夫模型對這樣的過(guò)程建模，這個(gè)模型包含了一個(gè)底層隱藏的隨時(shí)間改變的馬爾科夫過(guò)程，以及一個(gè)與隱藏狀態(tài)某種程度相關(guān)的可觀(guān)察到的狀態(tài)集合。
2、隱馬爾科夫模型（Hidden Markov Models）
下圖顯示的是天氣例子中的隱藏狀態(tài)和觀(guān)察狀態(tài)。假設隱藏狀態(tài)（實(shí)際的天氣）由一個(gè)簡(jiǎn)單的一階馬爾科夫過(guò)程描述，那么它們之間都相互連接。
隱藏狀態(tài)和觀(guān)察狀態(tài)之間的連接表示：在給定的馬爾科夫過(guò)程中，一個(gè)特定的隱藏狀態(tài)生成特定的觀(guān)察狀態(tài)的概率。這很清晰的表示了‘進(jìn)入’一個(gè)觀(guān)察狀態(tài)的 所有概率之和為1，在上面這個(gè)例子中就是Pr(Obs|Sun), Pr(Obs|Cloud) 及 Pr(Obs|Rain)之和。（對這句話(huà)我有點(diǎn)疑惑？）
除了定義了馬爾科夫過(guò)程的概率關(guān)系，我們還有另一個(gè)矩陣，定義為混淆矩陣（confusion matrix），它包含了給定一個(gè)隱藏狀態(tài)后得到的觀(guān)察狀態(tài)的概率。對于天氣例子，混淆矩陣是：
注意矩陣的每一行之和是1。
3、總結（Summary）
我們已經(jīng)看到在一些過(guò)程中一個(gè)觀(guān)察序列與一個(gè)底層馬爾科夫過(guò)程是概率相關(guān)的。在這些例子中，觀(guān)察狀態(tài)的數目可以和隱藏狀態(tài)的數碼不同。
我們使用一個(gè)隱馬爾科夫模型（HMM）對這些例子建模。這個(gè)模型包含兩組狀態(tài)集合和三組概率集合：
* 隱藏狀態(tài)：一個(gè)系統的（真實(shí)）狀態(tài)，可以由一個(gè)馬爾科夫過(guò)程進(jìn)行描述（例如，天氣）。
* 觀(guān)察狀態(tài)：在這個(gè)過(guò)程中‘可視’的狀態(tài)（例如，海藻的濕度）。
*
* 狀態(tài)轉移矩陣：包含了一個(gè)隱藏狀態(tài)到另一個(gè)隱藏狀態(tài)的概率
* 混淆矩陣：包含了給定隱馬爾科夫模型的某一個(gè)特殊的隱藏狀態(tài)，觀(guān)察到的某個(gè)觀(guān)察狀態(tài)的概率。
因此一個(gè)隱馬爾科夫模型是在一個(gè)標準的馬爾科夫過(guò)程中引入一組觀(guān)察狀態(tài)，以及其與隱藏狀態(tài)間的一些概率關(guān)系。
分類(lèi) 隱馬爾科夫模型
四、隱馬爾科夫模型（Hidden Markov Models）
1、定義（Definition of a hidden Markov model）
一個(gè)隱馬爾科夫模型是一個(gè)三元組（
在狀態(tài)轉移矩陣及混淆矩陣中的每一個(gè)概率都是時(shí)間無(wú)關(guān)的——也就是說(shuō)，當系統演化時(shí)這些矩陣并不隨時(shí)間改變。實(shí)際上，這是馬爾科夫模型關(guān)于真實(shí)世界最不現實(shí)的一個(gè)假設。
2、應用（Uses associated with HMMs）
一旦一個(gè)系統可以作為HMM被描述，就可以用來(lái)解決三個(gè)基本問(wèn)題。其中前兩個(gè)是模式識別的問(wèn)題：給定HMM求一個(gè)觀(guān)察序列的概率（評估）；搜索最有可能生成一個(gè)觀(guān)察序列的隱藏狀態(tài)訓練（解碼）。第三個(gè)問(wèn)題是給定觀(guān)察序列生成一個(gè)HMM（學(xué)習）。
a) 評估（Evaluation）
考慮這樣的問(wèn)題，我們有一些描述不同系統的隱馬爾科夫模型（也就是一些(
我們使用前向算法（forward algorithm）來(lái)計算給定隱馬爾科夫模型（HMM）后的一個(gè)觀(guān)察序列的概率，并因此選擇最合適的隱馬爾科夫模型(HMM)。
在語(yǔ)音識別中這種類(lèi)型的問(wèn)題發(fā)生在當一大堆數目的馬爾科夫模型被使用，并且每一個(gè)模型都對一個(gè)特殊的單詞進(jìn)行建模時(shí)。一個(gè)觀(guān)察序列從一個(gè)發(fā)音單詞中形成，并且通過(guò)尋找對于此觀(guān)察序列最有可能的隱馬爾科夫模型（HMM）識別這個(gè)單詞。
b) 解碼（ Decoding）
給定觀(guān)察序列搜索最可能的隱藏狀態(tài)序列。
另一個(gè)相關(guān)問(wèn)題，也是最感興趣的一個(gè)，就是搜索生成輸出序列的隱藏狀態(tài)序列。在許多情況下我們對于模型中的隱藏狀態(tài)更感興趣，因為它們代表了一些更有價(jià)值的東西，而這些東西通常不能直接觀(guān)察到。
考慮海藻和天氣這個(gè)例子，一個(gè)盲人隱士只能感覺(jué)到海藻的狀態(tài)，但是他更想知道天氣的情況，天氣狀態(tài)在這里就是隱藏狀態(tài)。
我們使用Viterbi 算法（Viterbi algorithm）確定（搜索）已知觀(guān)察序列及HMM下最可能的隱藏狀態(tài)序列。
Viterbi算法（Viterbi algorithm）的另一廣泛應用是自然語(yǔ)言處理中的詞性標注。在詞性標注中，句子中的單詞是觀(guān)察狀態(tài)，詞性（語(yǔ)法類(lèi)別）是隱藏狀態(tài)（注意對于許多單詞，如wind，fish擁有不止一個(gè)詞性）。對于每句話(huà)中的單詞，通過(guò)搜索其最可能的隱藏狀態(tài)，我們就可以在給定的上下文中找到每個(gè)單詞最可能的詞性標注。
C）學(xué)習（Learning）
根據觀(guān)察序列生成隱馬爾科夫模型。
第三個(gè)問(wèn)題，也是與HMM相關(guān)的問(wèn)題中最難的，根據一個(gè)觀(guān)察序列（來(lái)自于已知的集合），以及與其有關(guān)的一個(gè)隱藏狀態(tài)集，估計一個(gè)最合適的隱馬爾科夫模型（HMM），也就是確定對已知序列描述的最合適的（
當矩陣A和B不能夠直接被（估計）測量時(shí)，前向-后向算法（forward-backward algorithm）被用來(lái)進(jìn)行學(xué)習（參數估計），這也是實(shí)際應用中常見(jiàn)的情況。
3、總結（Summary）
由一個(gè)向量和兩個(gè)矩陣(
1. 對于一個(gè)觀(guān)察序列匹配最可能的系統——評估，使用前向算法（forward algorithm）解決；
2. 對于已生成的一個(gè)觀(guān)察序列，確定最可能的隱藏狀態(tài)序列——解碼，使用Viterbi 算法（Viterbi algorithm）解決；
3. 對于已生成的觀(guān)察序列，決定最可能的模型參數——學(xué)習，使用前向-后向算法（forward-backward algorithm）解決。
分類(lèi) 隱馬爾科夫模型
五、前向算法（Forward Algorithm）
計算觀(guān)察序列的概率（Finding the probability of an observed sequence）
1.窮舉搜索（ Exhaustive search for solution）
給定隱馬爾科夫模型，也就是在模型參數（
網(wǎng)格中的每一列都顯示了可能的的天氣狀態(tài)，并且每一列中的每個(gè)狀態(tài)都與相鄰列中的每一個(gè)狀態(tài)相連。而其狀態(tài)間的轉移都由狀態(tài)轉移矩陣提供一個(gè)概率。在每一列下面都是某個(gè)時(shí)間點(diǎn)上的觀(guān)察狀態(tài)，給定任一個(gè)隱藏狀態(tài)所得到的觀(guān)察狀態(tài)的概率由混淆矩陣提供。
可以看出，一種計算觀(guān)察序列概率的方法是找到每一個(gè)可能的隱藏狀態(tài)，并且將這些隱藏狀態(tài)下的觀(guān)察序列概率相加。對于上面那個(gè)（天氣）例子，將有3^3 = 27種不同的天氣序列可能性，因此，觀(guān)察序列的概率是：
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)
用這種方式計算觀(guān)察序列概率極為昂貴，特別對于大的模型或較長(cháng)的序列，因此我們可以利用這些概率的時(shí)間不變性來(lái)減少問(wèn)題的復雜度。
2.使用遞歸降低問(wèn)題復雜度
給定一個(gè)隱馬爾科夫模型（HMM），我們將考慮遞歸地計算一個(gè)觀(guān)察序列的概率。我們首先定義局部概率（partial probability）,它是到達網(wǎng)格中的某個(gè)中間狀態(tài)時(shí)的概率。然后，我們將介紹如何在t=1和t=n(>1)時(shí)計算這些局部概率。
假設一個(gè)T-長(cháng)觀(guān)察序列是：
考慮下面這個(gè)網(wǎng)格，它顯示的是天氣狀態(tài)及對于觀(guān)察序列干燥，濕潤及濕透的一階狀態(tài)轉移情況：
我們可以將計算到達網(wǎng)格中某個(gè)中間狀態(tài)的概率作為所有到達這個(gè)狀態(tài)的可能路徑的概率求和問(wèn)題。
例如，t=2時(shí)位于“多云”狀態(tài)的局部概率通過(guò)如下路徑計算得出：
我們定義t時(shí)刻位于狀態(tài)j的局部概率為at(j)——這個(gè)局部概率計算如下：
對于最后的觀(guān)察狀態(tài)，其局部概率包括了通過(guò)所有可能的路徑到達這些狀態(tài)的概率——例如，對于上述網(wǎng)格，最終的局部概率通過(guò)如下路徑計算得出：
由此可見(jiàn)，對于這些最終局部概率求和等價(jià)于對于網(wǎng)格中所有可能的路徑概率求和，也就求出了給定隱馬爾科夫模型(HMM)后的觀(guān)察序列概率。
第3節給出了一個(gè)計算這些概率的動(dòng)態(tài)示例。
分類(lèi) 隱馬爾科夫模型
五、前向算法（Forward Algorithm）
計算觀(guān)察序列的概率（Finding the probability of an observed sequence）
2b.計算t=1時(shí)的局部概率
我們按如下公式計算局部概率：
特別當t=1時(shí)，沒(méi)有任何指向當前狀態(tài)的路徑。故t=1時(shí)位于當前狀態(tài)的概率是初始概率，即Pr(state|t=1)=P(state)，因此，t=1時(shí)的局部概率等于當前狀態(tài)的初始概率乘以相關(guān)的觀(guān)察概率：
所以初始時(shí)刻狀態(tài)j的局部概率依賴(lài)于此狀態(tài)的初始概率及相應時(shí)刻我們所見(jiàn)的觀(guān)察概率。
我們再次回顧局部概率的計算公式如下：
我們可以假設（遞歸地），乘號左邊項“Pr( 觀(guān)察狀態(tài) | 隱藏狀態(tài)j )”已經(jīng)有了，現在考慮其右邊項“Pr(t時(shí)刻所有指向j狀態(tài)的路徑）”。
為了計算到達某個(gè)狀態(tài)的所有路徑的概率，我們可以計算到達此狀態(tài)的每條路徑的概率并對它們求和，例如：
計算
故我們所計算的這個(gè)概率等于相應的觀(guān)察概率（亦即，t+1時(shí)在狀態(tài)j所觀(guān)察到的符號的概率）與該時(shí)刻到達此狀態(tài)的概率總和——這來(lái)自于上一步每一個(gè)局部概率的計算結果與相應的狀態(tài)轉移概率乘積后再相加——的乘積。
注意我們已經(jīng)有了一個(gè)僅利用t時(shí)刻局部概率計算t+1時(shí)刻局部概率的表達式。
現在我們就可以遞歸地計算給定隱馬爾科夫模型(HMM)后一個(gè)觀(guān)察序列的概率了——即通過(guò)t=1時(shí)刻的局部概率
2d.降低計算復雜度
我們可以比較通過(guò)窮舉搜索（評估）和通過(guò)遞歸前向算法計算觀(guān)察序列概率的時(shí)間復雜度。
我們有一個(gè)長(cháng)度為T的觀(guān)察序列O以及一個(gè)含有n個(gè)隱藏狀態(tài)的隱馬爾科夫模型l=(
窮舉搜索將包括計算所有可能的序列：
公式
對我們所觀(guān)察到的概率求和——注意其復雜度與T成指數級關(guān)系。相反的，使用前向算法我們可以利用上一步計算的信息，相應地，其時(shí)間復雜度與T成線(xiàn)性關(guān)系。
注：窮舉搜索的時(shí)間復雜度是
3.總結
我們的目標是計算給定隱馬爾科夫模型HMM下的觀(guān)察序列的概率——Pr(observations |
我們首先通過(guò)計算局部概率（
t=1時(shí)，可以利用初始概率(來(lái)自于P向量）和觀(guān)察概率Pr(observation|state)（來(lái)自于混淆矩陣）計算局部概率；而t>1時(shí)的局部概率可以利用t-時(shí)的局部概率計算。
因此，這個(gè)問(wèn)題是遞歸定義的，觀(guān)察序列的概率就是通過(guò)依次計算t=1,2,…,T時(shí)的局部概率，并且對于t=T時(shí)所有局部概率
注意，用這種方式計算觀(guān)察序列概率的時(shí)間復雜度遠遠小于計算所有序列的概率并對其相加（窮舉搜索）的時(shí)間復雜度。
分類(lèi) 隱馬爾科夫模型
五、前向算法（Forward Algorithm）
前向算法定義（Forward algorithm definition）
我們使用前向算法計算T長(cháng)觀(guān)察序列的概率:
其中y的每一個(gè)是觀(guān)察集合之一。局部（中間）概率(
然后在每個(gè)時(shí)間點(diǎn)，t=2，… ，T時(shí)，對于每個(gè)狀態(tài)的局部概率，由下式計算局部概率
也就是當前狀態(tài)相應的觀(guān)察概率與所有到達該狀態(tài)的路徑概率之積，其遞歸地利用了上一個(gè)時(shí)間點(diǎn)已經(jīng)計算好的一些值。
最后，給定HMM,
再重復說(shuō)明一下，每一個(gè)局部概率（t > 2 時(shí)）都由前一時(shí)刻的結果計算得出。
對于“天氣”那個(gè)例子，下面的圖表顯示了t = 2為狀態(tài)為多云時(shí)局部概率
總結（Summary）
我們使用前向算法來(lái)計算給定隱馬爾科夫模型（HMM）后的一個(gè)觀(guān)察序列的概率。它在計算中利用遞歸避免對網(wǎng)格所有路徑進(jìn)行窮舉計算。
給定這種算法，可以直接用來(lái)確定對于已知的一個(gè)觀(guān)察序列，在一些隱馬爾科夫模型（HMMs）中哪一個(gè)HMM最好的描述了它——先用前向算法評估每一個(gè)（HMM），再選取其中概率最高的一個(gè)。
分類(lèi) 隱馬爾科夫模型
首先需要說(shuō)明的是，本節不是這個(gè)系列的翻譯，而是作為前向算法這一章的補充，希望能從實(shí)踐的角度來(lái)說(shuō)明前向算法。除了用程序來(lái)解讀hmm的前向算法外，還希望將原文所舉例子的問(wèn)題拿出來(lái)和大家探討。
文中所舉的程序來(lái)自于UMDHMM這個(gè)C語(yǔ)言版本的HMM工具包，具體見(jiàn)《幾種不同程序語(yǔ)言的HMM版本》。先說(shuō)明一下UMDHMM這個(gè)包的基本情況，在linux環(huán)境下，進(jìn)入umdhmm-v1.02目錄，“make all”之后會(huì )產(chǎn)生4個(gè)可執行文件，分別是：
genseq: 利用一個(gè)給定的隱馬爾科夫模型產(chǎn)生一個(gè)符號序列（Generates a symbol sequence using the specified model sequence using the specified model）
testfor: 利用前向算法計算log Prob(觀(guān)察序列| HMM模型)（Computes log Prob(observation|model) using the Forward algorithm.）
testvit: 對于給定的觀(guān)察符號序列及HMM，利用Viterbi 算法生成最可能的隱藏狀態(tài)序列（Generates the most like state sequence for a given symbol sequence, given the HMM, using Viterbi）
esthmm: 對于給定的觀(guān)察符號序列，利用BaumWelch算法學(xué)習隱馬爾科夫模型HMM（Estimates the HMM from a given symbol sequence using BaumWelch）。
這些可執行文件需要讀入有固定格式的HMM文件及觀(guān)察符號序列文件，格式要求及舉例如下：
HMM 文件格式：
——————————————————————–
M= number of symbols
N= number of states
A:
a
a
. . . .
. . . .
. . . .
aN1 aN2 … aNN
B:
b11 b12 … b
b21 b22 … b
. . . .
. . . .
. . . .
bN1 bN2 … bNM
pi:
pi1 pi2 … piN
——————————————————————–
HMM文件舉例：
——————————————————————–
M= 2
N= 3
A:
0.333 0.333 0.333
0.333 0.333 0.333
0.333 0.333 0.333
B:
0.5 0.5
0.75 0.25
0.25 0.75
pi:
0.333 0.333 0.333
——————————————————————–
觀(guān)察序列文件格式：
——————————————————————–
T=seqence length
o1 o2 o3 . . . oT
——————————————————————–
觀(guān)察序列文件舉例：
——————————————————————–
T= 10
1 1 1 1 2 1 2 2 2 2
——————————————————————–
對于前向算法的測試程序testfor來(lái)說(shuō)，運行：
testfor model.hmm（HMM文件） obs.seq（觀(guān)察序列文件）
就可以得到觀(guān)察序列的概率結果的對數值，這里我們在testfor.c的第58行對數結果的輸出下再加一行輸出：
fprintf(stdout, “prob(O| model) = %fn”, proba);
就可以輸出運用前向算法計算觀(guān)察序列所得到的概率值。至此，所有的準備工作已結束，接下來(lái)，我們將進(jìn)入具體的程序解讀。
首先，需要定義HMM的數據結構，也就是HMM的五個(gè)基本要素，在UMDHMM中是如下定義的（在hmm.h中）：
typedef struct
{
int N; /* 隱藏狀態(tài)數目;Q={1,2,…,N} */
int M; /* 觀(guān)察符號數目; V={1,2,…,M}*/
double **A; /* 狀態(tài)轉移矩陣A[1..N][1..N]. a[i][j] 是從t時(shí)刻狀態(tài)i到t+1時(shí)刻狀態(tài)j的轉移概率 */
double **B; /* 混淆矩陣B[1..N][1..M]. b[j][k]在狀態(tài)j時(shí)觀(guān)察到符合k的概率。*/
double *pi; /* 初始向量pi[1..N]，pi[i] 是初始狀態(tài)概率分布 */
} HMM;
前向算法程序示例如下（在forward.c中）：
/*
函數參數說(shuō)明：
*phmm：已知的HMM模型；T：觀(guān)察符號序列長(cháng)度；
*O：觀(guān)察序列；**alpha：局部概率；*pprob：最終的觀(guān)察概率
*/
void Forward(HMM *phmm, int T, int *O, double **alpha, double *pprob)
{
int i, j; /* 狀態(tài)索引 */
int t; /* 時(shí)間索引 */
double sum; /*求局部概率時(shí)的中間值 */
/* 1. 初始化：計算t=1時(shí)刻所有狀態(tài)的局部概率
for (i = 1; i <= phmm->N; i++)
alpha[1][i] = phmm->pi[i]* phmm->B[i][O[1]];
/* 2. 歸納：遞歸計算每個(gè)時(shí)間點(diǎn)，t=2，… ，T時(shí)的局部概率 */
for (t = 1; t < T; t++)
{
for (j = 1; j <= phmm->N; j++)
{
sum = 0.0;
for (i = 1; i <= phmm->N; i++)
sum += alpha[t][i]* (phmm->A[i][j]);
alpha[t+1][j] = sum*(phmm->B[j][O[t+1]]);
}
}
/* 3. 終止：觀(guān)察序列的概率等于T時(shí)刻所有局部概率之和*/
*pprob = 0.0;
for (i = 1; i <= phmm->N; i++)
*pprob += alpha[T][i];
}
下一節我將用這個(gè)程序來(lái)驗證英文原文中所舉前向算法演示例子的問(wèn)題。
分類(lèi) 隱馬爾科夫模型
在HMM這個(gè)翻譯系列的原文中，作者舉了一個(gè)前向算法的交互例子，這也是這個(gè)系列中比較出彩的地方，但是，在具體運行這個(gè)例子的時(shí)候，卻發(fā)現其似乎有點(diǎn)問(wèn)題。
先說(shuō)一下如何使用這個(gè)交互例子，運行時(shí)需要瀏覽器支持java，我用的是firefox。首先在Set按鈕前面的對話(huà)框里上觀(guān)察序列，如“Dry,Damp, Soggy” 或“Dry Damp Soggy”，觀(guān)察符號間用逗號或空格隔開(kāi)；然后再點(diǎn)擊Set按鈕，這樣就初始化了觀(guān)察矩陣；如果想得到一個(gè)總的結果，即Pr(觀(guān)察序列|隱馬爾科夫模 型)，就點(diǎn)旁邊的Run按鈕；如果想一步一步觀(guān)察計算過(guò)程，即每個(gè)節點(diǎn)的局部概率，就單擊旁邊的Step按鈕。
原文交互例子（即天氣這個(gè)例子）中所定義的已知隱馬爾科夫模型如下：
1、隱藏狀態(tài) (天氣)：Sunny，Cloudy，Rainy；
2、觀(guān)察狀態(tài)（海藻濕度）：Dry，Dryish，Damp，Soggy；
3、初始狀態(tài)概率： Sunny（0.63）， Cloudy（0.17）， Rainy（0.20）；
4、狀態(tài)轉移矩陣：
weather today
Sunny Cloudy Rainy
weather Sunny 0.500 0.375 0.125
yesterday Cloudy 0.250 0.125 0.625
Rainy 0.250 0.375 0.375
5、混淆矩陣：
observed states
Dry Dryish Damp Soggy
Sunny 0.60 0.20 0.15 0.05
hidden Cloudy 0.25 0.25 0.25 0.25
states Rainy 0.05 0.10 0.35 0.50
為了UMDHMM也能運行這個(gè)例子，我們將上述天氣例子中的隱馬爾科夫模型轉化為如下的UMDHMM可讀的HMM文件weather.hmm：
——————————————————————–
M= 4
N= 3
A:
0.500 0.375 0.125
0.250 0.125 0.625
0.250 0.375 0.375
B:
0.60 0.20 0.15 0.05
0.25 0.25 0.25 0.25
0.05 0.10 0.35 0.50
pi:
0.63 0.17 0.20
——————————————————————–
在運行例子之前，如果讀者也想觀(guān)察每一步的運算結果，可以將umdhmm-v1.02目錄下forward.c中的void Forward(…)函數替換如下：
——————————————————————–
void Forward(HMM *phmm, int T, int *O, double **alpha, double *pprob)
{
int i, j; /* state indices */
int t; /* time index */
double sum; /* partial sum */
/* 1. Initialization */
for (i = 1; i <= phmm->N; i++)
{
alpha[1][i] = phmm->pi[i]* phmm->B[i][O[1]];
printf( “a[1][%d] = pi[%d] * b[%d][%d] = %f * %f = %f\n”,i, i, i, O[i], phmm->pi[i], phmm->B[i][O[1]], alpha[1][i] );
}
/* 2. Induction */
for (t = 1; t < T; t++)
{
for (j = 1; j <= phmm->N; j++)
{
sum = 0.0;
for (i = 1; i <= phmm->N; i++)
{
sum += alpha[t][i]* (phmm->A[i][j]);
printf( “a[%d][%d] * A[%d][%d] = %f * %f = %f\n”, t, i, i, j, alpha[t][i], phmm->A[i][j], alpha[t][i]* (phmm->A[i][j]));
printf( “sum = %f\n”, sum );
}
alpha[t+1][j] = sum*(phmm->B[j][O[t+1]]);
printf( “a[%d][%d] = sum * b[%d][%d]] = %f * %f = %f\n”,t+1, j, j, O[t+1], sum, phmm->B[j][O[t+1]], alpha[t+1][j] );
}
}
/* 3. Termination */
*pprob = 0.0;
for (i = 1; i <= phmm->N; i++)
{
*pprob += alpha[T][i];
printf( “alpha[%d][%d] = %f\n”, T, i, alpha[T][i] );
printf( “pprob = %f\n”, *pprob );
}
}
——————————————————————–
替換完畢之后，重新“make clean”，“make all”，這樣新的testfor可執行程序就可以輸出前向算法每一步的計算結果。
現在我們就用testfor來(lái)運行原文中默認給出的觀(guān)察序列“Dry,Damp,Soggy”，其所對應的UMDHMM可讀的觀(guān)察序列文件test1.seq：
——————————————————————–
T=3
1 3 4
——————————————————————–
好了，一切準備工作就緒，現在就輸入如下命令：
testfor weather.hmm test1.seq > result1
result1就包含了所有的結果細節：
——————————————————————–
Forward without scaling
a[1][1] = pi[1] * b[1][1] = 0.630000 * 0.600000 =
a
a
…
pprob = 0.026901
log prob(O| model) = -3.615577E+00
prob(O| model) = 0.026901
…
——————————————————————–
黑體部分是最終的觀(guān)察序列的概率結果，即本例中的Pr(觀(guān)察序列|HMM) = 0.026901。
但是，在原文中點(diǎn)Run按鈕后，結果卻是：Probability of this model = 0.027386915。
這其中的差別到底在哪里？我們來(lái)仔細觀(guān)察一下中間運行過(guò)程：
在初始化亦t=1時(shí)刻的局部概率計算兩個(gè)是一致的，沒(méi)有問(wèn)題。但是，t=2時(shí)，在隱藏狀態(tài)“Sunny”的局部概率是不一致的。英文原文給出的例子的運行結果是：
Alpha = (((0.37800002*0.5) + (0.0425*0.375) + (0.010000001*0.125)) * 0.15) = 0.03092813
而UMDHMM給出的結果是：
——————————————————————–
a[1][1] * A[1][1] = 0.378000 * 0.500000 = 0.189000
sum = 0.189000
a[1][2] * A[2][1] = 0.042500 * 0.250000 = 0.010625
sum = 0.199625
a[1][3] * A[3][1] = 0.010000 * 0.250000 = 0.002500
sum = 0.202125
a[2][1] = sum * b[1][3]] = 0.202125 * 0.150000 = 0.030319
——————————————————————–
區別就在于狀態(tài)轉移概率的選擇上，原文選擇的是狀態(tài)轉移矩陣中的第一行，而UMDHMM選擇的則是狀態(tài)轉移矩陣中的第一列。如果從原文給出的狀態(tài)轉移矩陣來(lái)看，第一行代表的是從前一時(shí)刻的狀態(tài)“Sunny”分別到當前時(shí)刻的狀態(tài)“Sunny”，“Cloudy”，“Rainy”的概率；而第一列代表的 是從前一時(shí)刻的狀態(tài)“Sunny”，“Cloudy”，“Rainy”分別到當前時(shí)刻狀態(tài)“Sunny”的概率。這樣看來(lái)似乎原文的計算過(guò)程有誤，讀者不 妨多試幾個(gè)例子看看，前向算法這一章就到此為止了。
分類(lèi) 隱馬爾科夫模型
六、維特比算法（Viterbi Algorithm）
尋找最可能的隱藏狀態(tài)序列(Finding most probable sequence of hidden states)
對于一個(gè)特殊的隱馬爾科夫模型(HMM)及一個(gè)相應的觀(guān)察序列，我們常常希望能找到生成此序列最可能的隱藏狀態(tài)序列。
1.窮舉搜索
我們使用下面這張網(wǎng)格圖片來(lái)形象化的說(shuō)明隱藏狀態(tài)和觀(guān)察狀態(tài)之間的關(guān)系：
我們可以通過(guò)列出所有可能的隱藏狀態(tài)序列并且計算對于每個(gè)組合相應的觀(guān)察序列的概率來(lái)找到最可能的隱藏狀態(tài)序列。最可能的隱藏狀態(tài)序列是使下面這個(gè)概率最大的組合：
Pr（觀(guān)察序列|隱藏狀態(tài)的組合）
例如，對于網(wǎng)格中所顯示的觀(guān)察序列，最可能的隱藏狀態(tài)序列是下面這些概率中最大概率所對應的那個(gè)隱藏狀態(tài)序列：
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)
這種方法是可行的，但是通過(guò)窮舉計算每一個(gè)組合的概率找到最可能的序列是極為昂貴的。與前向算法類(lèi)似，我們可以利用這些概率的時(shí)間不變性來(lái)降低計算復雜度。
2.使用遞歸降低復雜度
給定一個(gè)觀(guān)察序列和一個(gè)隱馬爾科夫模型（HMM），我們將考慮遞歸地尋找最有可能的隱藏狀態(tài)序列。我們首先定義局部概率
這些局部概率與前向算法中所計算的局部概率是不同的，因為它們表示的是時(shí)刻t時(shí)到達某個(gè)狀態(tài)最可能的路徑的概率，而不是所有路徑概率的總和。
考慮下面這個(gè)網(wǎng)格，它顯示的是天氣狀態(tài)及對于觀(guān)察序列干燥，濕潤及濕透的一階狀態(tài)轉移情況：
對于網(wǎng)格中的每一個(gè)中間及終止狀態(tài)，都有一個(gè)到達該狀態(tài)的最可能路徑。舉例來(lái)說(shuō)，在t=3時(shí)刻的3個(gè)狀態(tài)中的每一個(gè)都有一個(gè)到達此狀態(tài)的最可能路徑，或許是這樣的：
我們稱(chēng)這些路徑局部最佳路徑(partial best paths)。其中每個(gè)局部最佳路徑都有一個(gè)相關(guān)聯(lián)的概率，即局部概率或
因而
特別地，在t=T時(shí)每一個(gè)狀態(tài)都有一個(gè)局部概率和一個(gè)局部最佳路徑。這樣我們就可以通過(guò)選擇此時(shí)刻包含最大局部概率的狀態(tài)及其相應的局部最佳路徑來(lái)確定全局最佳路徑（最佳隱藏狀態(tài)序列）。
分類(lèi) 隱馬爾科夫模型
六、維特比算法（Viterbi Algorithm）
尋找最可能的隱藏狀態(tài)序列(Finding most probable sequence of hidden states)
2b.計算t=1時(shí)刻的局部概率
我們計算的局部概率
——與前向算法類(lèi)似，這個(gè)結果是通過(guò)初始概率和相應的觀(guān)察概率相乘得出的。
現在我們來(lái)展示如何利用t-1時(shí)刻的局部概率
考慮如下的網(wǎng)格：
我們考慮計算t時(shí)刻到達狀態(tài)X的最可能的路徑；這條到達狀態(tài)X的路徑將通過(guò)t-1時(shí)刻的狀態(tài)A，B或C中的某一個(gè)。
因此，最可能的到達狀態(tài)X的路徑將是下面這些路徑的某一個(gè)
?。顟B(tài)序列），…，A，X
?。顟B(tài)序列），…，B，X
或 ?。顟B(tài)序列），…，C，X
我們想找到路徑末端是AX,BX或CX并且擁有最大概率的路徑。
回顧一下馬爾科夫假設：給定一個(gè)狀態(tài)序列，一個(gè)狀態(tài)發(fā)生的概率只依賴(lài)于前n個(gè)狀態(tài)。特別地，在一階馬爾可夫假設下，狀態(tài)X在一個(gè)狀態(tài)序列后發(fā)生的概率只取決于之前的一個(gè)狀態(tài)，即
Pr (到達狀態(tài)A最可能的路徑) .Pr (X | A) . Pr (觀(guān)察狀態(tài) | X)
與此相同，路徑末端是AX的最可能的路徑將是到達A的最可能路徑再緊跟X。相似地，這條路徑的概率將是：
Pr (到達狀態(tài)A最可能的路徑) .Pr (X | A) . Pr (觀(guān)察狀態(tài) | X)
因此，到達狀態(tài)X的最可能路徑概率是：
其中第一項是t-1時(shí)刻的局部概率
泛化上述公式，就是在t時(shí)刻，觀(guān)察狀態(tài)是kt，到達隱藏狀態(tài)i的最佳局部路徑的概率是：
這里，我們假設前一個(gè)狀態(tài)的知識（局部概率）是已知的，同時(shí)利用了狀態(tài)轉移概率和相應的觀(guān)察概率之積。然后，我們就可以在其中選擇最大的概率了（局部概率
分類(lèi) 隱馬爾科夫模型
六、維特比算法（Viterbi Algorithm）
尋找最可能的隱藏狀態(tài)序列(Finding most probable sequence of hidden states)
2d.反向指針，
考慮下面這個(gè)網(wǎng)格
在每一個(gè)中間及終止狀態(tài)我們都知道了局部概率，
回顧一下我們是如何計算局部概率的，計算t時(shí)刻的
形式上，我們可以寫(xiě)成如下的公式
其中argmax運算符是用來(lái)計算使括號中表達式的值最大的索引j的。
請注意這個(gè)表達式是通過(guò)前一個(gè)時(shí)間步驟的局部概率
2e.維特比算法的優(yōu)點(diǎn)
使用Viterbi算法對觀(guān)察序列進(jìn)行解碼有兩個(gè)重要的優(yōu)點(diǎn)：
1. 通過(guò)使用遞歸減少計算復雜度——這一點(diǎn)和前向算法使用遞歸減少計算復雜度是完全類(lèi)似的。
2.維特比算法有一個(gè)非常有用的性質(zhì)，就是對于觀(guān)察序列的整個(gè)上下文進(jìn)行了最好的解釋?zhuān)紤]）。事實(shí)上，尋找最可能的隱藏狀態(tài)序列不止這一種方法，其他替代方法也可以，譬如，可以這樣確定如下的隱藏狀態(tài)序列：
其中
這里，采用了“自左向右”的決策方式進(jìn)行一種近似的判斷，其對于每個(gè)隱藏狀態(tài)的判斷是建立在前一個(gè)步驟的判斷的基礎之上（而第一步從隱藏狀態(tài)的初始向量
這種做法，如果在整個(gè)觀(guān)察序列的中部發(fā)生“噪音干擾”時(shí)，其最終的結果將與正確的答案嚴重偏離。
相反， 維特比算法在確定最可能的終止狀態(tài)前將考慮整個(gè)觀(guān)察序列，然后通過(guò)
3.小結
維特比算法提供了一種有效的計算方法來(lái)分析隱馬爾科夫模型的觀(guān)察序列，并捕獲最可能的隱藏狀態(tài)序列。它利用遞歸減少計算量，并使用整個(gè)序列的上下文來(lái)做判斷，從而對包含“噪音”的序列也能進(jìn)行良好的分析。
在使用時(shí)，維特比算法對于網(wǎng)格中的每一個(gè)單元(cell)都計算一個(gè)局部概率，同時(shí)包括一個(gè)反向指針用來(lái)指示最可能的到達該單元的路徑。當完成整個(gè)計算過(guò)程后，首先在終止時(shí)刻找到最可能的狀態(tài)，然后通過(guò)反向指針回溯到t=1時(shí)刻，這樣回溯路徑上的狀態(tài)序列就是最可能的隱藏狀態(tài)序列了。
分類(lèi) 隱馬爾科夫模型
六、維特比算法（Viterbi Algorithm）
維特比算法定義(Viterbi algorithm definition)
1、維特比算法的形式化定義
維特比算法可以形式化的概括為：
對于每一個(gè)i，i = 1，… ，n，令：
——這一步是通過(guò)隱藏狀態(tài)的初始概率和相應的觀(guān)察概率之積計算了t=1時(shí)刻的局部概率。
對于t=2，…，T和i=1，…，n,令：
——這樣就確定了到達下一個(gè)狀態(tài)的最可能路徑，并對如何到達下一個(gè)狀態(tài)做了記錄。具體來(lái)說(shuō)首先通過(guò)考察所有的轉移概率與上一步獲得的最大的局部概率之積，然后記錄下其中最大的一個(gè)，同時(shí)也包含了上一步觸發(fā)此概率的狀態(tài)。
令：
——這樣就確定了系統完成時(shí)(t=T)最可能的隱藏狀態(tài)。
對于t=T-1，…，1
令：
——這樣就可以按最可能的狀態(tài)路徑在整個(gè)網(wǎng)格回溯?；厮萃瓿蓵r(shí)，對于觀(guān)察序列來(lái)說(shuō)，序列i1 … iT就是生成此觀(guān)察序列的最可能的隱藏狀態(tài)序列。
2.計算單獨的
維特比算法中的局部概率
唯一不同的是前向算法中計算局部概率
總結(Summary)
對于一個(gè)特定的隱馬爾科夫模型，維特比算法被用來(lái)尋找生成一個(gè)觀(guān)察序列的最可能的隱藏狀態(tài)序列。我們利用概率的時(shí)間不變性，通過(guò)避免計算網(wǎng)格中每一條路徑的概率來(lái)降低問(wèn)題的復雜度。維特比算法對于每一個(gè)狀態(tài)(t>1)都保存了一個(gè)反向指針(
局部概率
當t=T時(shí)，維特比算法所到達的這些終止狀態(tài)的局部概率
關(guān)于維特比算法，需要著(zhù)重強調的一點(diǎn)是它不是簡(jiǎn)單的對于某個(gè)給定的時(shí)間點(diǎn)選擇最可能的隱藏狀態(tài)，而是基于全局序列做決策——因此，如果在觀(guān)察序列中有一個(gè)“非尋常”的事件發(fā)生，對于維特比算法的結果也影響不大。
這在語(yǔ)音處理中是特別有價(jià)值的，譬如當某個(gè)單詞發(fā)音的一個(gè)中間音素出現失真或丟失的情況時(shí)，該單詞也可以被識別出來(lái)。
分類(lèi) 隱馬爾科夫模型
六、維特比算法（Viterbi Algorithm）
維特比算法程序示例
仍然需要說(shuō)明的是，本節不是這個(gè)系列的翻譯，而是作為維特比算法這一章的補充，將UMDHMM這個(gè)C語(yǔ)言版本的HMM工具包中的維特比算法程序展示給大家，并運行包中所附帶的例子。關(guān)于UMDHMM這個(gè)工具包的介紹，大家可以參考前向算法4中的介紹。
維特比算法程序示例如下（在viterbi.c中):
void Viterbi(HMM *phmm, int T, int *O, double **delta, int **psi,int *q, double *pprob)
{
int i, j; /* state indices */
int t; /* time index */
int maxvalind;
double maxval, val;
/* 1. Initialization */
for (i = 1; i <= phmm->N; i++)
{
delta[1][i] = phmm->pi[i] * (phmm->B[i][O[1]]);
psi[1][i] = 0;
}
/* 2. Recursion */
for (t = 2; t <= T; t++)
{
for (j = 1; j <= phmm->N; j++)
{
maxval = 0.0;
maxvalind = 1;
for (i = 1; i <= phmm->N; i++)
{
val = delta[t-1][i]*(phmm->A[i][j]);
if (val > maxval)
{
maxval = val;
maxvalind = i;
}
}
delta[t][j] = maxval*(phmm->B[j][O[t]]);
psi[t][j] = maxvalind;
}
}
/* 3. Termination */
*pprob = 0.0;
q[T] = 1;
for (i = 1; i <= phmm->N; i++)
{
if (delta[T][i] > *pprob)
{
*pprob = delta[T][i];
q[T] = i;
}
}
/* 4. Path (state sequence) backtracking */
for (t = T – 1; t >= 1; t–)
q[t] = psi[t+1][q[t+1]];
}
在UMDHMM包中所生成的4個(gè)可執行程序中，testvit是用來(lái)測試維特比算法的， 對于給定的觀(guān)察符號序列及HMM，利用Viterbi 算法生成最可能的隱藏狀態(tài)序列。這里我們利用UMDHMM包中test.hmm和test.seq來(lái)測試維特比算法，關(guān)于這兩個(gè)文件，具體如下：
test.hmm：
——————————————————————–
M= 2
N= 3
A:
0.333 0.333 0.333
0.333 0.333 0.333
0.333 0.333 0.333
B:
0.5 0.5
0.75 0.25
0.25 0.75
pi:
0.333 0.333 0.333
——————————————————————–
test.seq：
——————————————————————–
T= 10
1 1 1 1 2 1 2 2 2 2
——————————————————————–
對于維特比算法的測試程序testvit來(lái)說(shuō)，運行：
testvit test.hmm test.seq
結果如下：
————————————
Viterbi using direct probabilities
Viterbi MLE log prob = -1.387295E+01
Optimal state sequence:
T= 10
2 2 2 2 3 2 3 3 3 3
————————————
Viterbi using log probabilities
Viterbi MLE log prob = -1.387295E+01
Optimal state sequence:
T= 10
2 2 2 2 3 2 3 3 3 3
————————————
The two log probabilites and optimal state sequences
should identical (within numerical precision).
序列“2 2 2 2 3 2 3 3 3
分類(lèi) 隱馬爾科夫模型
七、前向-后向算法(Forward-backward algorithm)
根據觀(guān)察序列生成隱馬爾科夫模型(Generating a HMM from a sequence of obersvations)
與HMM模型相關(guān)的“有用”的問(wèn)題是評估（前向算法）和解碼（維特比算法）——它們一個(gè)被用來(lái)測量一個(gè)模型的相對適用性，另一個(gè)被用來(lái)推測模型隱藏的部分在做什么（“到底發(fā)生了”什么）?？梢钥闯鏊鼈兌家蕾?lài)于隱馬爾科夫模型（HMM）參數這一先驗知識——狀態(tài)轉移矩陣，混淆（觀(guān)察）矩陣，以及
然而，在許多實(shí)際問(wèn)題的情況下這些參數都不能直接計算的，而要需要進(jìn)行估計——這就是隱馬爾科夫模型中的學(xué)習問(wèn)題。前向-后向算法就可以以一個(gè)觀(guān)察序 列為基礎來(lái)進(jìn)行這樣的估計，而這個(gè)觀(guān)察序列來(lái)自于一個(gè)給定的集合，它所代表的是一個(gè)隱馬爾科夫模型中的一個(gè)已知的隱藏集合。
一個(gè)例子可能是一個(gè)龐大的語(yǔ)音處理數據庫，其底層的語(yǔ)音可能由一個(gè)馬爾可夫過(guò)程基于已知的音素建模的，而其可以觀(guān)察的部分可能由可識別的狀態(tài)（可能通過(guò)一些矢量數據表示）建模的，但是沒(méi)有（直接）的方式來(lái)獲取隱馬爾科夫模型（HMM）參數。
前向-后向算法并非特別難以理解，但自然地比前向算法和維特比算法更復雜。由于這個(gè)原因，這里就不詳細講解前向-后向算法了（任何有關(guān)HMM模型的參考文獻都會(huì )提供這方面的資料的）。
總之，前向-后向算法首先對于隱馬爾科夫模型的參數進(jìn)行一個(gè)初始的估計（這很可能是完全錯誤的），然后通過(guò)對于給定的數據評估這些參數的的價(jià)值并減少它們所引起的錯誤來(lái)重新修訂這些HMM參數。從這個(gè)意義上講，它是以一種梯度下降的形式尋找一種錯誤測度的最小值。
之所以稱(chēng)其為前向-后向算法，主要是因為對于網(wǎng)格中的每一個(gè)狀態(tài)，它既計算到達此狀態(tài)的“前向”概率（給定當前模型的近似估計），又計算生成此模型最 終狀態(tài)的“后向”概率（給定當前模型的近似估計）。 這些都可以通過(guò)利用遞歸進(jìn)行有利地計算，就像我們已經(jīng)看到的?？梢酝ㄟ^(guò)利用近似的HMM模型參數來(lái)提高這些中間概率進(jìn)行調整，而這些調整又形成了前向-后 向算法迭代的基礎。
注：關(guān)于前向-后向算法，原文只講了這么多，后繼我將按自己的理解補充一些內容。
分類(lèi) 隱馬爾科夫模型
七、前向-后向算法(Forward-backward algorithm)
要理解前向-后向算法，首先需要了解兩個(gè)算法：后向算法和EM算法。后向算法是必須的，因為前向-后向算法就是利用了前向算法與后向算法中的變 量因子，其得名也因于此；而EM算法不是必須的，不過(guò)由于前向-后向算法是EM算法的一個(gè)特例，因此了解一下EM算法也是有好處的，說(shuō)實(shí)話(huà)，對于EM算 法，我也是云里霧里的。好了，廢話(huà)少說(shuō)，我們先談?wù)労笙蛩惴ā?/font>
1、后向算法（Backward algorithm）
其實(shí)如果理解了前向算法，后向算法也是比較好理解的，這里首先重新定義一下前向算法中的局部概率at(i)，稱(chēng)其為前向變量，這也是為前向-后向算法做點(diǎn)準備：
相似地，我們也可以定義一個(gè)后向變量Bt(i)（同樣可以理解為一個(gè)局部概率）：
后向變量(局部概率)表示的是已知隱馬爾科夫模型
1）初始化，令t=T時(shí)刻所有狀態(tài)的后向變量為1：
2）歸納，遞歸計算每個(gè)時(shí)間點(diǎn)，t=T-1,T-2,…,1時(shí)的后向變量：
這樣就可以計算每個(gè)時(shí)間點(diǎn)上所有的隱藏狀態(tài)所對應的后向變量，如果需要利用后向算法計算觀(guān)察序列的概率，只需將t=1時(shí)刻的后向變量（局部概率）相加即可。下圖顯示的是t+1時(shí)刻與t時(shí)刻的后向變量之間的關(guān)系：
上述主要參考自HMM經(jīng)典論文《A tutorial on Hidden Markov Models and selected applications in speech recognition》。下面我們給出利用后向算法計算觀(guān)察序列概率的程序示例，這個(gè)程序仍然來(lái)自于UMDHMM。
后向算法程序示例如下（在backward.c中):void Backward(HMM *phmm, int T, int *O, double **beta, double *pprob){ int i, j; /* state indices */ int t; /* time index */ double sum;
/* 1. Initialization */
for (i = 1; i <= phmm->N; i++)
beta[T][i] = 1.0;
/* 2. Induction */
for (t = T - 1; t >= 1; t--)
{
for (i = 1; i <= phmm->N; i++)
{
sum = 0.0;
for (j = 1; j <= phmm->N; j++)
sum += phmm->A[i][j] *
(phmm->B[j][O[t+1]])*beta[t+1][j];
beta[t][i] = sum;
}
}
/* 3. Termination */
*pprob = 0.0;
for (i = 1; i <= phmm->N; i++)
*pprob += beta[1][i];
}
好了，后向算法就到此為止了，下一節我們粗略的談?wù)?span lang="EN-US">EM算法。
分類(lèi) 隱馬爾科夫模型
七、前向-后向算法(Forward-backward algorithm)
前向-后向算法是Baum于1972年提出來(lái)的，又稱(chēng)之為Baum-Welch算法，雖然它是EM(Expectation- Maximization)算法的一個(gè)特例，但EM算法卻是于1977年提出的。那么為什么說(shuō)前向-后向算法是EM算法的一個(gè)特例呢？這里有兩點(diǎn)需要說(shuō)明 一下。
第一，1977年A. P. Dempster、N. M. Laird、 D. B. Rubin在其論文“Maximum Likelihood from Incomplete Data via the EM Algorithm”中首次提出了EM算法的概念，但是他們也在論文的介紹中提到了在此之前就有一些學(xué)者利用了EM算法的思想解決了一些特殊問(wèn)題，其中就包括了Baum在70年代初期的相關(guān)工作，只是這類(lèi)方法沒(méi)有被總結而已，他們的工作就是對這類(lèi)解決問(wèn)題的方法在更高的層次上定義了一個(gè)完整的EM算法框 架。
第二，對于前向-后向算法與EM算法的關(guān)系，此后在許多與HMM或EM相關(guān)的論文里都被提及，其中賈里尼克（Jelinek）老先生在1997所著(zhù)的 書(shū)“Statistical Methods for Speech Recognition”中對于前向-后向算法與EM算法的關(guān)系進(jìn)行了完整的描述，讀者有興趣的話(huà)可以找來(lái)這本書(shū)讀讀。
關(guān)于EM算法的講解，網(wǎng)上有很多，這里我就不獻丑了，直接拿目前搜索“EM算法”在Google排名第一的文章做了參考，希望讀者不要拍磚：
EM 算法是 Dempster，Laind，Rubin 于 1977 年提出的求參數極大似然估計的一種方法，它可以從非完整數據集中對參數進(jìn)行 MLE 估計，是一種非常簡(jiǎn)單實(shí)用的學(xué)習算法。這種方法可以廣泛地應用于處理缺損數據，截尾數據，帶有討厭數據等所謂的不完全數據(incomplete data)。
假定集合Z = (X,Y)由觀(guān)測數據 X 和未觀(guān)測數據Y 組成，Z = (X,Y)和 X 分別稱(chēng)為完整數據和不完整數據。假設Z的聯(lián)合概率密度被參數化地定義為P(X，Y|Θ)，其中Θ 表示要被估計的參數。Θ 的最大似然估計是求不完整數據的對數似然函數L(X;Θ)的最大值而得到的：
L(Θ; X )= log p(X |Θ) = ∫log p(X ,Y |Θ)dY ；(1)
EM算法包括兩個(gè)步驟：由E步和M步組成，它是通過(guò)迭代地最大化完整數據的對數似然函數Lc( X;Θ )的期望來(lái)最大化不完整數據的對數似然函數，其中：
Lc(X;Θ) =log p(X，Y |Θ) ； (2)
假設在算法第t次迭代后Θ 獲得的估計記為Θ(t ) ，則在（t+1）次迭代時(shí)，
E-步：計算完整數據的對數似然函數的期望，記為：
Q(Θ |Θ (t) ) = E{Lc(Θ;Z)|X;Θ(t) }； (3)
M-步：通過(guò)最大化Q(Θ |Θ(t) ) 來(lái)獲得新的Θ 。
通過(guò)交替使用這兩個(gè)步驟，EM算法逐步改進(jìn)模型的參數，使參數和訓練樣本的似然概率逐漸增大，最后終止于一個(gè)極大點(diǎn)。
直 觀(guān)地理解EM算法，它也可被看作為一個(gè)逐次逼近算法：事先并不知道模型的參數，可以隨機的選擇一套參數或者事先粗略地給定某個(gè)初始參數λ0 ，確定出對應于這組參數的最可能的狀態(tài)，計算每個(gè)訓練樣本的可能結果的概率，在當前的狀態(tài)下再由樣本對參數修正，重新估計參數λ ，并在新的參數下重新確定模型的狀態(tài)，這樣，通過(guò)多次的迭代，循環(huán)直至某個(gè)收斂條件滿(mǎn)足為止，就可以使得模型的參數逐漸逼近真實(shí)參數。
EM算法的主要目的是提供一個(gè)簡(jiǎn)單的迭代算法計算后驗密度函數，它的最大優(yōu)點(diǎn)是簡(jiǎn)單和穩定，但容易陷入局部最優(yōu)。
參考原文見(jiàn)：http://49805085.spaces.live.com/Blog/cns!145C40DDDB4C6E5!670.entry
注意上面那段粗體字，讀者如果覺(jué)得EM算法不好理解的話(huà)，就記住這段粗體字的意思吧！
有了后向算法和EM算法的預備知識，下一節我們就正式的談一談前向-后向算法。
分類(lèi) 隱馬爾科夫模型
七、前向-后向算法(Forward-backward algorithm)
隱馬爾科夫模型（HMM）的三個(gè)基本問(wèn)題中，第三個(gè)HMM參數學(xué)習的問(wèn)題是最難的，因為對于給定的觀(guān)察序列O，沒(méi)有任何一種方法可以精確地找到一組最優(yōu)的隱馬爾科夫模型參數（A、B、
我們首先定義兩個(gè)變量。給定觀(guān)察序列O及隱馬爾科夫模型
回顧一下第二節中關(guān)于前向變量at(i)及后向變量Bt(i)的定義，我們可以很容易地將上式用前向、后向變量表示為：
其中分母的作用是確保：
給定觀(guān)察序列O及隱馬爾科夫模型
該變量在網(wǎng)格中所代表的關(guān)系如下圖所示：
同樣，該變量也可以由前向、后向變量表示：
而上述定義的兩個(gè)變量間也存在著(zhù)如下關(guān)系：
如果對于時(shí)間軸t上的所有
分類(lèi) 隱馬爾科夫模型
七、前向-后向算法(Forward-backward algorithm)
上一節我們定義了兩個(gè)變量及相應的期望值，本節我們利用這兩個(gè)變量及其期望值來(lái)重新估計隱馬爾科夫模型（HMM）的參數
如果我們定義當前的HMM模型為
關(guān)于前向-后向算法和EM算法的具體關(guān)系的解釋?zhuān)蠹铱梢詤⒖?span lang="EN-US">HMM經(jīng)典論文《A tutorial on Hidden Markov Models and selected applications in speech recognition》，這里就不詳述了。下面我們給出UMDHMM中的前向-后向算法示例，這個(gè)算法比較復雜，這里只取主函數，其中所引用的函數大家如果感興趣的話(huà)可以自行參考UMDHMM。
前向-后向算法程序示例如下（在baum.c中):void BaumWelch(HMM *phmm, int T, int *O, double **alpha, double **beta, double **gamma, int *pniter, double *plogprobinit, double *plogprobfinal){ int i, j, k; int t, l = 0;
double logprobf, logprobb, threshold;
double numeratorA, denominatorA;
double numeratorB, denominatorB;
double ***xi, *scale;
double delta, deltaprev, logprobprev;
deltaprev = 10e-70;
xi = AllocXi(T, phmm->N);
scale = dvector(1, T);
ForwardWithScale(phmm, T, O, alpha, scale, &logprobf);
*plogprobinit = logprobf; /* log P(O |intial model) */
BackwardWithScale(phmm, T, O, beta, scale, &logprobb);
ComputeGamma(phmm, T, alpha, beta, gamma);
ComputeXi(phmm, T, O, alpha, beta, xi);
logprobprev = logprobf;
do
{
/* reestimate frequency of state i in time t=1 */
for (i = 1; i <= phmm->N; i++)
phmm->pi[i] = .001 + .999*gamma[1][i];
/* reestimate transition matrix and symbol prob in
each state */
for (i = 1; i <= phmm->N; i++)
{
denominatorA = 0.0;
for (t = 1; t <= T - 1; t++)
denominatorA += gamma[t][i];
for (j = 1; j <= phmm->N; j++)
{
numeratorA = 0.0;
for (t = 1; t <= T - 1; t++)
numeratorA += xi[t][i][j];
phmm->A[i][j] = .001 +
.999*numeratorA/denominatorA;
}
denominatorB = denominatorA + gamma[T][i];
for (k = 1; k <= phmm->M; k++)
{
numeratorB = 0.0;
for (t = 1; t <= T; t++)
{
if (O[t] == k)
numeratorB += gamma[t][i];
}
phmm->B[i][k] = .001 +
.999*numeratorB/denominatorB;
}
}
ForwardWithScale(phmm, T, O, alpha, scale, &logprobf);
BackwardWithScale(phmm, T, O, beta, scale, &logprobb);
ComputeGamma(phmm, T, alpha, beta, gamma);
ComputeXi(phmm, T, O, alpha, beta, xi);
/* compute difference between log probability of
two iterations */
delta = logprobf - logprobprev;
logprobprev = logprobf;
l++;
}
while (delta > DELTA); /* if log probability does not
change much, exit */
*pniter = l;
*plogprobfinal = logprobf; /* log P(O|estimated model) */
FreeXi(xi, T, phmm->N);
free_dvector(scale, 1, T);
}
前向-后向算法就到此為止了。
分類(lèi) 隱馬爾科夫模型
八、總結(Summary)
通常，模式并不是單獨的出現，而是作為時(shí)間序列中的一個(gè)部分——這個(gè)過(guò)程有時(shí)候可以被輔助用來(lái)對它們進(jìn)行識別。在基于時(shí)間的進(jìn)程中，通常都會(huì )使用一些假設——一個(gè)最常用的假設是進(jìn)程的狀態(tài)只依賴(lài)于前面N個(gè)狀態(tài)——這樣我們就有了一個(gè)N階馬爾科夫模型。最簡(jiǎn)單的例子是N = 1。
存在很多例子，在這些例子中進(jìn)程的狀態(tài)（模式）是不能夠被直接觀(guān)察的，但是可以非直接地，或者概率地被觀(guān)察為模式的另外一種集合——這樣我們就可以定義一類(lèi)隱馬爾科夫模型——這些模型已被證明在當前許多研究領(lǐng)域，尤其是語(yǔ)音識別領(lǐng)域具有非常大的價(jià)值。
在實(shí)際的過(guò)程中這些模型提出了三個(gè)問(wèn)題都可以得到立即有效的解決，分別是：
* 評估：對于一個(gè)給定的隱馬爾科夫模型其生成一個(gè)給定的觀(guān)察序列的概率是多少。前向算法可以有效的解決此問(wèn)題。
* 解碼：什么樣的隱藏（底層）狀態(tài)序列最有可能生成一個(gè)給定的觀(guān)察序列。維特比算法可以有效的解決此問(wèn)題。
* 學(xué)習：對于一個(gè)給定的觀(guān)察序列樣本，什么樣的模型最可能生成該序列——也就是說(shuō)，該模型的參數是什么。這個(gè)問(wèn)題可以通過(guò)使用前向-后向算法解決。
隱馬爾科夫模型（HMM）在分析實(shí)際系統中已被證明有很大的價(jià)值；它們通常的缺點(diǎn)是過(guò)于簡(jiǎn)化的假設，這與馬爾可夫假設相關(guān)——即一個(gè)狀態(tài)只依賴(lài)于前一個(gè)狀態(tài)，并且這種依賴(lài)關(guān)系是獨立于時(shí)間之外的（與時(shí)間無(wú)關(guān)）。
關(guān)于隱馬爾科夫模型的完整論述，可參閱：
L R Rabiner and B H Juang, `An introduction to HMMs’, iEEE ASSP Magazine, 3, 4-16.
全文完！
后記：這個(gè)翻譯系列終于可以告一段落了，從
本文翻譯自：http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html
部分翻譯參考：隱馬爾科夫模型HMM自學(xué)
轉載請注明出處“我愛(ài)自然語(yǔ)言處理”：www.52nlp.cn
本文鏈接地址：http://www.52nlp.cn/hmm-learn-best-practices-eight-summary
聯(lián)系客服
