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

分類 隱馬爾科夫模型 

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

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

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

分類 隱馬爾科夫模型 

二、生成模式（Generating Patterns）

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

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

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

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

分類 隱馬爾科夫模型 

三、隱藏模式（Hidden Patterns）

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

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

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

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

分類 隱馬爾科夫模型 

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

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

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

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

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

分類 隱馬爾科夫模型 

五、前向算法（Forward Algorithm）

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

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

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

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

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

分類 隱馬爾科夫模型 

五、前向算法（Forward Algorithm）

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

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

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

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

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

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

分類 隱馬爾科夫模型 

五、前向算法（Forward Algorithm）

前向算法定義（Forward algorithm definition）

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

總結(jié)（Summary）

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

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

分類 隱馬爾科夫模型 

　　首先需要說明的是，本節(jié)不是這個(gè)系列的翻譯，而是作為前向算法這一章的補(bǔ)充，希望能從實(shí)踐的角度來說明前向算法。除了用程序來解讀hmm的前向算法外，還希望將原文所舉例子的問題拿出來和大家探討。
　　文中所舉的程序來自于UMDHMM這個(gè)C語(yǔ)言版本的HMM工具包，具體見《幾種不同程序語(yǔ)言的HMM版本》。先說明一下UMDHMM這個(gè)包的基本情況，在linux環(huán)境下，進(jìn)入umdhmm-v1.02目錄，“make all”之后會(huì)產(chǎn)生4個(gè)可執(zhí)行文件，分別是：
　　genseq: 利用一個(gè)給定的隱馬爾科夫模型產(chǎn)生一個(gè)符號(hào)序列（Generates a symbol sequence using the specified model sequence using the specified model）
　　testfor: 利用前向算法計(jì)算log Prob(觀察序列| HMM模型)（Computes log Prob(observation|model) using the Forward algorithm.）
　　testvit: 對(duì)于給定的觀察符號(hào)序列及HMM，利用Viterbi 算法生成最可能的隱藏狀態(tài)序列（Generates the most like state sequence for a given symbol sequence, given the HMM, using Viterbi）
　　esthmm: 對(duì)于給定的觀察符號(hào)序列，利用BaumWelch算法學(xué)習(xí)隱馬爾科夫模型HMM（Estimates the HMM from a given symbol sequence using BaumWelch）。
　　這些可執(zhí)行文件需要讀入有固定格式的HMM文件及觀察符號(hào)序列文件，格式要求及舉例如下：
　　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
——————————————————————–

　　對(duì)于前向算法的測(cè)試程序testfor來說，運(yùn)行：
　　　testfor model.hmm（HMM文件） obs.seq（觀察序列文件）
　　就可以得到觀察序列的概率結(jié)果的對(duì)數(shù)值，這里我們?cè)?span lang=EN-US>testfor.c的第58行對(duì)數(shù)結(jié)果的輸出下再加一行輸出：
　　　fprintf(stdout, “prob(O| model) = %fn”, proba);
　　就可以輸出運(yùn)用前向算法計(jì)算觀察序列所得到的概率值。至此，所有的準(zhǔn)備工作已結(jié)束，接下來，我們將進(jìn)入具體的程序解讀。
　　首先，需要定義HMM的數(shù)據(jù)結(jié)構(gòu)，也就是HMM的五個(gè)基本要素，在UMDHMM中是如下定義的（在hmm.h中）：

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

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

　　/* 1. 初始化：計(jì)算t=1時(shí)刻所有狀態(tài)的局部概率 ： */
　　for (i = 1; i <= phmm->N; i++)
　　　　alpha[1][i] = phmm->pi[i]* phmm->B[i][O[1]];
　　
　　/* 2. 歸納：遞歸計(jì)算每個(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. 終止：觀察序列的概率等于T時(shí)刻所有局部概率之和*/
　　*pprob = 0.0;
　　for (i = 1; i <= phmm->N; i++)
　　　　*pprob += alpha[T][i];
}

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

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

分類 隱馬爾科夫模型 

　　在HMM這個(gè)翻譯系列的原文中，作者舉了一個(gè)前向算法的交互例子，這也是這個(gè)系列中比較出彩的地方，但是，在具體運(yùn)行這個(gè)例子的時(shí)候，卻發(fā)現(xiàn)其似乎有點(diǎn)問題。
　　先說一下如何使用這個(gè)交互例子，運(yùn)行時(shí)需要瀏覽器支持java，我用的是firefox。首先在Set按鈕前面的對(duì)話框里上觀察序列，如“Dry,Damp, Soggy” 或“Dry Damp Soggy”，觀察符號(hào)間用逗號(hào)或空格隔開；然后再點(diǎn)擊Set按鈕，這樣就初始化了觀察矩陣；如果想得到一個(gè)總的結(jié)果，即Pr(觀察序列|隱馬爾科夫模 型)，就點(diǎn)旁邊的Run按鈕；如果想一步一步觀察計(jì)算過程，即每個(gè)節(jié)點(diǎn)的局部概率，就單擊旁邊的Step按鈕。
　　原文交互例子（即天氣這個(gè)例子）中所定義的已知隱馬爾科夫模型如下：
　　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也能運(yùn)行這個(gè)例子，我們將上述天氣例子中的隱馬爾科夫模型轉(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
——————————————————————–
　　在運(yùn)行例子之前，如果讀者也想觀察每一步的運(yùn)算結(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í)行程序就可以輸出前向算法每一步的計(jì)算結(jié)果。
　　現(xiàn)在我們就用testfor來運(yùn)行原文中默認(rèn)給出的觀察序列“Dry,Damp,Soggy”，其所對(duì)應(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。
　　但是，在原文中點(diǎn)Run按鈕后，結(jié)果卻是：Probability of this model = 0.027386915。
　　這其中的差別到底在哪里？我們來仔細(xì)觀察一下中間運(yùn)行過程：
　　在初始化亦t=1時(shí)刻的局部概率計(jì)算兩個(gè)是一致的，沒有問題。但是，t=2時(shí)，在隱藏狀態(tài)“Sunny”的局部概率是不一致的。英文原文給出的例子的運(yùn)行結(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)移矩陣來看，第一行代表的是從前一時(shí)刻的狀態(tài)“Sunny”分別到當(dāng)前時(shí)刻的狀態(tài)“Sunny”，“Cloudy”，“Rainy”的概率；而第一列代表的 是從前一時(shí)刻的狀態(tài)“Sunny”，“Cloudy”，“Rainy”分別到當(dāng)前時(shí)刻狀態(tài)“Sunny”的概率。這樣看來似乎原文的計(jì)算過程有誤，讀者不 妨多試幾個(gè)例子看看，前向算法這一章就到此為止了。

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

分類 隱馬爾科夫模型 

六、維特比算法（Viterbi Algorithm）

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

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

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

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

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

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

分類 隱馬爾科夫模型 

六、維特比算法（Viterbi Algorithm）

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

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

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

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

分類 隱馬爾科夫模型 

六、維特比算法（Viterbi Algorithm）

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

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

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

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

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

分類 隱馬爾科夫模型 

六、維特比算法（Viterbi Algorithm）

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

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

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

總結(jié)(Summary)

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

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

分類 隱馬爾科夫模型 

六、維特比算法（Viterbi Algorithm）

維特比算法程序示例

　　仍然需要說明的是，本節(jié)不是這個(gè)系列的翻譯，而是作為維特比算法這一章的補(bǔ)充，將UMDHMM這個(gè)C語(yǔ)言版本的HMM工具包中的維特比算法程序展示給大家，并運(yùn)行包中所附帶的例子。關(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è)可執(zhí)行程序中，testvit是用來測(cè)試維特比算法的， 對(duì)于給定的觀察符號(hào)序列及HMM，利用Viterbi 算法生成最可能的隱藏狀態(tài)序列。這里我們利用UMDHMM包中test.hmm和test.seq來測(cè)試維特比算法，關(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
——————————————————————–

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

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

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

分類 隱馬爾科夫模型 

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

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