分類 隱馬爾科夫模型
隱馬爾科夫模型（HMM）依然是讀者訪問“我愛自然語言處理”的一個熱門相關關鍵詞，我曾在《HMM學習最佳范例與崔曉源的博客》中介紹過國外的一個不錯的HMM學習教程，并且國內崔曉源師兄有一個相應的翻譯版本，不過這個版本比較簡化和粗略，有些地方只是概況性的翻譯了一下，省去了一些內容，所以從今天開始計劃在52nlp上系統的重新翻譯這個學習教程，希望對大家有點用。
一、介紹（Introduction）
我們通常都習慣尋找一個事物在一段時間里的變化模式（規律）。這些模式發生在很多領域，比如計算機中的指令序列，句子中的詞語順序和口語單詞中的音素序列等等，事實上任何領域中的一系列事件都有可能產生有用的模式。
考慮一個簡單的例子，有人試圖通過一片海藻推斷天氣——民間傳說告訴我們‘濕透的’海藻意味著潮濕陰雨，而‘干燥的’海藻則意味著陽光燦爛。如果它處 于一個中間狀態（‘有濕氣’），我們就無法確定天氣如何。然而，天氣的狀態并沒有受限于海藻的狀態，所以我們可以在觀察的基礎上預測天氣是雨天或晴天的可 能性。另一個有用的線索是前一天的天氣狀態（或者，至少是它的可能狀態）——通過綜合昨天的天氣及相應觀察到的海藻狀態，我們有可能更好的預測今天的天 氣。
這是本教程中我們將考慮的一個典型的系統類型。
首先，我們將介紹產生概率模式的系統，如晴天及雨天間的天氣波動。
然后，我們將會看到這樣一個系統，我們希望預測的狀態并不是觀察到的——其底層系統是隱藏的。在上面的例子中，觀察到的序列將是海藻而隱藏的系統將是實際的天氣。
最后，我們會利用已經建立的模型解決一些實際的問題。對于上述例子，我們想知道：
1. 給出一個星期每天的海藻觀察狀態，之后的天氣將會是什么?
2. 給定一個海藻的觀察狀態序列，預測一下此時是冬季還是夏季？直觀地，如果一段時間內海藻都是干燥的，那么這段時間很可能是夏季，反之，如果一段時間內海藻都是潮濕的，那么這段時間可能是冬季。
分類 隱馬爾科夫模型
二、生成模式（Generating Patterns）
1、確定性模式（Deterministic Patterns）
考慮一套交通信號燈，燈的顏色變化序列依次是紅色-紅色/黃色-綠色-黃色-紅色。這個序列可以作為一個狀態機器，交通信號燈的不同狀態都緊跟著上一個狀態。
注意每一個狀態都是唯一的依賴于前一個狀態，所以，如果交通燈為綠色，那么下一個顏色狀態將始終是黃色——也就是說，該系統是確定性的。確定性系統相對比較容易理解和分析，因為狀態間的轉移是完全已知的。
2、非確定性模式（Non-deterministic patterns）
為了使天氣那個例子更符合實際，加入第三個狀態——多云。與交通信號燈例子不同，我們并不期望這三個天氣狀態之間的變化是確定性的，但是我們依然希望對這個系統建模以便生成一個天氣變化模式（規律）。
一種做法是假設模型的當前狀態僅僅依賴于前面的幾個狀態，這被稱為馬爾科夫假設，它極大地簡化了問題。顯然，這可能是一種粗糙的假設，并且因此可能將一些非常重要的信息丟失。
當考慮天氣問題時，馬爾科夫假設假定今天的天氣只能通過過去幾天已知的天氣情況進行預測——而對于其他因素，譬如風力、氣壓等則沒有考慮。在這個例子以及其他相似的例子中，這樣的假設顯然是不現實的。然而，由于這樣經過簡化的系統可以用來分析，我們常常接受這樣的知識假設，雖然它產生的某些信息不完全 準確。
一個馬爾科夫過程是狀態間的轉移僅依賴于前n個狀態的過程。這個過程被稱之為n階馬爾科夫模型，其中n是影響下一個狀態選擇的（前）n個狀態。最簡單 的馬爾科夫過程是一階模型，它的狀態選擇僅與前一個狀態有關。這里要注意它與確定性系統并不相同，因為下一個狀態的選擇由相應的概率決定，并不是確定性的。
下圖是天氣例子中狀態間所有可能的一階狀態轉移情況：
對于有M個狀態的一階馬爾科夫模型，共有 個狀態轉移，因為任何一個狀態都有可能是所有狀態的下一個轉移狀態。每一個狀態轉移都有一個概率值，稱為狀態轉移概率——這是從一個狀態轉移到另一個狀態的概率。所有的 個概率可以用一個狀態轉移矩陣表示。注意這些概率并不隨時間變化而不同——這是一個非常重要（但常常不符合實際）的假設。
下面的狀態轉移矩陣顯示的是天氣例子中可能的狀態轉移概率：
-也就是說，如果昨天是晴天，那么今天是晴天的概率為0.5，是多云的概率為0.375。注意，每一行的概率之和為1。
要初始化這樣一個系統，我們需要確定起始日天氣的（或可能的）情況，定義其為一個初始概率向量，稱為 向量。
-也就是說，第一天為晴天的概率為1。
現在我們定義一個一階馬爾科夫過程如下：
狀態：三個狀態——晴天，多云，雨天。
向量：定義系統初始化時每一個狀態的概率。
狀態轉移矩陣：給定前一天天氣情況下的當前天氣概率。
任何一個可以用這種方式描述的系統都是一個馬爾科夫過程。
3、總結
我們嘗試識別時間變化中的模式，并且為了達到這個目我們試圖對這個過程建模以便產生這樣的模式。我們使用了離散時間點、離散狀態以及做了馬爾科夫假設。在采用了這些假設之后，系統產生了這個被描述為馬爾科夫過程的模式，它包含了一個 向量（初始概率）和一個狀態轉移矩陣。關于假設，重要的一點是狀態轉移矩陣并不隨時間的改變而改變——這個矩陣在整個系統的生命周期中是固定不變的。
分類 隱馬爾科夫模型
三、隱藏模式（Hidden Patterns）
1、馬爾科夫過程的局限性
在某些情況下，我們希望找到的模式用馬爾科夫過程描述還顯得不充分。回顧一下天氣那個例子，一個隱士也許不能夠直接獲取到天氣的觀察情況，但是他有一些水藻。民間傳說告訴我們水藻的狀態與天氣狀態有一定的概率關系——天氣和水藻的狀態是緊密相關的。在這個例子中我們有兩組狀態，觀察的狀態（水藻的狀態）和隱藏的狀態（天氣的狀態）。我們希望為隱士設計一種算法，在不能夠直接觀察天氣的情況下，通過水藻和馬爾科夫假設來預測天氣。
一個更實際的問題是語音識別，我們聽到的聲音是來自于聲帶、喉嚨大小、舌頭位置以及其他一些東西的組合結果。所有這些因素相互作用產生一個單詞的聲音，一套語音識別系統檢測的聲音就是來自于個人發音時身體內部物理變化所引起的不斷改變的聲音。
一些語音識別裝置工作的原理是將內部的語音產出看作是隱藏的狀態，而將聲音結果作為一系列觀察的狀態，這些由語音過程生成并且最好的近似了實際（隱 藏）的狀態。在這兩個例子中，需要著重指出的是，隱藏狀態的數目與觀察狀態的數目可以是不同的。一個包含三個狀態的天氣系統（晴天、多云、雨天）中，可以觀察到4個等級的海藻濕潤情況（干、稍干、潮濕、濕潤）；純粹的語音可以由80個音素描述，而身體的發音系統會產生出不同數目的聲音，或者比80多，或者 比80少。
在這種情況下，觀察到的狀態序列與隱藏過程有一定的概率關系。我們使用隱馬爾科夫模型對這樣的過程建模，這個模型包含了一個底層隱藏的隨時間改變的馬爾科夫過程，以及一個與隱藏狀態某種程度相關的可觀察到的狀態集合。
2、隱馬爾科夫模型（Hidden Markov Models）
下圖顯示的是天氣例子中的隱藏狀態和觀察狀態。假設隱藏狀態（實際的天氣）由一個簡單的一階馬爾科夫過程描述，那么它們之間都相互連接。
隱藏狀態和觀察狀態之間的連接表示：在給定的馬爾科夫過程中，一個特定的隱藏狀態生成特定的觀察狀態的概率。這很清晰的表示了‘進入’一個觀察狀態的 所有概率之和為1，在上面這個例子中就是Pr(Obs|Sun), Pr(Obs|Cloud) 及 Pr(Obs|Rain)之和。（對這句話我有點疑惑？）
除了定義了馬爾科夫過程的概率關系，我們還有另一個矩陣，定義為混淆矩陣（confusion matrix），它包含了給定一個隱藏狀態后得到的觀察狀態的概率。對于天氣例子，混淆矩陣是：
注意矩陣的每一行之和是1。
3、總結（Summary）
我們已經看到在一些過程中一個觀察序列與一個底層馬爾科夫過程是概率相關的。在這些例子中，觀察狀態的數目可以和隱藏狀態的數碼不同。
我們使用一個隱馬爾科夫模型（HMM）對這些例子建模。這個模型包含兩組狀態集合和三組概率集合：
* 隱藏狀態：一個系統的（真實）狀態，可以由一個馬爾科夫過程進行描述（例如，天氣）。
* 觀察狀態：在這個過程中‘可視’的狀態（例如，海藻的濕度）。
* 向量：包含了（隱）模型在時間t=1時一個特殊的隱藏狀態的概率（初始概率）。
* 狀態轉移矩陣：包含了一個隱藏狀態到另一個隱藏狀態的概率
* 混淆矩陣：包含了給定隱馬爾科夫模型的某一個特殊的隱藏狀態，觀察到的某個觀察狀態的概率。
因此一個隱馬爾科夫模型是在一個標準的馬爾科夫過程中引入一組觀察狀態，以及其與隱藏狀態間的一些概率關系。
分類 隱馬爾科夫模型
四、隱馬爾科夫模型（Hidden Markov Models）
1、定義（Definition of a hidden Markov model）
一個隱馬爾科夫模型是一個三元組（ , A, B）。
：初始化概率向量；
：狀態轉移矩陣；
：混淆矩陣；
在狀態轉移矩陣及混淆矩陣中的每一個概率都是時間無關的——也就是說，當系統演化時這些矩陣并不隨時間改變。實際上，這是馬爾科夫模型關于真實世界最不現實的一個假設。
2、應用（Uses associated with HMMs）
一旦一個系統可以作為HMM被描述，就可以用來解決三個基本問題。其中前兩個是模式識別的問題：給定HMM求一個觀察序列的概率（評估）；搜索最有可能生成一個觀察序列的隱藏狀態訓練（解碼）。第三個問題是給定觀察序列生成一個HMM（學習）。
a) 評估（Evaluation）
考慮這樣的問題，我們有一些描述不同系統的隱馬爾科夫模型（也就是一些( ,A,B)三元組的集合）及一個觀察序列。我們想知道哪一個HMM最有可能產生了這個給定的觀察序列。例如，對于海藻來說，我們也許會有一個“夏季”模型和一個“冬季”模型，因為不同季節之間的情況是不同的——我們也許想根據海藻濕度的觀察序列來確定當前的季節。
我們使用前向算法（forward algorithm）來計算給定隱馬爾科夫模型（HMM）后的一個觀察序列的概率，并因此選擇最合適的隱馬爾科夫模型(HMM)。
在語音識別中這種類型的問題發生在當一大堆數目的馬爾科夫模型被使用，并且每一個模型都對一個特殊的單詞進行建模時。一個觀察序列從一個發音單詞中形成，并且通過尋找對于此觀察序列最有可能的隱馬爾科夫模型（HMM）識別這個單詞。
b) 解碼（ Decoding）
給定觀察序列搜索最可能的隱藏狀態序列。
另一個相關問題，也是最感興趣的一個，就是搜索生成輸出序列的隱藏狀態序列。在許多情況下我們對于模型中的隱藏狀態更感興趣，因為它們代表了一些更有價值的東西，而這些東西通常不能直接觀察到。
考慮海藻和天氣這個例子，一個盲人隱士只能感覺到海藻的狀態，但是他更想知道天氣的情況，天氣狀態在這里就是隱藏狀態。
我們使用Viterbi 算法（Viterbi algorithm）確定（搜索）已知觀察序列及HMM下最可能的隱藏狀態序列。
Viterbi算法（Viterbi algorithm）的另一廣泛應用是自然語言處理中的詞性標注。在詞性標注中，句子中的單詞是觀察狀態，詞性（語法類別）是隱藏狀態（注意對于許多單詞，如wind，fish擁有不止一個詞性）。對于每句話中的單詞，通過搜索其最可能的隱藏狀態，我們就可以在給定的上下文中找到每個單詞最可能的詞性標注。
C）學習（Learning）
根據觀察序列生成隱馬爾科夫模型。
第三個問題，也是與HMM相關的問題中最難的，根據一個觀察序列（來自于已知的集合），以及與其有關的一個隱藏狀態集，估計一個最合適的隱馬爾科夫模型（HMM），也就是確定對已知序列描述的最合適的（ ,A,B）三元組。
當矩陣A和B不能夠直接被（估計）測量時，前向-后向算法（forward-backward algorithm）被用來進行學習（參數估計），這也是實際應用中常見的情況。
3、總結（Summary）
由一個向量和兩個矩陣( ,A,B)描述的隱馬爾科夫模型對于實際系統有著巨大的價值，雖然經常只是一種近似，但它們卻是經得起分析的。隱馬爾科夫模型通常解決的問題包括：
1. 對于一個觀察序列匹配最可能的系統——評估，使用前向算法（forward algorithm）解決；
2. 對于已生成的一個觀察序列，確定最可能的隱藏狀態序列——解碼，使用Viterbi 算法（Viterbi algorithm）解決；
3. 對于已生成的觀察序列，決定最可能的模型參數——學習，使用前向-后向算法（forward-backward algorithm）解決。
分類 隱馬爾科夫模型
五、前向算法（Forward Algorithm）
計算觀察序列的概率（Finding the probability of an observed sequence）
1.窮舉搜索（ Exhaustive search for solution）
給定隱馬爾科夫模型，也就是在模型參數（ , A, B)已知的情況下，我們想找到觀察序列的概率。還是考慮天氣這個例子，我們有一個用來描述天氣及與它密切相關的海藻濕度狀態的隱馬爾科夫模型(HMM)， 另外我們還有一個海藻的濕度狀態觀察序列。假設連續3天海藻濕度的觀察結果是（干燥、濕潤、濕透）——而這三天每一天都可能是晴天、多云或下雨，對于觀察 序列以及隱藏的狀態，可以將其視為網格：
網格中的每一列都顯示了可能的的天氣狀態，并且每一列中的每個狀態都與相鄰列中的每一個狀態相連。而其狀態間的轉移都由狀態轉移矩陣提供一個概率。在每一列下面都是某個時間點上的觀察狀態，給定任一個隱藏狀態所得到的觀察狀態的概率由混淆矩陣提供。
可以看出，一種計算觀察序列概率的方法是找到每一個可能的隱藏狀態，并且將這些隱藏狀態下的觀察序列概率相加。對于上面那個（天氣）例子，將有3^3 = 27種不同的天氣序列可能性，因此，觀察序列的概率是：
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)
用這種方式計算觀察序列概率極為昂貴，特別對于大的模型或較長的序列，因此我們可以利用這些概率的時間不變性來減少問題的復雜度。
2.使用遞歸降低問題復雜度
給定一個隱馬爾科夫模型（HMM），我們將考慮遞歸地計算一個觀察序列的概率。我們首先定義局部概率（partial probability）,它是到達網格中的某個中間狀態時的概率。然后，我們將介紹如何在t=1和t=n(>1)時計算這些局部概率。
假設一個T-長觀察序列是：
2a.局部概率( ’s)
考慮下面這個網格，它顯示的是天氣狀態及對于觀察序列干燥，濕潤及濕透的一階狀態轉移情況：
我們可以將計算到達網格中某個中間狀態的概率作為所有到達這個狀態的可能路徑的概率求和問題。
例如，t=2時位于“多云”狀態的局部概率通過如下路徑計算得出：
我們定義t時刻位于狀態j的局部概率為at(j)——這個局部概率計算如下：
t ( j )= Pr( 觀察狀態 | 隱藏狀態j ) x Pr(t時刻所有指向j狀態的路徑）
對于最后的觀察狀態，其局部概率包括了通過所有可能的路徑到達這些狀態的概率——例如，對于上述網格，最終的局部概率通過如下路徑計算得出：
由此可見，對于這些最終局部概率求和等價于對于網格中所有可能的路徑概率求和，也就求出了給定隱馬爾科夫模型(HMM)后的觀察序列概率。
第3節給出了一個計算這些概率的動態示例。
分類 隱馬爾科夫模型
五、前向算法（Forward Algorithm）
計算觀察序列的概率（Finding the probability of an observed sequence）
2b.計算t=1時的局部概率 ’s
我們按如下公式計算局部概率：
t ( j )= Pr( 觀察狀態 | 隱藏狀態j ) x Pr(t時刻所有指向j狀態的路徑）
特別當t=1時，沒有任何指向當前狀態的路徑。故t=1時位于當前狀態的概率是初始概率，即Pr(state|t=1)=P(state)，因此，t=1時的局部概率等于當前狀態的初始概率乘以相關的觀察概率：
所以初始時刻狀態j的局部概率依賴于此狀態的初始概率及相應時刻我們所見的觀察概率。
2c.計算t>1時的局部概率 ’s
我們再次回顧局部概率的計算公式如下：
t ( j )= Pr( 觀察狀態 | 隱藏狀態j ) x Pr(t時刻所有指向j狀態的路徑）
我們可以假設（遞歸地），乘號左邊項“Pr( 觀察狀態 | 隱藏狀態j )”已經有了，現在考慮其右邊項“Pr(t時刻所有指向j狀態的路徑）”。
為了計算到達某個狀態的所有路徑的概率，我們可以計算到達此狀態的每條路徑的概率并對它們求和，例如：
計算 所需要的路徑數目隨著觀察序列的增加而指數級遞增，但是t-1時刻 ’s給出了所有到達此狀態的前一路徑概率，因此，我們可以通過t-1時刻的局部概率定義t時刻的 ’s，即：
故我們所計算的這個概率等于相應的觀察概率（亦即，t+1時在狀態j所觀察到的符號的概率）與該時刻到達此狀態的概率總和——這來自于上一步每一個局部概率的計算結果與相應的狀態轉移概率乘積后再相加——的乘積。
注意我們已經有了一個僅利用t時刻局部概率計算t+1時刻局部概率的表達式。
現在我們就可以遞歸地計算給定隱馬爾科夫模型(HMM)后一個觀察序列的概率了——即通過t=1時刻的局部概率 ’s計算t=2時刻的 ’s，通過t=2時刻的 ’s計算t=3時刻的 ’s等等直到t=T。給定隱馬爾科夫模型(HMM)的觀察序列的概率就等于t=T時刻的局部概率之和。
2d.降低計算復雜度
我們可以比較通過窮舉搜索（評估）和通過遞歸前向算法計算觀察序列概率的時間復雜度。
我們有一個長度為T的觀察序列O以及一個含有n個隱藏狀態的隱馬爾科夫模型l=( ,A,B)。
窮舉搜索將包括計算所有可能的序列：
公式
對我們所觀察到的概率求和——注意其復雜度與T成指數級關系。相反的，使用前向算法我們可以利用上一步計算的信息，相應地，其時間復雜度與T成線性關系。
注：窮舉搜索的時間復雜度是 ，前向算法的時間復雜度是 ，其中T指的是觀察序列長度，N指的是隱藏狀態數目。
3.總結
我們的目標是計算給定隱馬爾科夫模型HMM下的觀察序列的概率——Pr(observations | )。
我們首先通過計算局部概率（ ’s）降低計算整個概率的復雜度，局部概率表示的是t時刻到達某個狀態s的概率。
t=1時，可以利用初始概率(來自于P向量）和觀察概率Pr(observation|state)（來自于混淆矩陣）計算局部概率；而t>1時的局部概率可以利用t-時的局部概率計算。
因此，這個問題是遞歸定義的，觀察序列的概率就是通過依次計算t=1,2,…,T時的局部概率，并且對于t=T時所有局部概率 ’s相加得到的。
注意，用這種方式計算觀察序列概率的時間復雜度遠遠小于計算所有序列的概率并對其相加（窮舉搜索）的時間復雜度。
分類 隱馬爾科夫模型
五、前向算法（Forward Algorithm）
前向算法定義（Forward algorithm definition）
我們使用前向算法計算T長觀察序列的概率:
其中y的每一個是觀察集合之一。局部（中間）概率( ’s)是遞歸計算的，首先通過計算t=1時刻所有狀態的局部概率 ：
然后在每個時間點，t=2，… ，T時，對于每個狀態的局部概率，由下式計算局部概率 :
也就是當前狀態相應的觀察概率與所有到達該狀態的路徑概率之積，其遞歸地利用了上一個時間點已經計算好的一些值。
最后，給定HMM, ,觀察序列的概率等于T時刻所有局部概率之和：
再重復說明一下，每一個局部概率（t > 2 時）都由前一時刻的結果計算得出。
對于“天氣”那個例子，下面的圖表顯示了t = 2為狀態為多云時局部概率 的計算過程。這是相應的觀察概率b與前一時刻的局部概率與狀態轉移概率a相乘后的總和再求積的結果：
總結（Summary）
我們使用前向算法來計算給定隱馬爾科夫模型（HMM）后的一個觀察序列的概率。它在計算中利用遞歸避免對網格所有路徑進行窮舉計算。
給定這種算法，可以直接用來確定對于已知的一個觀察序列，在一些隱馬爾科夫模型（HMMs）中哪一個HMM最好的描述了它——先用前向算法評估每一個（HMM），再選取其中概率最高的一個。
分類 隱馬爾科夫模型
首先需要說明的是，本節不是這個系列的翻譯，而是作為前向算法這一章的補充，希望能從實踐的角度來說明前向算法。除了用程序來解讀hmm的前向算法外，還希望將原文所舉例子的問題拿出來和大家探討。
文中所舉的程序來自于UMDHMM這個C語言版本的HMM工具包，具體見《幾種不同程序語言的HMM版本》。先說明一下UMDHMM這個包的基本情況，在linux環境下，進入umdhmm-v1.02目錄，“make all”之后會產生4個可執行文件，分別是：
genseq: 利用一個給定的隱馬爾科夫模型產生一個符號序列（Generates a symbol sequence using the specified model sequence using the specified model）
testfor: 利用前向算法計算log Prob(觀察序列| HMM模型)（Computes log Prob(observation|model) using the Forward algorithm.）
testvit: 對于給定的觀察符號序列及HMM，利用Viterbi 算法生成最可能的隱藏狀態序列（Generates the most like state sequence for a given symbol sequence, given the HMM, using Viterbi）
esthmm: 對于給定的觀察符號序列，利用BaumWelch算法學習隱馬爾科夫模型HMM（Estimates the HMM from a given symbol sequence using BaumWelch）。
這些可執行文件需要讀入有固定格式的HMM文件及觀察符號序列文件，格式要求及舉例如下：
HMM 文件格式：
——————————————————————–
M= number of symbols
N= number of states
A:
a11 a12 … a1N
a21 a22 … a2N
. . . .
. . . .
. . . .
aN1 aN2 … aNN
B:
b11 b12 … b1M
b21 b22 … b2M
. . . .
. . . .
. . . .
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
——————————————————————–
觀察序列文件格式：
——————————————————————–
T=seqence length
o1 o2 o3 . . . oT
——————————————————————–
觀察序列文件舉例：
——————————————————————–
T= 10
1 1 1 1 2 1 2 2 2 2
——————————————————————–
對于前向算法的測試程序testfor來說，運行：
testfor model.hmm（HMM文件） obs.seq（觀察序列文件）
就可以得到觀察序列的概率結果的對數值，這里我們在testfor.c的第58行對數結果的輸出下再加一行輸出：
fprintf(stdout, “prob(O| model) = %fn”, proba);
就可以輸出運用前向算法計算觀察序列所得到的概率值。至此，所有的準備工作已結束，接下來，我們將進入具體的程序解讀。
首先，需要定義HMM的數據結構，也就是HMM的五個基本要素，在UMDHMM中是如下定義的（在hmm.h中）：
typedef struct
{
int N; /* 隱藏狀態數目;Q={1,2,…,N} */
int M; /* 觀察符號數目; V={1,2,…,M}*/
double **A; /* 狀態轉移矩陣A[1..N][1..N]. a[i][j] 是從t時刻狀態i到t+1時刻狀態j的轉移概率 */
double **B; /* 混淆矩陣B[1..N][1..M]. b[j][k]在狀態j時觀察到符合k的概率。*/
double *pi; /* 初始向量pi[1..N]，pi[i] 是初始狀態概率分布 */
} HMM;
前向算法程序示例如下（在forward.c中）：
/*
函數參數說明：
*phmm：已知的HMM模型；T：觀察符號序列長度；
*O：觀察序列；**alpha：局部概率；*pprob：最終的觀察概率
*/
void Forward(HMM *phmm, int T, int *O, double **alpha, double *pprob)
{
int i, j; /* 狀態索引 */
int t; /* 時間索引 */
double sum; /*求局部概率時的中間值 */
/* 1. 初始化：計算t=1時刻所有狀態的局部概率 ： */
for (i = 1; i <= phmm->N; i++)
alpha[1][i] = phmm->pi[i]* phmm->B[i][O[1]];
/* 2. 歸納：遞歸計算每個時間點，t=2，… ，T時的局部概率 */
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. 終止：觀察序列的概率等于T時刻所有局部概率之和*/
*pprob = 0.0;
for (i = 1; i <= phmm->N; i++)
*pprob += alpha[T][i];
}
下一節我將用這個程序來驗證英文原文中所舉前向算法演示例子的問題。
分類 隱馬爾科夫模型
在HMM這個翻譯系列的原文中，作者舉了一個前向算法的交互例子，這也是這個系列中比較出彩的地方，但是，在具體運行這個例子的時候，卻發現其似乎有點問題。
先說一下如何使用這個交互例子，運行時需要瀏覽器支持java，我用的是firefox。首先在Set按鈕前面的對話框里上觀察序列，如“Dry,Damp, Soggy” 或“Dry Damp Soggy”，觀察符號間用逗號或空格隔開；然后再點擊Set按鈕，這樣就初始化了觀察矩陣；如果想得到一個總的結果，即Pr(觀察序列|隱馬爾科夫模 型)，就點旁邊的Run按鈕；如果想一步一步觀察計算過程，即每個節點的局部概率，就單擊旁邊的Step按鈕。
原文交互例子（即天氣這個例子）中所定義的已知隱馬爾科夫模型如下：
1、隱藏狀態 (天氣)：Sunny，Cloudy，Rainy；
2、觀察狀態（海藻濕度）：Dry，Dryish，Damp，Soggy；
3、初始狀態概率： Sunny（0.63）， Cloudy（0.17）， Rainy（0.20）；
4、狀態轉移矩陣：
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也能運行這個例子，我們將上述天氣例子中的隱馬爾科夫模型轉化為如下的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
——————————————————————–
在運行例子之前，如果讀者也想觀察每一步的運算結果，可以將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來運行原文中默認給出的觀察序列“Dry,Damp,Soggy”，其所對應的UMDHMM可讀的觀察序列文件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 = 0.378000
a[1][2] = pi[2] * b[2][3] = 0.170000 * 0.250000 = 0.042500
a[1][3] = pi[3] * b[3][4] = 0.200000 * 0.050000 = 0.010000
…
pprob = 0.026901
log prob(O| model) = -3.615577E+00
prob(O| model) = 0.026901
…
——————————————————————–
黑體部分是最終的觀察序列的概率結果，即本例中的Pr(觀察序列|HMM) = 0.026901。
但是，在原文中點Run按鈕后，結果卻是：Probability of this model = 0.027386915。
這其中的差別到底在哪里？我們來仔細觀察一下中間運行過程：
在初始化亦t=1時刻的局部概率計算兩個是一致的，沒有問題。但是，t=2時，在隱藏狀態“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
——————————————————————–
區別就在于狀態轉移概率的選擇上，原文選擇的是狀態轉移矩陣中的第一行，而UMDHMM選擇的則是狀態轉移矩陣中的第一列。如果從原文給出的狀態轉移矩陣來看，第一行代表的是從前一時刻的狀態“Sunny”分別到當前時刻的狀態“Sunny”，“Cloudy”，“Rainy”的概率；而第一列代表的 是從前一時刻的狀態“Sunny”，“Cloudy”，“Rainy”分別到當前時刻狀態“Sunny”的概率。這樣看來似乎原文的計算過程有誤，讀者不 妨多試幾個例子看看，前向算法這一章就到此為止了。
分類 隱馬爾科夫模型
六、維特比算法（Viterbi Algorithm）
尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)
對于一個特殊的隱馬爾科夫模型(HMM)及一個相應的觀察序列，我們常常希望能找到生成此序列最可能的隱藏狀態序列。
1.窮舉搜索
我們使用下面這張網格圖片來形象化的說明隱藏狀態和觀察狀態之間的關系：
我們可以通過列出所有可能的隱藏狀態序列并且計算對于每個組合相應的觀察序列的概率來找到最可能的隱藏狀態序列。最可能的隱藏狀態序列是使下面這個概率最大的組合：
Pr（觀察序列|隱藏狀態的組合）
例如，對于網格中所顯示的觀察序列，最可能的隱藏狀態序列是下面這些概率中最大概率所對應的那個隱藏狀態序列：
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)
這種方法是可行的，但是通過窮舉計算每一個組合的概率找到最可能的序列是極為昂貴的。與前向算法類似，我們可以利用這些概率的時間不變性來降低計算復雜度。
2.使用遞歸降低復雜度
給定一個觀察序列和一個隱馬爾科夫模型（HMM），我們將考慮遞歸地尋找最有可能的隱藏狀態序列。我們首先定義局部概率 ,它是到達網格中的某個特殊的中間狀態時的概率。然后，我們將介紹如何在t=1和t=n(>1)時計算這些局部概率。
這些局部概率與前向算法中所計算的局部概率是不同的，因為它們表示的是時刻t時到達某個狀態最可能的路徑的概率，而不是所有路徑概率的總和。
2a.局部概率 ’s和局部最佳途徑
考慮下面這個網格，它顯示的是天氣狀態及對于觀察序列干燥，濕潤及濕透的一階狀態轉移情況：
對于網格中的每一個中間及終止狀態，都有一個到達該狀態的最可能路徑。舉例來說，在t=3時刻的3個狀態中的每一個都有一個到達此狀態的最可能路徑，或許是這樣的：
我們稱這些路徑局部最佳路徑(partial best paths)。其中每個局部最佳路徑都有一個相關聯的概率，即局部概率或 。與前向算法中的局部概率不同， 是到達該狀態（最可能）的一條路徑的概率。
因而 (i,t)是t時刻到達狀態i的所有序列概率中最大的概率，而局部最佳路徑是得到此最大概率的隱藏狀態序列。對于每一個可能的i和t值來說，這一類概率（及局部路徑）均存在。
特別地，在t=T時每一個狀態都有一個局部概率和一個局部最佳路徑。這樣我們就可以通過選擇此時刻包含最大局部概率的狀態及其相應的局部最佳路徑來確定全局最佳路徑（最佳隱藏狀態序列）。
分類 隱馬爾科夫模型
六、維特比算法（Viterbi Algorithm）
尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)
2b.計算t=1時刻的局部概率 ’s
我們計算的局部概率 是作為最可能到達我們當前位置的路徑的概率（已知的特殊知識如觀察概率及前一個狀態的概率）。當t=1的時候，到達某狀態的最可能路徑明顯是不存在的；但是，我們使用t=1時的所處狀態的初始概率及相應的觀察狀態k1的觀察概率計算局部概率 ；即
——與前向算法類似，這個結果是通過初始概率和相應的觀察概率相乘得出的。
2c.計算t>1時刻的局部概率 ’s
現在我們來展示如何利用t-1時刻的局部概率 計算t時刻的局部概率 。
考慮如下的網格：
我們考慮計算t時刻到達狀態X的最可能的路徑；這條到達狀態X的路徑將通過t-1時刻的狀態A，B或C中的某一個。
因此，最可能的到達狀態X的路徑將是下面這些路徑的某一個
（狀態序列），…，A，X
（狀態序列），…，B，X
或 （狀態序列），…，C，X
我們想找到路徑末端是AX,BX或CX并且擁有最大概率的路徑。
回顧一下馬爾科夫假設：給定一個狀態序列，一個狀態發生的概率只依賴于前n個狀態。特別地，在一階馬爾可夫假設下，狀態X在一個狀態序列后發生的概率只取決于之前的一個狀態，即
Pr (到達狀態A最可能的路徑) .Pr (X | A) . Pr (觀察狀態 | X)
與此相同，路徑末端是AX的最可能的路徑將是到達A的最可能路徑再緊跟X。相似地，這條路徑的概率將是：
Pr (到達狀態A最可能的路徑) .Pr (X | A) . Pr (觀察狀態 | X)
因此，到達狀態X的最可能路徑概率是：
其中第一項是t-1時刻的局部概率 ，第二項是狀態轉移概率以及第三項是觀察概率。
泛化上述公式，就是在t時刻，觀察狀態是kt，到達隱藏狀態i的最佳局部路徑的概率是：
這里，我們假設前一個狀態的知識（局部概率）是已知的，同時利用了狀態轉移概率和相應的觀察概率之積。然后，我們就可以在其中選擇最大的概率了（局部概率 ）。
分類 隱馬爾科夫模型
六、維特比算法（Viterbi Algorithm）
尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)
2d.反向指針， ’s
考慮下面這個網格
在每一個中間及終止狀態我們都知道了局部概率， (i,t)。然而我們的目標是在給定一個觀察序列的情況下尋找網格中最可能的隱藏狀態序列——因此，我們需要一些方法來記住網格中的局部最佳路徑。
回顧一下我們是如何計算局部概率的，計算t時刻的 ’s我們僅僅需要知道t-1時刻的 ’s。在這個局部概率計算之后，就有可能記錄前一時刻哪個狀態生成了 (i,t)——也就是說，在t-1時刻系統必須處于某個狀態，該狀態導致了系統在t時刻到達狀態i是最優的。這種記錄（記憶）是通過對每一個狀態賦予一個反向指針 完成的，這個指針指向最優的引發當前狀態的前一時刻的某個狀態。
形式上，我們可以寫成如下的公式
其中argmax運算符是用來計算使括號中表達式的值最大的索引j的。
請注意這個表達式是通過前一個時間步驟的局部概率 ’s和轉移概率計算的，并不包括觀察概率（與計算局部概率 ’s本身不同）。這是因為我們希望這些 ’s能回答這個問題“如果我在這里，最可能通過哪條路徑到達下一個狀態？”——這個問題與隱藏狀態有關，因此與觀察概率有關的混淆（矩陣）因子是可以被忽略的。
2e.維特比算法的優點
使用Viterbi算法對觀察序列進行解碼有兩個重要的優點：
1. 通過使用遞歸減少計算復雜度——這一點和前向算法使用遞歸減少計算復雜度是完全類似的。
2.維特比算法有一個非常有用的性質，就是對于觀察序列的整個上下文進行了最好的解釋（考慮）。事實上，尋找最可能的隱藏狀態序列不止這一種方法，其他替代方法也可以，譬如，可以這樣確定如下的隱藏狀態序列：
其中
這里，采用了“自左向右”的決策方式進行一種近似的判斷，其對于每個隱藏狀態的判斷是建立在前一個步驟的判斷的基礎之上（而第一步從隱藏狀態的初始向量 開始）。
這種做法，如果在整個觀察序列的中部發生“噪音干擾”時，其最終的結果將與正確的答案嚴重偏離。
相反， 維特比算法在確定最可能的終止狀態前將考慮整個觀察序列，然后通過 指針“回溯”以確定某個隱藏狀態是否是最可能的隱藏狀態序列中的一員。這是非常有用的，因為這樣就可以孤立序列中的“噪音”，而這些“噪音”在實時數據中是很常見的。
3.小結
維特比算法提供了一種有效的計算方法來分析隱馬爾科夫模型的觀察序列，并捕獲最可能的隱藏狀態序列。它利用遞歸減少計算量，并使用整個序列的上下文來做判斷，從而對包含“噪音”的序列也能進行良好的分析。
在使用時，維特比算法對于網格中的每一個單元(cell)都計算一個局部概率，同時包括一個反向指針用來指示最可能的到達該單元的路徑。當完成整個計算過程后，首先在終止時刻找到最可能的狀態，然后通過反向指針回溯到t=1時刻，這樣回溯路徑上的狀態序列就是最可能的隱藏狀態序列了。
分類 隱馬爾科夫模型
六、維特比算法（Viterbi Algorithm）
維特比算法定義(Viterbi algorithm definition)
1、維特比算法的形式化定義
維特比算法可以形式化的概括為：
對于每一個i，i = 1，… ，n，令：
——這一步是通過隱藏狀態的初始概率和相應的觀察概率之積計算了t=1時刻的局部概率。
對于t=2，…，T和i=1，…，n,令：
——這樣就確定了到達下一個狀態的最可能路徑，并對如何到達下一個狀態做了記錄。具體來說首先通過考察所有的轉移概率與上一步獲得的最大的局部概率之積，然后記錄下其中最大的一個，同時也包含了上一步觸發此概率的狀態。
令：
——這樣就確定了系統完成時(t=T)最可能的隱藏狀態。
對于t=T-1，…，1
令：
——這樣就可以按最可能的狀態路徑在整個網格回溯。回溯完成時，對于觀察序列來說，序列i1 … iT就是生成此觀察序列的最可能的隱藏狀態序列。
2.計算單獨的 ’s和 ’s
維特比算法中的局部概率 ’s的計算與前向算法中的局部概率 ’s的很相似。下面這幅圖表顯示了 ’s和 ’s的計算細節，可以對比一下前向算法3中的計算局部概率 ’s的那幅圖表：
唯一不同的是前向算法中計算局部概率 ’s時的求和符號（ ）在維特比算法中計算局部概率 ’s時被替換為max——這一個重要的不同也說明了在維特比算法中我們選擇的是到達當前狀態的最可能路徑，而不是總的概率。我們在維特比算法中維護了一個“反向指針”記錄了到達當前狀態的最佳路徑，即在計算 ’s時通過argmax運算符獲得。
總結(Summary)
對于一個特定的隱馬爾科夫模型，維特比算法被用來尋找生成一個觀察序列的最可能的隱藏狀態序列。我們利用概率的時間不變性，通過避免計算網格中每一條路徑的概率來降低問題的復雜度。維特比算法對于每一個狀態(t>1)都保存了一個反向指針( )，并在每一個狀態中存儲了一個局部概率( )。
局部概率 是由反向指針指示的路徑到達某個狀態的概率。
當t=T時，維特比算法所到達的這些終止狀態的局部概率 ’s是按照最優（最可能）的路徑到達該狀態的概率。因此，選擇其中最大的一個，并回溯找出所隱藏的狀態路徑，就是這個問題的最好答案。
關于維特比算法，需要著重強調的一點是它不是簡單的對于某個給定的時間點選擇最可能的隱藏狀態，而是基于全局序列做決策——因此，如果在觀察序列中有一個“非尋常”的事件發生，對于維特比算法的結果也影響不大。
這在語音處理中是特別有價值的，譬如當某個單詞發音的一個中間音素出現失真或丟失的情況時，該單詞也可以被識別出來。
分類 隱馬爾科夫模型
六、維特比算法（Viterbi Algorithm）
維特比算法程序示例
仍然需要說明的是，本節不是這個系列的翻譯，而是作為維特比算法這一章的補充，將UMDHMM這個C語言版本的HMM工具包中的維特比算法程序展示給大家，并運行包中所附帶的例子。關于UMDHMM這個工具包的介紹，大家可以參考前向算法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個可執行程序中，testvit是用來測試維特比算法的， 對于給定的觀察符號序列及HMM，利用Viterbi 算法生成最可能的隱藏狀態序列。這里我們利用UMDHMM包中test.hmm和test.seq來測試維特比算法，關于這兩個文件，具體如下：
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來說，運行：
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 3”就是最終所找到的隱藏狀態序列。好了，維特比算法這一章就到此為止了。
分類 隱馬爾科夫模型
七、前向-后向算法(Forward-backward algorithm)
根據觀察序列生成隱馬爾科夫模型(Generating a HMM from a sequence of obersvations)
與HMM模型相關的“有用”的問題是評估（前向算法）和解碼（維特比算法）——它們一個被用來測量一個模型的相對適用性，另一個被用來推測模型隱藏的部分在做什么（“到底發生了”什么）。可以看出它們都依賴于隱馬爾科夫模型（HMM）參數這一先驗知識——狀態轉移矩陣，混淆（觀察）矩陣，以及 向量（初始化概率向量）。
然而，在許多實際問題的情況下這些參數都不能直接計算的，而要需要進行估計——這就是隱馬爾科夫模型中的學習問題。前向-后向算法就可以以一個觀察序 列為基礎來進行這樣的估計，而這個觀察序列來自于一個給定的集合，它所代表的是一個隱馬爾科夫模型中的一個已知的隱藏集合。
一個例子可能是一個龐大的語音處理數據庫，其底層的語音可能由一個馬爾可夫過程基于已知的音素建模的，而其可以觀察的部分可能由可識別的狀態（可能通過一些矢量數據表示）建模的，但是沒有（直接）的方式來獲取隱馬爾科夫模型（HMM）參數。
前向-后向算法并非特別難以理解，但自然地比前向算法和維特比算法更復雜。由于這個原因，這里就不詳細講解前向-后向算法了（任何有關HMM模型的參考文獻都會提供這方面的資料的）。
總之，前向-后向算法首先對于隱馬爾科夫模型的參數進行一個初始的估計（這很可能是完全錯誤的），然后通過對于給定的數據評估這些參數的的價值并減少它們所引起的錯誤來重新修訂這些HMM參數。從這個意義上講，它是以一種梯度下降的形式尋找一種錯誤測度的最小值。
之所以稱其為前向-后向算法，主要是因為對于網格中的每一個狀態，它既計算到達此狀態的“前向”概率（給定當前模型的近似估計），又計算生成此模型最 終狀態的“后向”概率（給定當前模型的近似估計）。 這些都可以通過利用遞歸進行有利地計算，就像我們已經看到的。可以通過利用近似的HMM模型參數來提高這些中間概率進行調整，而這些調整又形成了前向-后 向算法迭代的基礎。
注：關于前向-后向算法，原文只講了這么多，后繼我將按自己的理解補充一些內容。
分類 隱馬爾科夫模型
七、前向-后向算法(Forward-backward algorithm)
要理解前向-后向算法，首先需要了解兩個算法：后向算法和EM算法。后向算法是必須的，因為前向-后向算法就是利用了前向算法與后向算法中的變 量因子，其得名也因于此；而EM算法不是必須的，不過由于前向-后向算法是EM算法的一個特例，因此了解一下EM算法也是有好處的，說實話，對于EM算 法，我也是云里霧里的。好了，廢話少說，我們先談談后向算法。
1、后向算法（Backward algorithm）
其實如果理解了前向算法，后向算法也是比較好理解的，這里首先重新定義一下前向算法中的局部概率at(i)，稱其為前向變量，這也是為前向-后向算法做點準備：
相似地，我們也可以定義一個后向變量Bt(i)（同樣可以理解為一個局部概率）：
后向變量(局部概率)表示的是已知隱馬爾科夫模型 及t時刻位于隱藏狀態Si這一事實，從t+1時刻到終止時刻的局部觀察序列的概率。同樣與前向算法相似，我們可以從后向前（故稱之為后向算法）遞歸地計算后向變量：
1）初始化，令t=T時刻所有狀態的后向變量為1：
2）歸納，遞歸計算每個時間點，t=T-1,T-2,…,1時的后向變量：
這樣就可以計算每個時間點上所有的隱藏狀態所對應的后向變量，如果需要利用后向算法計算觀察序列的概率，只需將t=1時刻的后向變量（局部概率）相加即可。下圖顯示的是t+1時刻與t時刻的后向變量之間的關系：
上述主要參考自HMM經典論文《A tutorial on Hidden Markov Models and selected applications in speech recognition》。下面我們給出利用后向算法計算觀察序列概率的程序示例，這個程序仍然來自于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];
}
好了，后向算法就到此為止了，下一節我們粗略的談談EM算法。
分類 隱馬爾科夫模型
七、前向-后向算法(Forward-backward algorithm)
前向-后向算法是Baum于1972年提出來的，又稱之為Baum-Welch算法，雖然它是EM(Expectation- Maximization)算法的一個特例，但EM算法卻是于1977年提出的。那么為什么說前向-后向算法是EM算法的一個特例呢？這里有兩點需要說明 一下。
第一，1977年A. P. Dempster、N. M. Laird、 D. B. Rubin在其論文“Maximum Likelihood from Incomplete Data via the EM Algorithm”中首次提出了EM算法的概念，但是他們也在論文的介紹中提到了在此之前就有一些學者利用了EM算法的思想解決了一些特殊問題，其中就包括了Baum在70年代初期的相關工作，只是這類方法沒有被總結而已，他們的工作就是對這類解決問題的方法在更高的層次上定義了一個完整的EM算法框 架。
第二，對于前向-后向算法與EM算法的關系，此后在許多與HMM或EM相關的論文里都被提及，其中賈里尼克（Jelinek）老先生在1997所著的 書“Statistical Methods for Speech Recognition”中對于前向-后向算法與EM算法的關系進行了完整的描述，讀者有興趣的話可以找來這本書讀讀。
關于EM算法的講解，網上有很多，這里我就不獻丑了，直接拿目前搜索“EM算法”在Google排名第一的文章做了參考，希望讀者不要拍磚：
EM 算法是 Dempster，Laind，Rubin 于 1977 年提出的求參數極大似然估計的一種方法，它可以從非完整數據集中對參數進行 MLE 估計，是一種非常簡單實用的學習算法。這種方法可以廣泛地應用于處理缺損數據，截尾數據，帶有討厭數據等所謂的不完全數據(incomplete data)。
假定集合Z = (X,Y)由觀測數據 X 和未觀測數據Y 組成，Z = (X,Y)和 X 分別稱為完整數據和不完整數據。假設Z的聯合概率密度被參數化地定義為P(X，Y|Θ)，其中Θ 表示要被估計的參數。Θ 的最大似然估計是求不完整數據的對數似然函數L(X;Θ)的最大值而得到的：
L(Θ; X )= log p(X |Θ) = ∫log p(X ,Y |Θ)dY ；(1)
EM算法包括兩個步驟：由E步和M步組成，它是通過迭代地最大化完整數據的對數似然函數Lc( X;Θ )的期望來最大化不完整數據的對數似然函數，其中：
Lc(X;Θ) =log p(X，Y |Θ) ； (2)
假設在算法第t次迭代后Θ 獲得的估計記為Θ(t ) ，則在（t+1）次迭代時，
E-步：計算完整數據的對數似然函數的期望，記為：
Q(Θ |Θ (t) ) = E{Lc(Θ;Z)|X;Θ(t) }； (3)
M-步：通過最大化Q(Θ |Θ(t) ) 來獲得新的Θ 。
通過交替使用這兩個步驟，EM算法逐步改進模型的參數，使參數和訓練樣本的似然概率逐漸增大，最后終止于一個極大點。
直 觀地理解EM算法，它也可被看作為一個逐次逼近算法：事先并不知道模型的參數，可以隨機的選擇一套參數或者事先粗略地給定某個初始參數λ0 ，確定出對應于這組參數的最可能的狀態，計算每個訓練樣本的可能結果的概率，在當前的狀態下再由樣本對參數修正，重新估計參數λ ，并在新的參數下重新確定模型的狀態，這樣，通過多次的迭代，循環直至某個收斂條件滿足為止，就可以使得模型的參數逐漸逼近真實參數。
EM算法的主要目的是提供一個簡單的迭代算法計算后驗密度函數，它的最大優點是簡單和穩定，但容易陷入局部最優。
參考原文見：http://49805085.spaces./Blog/cns!145C40DDDB4C6E5!670.entry
注意上面那段粗體字，讀者如果覺得EM算法不好理解的話，就記住這段粗體字的意思吧！
有了后向算法和EM算法的預備知識，下一節我們就正式的談一談前向-后向算法。
分類 隱馬爾科夫模型
七、前向-后向算法(Forward-backward algorithm)
隱馬爾科夫模型（HMM）的三個基本問題中，第三個HMM參數學習的問題是最難的，因為對于給定的觀察序列O，沒有任何一種方法可以精確地找到一組最優的隱馬爾科夫模型參數（A、B、 ）使P(O| )最大。因而，學者們退而求其次，不能使P(O| )全局最優，就尋求使其局部最優（最大化）的解決方法，而前向-后向算法（又稱之為Baum-Welch算法）就成了隱馬爾科夫模型學習問題的一種替代（近似）解決方法。
我們首先定義兩個變量。給定觀察序列O及隱馬爾科夫模型 ，定義t時刻位于隱藏狀態Si的概率變量為：
回顧一下第二節中關于前向變量at(i)及后向變量Bt(i)的定義，我們可以很容易地將上式用前向、后向變量表示為：
其中分母的作用是確保：
給定觀察序列O及隱馬爾科夫模型 ，定義t時刻位于隱藏狀態Si及t+1時刻位于隱藏狀態Sj的概率變量為：
該變量在網格中所代表的關系如下圖所示：
同樣，該變量也可以由前向、后向變量表示：
而上述定義的兩個變量間也存在著如下關系：
如果對于時間軸t上的所有 相加，我們可以得到一個總和，它可以被解釋為從其他隱藏狀態訪問Si的期望值（網格中的所有時間的期望），或者，如果我們求和時不包括時間軸上的t=T時刻，那么它可以被解釋為從隱藏狀態Si出發的狀態轉移期望值。相似地，如果對 在時間軸t上求和（從t=1到t=T-1），那么該和可以被解釋為從狀態Si到狀態Sj的狀態轉移期望值。即：
分類 隱馬爾科夫模型
七、前向-后向算法(Forward-backward algorithm)
上一節我們定義了兩個變量及相應的期望值，本節我們利用這兩個變量及其期望值來重新估計隱馬爾科夫模型（HMM）的參數 ，A及B：
如果我們定義當前的HMM模型為 ，那么可以利用該模型計算上面三個式子的右端；我們再定義重新估計的HMM模型為 ，那么上面三個式子的左端就是重估的HMM模型參數。Baum及他的同事在70年代證明了 因此如果我們迭代地的計算上面三個式子，由此不斷地重新估計HMM的參數，那么在多次迭代后可以得到的HMM模型的一個最大似然估計。不過需要注意的是，前向-后向算法所得的這個結果（最大似然估計）是一個局部最優解。
關于前向-后向算法和EM算法的具體關系的解釋，大家可以參考HMM經典論文《A tutorial on Hidden Markov Models and selected applications in speech recognition》，這里就不詳述了。下面我們給出UMDHMM中的前向-后向算法示例，這個算法比較復雜，這里只取主函數，其中所引用的函數大家如果感興趣的話可以自行參考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);
}
前向-后向算法就到此為止了。
分類 隱馬爾科夫模型
八、總結(Summary)
通常，模式并不是單獨的出現，而是作為時間序列中的一個部分——這個過程有時候可以被輔助用來對它們進行識別。在基于時間的進程中，通常都會使用一些假設——一個最常用的假設是進程的狀態只依賴于前面N個狀態——這樣我們就有了一個N階馬爾科夫模型。最簡單的例子是N = 1。
存在很多例子，在這些例子中進程的狀態（模式）是不能夠被直接觀察的，但是可以非直接地，或者概率地被觀察為模式的另外一種集合——這樣我們就可以定義一類隱馬爾科夫模型——這些模型已被證明在當前許多研究領域，尤其是語音識別領域具有非常大的價值。
在實際的過程中這些模型提出了三個問題都可以得到立即有效的解決，分別是：
* 評估：對于一個給定的隱馬爾科夫模型其生成一個給定的觀察序列的概率是多少。前向算法可以有效的解決此問題。
* 解碼：什么樣的隱藏（底層）狀態序列最有可能生成一個給定的觀察序列。維特比算法可以有效的解決此問題。
* 學習：對于一個給定的觀察序列樣本，什么樣的模型最可能生成該序列——也就是說，該模型的參數是什么。這個問題可以通過使用前向-后向算法解決。
隱馬爾科夫模型（HMM）在分析實際系統中已被證明有很大的價值；它們通常的缺點是過于簡化的假設，這與馬爾可夫假設相關——即一個狀態只依賴于前一個狀態，并且這種依賴關系是獨立于時間之外的（與時間無關）。
關于隱馬爾科夫模型的完整論述，可參閱：
L R Rabiner and B H Juang, `An introduction to HMMs’, iEEE ASSP Magazine, 3, 4-16.
全文完！
后記：這個翻譯系列終于可以告一段落了，從6月2日起至今，歷史四個多月，期間斷斷續續翻譯并夾雜些自己個人的理解，希望這個系列對于HMM的 學習者能有些用處，我個人也就很滿足了。接下來，我會結合HMM在自然語言處理中的一些典型應用，譬如詞性標注、中文分詞等，從實踐的角度講講自己的理解，歡迎大家繼續關注52nlp。
本文翻譯自：http://www.comp./roger/HiddenMarkovModels/html_dev/main.html
部分翻譯參考：隱馬爾科夫模型HMM自學
轉載請注明出處“我愛自然語言處理”：www.
本文鏈接地址：http://www./hmm-learn-best-practices-eight-summary
