HMM學(xué)習(xí)最佳范例一：介紹

分類 隱馬爾科夫模型 

　　隱馬爾科夫模型（HMM）依然是讀者訪問“我愛自然語言處理”的一個熱門相關(guān)關(guān)鍵詞，我曾在《HMM學(xué)習(xí)最佳范例與崔曉源的博客》中介紹過國外的一個不錯的HMM學(xué)習(xí)教程，并且國內(nèi)崔曉源師兄有一個相應(yīng)的翻譯版本，不過這個版本比較簡化和粗略，有些地方只是概況性的翻譯了一下，省去了一些內(nèi)容，所以從今天開始計劃在52nlp上系統(tǒng)的重新翻譯這個學(xué)習(xí)教程，希望對大家有點用。

一、介紹（Introduction）
　　我們通常都習(xí)慣尋找一個事物在一段時間里的變化模式（規(guī)律）。這些模式發(fā)生在很多領(lǐng)域，比如計算機中的指令序列，句子中的詞語順序和口語單詞中的音素序列等等，事實上任何領(lǐng)域中的一系列事件都有可能產(chǎn)生有用的模式。
　　考慮一個簡單的例子，有人試圖通過一片海藻推斷天氣——民間傳說告訴我們‘濕透的’海藻意味著潮濕陰雨，而‘干燥的’海藻則意味著陽光燦爛。如果它處 于一個中間狀態(tài)（‘有濕氣’），我們就無法確定天氣如何。然而，天氣的狀態(tài)并沒有受限于海藻的狀態(tài)，所以我們可以在觀察的基礎(chǔ)上預(yù)測天氣是雨天或晴天的可 能性。另一個有用的線索是前一天的天氣狀態(tài)（或者，至少是它的可能狀態(tài)）——通過綜合昨天的天氣及相應(yīng)觀察到的海藻狀態(tài)，我們有可能更好的預(yù)測今天的天 氣。
　　這是本教程中我們將考慮的一個典型的系統(tǒng)類型。
　　首先，我們將介紹產(chǎn)生概率模式的系統(tǒng)，如晴天及雨天間的天氣波動。
　　然后，我們將會看到這樣一個系統(tǒng)，我們希望預(yù)測的狀態(tài)并不是觀察到的——其底層系統(tǒng)是隱藏的。在上面的例子中，觀察到的序列將是海藻而隱藏的系統(tǒng)將是實際的天氣。
　　最后，我們會利用已經(jīng)建立的模型解決一些實際的問題。對于上述例子，我們想知道：
　　1. 給出一個星期每天的海藻觀察狀態(tài)，之后的天氣將會是什么?
　　2. 給定一個海藻的觀察狀態(tài)序列，預(yù)測一下此時是冬季還是夏季？直觀地，如果一段時間內(nèi)海藻都是干燥的，那么這段時間很可能是夏季，反之，如果一段時間內(nèi)海藻都是潮濕的，那么這段時間可能是冬季。

HMM學(xué)習(xí)最佳范例二：生成模式

分類 隱馬爾科夫模型 

二、生成模式（Generating Patterns）

1、確定性模式（Deterministic Patterns）
　　考慮一套交通信號燈，燈的顏色變化序列依次是紅色-紅色/黃色-綠色-黃色-紅色。這個序列可以作為一個狀態(tài)機器，交通信號燈的不同狀態(tài)都緊跟著上一個狀態(tài)。
　　　　
　　注意每一個狀態(tài)都是唯一的依賴于前一個狀態(tài)，所以，如果交通燈為綠色，那么下一個顏色狀態(tài)將始終是黃色——也就是說，該系統(tǒng)是確定性的。確定性系統(tǒng)相對比較容易理解和分析，因為狀態(tài)間的轉(zhuǎn)移是完全已知的。

2、非確定性模式（Non-deterministic patterns）
　　為了使天氣那個例子更符合實際，加入第三個狀態(tài)——多云。與交通信號燈例子不同，我們并不期望這三個天氣狀態(tài)之間的變化是確定性的，但是我們依然希望對這個系統(tǒng)建模以便生成一個天氣變化模式（規(guī)律）。
　　一種做法是假設(shè)模型的當(dāng)前狀態(tài)僅僅依賴于前面的幾個狀態(tài)，這被稱為馬爾科夫假設(shè)，它極大地簡化了問題。顯然，這可能是一種粗糙的假設(shè)，并且因此可能將一些非常重要的信息丟失。
　　當(dāng)考慮天氣問題時，馬爾科夫假設(shè)假定今天的天氣只能通過過去幾天已知的天氣情況進行預(yù)測——而對于其他因素，譬如風(fēng)力、氣壓等則沒有考慮。在這個例子以及其他相似的例子中，這樣的假設(shè)顯然是不現(xiàn)實的。然而，由于這樣經(jīng)過簡化的系統(tǒng)可以用來分析，我們常常接受這樣的知識假設(shè)，雖然它產(chǎn)生的某些信息不完全 準(zhǔn)確。
　　　　　　　　　　 　 　
　　一個馬爾科夫過程是狀態(tài)間的轉(zhuǎn)移僅依賴于前n個狀態(tài)的過程。這個過程被稱之為n階馬爾科夫模型，其中n是影響下一個狀態(tài)選擇的（前）n個狀態(tài)。最簡單 的馬爾科夫過程是一階模型，它的狀態(tài)選擇僅與前一個狀態(tài)有關(guān)。這里要注意它與確定性系統(tǒng)并不相同，因為下一個狀態(tài)的選擇由相應(yīng)的概率決定，并不是確定性的。
　　下圖是天氣例子中狀態(tài)間所有可能的一階狀態(tài)轉(zhuǎn)移情況：
　　　　
　　對于有M個狀態(tài)的一階馬爾科夫模型，共有 個狀態(tài)轉(zhuǎn)移，因為任何一個狀態(tài)都有可能是所有狀態(tài)的下一個轉(zhuǎn)移狀態(tài)。每一個狀態(tài)轉(zhuǎn)移都有一個概率值，稱為狀態(tài)轉(zhuǎn)移概率——這是從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)的概率。所有的 個概率可以用一個狀態(tài)轉(zhuǎn)移矩陣表示。注意這些概率并不隨時間變化而不同——這是一個非常重要（但常常不符合實際）的假設(shè)。
　　下面的狀態(tài)轉(zhuǎn)移矩陣顯示的是天氣例子中可能的狀態(tài)轉(zhuǎn)移概率：
　　　　
　　-也就是說，如果昨天是晴天，那么今天是晴天的概率為0.5，是多云的概率為0.375。注意，每一行的概率之和為1。
　　要初始化這樣一個系統(tǒng)，我們需要確定起始日天氣的（或可能的）情況，定義其為一個初始概率向量，稱為 向量。
　　　　　　　　　　
　　-也就是說，第一天為晴天的概率為1。
　　現(xiàn)在我們定義一個一階馬爾科夫過程如下：
　　　狀態(tài)：三個狀態(tài)——晴天，多云，雨天。
　　　 向量：定義系統(tǒng)初始化時每一個狀態(tài)的概率。
　　　狀態(tài)轉(zhuǎn)移矩陣：給定前一天天氣情況下的當(dāng)前天氣概率。
　　任何一個可以用這種方式描述的系統(tǒng)都是一個馬爾科夫過程。

3、總結(jié)
　　我們嘗試識別時間變化中的模式，并且為了達(dá)到這個目我們試圖對這個過程建模以便產(chǎn)生這樣的模式。我們使用了離散時間點、離散狀態(tài)以及做了馬爾科夫假設(shè)。在采用了這些假設(shè)之后，系統(tǒng)產(chǎn)生了這個被描述為馬爾科夫過程的模式，它包含了一個 向量（初始概率）和一個狀態(tài)轉(zhuǎn)移矩陣。關(guān)于假設(shè)，重要的一點是狀態(tài)轉(zhuǎn)移矩陣并不隨時間的改變而改變——這個矩陣在整個系統(tǒng)的生命周期中是固定不變的。

HMM學(xué)習(xí)最佳范例三：隱藏模式

分類 隱馬爾科夫模型 

三、隱藏模式（Hidden Patterns）

1、馬爾科夫過程的局限性
　　在某些情況下，我們希望找到的模式用馬爾科夫過程描述還顯得不充分?；仡櫼幌绿鞖饽莻€例子，一個隱士也許不能夠直接獲取到天氣的觀察情況，但是他有一些水藻。民間傳說告訴我們水藻的狀態(tài)與天氣狀態(tài)有一定的概率關(guān)系——天氣和水藻的狀態(tài)是緊密相關(guān)的。在這個例子中我們有兩組狀態(tài)，觀察的狀態(tài)（水藻的狀態(tài)）和隱藏的狀態(tài)（天氣的狀態(tài)）。我們希望為隱士設(shè)計一種算法，在不能夠直接觀察天氣的情況下，通過水藻和馬爾科夫假設(shè)來預(yù)測天氣。
　　一個更實際的問題是語音識別，我們聽到的聲音是來自于聲帶、喉嚨大小、舌頭位置以及其他一些東西的組合結(jié)果。所有這些因素相互作用產(chǎn)生一個單詞的聲音，一套語音識別系統(tǒng)檢測的聲音就是來自于個人發(fā)音時身體內(nèi)部物理變化所引起的不斷改變的聲音。
　　一些語音識別裝置工作的原理是將內(nèi)部的語音產(chǎn)出看作是隱藏的狀態(tài)，而將聲音結(jié)果作為一系列觀察的狀態(tài)，這些由語音過程生成并且最好的近似了實際（隱 藏）的狀態(tài)。在這兩個例子中，需要著重指出的是，隱藏狀態(tài)的數(shù)目與觀察狀態(tài)的數(shù)目可以是不同的。一個包含三個狀態(tài)的天氣系統(tǒng)（晴天、多云、雨天）中，可以觀察到4個等級的海藻濕潤情況（干、稍干、潮濕、濕潤）；純粹的語音可以由80個音素描述，而身體的發(fā)音系統(tǒng)會產(chǎn)生出不同數(shù)目的聲音，或者比80多，或者 比80少。
　　在這種情況下，觀察到的狀態(tài)序列與隱藏過程有一定的概率關(guān)系。我們使用隱馬爾科夫模型對這樣的過程建模，這個模型包含了一個底層隱藏的隨時間改變的馬爾科夫過程，以及一個與隱藏狀態(tài)某種程度相關(guān)的可觀察到的狀態(tài)集合。

2、隱馬爾科夫模型（Hidden Markov Models）
　　下圖顯示的是天氣例子中的隱藏狀態(tài)和觀察狀態(tài)。假設(shè)隱藏狀態(tài)（實際的天氣）由一個簡單的一階馬爾科夫過程描述，那么它們之間都相互連接。
　　
　　隱藏狀態(tài)和觀察狀態(tài)之間的連接表示：在給定的馬爾科夫過程中，一個特定的隱藏狀態(tài)生成特定的觀察狀態(tài)的概率。這很清晰的表示了‘進入’一個觀察狀態(tài)的 所有概率之和為1，在上面這個例子中就是Pr(Obs|Sun), Pr(Obs|Cloud) 及 Pr(Obs|Rain)之和。（對這句話我有點疑惑？）
　　除了定義了馬爾科夫過程的概率關(guān)系，我們還有另一個矩陣，定義為混淆矩陣（confusion matrix），它包含了給定一個隱藏狀態(tài)后得到的觀察狀態(tài)的概率。對于天氣例子，混淆矩陣是：
　　
　　注意矩陣的每一行之和是1。

3、總結(jié)（Summary）
　　我們已經(jīng)看到在一些過程中一個觀察序列與一個底層馬爾科夫過程是概率相關(guān)的。在這些例子中，觀察狀態(tài)的數(shù)目可以和隱藏狀態(tài)的數(shù)碼不同。
　　我們使用一個隱馬爾科夫模型（HMM）對這些例子建模。這個模型包含兩組狀態(tài)集合和三組概率集合：
　　* 隱藏狀態(tài)：一個系統(tǒng)的（真實）狀態(tài)，可以由一個馬爾科夫過程進行描述（例如，天氣）。
　　* 觀察狀態(tài)：在這個過程中‘可視’的狀態(tài)（例如，海藻的濕度）。
　　* 向量：包含了（隱）模型在時間t=1時一個特殊的隱藏狀態(tài)的概率（初始概率）。
　　* 狀態(tài)轉(zhuǎn)移矩陣：包含了一個隱藏狀態(tài)到另一個隱藏狀態(tài)的概率
　　* 混淆矩陣：包含了給定隱馬爾科夫模型的某一個特殊的隱藏狀態(tài)，觀察到的某個觀察狀態(tài)的概率。
　　因此一個隱馬爾科夫模型是在一個標(biāo)準(zhǔn)的馬爾科夫過程中引入一組觀察狀態(tài)，以及其與隱藏狀態(tài)間的一些概率關(guān)系。

HMM學(xué)習(xí)最佳范例四：隱馬爾科夫模型

分類 隱馬爾科夫模型 

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

1、定義（Definition of a hidden Markov model）
　　一個隱馬爾科夫模型是一個三元組（ , A, B）。
　　 ：初始化概率向量；
　　 ：狀態(tài)轉(zhuǎn)移矩陣；
　　 ：混淆矩陣；
　　在狀態(tài)轉(zhuǎn)移矩陣及混淆矩陣中的每一個概率都是時間無關(guān)的——也就是說，當(dāng)系統(tǒng)演化時這些矩陣并不隨時間改變。實際上，這是馬爾科夫模型關(guān)于真實世界最不現(xiàn)實的一個假設(shè)。

2、應(yīng)用（Uses associated with HMMs）
　　一旦一個系統(tǒng)可以作為HMM被描述，就可以用來解決三個基本問題。其中前兩個是模式識別的問題：給定HMM求一個觀察序列的概率（評估）；搜索最有可能生成一個觀察序列的隱藏狀態(tài)訓(xùn)練（解碼）。第三個問題是給定觀察序列生成一個HMM（學(xué)習(xí)）。
　a) 評估（Evaluation）
　　考慮這樣的問題，我們有一些描述不同系統(tǒng)的隱馬爾科夫模型（也就是一些( ,A,B)三元組的集合）及一個觀察序列。我們想知道哪一個HMM最有可能產(chǎn)生了這個給定的觀察序列。例如，對于海藻來說，我們也許會有一個“夏季”模型和一個“冬季”模型，因為不同季節(jié)之間的情況是不同的——我們也許想根據(jù)海藻濕度的觀察序列來確定當(dāng)前的季節(jié)。
　　我們使用前向算法（forward algorithm）來計算給定隱馬爾科夫模型（HMM）后的一個觀察序列的概率，并因此選擇最合適的隱馬爾科夫模型(HMM)。
　　在語音識別中這種類型的問題發(fā)生在當(dāng)一大堆數(shù)目的馬爾科夫模型被使用，并且每一個模型都對一個特殊的單詞進行建模時。一個觀察序列從一個發(fā)音單詞中形成，并且通過尋找對于此觀察序列最有可能的隱馬爾科夫模型（HMM）識別這個單詞。
　b) 解碼（ Decoding）
　　給定觀察序列搜索最可能的隱藏狀態(tài)序列。
　　另一個相關(guān)問題，也是最感興趣的一個，就是搜索生成輸出序列的隱藏狀態(tài)序列。在許多情況下我們對于模型中的隱藏狀態(tài)更感興趣，因為它們代表了一些更有價值的東西，而這些東西通常不能直接觀察到。
　　考慮海藻和天氣這個例子，一個盲人隱士只能感覺到海藻的狀態(tài)，但是他更想知道天氣的情況，天氣狀態(tài)在這里就是隱藏狀態(tài)。
　　我們使用Viterbi 算法（Viterbi algorithm）確定（搜索）已知觀察序列及HMM下最可能的隱藏狀態(tài)序列。
　　Viterbi算法（Viterbi algorithm）的另一廣泛應(yīng)用是自然語言處理中的詞性標(biāo)注。在詞性標(biāo)注中，句子中的單詞是觀察狀態(tài)，詞性（語法類別）是隱藏狀態(tài)（注意對于許多單詞，如wind，fish擁有不止一個詞性）。對于每句話中的單詞，通過搜索其最可能的隱藏狀態(tài)，我們就可以在給定的上下文中找到每個單詞最可能的詞性標(biāo)注。
　C）學(xué)習(xí)（Learning）
　　根據(jù)觀察序列生成隱馬爾科夫模型。
　　第三個問題，也是與HMM相關(guān)的問題中最難的，根據(jù)一個觀察序列（來自于已知的集合），以及與其有關(guān)的一個隱藏狀態(tài)集，估計一個最合適的隱馬爾科夫模型（HMM），也就是確定對已知序列描述的最合適的（ ,A,B）三元組。
　　當(dāng)矩陣A和B不能夠直接被（估計）測量時，前向-后向算法（forward-backward algorithm）被用來進行學(xué)習(xí)（參數(shù)估計），這也是實際應(yīng)用中常見的情況。

3、總結(jié)（Summary）
　　由一個向量和兩個矩陣( ,A,B)描述的隱馬爾科夫模型對于實際系統(tǒng)有著巨大的價值，雖然經(jīng)常只是一種近似，但它們卻是經(jīng)得起分析的。隱馬爾科夫模型通常解決的問題包括：
　　1. 對于一個觀察序列匹配最可能的系統(tǒng)——評估，使用前向算法（forward algorithm）解決；
　　2. 對于已生成的一個觀察序列，確定最可能的隱藏狀態(tài)序列——解碼，使用Viterbi 算法（Viterbi algorithm）解決；
　　3. 對于已生成的觀察序列，決定最可能的模型參數(shù)——學(xué)習(xí)，使用前向-后向算法（forward-backward algorithm）解決。

HMM學(xué)習(xí)最佳范例五：前向算法1

分類 隱馬爾科夫模型 

五、前向算法（Forward Algorithm）

計算觀察序列的概率（Finding the probability of an observed sequence）

1.窮舉搜索（ Exhaustive search for solution）
　　給定隱馬爾科夫模型，也就是在模型參數(shù)（ , A, B)已知的情況下，我們想找到觀察序列的概率。還是考慮天氣這個例子，我們有一個用來描述天氣及與它密切相關(guān)的海藻濕度狀態(tài)的隱馬爾科夫模型(HMM)， 另外我們還有一個海藻的濕度狀態(tài)觀察序列。假設(shè)連續(xù)3天海藻濕度的觀察結(jié)果是（干燥、濕潤、濕透）——而這三天每一天都可能是晴天、多云或下雨，對于觀察 序列以及隱藏的狀態(tài)，可以將其視為網(wǎng)格：

　　網(wǎng)格中的每一列都顯示了可能的的天氣狀態(tài)，并且每一列中的每個狀態(tài)都與相鄰列中的每一個狀態(tài)相連。而其狀態(tài)間的轉(zhuǎn)移都由狀態(tài)轉(zhuǎn)移矩陣提供一個概率。在每一列下面都是某個時間點上的觀察狀態(tài)，給定任一個隱藏狀態(tài)所得到的觀察狀態(tài)的概率由混淆矩陣提供。
　　可以看出，一種計算觀察序列概率的方法是找到每一個可能的隱藏狀態(tài)，并且將這些隱藏狀態(tài)下的觀察序列概率相加。對于上面那個（天氣）例子，將有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)
　　用這種方式計算觀察序列概率極為昂貴，特別對于大的模型或較長的序列，因此我們可以利用這些概率的時間不變性來減少問題的復(fù)雜度。

2.使用遞歸降低問題復(fù)雜度
　　給定一個隱馬爾科夫模型（HMM），我們將考慮遞歸地計算一個觀察序列的概率。我們首先定義局部概率（partial probability）,它是到達(dá)網(wǎng)格中的某個中間狀態(tài)時的概率。然后，我們將介紹如何在t=1和t=n(>1)時計算這些局部概率。
　　假設(shè)一個T-長觀察序列是：
　　　　　
　　
　2a.局部概率( ’s)
　　考慮下面這個網(wǎng)格，它顯示的是天氣狀態(tài)及對于觀察序列干燥，濕潤及濕透的一階狀態(tài)轉(zhuǎn)移情況：
　　　
　　我們可以將計算到達(dá)網(wǎng)格中某個中間狀態(tài)的概率作為所有到達(dá)這個狀態(tài)的可能路徑的概率求和問題。
　　例如，t=2時位于“多云”狀態(tài)的局部概率通過如下路徑計算得出：
　　　
　　我們定義t時刻位于狀態(tài)j的局部概率為at(j)——這個局部概率計算如下：
　　 t ( j )= Pr( 觀察狀態(tài) | 隱藏狀態(tài)j ) x Pr(t時刻所有指向j狀態(tài)的路徑）
　　對于最后的觀察狀態(tài)，其局部概率包括了通過所有可能的路徑到達(dá)這些狀態(tài)的概率——例如，對于上述網(wǎng)格，最終的局部概率通過如下路徑計算得出：
　　　
　　由此可見，對于這些最終局部概率求和等價于對于網(wǎng)格中所有可能的路徑概率求和，也就求出了給定隱馬爾科夫模型(HMM)后的觀察序列概率。
　　第3節(jié)給出了一個計算這些概率的動態(tài)示例。

HMM學(xué)習(xí)最佳范例五：前向算法2

分類 隱馬爾科夫模型 

五、前向算法（Forward Algorithm）

計算觀察序列的概率（Finding the probability of an observed sequence）

2b.計算t=1時的局部概率 ’s
　　我們按如下公式計算局部概率：
　　 t ( j )= Pr( 觀察狀態(tài) | 隱藏狀態(tài)j ) x Pr(t時刻所有指向j狀態(tài)的路徑）
　　特別當(dāng)t=1時，沒有任何指向當(dāng)前狀態(tài)的路徑。故t=1時位于當(dāng)前狀態(tài)的概率是初始概率，即Pr(state|t=1)=P(state)，因此，t=1時的局部概率等于當(dāng)前狀態(tài)的初始概率乘以相關(guān)的觀察概率：
　　　　　　　　　
　　所以初始時刻狀態(tài)j的局部概率依賴于此狀態(tài)的初始概率及相應(yīng)時刻我們所見的觀察概率。

2c.計算t>1時的局部概率 ’s
　　我們再次回顧局部概率的計算公式如下：
　　 t ( j )= Pr( 觀察狀態(tài) | 隱藏狀態(tài)j ) x Pr(t時刻所有指向j狀態(tài)的路徑）
　　我們可以假設(shè)（遞歸地），乘號左邊項“Pr( 觀察狀態(tài) | 隱藏狀態(tài)j )”已經(jīng)有了，現(xiàn)在考慮其右邊項“Pr(t時刻所有指向j狀態(tài)的路徑）”。
　　為了計算到達(dá)某個狀態(tài)的所有路徑的概率，我們可以計算到達(dá)此狀態(tài)的每條路徑的概率并對它們求和，例如：
　　　　　　
　　計算 所需要的路徑數(shù)目隨著觀察序列的增加而指數(shù)級遞增，但是t-1時刻 ’s給出了所有到達(dá)此狀態(tài)的前一路徑概率，因此，我們可以通過t-1時刻的局部概率定義t時刻的 ’s，即：
　　　　　
　　故我們所計算的這個概率等于相應(yīng)的觀察概率（亦即，t+1時在狀態(tài)j所觀察到的符號的概率）與該時刻到達(dá)此狀態(tài)的概率總和——這來自于上一步每一個局部概率的計算結(jié)果與相應(yīng)的狀態(tài)轉(zhuǎn)移概率乘積后再相加——的乘積。
　　注意我們已經(jīng)有了一個僅利用t時刻局部概率計算t+1時刻局部概率的表達(dá)式。
　　現(xiàn)在我們就可以遞歸地計算給定隱馬爾科夫模型(HMM)后一個觀察序列的概率了——即通過t=1時刻的局部概率 ’s計算t=2時刻的 ’s，通過t=2時刻的 ’s計算t=3時刻的 ’s等等直到t=T。給定隱馬爾科夫模型(HMM)的觀察序列的概率就等于t=T時刻的局部概率之和。

2d.降低計算復(fù)雜度
　　我們可以比較通過窮舉搜索（評估）和通過遞歸前向算法計算觀察序列概率的時間復(fù)雜度。
　　我們有一個長度為T的觀察序列O以及一個含有n個隱藏狀態(tài)的隱馬爾科夫模型l=( ,A,B)。
　　窮舉搜索將包括計算所有可能的序列：
　　　
　　公式
　　　　
　　對我們所觀察到的概率求和——注意其復(fù)雜度與T成指數(shù)級關(guān)系。相反的，使用前向算法我們可以利用上一步計算的信息，相應(yīng)地，其時間復(fù)雜度與T成線性關(guān)系。
注：窮舉搜索的時間復(fù)雜度是 ，前向算法的時間復(fù)雜度是 ，其中T指的是觀察序列長度，N指的是隱藏狀態(tài)數(shù)目。

3.總結(jié)
　　我們的目標(biāo)是計算給定隱馬爾科夫模型HMM下的觀察序列的概率——Pr(observations | )。
　　我們首先通過計算局部概率（ ’s）降低計算整個概率的復(fù)雜度，局部概率表示的是t時刻到達(dá)某個狀態(tài)s的概率。
　　t=1時，可以利用初始概率(來自于P向量）和觀察概率Pr(observation|state)（來自于混淆矩陣）計算局部概率；而t>1時的局部概率可以利用t-時的局部概率計算。
　　因此，這個問題是遞歸定義的，觀察序列的概率就是通過依次計算t=1,2,…,T時的局部概率，并且對于t=T時所有局部概率 ’s相加得到的。
　　注意，用這種方式計算觀察序列概率的時間復(fù)雜度遠(yuǎn)遠(yuǎn)小于計算所有序列的概率并對其相加（窮舉搜索）的時間復(fù)雜度。

HMM學(xué)習(xí)最佳范例五：前向算法3

分類 隱馬爾科夫模型 

五、前向算法（Forward Algorithm）

前向算法定義（Forward algorithm definition）

　　我們使用前向算法計算T長觀察序列的概率:
　　　　　
　　其中y的每一個是觀察集合之一。局部（中間）概率( ’s)是遞歸計算的，首先通過計算t=1時刻所有狀態(tài)的局部概率 ：
　　　　　
　　然后在每個時間點，t=2，… ，T時，對于每個狀態(tài)的局部概率，由下式計算局部概率 :
　　　　　
　　也就是當(dāng)前狀態(tài)相應(yīng)的觀察概率與所有到達(dá)該狀態(tài)的路徑概率之積，其遞歸地利用了上一個時間點已經(jīng)計算好的一些值。
　　最后，給定HMM, ,觀察序列的概率等于T時刻所有局部概率之和：
　　　　　
　　再重復(fù)說明一下，每一個局部概率（t > 2 時）都由前一時刻的結(jié)果計算得出。
　　對于“天氣”那個例子，下面的圖表顯示了t = 2為狀態(tài)為多云時局部概率 的計算過程。這是相應(yīng)的觀察概率b與前一時刻的局部概率與狀態(tài)轉(zhuǎn)移概率a相乘后的總和再求積的結(jié)果：
　　　

總結(jié)（Summary）

　　我們使用前向算法來計算給定隱馬爾科夫模型（HMM）后的一個觀察序列的概率。它在計算中利用遞歸避免對網(wǎng)格所有路徑進行窮舉計算。
　　給定這種算法，可以直接用來確定對于已知的一個觀察序列，在一些隱馬爾科夫模型（HMMs）中哪一個HMM最好的描述了它——先用前向算法評估每一個（HMM），再選取其中概率最高的一個。

HMM學(xué)習(xí)最佳范例五：前向算法4

分類 隱馬爾科夫模型 

　　首先需要說明的是，本節(jié)不是這個系列的翻譯，而是作為前向算法這一章的補充，希望能從實踐的角度來說明前向算法。除了用程序來解讀hmm的前向算法外，還希望將原文所舉例子的問題拿出來和大家探討。
　　文中所舉的程序來自于UMDHMM這個C語言版本的HMM工具包，具體見《幾種不同程序語言的HMM版本》。先說明一下UMDHMM這個包的基本情況，在linux環(huán)境下，進入umdhmm-v1.02目錄，“make all”之后會產(chǎn)生4個可執(zhí)行文件，分別是：
　　genseq: 利用一個給定的隱馬爾科夫模型產(chǎn)生一個符號序列（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 算法生成最可能的隱藏狀態(tài)序列（Generates the most like state sequence for a given symbol sequence, given the HMM, using Viterbi）
　　esthmm: 對于給定的觀察符號序列，利用BaumWelch算法學(xué)習(xí)隱馬爾科夫模型HMM（Estimates the HMM from a given symbol sequence using BaumWelch）。
　　這些可執(zhí)行文件需要讀入有固定格式的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（觀察序列文件）
　　就可以得到觀察序列的概率結(jié)果的對數(shù)值，這里我們在testfor.c的第58行對數(shù)結(jié)果的輸出下再加一行輸出：
　　　fprintf(stdout, “prob(O| model) = %fn”, proba);
　　就可以輸出運用前向算法計算觀察序列所得到的概率值。至此，所有的準(zhǔn)備工作已結(jié)束，接下來，我們將進入具體的程序解讀。
　　首先，需要定義HMM的數(shù)據(jù)結(jié)構(gòu)，也就是HMM的五個基本要素，在UMDHMM中是如下定義的（在hmm.h中）：

typedef struct
{
int N; /* 隱藏狀態(tài)數(shù)目;Q={1,2,…,N} */
int M; /* 觀察符號數(shù)目; V={1,2,…,M}*/
double **A; /* 狀態(tài)轉(zhuǎn)移矩陣A[1..N][1..N]. a[i][j] 是從t時刻狀態(tài)i到t+1時刻狀態(tài)j的轉(zhuǎn)移概率 */
double **B; /* 混淆矩陣B[1..N][1..M]. b[j][k]在狀態(tài)j時觀察到符合k的概率。*/
double *pi; /* 初始向量pi[1..N]，pi[i] 是初始狀態(tài)概率分布 */
} HMM;

前向算法程序示例如下（在forward.c中）：
/*
　函數(shù)參數(shù)說明：
　*phmm：已知的HMM模型；T：觀察符號序列長度；
　*O：觀察序列；**alpha：局部概率；*pprob：最終的觀察概率
*/
void Forward(HMM *phmm, int T, int *O, double **alpha, double *pprob)
{
　　int i, j; 　　/* 狀態(tài)索引 */
　　int t; 　　 /* 時間索引 */
　　double sum; /*求局部概率時的中間值 */

　　/* 1. 初始化：計算t=1時刻所有狀態(tài)的局部概率 ： */
　　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];
}

　　下一節(jié)我將用這個程序來驗證英文原文中所舉前向算法演示例子的問題。

HMM學(xué)習(xí)最佳范例五：前向算法5

分類 隱馬爾科夫模型 

　　在HMM這個翻譯系列的原文中，作者舉了一個前向算法的交互例子，這也是這個系列中比較出彩的地方，但是，在具體運行這個例子的時候，卻發(fā)現(xiàn)其似乎有點問題。
　　先說一下如何使用這個交互例子，運行時需要瀏覽器支持java，我用的是firefox。首先在Set按鈕前面的對話框里上觀察序列，如“Dry,Damp, Soggy” 或“Dry Damp Soggy”，觀察符號間用逗號或空格隔開；然后再點擊Set按鈕，這樣就初始化了觀察矩陣；如果想得到一個總的結(jié)果，即Pr(觀察序列|隱馬爾科夫模 型)，就點旁邊的Run按鈕；如果想一步一步觀察計算過程，即每個節(jié)點的局部概率，就單擊旁邊的Step按鈕。
　　原文交互例子（即天氣這個例子）中所定義的已知隱馬爾科夫模型如下：
　　1、隱藏狀態(tài) (天氣)：Sunny，Cloudy，Rainy；
　　2、觀察狀態(tài)（海藻濕度）：Dry，Dryish，Damp，Soggy；
　　3、初始狀態(tài)概率： Sunny（0.63）， Cloudy（0.17）， Rainy（0.20）；
　　4、狀態(tài)轉(zhuǎn)移矩陣：

　　　　　　　　　　　　 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也能運行這個例子，我們將上述天氣例子中的隱馬爾科夫模型轉(zhuǎn)化為如下的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
——————————————————————–
　　在運行例子之前，如果讀者也想觀察每一步的運算結(jié)果，可以將umdhmm-v1.02目錄下forward.c中的void Forward(…)函數(shù)替換如下：
——————————————————————–
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可執(zhí)行程序就可以輸出前向算法每一步的計算結(jié)果。
　　現(xiàn)在我們就用testfor來運行原文中默認(rèn)給出的觀察序列“Dry,Damp,Soggy”，其所對應(yīng)的UMDHMM可讀的觀察序列文件test1.seq：
——————————————————————–
　　　　T=3
　　　　1 3 4
——————————————————————–
　　好了，一切準(zhǔn)備工作就緒，現(xiàn)在就輸入如下命令：
　　　　testfor weather.hmm test1.seq > result1
　　result1就包含了所有的結(jié)果細(xì)節(jié)：
——————————————————————–
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
…
——————————————————————–
　　黑體部分是最終的觀察序列的概率結(jié)果，即本例中的Pr(觀察序列|HMM) = 0.026901。
　　但是，在原文中點Run按鈕后，結(jié)果卻是：Probability of this model = 0.027386915。
　　這其中的差別到底在哪里？我們來仔細(xì)觀察一下中間運行過程：
　　在初始化亦t=1時刻的局部概率計算兩個是一致的，沒有問題。但是，t=2時，在隱藏狀態(tài)“Sunny”的局部概率是不一致的。英文原文給出的例子的運行結(jié)果是：
　　Alpha = (((0.37800002*0.5) + (0.0425*0.375) + (0.010000001*0.125)) * 0.15) = 0.03092813
　　而UMDHMM給出的結(jié)果是：
——————————————————————–
　　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
——————————————————————–
　　區(qū)別就在于狀態(tài)轉(zhuǎn)移概率的選擇上，原文選擇的是狀態(tài)轉(zhuǎn)移矩陣中的第一行，而UMDHMM選擇的則是狀態(tài)轉(zhuǎn)移矩陣中的第一列。如果從原文給出的狀態(tài)轉(zhuǎn)移矩陣來看，第一行代表的是從前一時刻的狀態(tài)“Sunny”分別到當(dāng)前時刻的狀態(tài)“Sunny”，“Cloudy”，“Rainy”的概率；而第一列代表的 是從前一時刻的狀態(tài)“Sunny”，“Cloudy”，“Rainy”分別到當(dāng)前時刻狀態(tài)“Sunny”的概率。這樣看來似乎原文的計算過程有誤，讀者不 妨多試幾個例子看看，前向算法這一章就到此為止了。

HMM學(xué)習(xí)最佳范例六：維特比算法1

分類 隱馬爾科夫模型 

六、維特比算法（Viterbi Algorithm）

尋找最可能的隱藏狀態(tài)序列(Finding most probable sequence of hidden states)

　　對于一個特殊的隱馬爾科夫模型(HMM)及一個相應(yīng)的觀察序列，我們常常希望能找到生成此序列最可能的隱藏狀態(tài)序列。

1.窮舉搜索
　　我們使用下面這張網(wǎng)格圖片來形象化的說明隱藏狀態(tài)和觀察狀態(tài)之間的關(guān)系：

　　我們可以通過列出所有可能的隱藏狀態(tài)序列并且計算對于每個組合相應(yīng)的觀察序列的概率來找到最可能的隱藏狀態(tài)序列。最可能的隱藏狀態(tài)序列是使下面這個概率最大的組合：
　　　　　　Pr（觀察序列|隱藏狀態(tài)的組合）
　　例如，對于網(wǎng)格中所顯示的觀察序列，最可能的隱藏狀態(tài)序列是下面這些概率中最大概率所對應(yīng)的那個隱藏狀態(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)
　　這種方法是可行的，但是通過窮舉計算每一個組合的概率找到最可能的序列是極為昂貴的。與前向算法類似，我們可以利用這些概率的時間不變性來降低計算復(fù)雜度。

2.使用遞歸降低復(fù)雜度
　　給定一個觀察序列和一個隱馬爾科夫模型（HMM），我們將考慮遞歸地尋找最有可能的隱藏狀態(tài)序列。我們首先定義局部概率 ,它是到達(dá)網(wǎng)格中的某個特殊的中間狀態(tài)時的概率。然后，我們將介紹如何在t=1和t=n(>1)時計算這些局部概率。
　　這些局部概率與前向算法中所計算的局部概率是不同的，因為它們表示的是時刻t時到達(dá)某個狀態(tài)最可能的路徑的概率，而不是所有路徑概率的總和。
　2a.局部概率 ’s和局部最佳途徑
　　考慮下面這個網(wǎng)格，它顯示的是天氣狀態(tài)及對于觀察序列干燥，濕潤及濕透的一階狀態(tài)轉(zhuǎn)移情況：
　　　
　　對于網(wǎng)格中的每一個中間及終止?fàn)顟B(tài)，都有一個到達(dá)該狀態(tài)的最可能路徑。舉例來說，在t=3時刻的3個狀態(tài)中的每一個都有一個到達(dá)此狀態(tài)的最可能路徑，或許是這樣的：
　　
　　我們稱這些路徑局部最佳路徑(partial best paths)。其中每個局部最佳路徑都有一個相關(guān)聯(lián)的概率，即局部概率或 。與前向算法中的局部概率不同， 是到達(dá)該狀態(tài)（最可能）的一條路徑的概率。
　　因而 (i,t)是t時刻到達(dá)狀態(tài)i的所有序列概率中最大的概率，而局部最佳路徑是得到此最大概率的隱藏狀態(tài)序列。對于每一個可能的i和t值來說，這一類概率（及局部路徑）均存在。
　　特別地，在t=T時每一個狀態(tài)都有一個局部概率和一個局部最佳路徑。這樣我們就可以通過選擇此時刻包含最大局部概率的狀態(tài)及其相應(yīng)的局部最佳路徑來確定全局最佳路徑（最佳隱藏狀態(tài)序列）。

HMM學(xué)習(xí)最佳范例六：維特比算法2

分類 隱馬爾科夫模型 

六、維特比算法（Viterbi Algorithm）

尋找最可能的隱藏狀態(tài)序列(Finding most probable sequence of hidden states)

2b.計算t=1時刻的局部概率 ’s
　　我們計算的局部概率 是作為最可能到達(dá)我們當(dāng)前位置的路徑的概率（已知的特殊知識如觀察概率及前一個狀態(tài)的概率）。當(dāng)t=1的時候，到達(dá)某狀態(tài)的最可能路徑明顯是不存在的；但是，我們使用t=1時的所處狀態(tài)的初始概率及相應(yīng)的觀察狀態(tài)k1的觀察概率計算局部概率 ；即
　　　　　　　　　　
　　——與前向算法類似，這個結(jié)果是通過初始概率和相應(yīng)的觀察概率相乘得出的。

2c.計算t>1時刻的局部概率 ’s
　　現(xiàn)在我們來展示如何利用t-1時刻的局部概率 計算t時刻的局部概率 。
　　考慮如下的網(wǎng)格：
　　　　
　　我們考慮計算t時刻到達(dá)狀態(tài)X的最可能的路徑；這條到達(dá)狀態(tài)X的路徑將通過t-1時刻的狀態(tài)A，B或C中的某一個。
　　因此，最可能的到達(dá)狀態(tài)X的路徑將是下面這些路徑的某一個
　　　　　　　（狀態(tài)序列），…，A，X
　　　　　　?。顟B(tài)序列），…，B，X
或　　　　　?。顟B(tài)序列），…，C，X
　　我們想找到路徑末端是AX,BX或CX并且擁有最大概率的路徑。
　　回顧一下馬爾科夫假設(shè)：給定一個狀態(tài)序列，一個狀態(tài)發(fā)生的概率只依賴于前n個狀態(tài)。特別地，在一階馬爾可夫假設(shè)下，狀態(tài)X在一個狀態(tài)序列后發(fā)生的概率只取決于之前的一個狀態(tài)，即
　　　Pr (到達(dá)狀態(tài)A最可能的路徑) .Pr (X | A) . Pr (觀察狀態(tài) | X)
　　與此相同，路徑末端是AX的最可能的路徑將是到達(dá)A的最可能路徑再緊跟X。相似地，這條路徑的概率將是：
　　　Pr (到達(dá)狀態(tài)A最可能的路徑) .Pr (X | A) . Pr (觀察狀態(tài) | X)
　　因此，到達(dá)狀態(tài)X的最可能路徑概率是：
　　
　　其中第一項是t-1時刻的局部概率 ，第二項是狀態(tài)轉(zhuǎn)移概率以及第三項是觀察概率。
　　泛化上述公式，就是在t時刻，觀察狀態(tài)是kt，到達(dá)隱藏狀態(tài)i的最佳局部路徑的概率是：
　　　　　
　　這里，我們假設(shè)前一個狀態(tài)的知識（局部概率）是已知的，同時利用了狀態(tài)轉(zhuǎn)移概率和相應(yīng)的觀察概率之積。然后，我們就可以在其中選擇最大的概率了（局部概率 ）。

HMM學(xué)習(xí)最佳范例六：維特比算法3

分類 隱馬爾科夫模型 

六、維特比算法（Viterbi Algorithm）

尋找最可能的隱藏狀態(tài)序列(Finding most probable sequence of hidden states)

2d.反向指針， ’s
　　考慮下面這個網(wǎng)格
　　　
　　在每一個中間及終止?fàn)顟B(tài)我們都知道了局部概率， (i,t)。然而我們的目標(biāo)是在給定一個觀察序列的情況下尋找網(wǎng)格中最可能的隱藏狀態(tài)序列——因此，我們需要一些方法來記住網(wǎng)格中的局部最佳路徑。
　　回顧一下我們是如何計算局部概率的，計算t時刻的 ’s我們僅僅需要知道t-1時刻的 ’s。在這個局部概率計算之后，就有可能記錄前一時刻哪個狀態(tài)生成了 (i,t)——也就是說，在t-1時刻系統(tǒng)必須處于某個狀態(tài)，該狀態(tài)導(dǎo)致了系統(tǒng)在t時刻到達(dá)狀態(tài)i是最優(yōu)的。這種記錄（記憶）是通過對每一個狀態(tài)賦予一個反向指針 完成的，這個指針指向最優(yōu)的引發(fā)當(dāng)前狀態(tài)的前一時刻的某個狀態(tài)。
　　形式上，我們可以寫成如下的公式
　　　　
　　其中argmax運算符是用來計算使括號中表達(dá)式的值最大的索引j的。
　　請注意這個表達(dá)式是通過前一個時間步驟的局部概率 ’s和轉(zhuǎn)移概率計算的，并不包括觀察概率（與計算局部概率 ’s本身不同）。這是因為我們希望這些 ’s能回答這個問題“如果我在這里，最可能通過哪條路徑到達(dá)下一個狀態(tài)？”——這個問題與隱藏狀態(tài)有關(guān)，因此與觀察概率有關(guān)的混淆（矩陣）因子是可以被忽略的。

2e.維特比算法的優(yōu)點
　　使用Viterbi算法對觀察序列進行解碼有兩個重要的優(yōu)點：
　　1. 通過使用遞歸減少計算復(fù)雜度——這一點和前向算法使用遞歸減少計算復(fù)雜度是完全類似的。
　　2.維特比算法有一個非常有用的性質(zhì)，就是對于觀察序列的整個上下文進行了最好的解釋（考慮）。事實上，尋找最可能的隱藏狀態(tài)序列不止這一種方法，其他替代方法也可以，譬如，可以這樣確定如下的隱藏狀態(tài)序列：
　　　　
其中
　　　　
　　這里，采用了“自左向右”的決策方式進行一種近似的判斷，其對于每個隱藏狀態(tài)的判斷是建立在前一個步驟的判斷的基礎(chǔ)之上（而第一步從隱藏狀態(tài)的初始向量 開始）。
　　這種做法，如果在整個觀察序列的中部發(fā)生“噪音干擾”時，其最終的結(jié)果將與正確的答案嚴(yán)重偏離。
　　相反， 維特比算法在確定最可能的終止?fàn)顟B(tài)前將考慮整個觀察序列，然后通過 指針“回溯”以確定某個隱藏狀態(tài)是否是最可能的隱藏狀態(tài)序列中的一員。這是非常有用的，因為這樣就可以孤立序列中的“噪音”，而這些“噪音”在實時數(shù)據(jù)中是很常見的。

3.小結(jié)
　　維特比算法提供了一種有效的計算方法來分析隱馬爾科夫模型的觀察序列，并捕獲最可能的隱藏狀態(tài)序列。它利用遞歸減少計算量，并使用整個序列的上下文來做判斷，從而對包含“噪音”的序列也能進行良好的分析。
　　在使用時，維特比算法對于網(wǎng)格中的每一個單元(cell)都計算一個局部概率，同時包括一個反向指針用來指示最可能的到達(dá)該單元的路徑。當(dāng)完成整個計算過程后，首先在終止時刻找到最可能的狀態(tài)，然后通過反向指針回溯到t=1時刻，這樣回溯路徑上的狀態(tài)序列就是最可能的隱藏狀態(tài)序列了。

HMM學(xué)習(xí)最佳范例六：維特比算法4

分類 隱馬爾科夫模型 

六、維特比算法（Viterbi Algorithm）

維特比算法定義(Viterbi algorithm definition)

1、維特比算法的形式化定義
　　維特比算法可以形式化的概括為：
　　對于每一個i，i = 1，… ，n，令：
　　　　　
　　——這一步是通過隱藏狀態(tài)的初始概率和相應(yīng)的觀察概率之積計算了t=1時刻的局部概率。
　　對于t=2，…，T和i=1，…，n,令：
　　　　　
　　——這樣就確定了到達(dá)下一個狀態(tài)的最可能路徑，并對如何到達(dá)下一個狀態(tài)做了記錄。具體來說首先通過考察所有的轉(zhuǎn)移概率與上一步獲得的最大的局部概率之積，然后記錄下其中最大的一個，同時也包含了上一步觸發(fā)此概率的狀態(tài)。
　　令：
　　　　　
　　——這樣就確定了系統(tǒng)完成時(t=T)最可能的隱藏狀態(tài)。
　　對于t=T-1，…，1
　　令：
　　　　　
　　——這樣就可以按最可能的狀態(tài)路徑在整個網(wǎng)格回溯。回溯完成時，對于觀察序列來說，序列i1 … iT就是生成此觀察序列的最可能的隱藏狀態(tài)序列。

　　2.計算單獨的 ’s和 ’s
　　維特比算法中的局部概率 ’s的計算與前向算法中的局部概率 ’s的很相似。下面這幅圖表顯示了 ’s和 ’s的計算細(xì)節(jié)，可以對比一下前向算法3中的計算局部概率 ’s的那幅圖表：
　　
　　唯一不同的是前向算法中計算局部概率 ’s時的求和符號（ ）在維特比算法中計算局部概率 ’s時被替換為max——這一個重要的不同也說明了在維特比算法中我們選擇的是到達(dá)當(dāng)前狀態(tài)的最可能路徑，而不是總的概率。我們在維特比算法中維護了一個“反向指針”記錄了到達(dá)當(dāng)前狀態(tài)的最佳路徑，即在計算 ’s時通過argmax運算符獲得。

總結(jié)(Summary)

　　對于一個特定的隱馬爾科夫模型，維特比算法被用來尋找生成一個觀察序列的最可能的隱藏狀態(tài)序列。我們利用概率的時間不變性，通過避免計算網(wǎng)格中每一條路徑的概率來降低問題的復(fù)雜度。維特比算法對于每一個狀態(tài)(t>1)都保存了一個反向指針( )，并在每一個狀態(tài)中存儲了一個局部概率( )。
　　局部概率 是由反向指針指示的路徑到達(dá)某個狀態(tài)的概率。
　　當(dāng)t=T時，維特比算法所到達(dá)的這些終止?fàn)顟B(tài)的局部概率 ’s是按照最優(yōu)（最可能）的路徑到達(dá)該狀態(tài)的概率。因此，選擇其中最大的一個，并回溯找出所隱藏的狀態(tài)路徑，就是這個問題的最好答案。
　　關(guān)于維特比算法，需要著重強調(diào)的一點是它不是簡單的對于某個給定的時間點選擇最可能的隱藏狀態(tài)，而是基于全局序列做決策——因此，如果在觀察序列中有一個“非尋常”的事件發(fā)生，對于維特比算法的結(jié)果也影響不大。
　　這在語音處理中是特別有價值的，譬如當(dāng)某個單詞發(fā)音的一個中間音素出現(xiàn)失真或丟失的情況時，該單詞也可以被識別出來。

HMM學(xué)習(xí)最佳范例六：維特比算法5

分類 隱馬爾科夫模型 

六、維特比算法（Viterbi Algorithm）

維特比算法程序示例

　　仍然需要說明的是，本節(jié)不是這個系列的翻譯，而是作為維特比算法這一章的補充，將UMDHMM這個C語言版本的HMM工具包中的維特比算法程序展示給大家，并運行包中所附帶的例子。關(guān)于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個可執(zhí)行程序中，testvit是用來測試維特比算法的， 對于給定的觀察符號序列及HMM，利用Viterbi 算法生成最可能的隱藏狀態(tài)序列。這里我們利用UMDHMM包中test.hmm和test.seq來測試維特比算法，關(guān)于這兩個文件，具體如下：
　　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
　　結(jié)果如下：
　　————————————
　　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”就是最終所找到的隱藏狀態(tài)序列。好了，維特比算法這一章就到此為止了。

HMM學(xué)習(xí)最佳范例七：前向-后向算法1

分類 隱馬爾科夫模型 

七、前向-后向算法(Forward-backward algorithm)

根據(jù)觀察序列生成隱馬爾科夫模型(Generating a HMM from a sequence of obersvations)

　　與HMM模型相關(guān)的“有用”的問題是評估（前向算法）和解碼（維特比算法）——它們一個被用來測量一個模型的相對適用性，另一個被用來推測模型隱藏的部分在做什么（“到底發(fā)生了”什么）?？梢钥闯鏊鼈兌家蕾囉陔[馬爾科夫模型（HMM）參數(shù)這一先驗知識——狀態(tài)轉(zhuǎn)移矩陣，混淆（觀察）矩陣，以及 向量（初始化概率向量）。
　　然而，在許多實際問題的情況下這些參數(shù)都不能直接計算的，而要需要進行估計——這就是隱馬爾科夫模型中的學(xué)習(xí)問題。前向-后向算法就可以以一個觀察序 列為基礎(chǔ)來進行這樣的估計，而這個觀察序列來自于一個給定的集合，它所代表的是一個隱馬爾科夫模型中的一個已知的隱藏集合。
　　一個例子可能是一個龐大的語音處理數(shù)據(jù)庫，其底層的語音可能由一個馬爾可夫過程基于已知的音素建模的，而其可以觀察的部分可能由可識別的狀態(tài)（可能通過一些矢量數(shù)據(jù)表示）建模的，但是沒有（直接）的方式來獲取隱馬爾科夫模型（HMM）參數(shù)。
　　前向-后向算法并非特別難以理解，但自然地比前向算法和維特比算法更復(fù)雜。由于這個原因，這里就不詳細(xì)講解前向-后向算法了（任何有關(guān)HMM模型的參考文獻(xiàn)都會提供這方面的資料的）。
　　總之，前向-后向算法首先對于隱馬爾科夫模型的參數(shù)進行一個初始的估計（這很可能是完全錯誤的），然后通過對于給定的數(shù)據(jù)評估這些參數(shù)的的價值并減少它們所引起的錯誤來重新修訂這些HMM參數(shù)。從這個意義上講，它是以一種梯度下降的形式尋找一種錯誤測度的最小值。
　　之所以稱其為前向-后向算法，主要是因為對于網(wǎng)格中的每一個狀態(tài)，它既計算到達(dá)此狀態(tài)的“前向”概率（給定當(dāng)前模型的近似估計），又計算生成此模型最 終狀態(tài)的“后向”概率（給定當(dāng)前模型的近似估計）。 這些都可以通過利用遞歸進行有利地計算，就像我們已經(jīng)看到的?？梢酝ㄟ^利用近似的HMM模型參數(shù)來提高這些中間概率進行調(diào)整，而這些調(diào)整又形成了前向-后 向算法迭代的基礎(chǔ)。

注：關(guān)于前向-后向算法，原文只講了這么多，后繼我將按自己的理解補充一些內(nèi)容。

HMM學(xué)習(xí)最佳范例七：前向-后向算法2

分類 隱馬爾科夫模型 

七、前向-后向算法(Forward-backward algorithm)

　　要理解前向-后向算法，首先需要了解兩個算法：后向算法和EM算法。后向算法是必須的，因為前向-后向算法就是利用了前向算法與后向算法中的變 量因子，其得名也因于此；而EM算法不是必須的，不過由于前向-后向算法是EM算法的一個特例，因此了解一下EM算法也是有好處的，說實話，對于EM算 法，我也是云里霧里的。好了，廢話少說，我們先談?wù)労笙蛩惴ā?/font>