考慮下面交通燈的例子，一個(gè)序列可能是紅-紅/橙-綠-橙-紅。這個(gè)序列可以畫成一個(gè)狀態(tài)機(jī)，不同的狀態(tài)按照這個(gè)狀態(tài)機(jī)互相交替，每一個(gè)狀態(tài)都只依賴于前一個(gè)狀態(tài)，如果當(dāng)前的是綠燈，那么接下來(lái)就是橙燈，這是一個(gè)確定性系統(tǒng)，因此更容易理解和分析，只要這些狀態(tài)轉(zhuǎn)移都是已知的。但是在實(shí)際當(dāng)中還存在許多不確定性系統(tǒng)。

　　在日常生活當(dāng)中，我們總是希望根據(jù)當(dāng)前天氣的情況來(lái)預(yù)測(cè)未來(lái)天氣情況，和上面的交通燈的例子不同，我們不能依靠現(xiàn)有知識(shí)確定天氣情況的轉(zhuǎn)移，但是我們還是希望能得到一個(gè)天氣的模式。一種辦法就是假設(shè)這個(gè)模型的每個(gè)狀態(tài)都只依賴于前一個(gè)的狀態(tài)，這個(gè)假設(shè)被稱為馬爾科夫假設(shè)，這個(gè)假設(shè)可以極大簡(jiǎn)化這個(gè)問(wèn)題。顯然，這個(gè)假設(shè)也是一個(gè)非常糟糕的假設(shè)，導(dǎo)致很多重要的信息都丟失了。

　　當(dāng)涉及到天氣的時(shí)候，馬爾科夫假設(shè)描述為，假設(shè)如果我們知道之前一些天的天氣信息，那么我們就能預(yù)測(cè)今天的天氣。當(dāng)然，這個(gè)例子也是有些不合實(shí)際的。但是，這樣一個(gè)簡(jiǎn)化的系統(tǒng)可以有利于我們的分析，所以我們通常接受這樣的假設(shè)，因?yàn)槲覀冎肋@樣的系統(tǒng)能讓我們獲得一些有用的信息，盡管不是十分準(zhǔn)確的。

　　談到 HMM，首先簡(jiǎn)單介紹一下馬爾可夫過(guò)程 (Markov Process)，它因俄羅斯數(shù)學(xué)家安德烈·馬爾可夫而得名，代表數(shù)學(xué)中具有馬爾可夫性質(zhì)的離散隨機(jī)過(guò)程。該過(guò)程中，每個(gè)狀態(tài)的轉(zhuǎn)移只依賴于之前的 n 個(gè)狀態(tài)，這個(gè)過(guò)程被稱為1個(gè) n 階的模型，其中 n 是影響轉(zhuǎn)移狀態(tài)的數(shù)目。最簡(jiǎn)單的馬爾科夫過(guò)程就是一階過(guò)程，每一個(gè)狀態(tài)的轉(zhuǎn)移只依賴于其之前的那一個(gè)狀態(tài)。注意這和確定性系統(tǒng)不一樣，因?yàn)檫@種轉(zhuǎn)移是有概率的，而不是確定性的。

　　馬爾可夫鏈?zhǔn)请S機(jī)變量X₁, … , X_n 的一個(gè)數(shù)列。這些變量的范圍，即他們所有可能取值的集合，被稱為“狀態(tài)空間”，而 X_n  的值則是在時(shí)間 n 的狀態(tài)。如果X_n+1 對(duì)于過(guò)去狀態(tài)的條件概率分布僅是 X_n 的一個(gè)函數(shù)，則

　　這里 x 為過(guò)程中的某個(gè)狀態(tài)。上面這個(gè)恒等式可以被看作是馬爾可夫性質(zhì)。

　　馬爾可夫鏈的在很多應(yīng)用中發(fā)揮了重要作用，例如，谷歌所使用的網(wǎng)頁(yè)排序算法（PageRank）就是由馬爾可夫鏈定義的。

　　下圖展示了天氣這個(gè)例子中所有可能的一階轉(zhuǎn)移：

　　注意一個(gè)含有 N 個(gè)狀態(tài)的一階過(guò)程有 N² 個(gè)狀態(tài)轉(zhuǎn)移。每一個(gè)轉(zhuǎn)移的概率叫做狀態(tài)轉(zhuǎn)移概率(state transition probability)，就是從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的概率。這所有的 N² 個(gè)概率可以用一個(gè)狀態(tài)轉(zhuǎn)移矩陣來(lái)表示，其表示形式如下：

　　對(duì)該矩陣有如下約束條件：

　　下面就是海藻例子的狀態(tài)轉(zhuǎn)移矩陣：

　　這個(gè)矩陣表示，如果昨天是晴天，那么今天有50%的可能是晴天，37.5%的概率是陰天，12.5%的概率會(huì)下雨，很明顯，矩陣中每一行的和都是1。

　　為了初始化這樣一個(gè)系統(tǒng)，我們需要一個(gè)初始的概率向量：

　　這個(gè)向量表示第一天是晴天。

　　到這里，我們就為上面的一階馬爾科夫過(guò)程定義了以下三個(gè)部分：

　　狀態(tài)：晴天、陰天和下雨

　　初始向量：定義系統(tǒng)在時(shí)間為0的時(shí)候的狀態(tài)的概率

　　狀態(tài)轉(zhuǎn)移矩陣：每種天氣轉(zhuǎn)換的概率

　　所有的能被這樣描述的系統(tǒng)都是一個(gè)馬爾科夫過(guò)程。

　　然而，當(dāng)馬爾科夫過(guò)程不夠強(qiáng)大的時(shí)候，我們又該怎么辦呢？在某些情況下，馬爾科夫過(guò)程不足以描述我們希望發(fā)現(xiàn)的模式。

　　例如，一個(gè)隱居的人可能不能直觀的觀察到天氣的情況，但是民間傳說(shuō)告訴我們海藻的狀態(tài)在某種概率上是和天氣的情況相關(guān)的。在這種情況下我們有兩個(gè)狀態(tài)集合，一個(gè)可以觀察到的狀態(tài)集合（海藻的狀態(tài)）和一個(gè)隱藏的狀態(tài)（天氣狀況）。我們希望能找到一個(gè)算法可以根據(jù)海藻的狀況和馬爾科夫假設(shè)來(lái)預(yù)測(cè)天氣的狀況。

　　一個(gè)更現(xiàn)實(shí)的例子是語(yǔ)音識(shí)別，我們聽(tīng)到的聲音是聲帶、喉嚨和一起其他的發(fā)音器官共同作用的結(jié)果。這些因素相互作用，共同決定了每一個(gè)單詞的聲音，而一個(gè)語(yǔ)音識(shí)別系統(tǒng)檢測(cè)的聲音（可以觀察的狀態(tài)）是人體內(nèi)部各種物理變化（隱藏的狀態(tài)、引申一個(gè)人真正想表達(dá)的意思）產(chǎn)生的。

　　某些語(yǔ)音識(shí)別設(shè)備把內(nèi)部的發(fā)音機(jī)制作為一個(gè)隱藏的狀態(tài)序列，把最后的聲音看成是一個(gè)和隱藏的狀態(tài)序列十分相似的可以觀察到的狀態(tài)的序列。在這兩個(gè)例子中，一個(gè)非常重要的地方是隱藏狀態(tài)的數(shù)目和可以觀察到的狀態(tài)的數(shù)目可能是不一樣的。在一個(gè)有3種狀態(tài)的天氣系統(tǒng)（sunny、cloudy、rainy）中，也許可以觀察到4種潮濕程度的海藻（dry、dryish、damp、soggy）。在語(yǔ)音識(shí)別中，一個(gè)簡(jiǎn)單的發(fā)言也許只需要80個(gè)語(yǔ)素來(lái)描述，但是一個(gè)內(nèi)部的發(fā)音機(jī)制可以產(chǎn)生不到80或者超過(guò)80種不同的聲音。

　　在上面的這些情況下，可以觀察到的狀態(tài)序列和隱藏的狀態(tài)序列是概率相關(guān)的。于是我們可以將這種類型的過(guò)程建模為有一個(gè)隱藏的馬爾科夫過(guò)程和一個(gè)與這個(gè)隱藏馬爾科夫過(guò)程概率相關(guān)的并且可以觀察到的狀態(tài)集合。這就是本文重點(diǎn)介紹的隱馬爾可夫模型。

　　隱馬爾可夫模型 (Hidden Markov Model) 是一種統(tǒng)計(jì)模型，用來(lái)描述一個(gè)含有隱含未知參數(shù)的馬爾可夫過(guò)程。其難點(diǎn)是從可觀察的參數(shù)中確定該過(guò)程的隱含參數(shù)，然后利用這些參數(shù)來(lái)作進(jìn)一步的分析。下圖是一個(gè)三個(gè)狀態(tài)的隱馬爾可夫模型狀態(tài)轉(zhuǎn)移圖，其中x 表示隱含狀態(tài)，y 表示可觀察的輸出，a 表示狀態(tài)轉(zhuǎn)換概率，b 表示輸出概率。

　　下圖顯示了天氣的例子中隱藏的狀態(tài)和可以觀察到的狀態(tài)之間的關(guān)系。我們假設(shè)隱藏的狀態(tài)是一個(gè)簡(jiǎn)單的一階馬爾科夫過(guò)程，并且他們兩兩之間都可以相互轉(zhuǎn)換。

　　對(duì) HMM 來(lái)說(shuō)，有如下三個(gè)重要假設(shè)，盡管這些假設(shè)是不現(xiàn)實(shí)的。

　　假設(shè)1：馬爾可夫假設(shè)（狀態(tài)構(gòu)成一階馬爾可夫鏈）

　　假設(shè)2：不動(dòng)性假設(shè)（狀態(tài)與具體時(shí)間無(wú)關(guān)）

　　假設(shè)3：輸出獨(dú)立性假設(shè)（輸出僅與當(dāng)前狀態(tài)有關(guān)）

　　隱藏的狀態(tài)和可觀察到的狀態(tài)之間有一種概率上的關(guān)系，也就是說(shuō)某種隱藏狀態(tài) H 被認(rèn)為是某個(gè)可以觀察的狀態(tài) O₁ 是有概率的，假設(shè)為 P(O₁ | H)。如果可以觀察的狀態(tài)有3種，那么很顯然 P(O₁ | H)+P(O₂ | H)+ P(O₃ | H) = 1。

　　這樣，我們也可以得到一個(gè)另一個(gè)矩陣，稱為混淆矩陣(confusion matrix)。這個(gè)矩陣的內(nèi)容是某個(gè)隱藏的狀態(tài)被分別觀察成幾種不同的可以觀察的狀態(tài)的概率，在天氣的例子中，這個(gè)矩陣如下圖：

　　上邊的圖示都強(qiáng)調(diào)了 HMM 的狀態(tài)變遷。而下圖則明確的表示出模型的演化，其中綠色的圓圈表示隱藏狀態(tài)，紫色圓圈表示可觀察到狀態(tài)，箭頭表示狀態(tài)之間的依存概率，一個(gè) HMM 可用一個(gè)5元組 { N, M, π，A，B } 表示，其中 N 表示隱藏狀態(tài)的數(shù)量，我們要么知道確切的值，要么猜測(cè)該值，M 表示可觀測(cè)狀態(tài)的數(shù)量，可以通過(guò)訓(xùn)練集獲得， π={π_i} 為初始狀態(tài)概率，A={a_ij} 為隱藏狀態(tài)的轉(zhuǎn)移矩陣 Pr(x_t(i) | x_t-1(j))，B={b_ik} 表示某個(gè)時(shí)刻因隱藏狀態(tài)而可觀察的狀態(tài)的概率，即混淆矩陣，Pr(o_t(i) | x_t(j))。在狀態(tài)轉(zhuǎn)移矩陣和混淆矩陣中的每個(gè)概率都是時(shí)間無(wú)關(guān)的，即當(dāng)系統(tǒng)演化時(shí)，這些矩陣并不隨時(shí)間改變。對(duì)于一個(gè) N 和 M 固定的 HMM 來(lái)說(shuō)，用 λ={ π, A, B } 表示 HMM 參數(shù)。

　　在正常的馬爾可夫模型中，狀態(tài)對(duì)于觀察者來(lái)說(shuō)是直接可見(jiàn)的。這樣狀態(tài)的轉(zhuǎn)換概率便是全部的參數(shù)。而在隱馬爾可夫模型中，狀態(tài)并不是直接可見(jiàn)的，但受狀態(tài)影響的某些變量則是可見(jiàn)的。每一個(gè)狀態(tài)在可能輸出的符號(hào)上都有一概率分布。因此輸出符號(hào)的序列能夠透露出狀態(tài)序列的一些信息。

　　在HMM 中有三個(gè)典型問(wèn)題：

　?。ㄒ唬?已知模型參數(shù)，計(jì)算某一給定可觀察狀態(tài)序列的概率

假設(shè)我們已經(jīng)有一個(gè)特定的隱馬爾科夫模型 λ 和一個(gè)可觀察狀態(tài)序列集。我們也許想知道在所有可能的隱藏狀態(tài)序列下，給定的可觀察狀態(tài)序列的概率。當(dāng)給定如下一個(gè)隱藏狀態(tài)序列：

　　那么在 HMM 和這個(gè)隱藏狀態(tài)序列的條件下，可觀察狀態(tài)序列的概率為：

　　而隱藏狀態(tài)序列在 HMM 條件下的概率為：

　　因此，隱藏狀態(tài)序列和可觀察狀態(tài)序列的聯(lián)合概率為：

　　那么所有可能的隱藏狀態(tài)序列上，可觀察狀態(tài)序列的概率為：

　　例如，我們也許有一個(gè)海藻的“Summer”模型和一個(gè)“Winter”模型，因?yàn)楹Ｔ逶谙奶旌投斓臓顟B(tài)應(yīng)該是不同的，我們希望根據(jù)一個(gè)可觀察狀態(tài)（海藻的潮濕與否）序列來(lái)判斷現(xiàn)在是夏天還是冬天。

　　我們可以使用前向算法來(lái)計(jì)算在某個(gè)特定的HMM 下一個(gè)可觀察狀態(tài)序列的概率，然后據(jù)此找到最可能的模型。

　　這種類型的應(yīng)用通常出現(xiàn)在語(yǔ)音設(shè)別中，通常我們會(huì)使用很多 HMM，每一個(gè)針對(duì)一個(gè)特別的單詞。一個(gè)可觀察狀態(tài)的序列是從一個(gè)可以聽(tīng)到的單詞向前得到的，然后這個(gè)單詞就可以通過(guò)找到滿足這個(gè)可觀察狀態(tài)序列的最大概率的HMM 來(lái)識(shí)別。

　　下面介紹一下前向算法(Forward Algorithm)

　　如何計(jì)算一個(gè)可觀察序列的概率？

　　1. 窮舉搜索

　　給定一個(gè) HMM，我們想計(jì)算出某個(gè)可觀察序列的概率。考慮天氣的例子，我們知道一個(gè)描述天氣和海藻狀態(tài)的 HMM，而且我們還有一個(gè)海藻狀態(tài)的序列。假設(shè)這個(gè)狀態(tài)中的某三天是（dry，damp，soggy），在這三天中的每一天，天氣都可能是晴朗，多云或者下雨，我們可以用下圖來(lái)描述觀察序列和隱藏序列：

　　在這個(gè)圖中的每一列表示天氣的狀態(tài)可能，并且每個(gè)狀態(tài)都指向相鄰的列的每個(gè)狀態(tài)，每個(gè)狀態(tài)轉(zhuǎn)換在狀態(tài)轉(zhuǎn)移矩陣中都有一個(gè)概率。每一列的下面是當(dāng)天的可觀察的海藻的狀態(tài)，在每種狀態(tài)下出現(xiàn)這種可觀察狀態(tài)的概率是由混淆矩陣給出的。

　　一個(gè)可能的計(jì)算可觀察概率的方法是找到每一個(gè)可能的隱藏狀態(tài)的序列，這里有3² = 27種，這個(gè)時(shí)候的可觀察序列的概率就是 Pr(dry, damp, soggy | HMM)=Pr(dry, damp, soggy | sunny, sunny, sunny) + . . . . + Pr(dry, damp, soggy | rainy, rainy, rainy)。

　　很顯然，這種計(jì)算的效率非常低，尤其是當(dāng)模型中的狀態(tài)非常多或者序列很長(zhǎng)的時(shí)候。事實(shí)上，我們可以利用概率不隨時(shí)間變化這個(gè)假設(shè)來(lái)降低時(shí)間的開(kāi)銷。

　　2. 使用遞歸來(lái)降低復(fù)雜度

　　我們可以考慮給定 HMM 的情況下，遞歸的計(jì)算一個(gè)可觀察序列的概率。我們可以首先定義一個(gè)部分概率，表示達(dá)到某個(gè)中間狀態(tài)的概率。接下來(lái)我們將看到這些部分概率是如何 在time=1 和 time = n (n > 1) 的時(shí)候計(jì)算的。

　　假設(shè)一個(gè)T時(shí)間段的可觀察序列是：

　　1) 部分概率

　　下面這張圖表示了一個(gè)觀察序列（dry，damp，soggy）的一階轉(zhuǎn)移

　　我們可以通過(guò)計(jì)算到達(dá)某個(gè)狀態(tài)的所有路徑的概率和來(lái)計(jì)算到達(dá)某個(gè)中間狀態(tài)的概率。比如說(shuō)，t=2時(shí)刻，cloudy的概率用三條路徑的概率之和來(lái)表示：

　　我們用 α_t(j) 來(lái)表示在 t 時(shí)刻是狀態(tài) j 的概率，α_t(j)=Pr(觀察狀態(tài) | 隱藏狀態(tài) j ) x Pr(t 時(shí)刻到達(dá)狀態(tài) j 的所有路徑)。

　　最后一個(gè)觀察狀態(tài)的部分概率就表示了整個(gè)序列最后達(dá)到某個(gè)狀態(tài)的所有可能的路徑的概率和，比如說(shuō)在這個(gè)例子中，最后一列的部分狀態(tài)是通過(guò)下列路徑計(jì)算得到的：

　　因?yàn)樽詈笠涣械牟糠指怕适撬锌赡艿穆窂降母怕屎停跃褪沁@個(gè)觀察序列在給定 HMM 下的概率了。

　　2) 計(jì)算 t=1時(shí)候的部分概率

　　當(dāng) t=1 的時(shí)候，沒(méi)有路徑到某個(gè)狀態(tài)，所以這里是初始概率，Pr(狀態(tài) j | t=0) = π(狀態(tài) j )，這樣我們就可以計(jì)算 t=1 時(shí)候的部分概率為：

　　因?yàn)樵诔跏嫉臅r(shí)候，狀態(tài) j 的概率不僅和這個(gè)狀態(tài)本身相關(guān)，還和觀察狀態(tài)有關(guān)，所以這里用到了混淆矩陣的值，k₁ 表示第一個(gè)觀察狀態(tài)，b_jk1 表示隱藏狀態(tài)是 j，但是觀察成 k₁ 的概率。

　　3) 計(jì)算 t>1 時(shí)候的部分概率

　　還是看計(jì)算部分概率的公式是：α_t(j) = Pr(觀察狀態(tài) | 隱藏狀態(tài) j) x Pr(t 時(shí)刻到達(dá)狀態(tài) j 的所有路徑)。 這個(gè)公式的左邊是從混淆矩陣中已知的，我只需要計(jì)算右邊部分，很顯然右邊是所有路徑的和：

　　需要計(jì)算的路徑數(shù)是和觀察序列的長(zhǎng)度的平方相關(guān)的，但是 t 時(shí)刻的部分概率已經(jīng)計(jì)算過(guò)了之前的所有路徑，所以在 t+1 時(shí)刻只需要根據(jù) t 時(shí)刻的概率來(lái)計(jì)算就可以了：

　　這里簡(jiǎn)單解釋下，b_jk(t+1) 就是在 t+1 時(shí)刻的第 j 個(gè)隱藏狀態(tài)被認(rèn)為是當(dāng)前的觀察狀態(tài)的概率，后面一部分是所有t時(shí)刻的隱藏狀態(tài)到 t+1 時(shí)候的隱藏狀態(tài)j的轉(zhuǎn)移的概率的和。這樣我們每一步的計(jì)算都可以利用上一步的結(jié)果，節(jié)省了很多時(shí)間。

　　4) 公式推導(dǎo)

　　5) 降低計(jì)算復(fù)雜度

　　我們可以比較窮舉和遞歸算法的復(fù)雜度。假設(shè)有一個(gè) HMM，其中有 n 個(gè)隱藏狀態(tài)，我們有一個(gè)長(zhǎng)度為 T 的觀察序列。

　　窮舉算法的需要計(jì)算所有可能的隱藏序列：

　　需要計(jì)算：

　　很顯然窮舉算法的時(shí)間開(kāi)銷是和 T 指數(shù)相關(guān)的，即 N^T，而如果采用遞歸算法，由于我們每一步都可以利用上一步的結(jié)果，所以是和 T 線性相關(guān)的，即復(fù)雜度是 N²T。

　　這里我們的目的是在某個(gè)給定的 HMM 下，計(jì)算出某個(gè)可觀察序列的概率。我們通過(guò)先計(jì)算部分概率的方式遞歸的計(jì)算整個(gè)序列的所有路徑的概率，大大節(jié)省了時(shí)間。在 t=1 的時(shí)候，使用了初始概率和混淆矩陣的概率，而在t時(shí)刻的概率則可以利用 t-1 時(shí)刻的結(jié)果。

　　這樣我們就可以用遞歸的方式來(lái)計(jì)算所有可能的路徑的概率和，最后，所有的部分概率的計(jì)算公式為

　　使用天氣的例子，計(jì)算 t=2 時(shí)刻的 cloudy 狀態(tài)的概率方法如圖：

　　我們使用前向算法在給定的一個(gè) HMM 下計(jì)算某個(gè)可觀察序列的概率。前向算法主要采用的是遞歸的思想，利用之前的計(jì)算結(jié)果。有了這個(gè)算法，我們就可以在一堆 HMM 中，找到一個(gè)最滿足當(dāng)前的可觀察序列的模型（前向算法計(jì)算出來(lái)的概率最大）。

　?。ǘ?根據(jù)可觀察狀態(tài)的序列找到一個(gè)最可能的隱藏狀態(tài)序列

　　和上面一個(gè)問(wèn)題相似的并且更有趣的是根據(jù)可觀察序列找到隱藏序列。在很多情況下，我們對(duì)隱藏狀態(tài)更有興趣，因?yàn)槠浒艘恍┎荒鼙恢苯佑^察到的有價(jià)值的信息。比如說(shuō)在海藻和天氣的例子中，一個(gè)隱居的人只能看到海藻的狀態(tài)，但是他想知道天氣的狀態(tài)。這時(shí)候我們就可以使用 Viterbi 算法來(lái)根據(jù)可觀察序列得到最優(yōu)可能的隱藏狀態(tài)的序列，當(dāng)然前提是已經(jīng)有一個(gè)HMM。

　　另一個(gè)廣泛使用 Viterbi 算法的領(lǐng)域是自然語(yǔ)言處理中的詞性標(biāo)注。句子中的單詞是可以觀察到的，詞性是隱藏的狀態(tài)。通過(guò)根據(jù)語(yǔ)句的上下文找到一句話中的單詞序列的最有可能的隱藏狀態(tài)序列，我們就可以得到一個(gè)單詞的詞性（可能性最大）。這樣我們就可以用這種信息來(lái)完成其他一些工作。

　　下面介紹一下維特比算法(Viterbi Algorithm)

　　一．如何找到可能性最大的隱藏狀態(tài)序列？

　　通常我們都有一個(gè)特定的 HMM，然后根據(jù)一個(gè)可觀察狀態(tài)序列去找到最可能生成這個(gè)可觀察狀態(tài)序列的隱藏狀態(tài)序列。

　　1. 窮舉搜索

　　我們可以在下圖中看到每個(gè)隱藏狀態(tài)和可觀察狀態(tài)的關(guān)系。

　　通過(guò)計(jì)算所有可能的隱藏序列的概率，我們可以找到一個(gè)可能性最大的隱藏序列，這個(gè)可能性最大的隱藏序列最大化了 Pr(觀察序列 | 隱藏狀態(tài)集)。比如說(shuō)，對(duì)于上圖中的可觀察序列 (dry damp soggy)，最可能的隱藏序列就是下面這些概率中最大的：

　　Pr(dry, damp, soggy | sunny, sunny, sunny), ……，Pr(dry, damp, soggy | rainy, rainy, rainy)

　　這個(gè)方法是可行的，但是計(jì)算代價(jià)很高。和前向算法一樣，我們可以利用轉(zhuǎn)移概率在時(shí)間上的不變性來(lái)降低計(jì)算的復(fù)雜度。

　　2. 使用遞歸降低復(fù)雜度

　　在給定了一個(gè)可觀察序列和HMM的情況下，我們可以考慮遞歸的來(lái)尋找最可能的隱藏序列。我們可以先定義一個(gè)部分概率 δ，即到達(dá)某個(gè)中間狀態(tài)的概率。接下來(lái)我們將討論如何計(jì)算 t=1 和 t=n (n>1) 的部分概率。

　　注意這里的部分概率和前向算法中的部分概率是不一樣的，這里的部分概率表示的是在t時(shí)刻最可能到達(dá)某個(gè)狀態(tài)的一條路徑的概率，而不是所有概率之和。

　　1) 部分概率和部分最優(yōu)路徑

　　考慮下面這個(gè)圖以及可觀察序列 (dry, damp, soggy) 的一階轉(zhuǎn)移

　　對(duì)于每一個(gè)中間狀態(tài)和終止?fàn)顟B(tài) (t=3) 都有一個(gè)最可能的路徑。比如說(shuō)，在 t=3 時(shí)刻的三個(gè)狀態(tài)都有一個(gè)如下的最可能的路徑：

　　我們可以稱這些路徑為部分最優(yōu)路徑。這些部分最優(yōu)路徑都有一個(gè)概率，也就是部分概率 δ。和前向算法中的部分概率不一樣，這里的概率只是一個(gè)最可能路徑的概率，而不是所有路徑的概率和。

　　我們可以用 δ(i, t) 來(lái)表示在t時(shí)刻，到狀態(tài)i的所有可能的序列（路徑）中概率最大的序列的概率，部分最優(yōu)路徑就是達(dá)到這個(gè)最大概率的路徑，對(duì)于每一個(gè)時(shí)刻的每一個(gè)狀態(tài)都有這樣一個(gè)概率和部分最優(yōu)路徑。

　　最后，我們通過(guò)計(jì)算 t=T 時(shí)刻的每一個(gè)狀態(tài)的最大概率和部分最優(yōu)路徑，選擇其中概率最大的狀態(tài)和它的部分最優(yōu)路徑來(lái)得到全局的最優(yōu)路徑。

　　2) 計(jì)算 t=1 時(shí)刻的部分概率

　　當(dāng) t=1 時(shí)刻的時(shí)候，到達(dá)某個(gè)狀態(tài)最大可能的路徑還不存在，但是我們可以直接使用在 t=1 時(shí)刻某個(gè)狀態(tài)的概率和這個(gè)狀態(tài)到可觀察序列 k₁ 的轉(zhuǎn)移概率：

　　3) 計(jì)算 t>1 時(shí)刻的部分概率

　　接下來(lái)我們可以根據(jù) t-1 時(shí)刻的部分概率來(lái)求 t 時(shí)刻的部分概率

　　我們可以計(jì)算所有到狀態(tài) X 的路徑的概率，找到其中最可能的路徑，也就是局部最優(yōu)路徑。注意到這里，到達(dá)X的路徑必然會(huì)經(jīng)過(guò) t-1 時(shí)刻的 A、B 和 C，所以我們可以利用之前的結(jié)果。達(dá)到X的最可能的路徑就是下面三個(gè)之一：

　　(狀態(tài)序列)，. . .，A，X (狀態(tài)序列)，. . .，B，X (狀態(tài)序列)，. . .，C，X

　　我們需要做的就是找到以 AX、BX 和 CX 結(jié)尾的路徑中概率最大的那個(gè)。

　　根據(jù)一階馬爾科夫的假設(shè)，一個(gè)狀態(tài)的發(fā)生之和之前的一個(gè)狀態(tài)有關(guān)系，所以X在某個(gè)序列的最后發(fā)生的概率只依賴于其之前的一個(gè)狀態(tài)：

Pr (到達(dá)A的最優(yōu)路徑) . Pr (X | A) . Pr (觀察狀態(tài) | X)

　　有個(gè)了這個(gè)公式，我們就可以利用t-1時(shí)刻的結(jié)果和狀態(tài)轉(zhuǎn)移矩陣和混淆矩陣的數(shù)據(jù)：

　　將上面這個(gè)表達(dá)式推廣一下，就可以得到 t 時(shí)刻可觀察狀態(tài)為 k_t 的第 i 個(gè)狀態(tài)的最大部分概率的計(jì)算公式：

　　其中 a_ji 表示從狀態(tài) j 轉(zhuǎn)移到狀態(tài) i 的概率，b_ikt 表示狀態(tài)i被觀察成 k_t 的概率。

　　4) 后向指針

　　考慮下圖

　　在每一個(gè)中間狀態(tài)和結(jié)束狀態(tài)都有一個(gè)部分最優(yōu)概率 δ(i, t)。但是我們的目的是找到最可能的隱藏狀態(tài)序列，所以我們需要一個(gè)方法去記住部分最優(yōu)路徑的每一個(gè)節(jié)點(diǎn)。

　　考慮到要計(jì)算 t 時(shí)刻的部分概率，我們只需要知道 t-1 時(shí)刻的部分概率，所以我們只需要記錄那個(gè)導(dǎo)致了 t 時(shí)刻最大部分概率的的狀態(tài)，也就是說(shuō)，在任意時(shí)刻，系統(tǒng)都必須處在一個(gè)能在下一時(shí)刻產(chǎn)生最大部分概率的狀態(tài)。如下圖所示：

　　我們可以利用一個(gè)后向指針 φ 來(lái)記錄導(dǎo)致某個(gè)狀態(tài)最大局部概率的前一個(gè)狀態(tài)，即

　　這里 argmax 表示能最大化后面公式的j值，同樣可以發(fā)現(xiàn)這個(gè)公式和 t-1 時(shí)刻的部分概率和轉(zhuǎn)移概率有關(guān)，因?yàn)楹笙蛑羔樦皇菫榱苏业健拔覐哪睦飦?lái)”，這個(gè)問(wèn)題和可觀察狀態(tài)沒(méi)有關(guān)系，所以這里不需要再乘上混淆矩陣因子。全局的行為如下圖所示：

　　5) 優(yōu)點(diǎn)

　　使用 viterbi 算法對(duì)一個(gè)可觀察狀態(tài)進(jìn)行解碼有兩個(gè)重要的優(yōu)點(diǎn)：

　　a) 通過(guò)使用遞歸來(lái)減少?gòu)?fù)雜度，這點(diǎn)和之前的前向算法是一樣的

　　b) 可以根據(jù)可觀察序列找到最優(yōu)的隱藏序列，這個(gè)的計(jì)算公式是：

其中 

　　這里就是一個(gè)從左往右翻譯的過(guò)程，通過(guò)前面的翻譯結(jié)果得到后面的結(jié)果，起始點(diǎn)是初始向量 π。

　　3. 補(bǔ)充

　　但在序列某個(gè)地方有噪聲干擾的時(shí)候，某些方法可能會(huì)和正確答案相差的較遠(yuǎn)。但是 Viterbi 算法會(huì)查看整個(gè)序列來(lái)決定最可能的終止?fàn)顟B(tài)，然后通過(guò)后向指針來(lái)找到之前的狀態(tài)，這對(duì)忽略孤立的噪聲非常有用。

　　Viterbi 算法提供了一個(gè)根據(jù)可觀察序列計(jì)算隱藏序列的很高效的方法，它利用遞歸來(lái)降低計(jì)算復(fù)雜度，并且使用之前全部的序列來(lái)做判斷，可以很好的容忍噪聲。

　　在計(jì)算的過(guò)程中，這個(gè)算法計(jì)算每一個(gè)時(shí)刻每一個(gè)狀態(tài)的部分概率，并且使用一個(gè)后向指針來(lái)記錄達(dá)到當(dāng)前狀態(tài)的最大可能的上一個(gè)狀態(tài)。最后，最可能的終止?fàn)顟B(tài)就是隱藏序列的最后一個(gè)狀態(tài)，然后通過(guò)后向指針來(lái)查找整個(gè)序列的全部狀態(tài)。

　?。ㄈ?根據(jù)觀察到的序列集來(lái)找到一個(gè)最有可能的 HMM。 

　　在很多實(shí)際的情況下，HMM 不能被直接的判斷，這就變成了一個(gè)學(xué)習(xí)問(wèn)題，因?yàn)閷?duì)于給定的可觀察狀態(tài)序列 O 來(lái)說(shuō)，沒(méi)有任何一種方法可以精確地找到一組最優(yōu)的HMM 參數(shù) λ 使 P(O | λ) 最大，于是人們尋求使其局部最優(yōu)的解決辦法，而前向后向算法（也稱為Baum-Welch算法）就成了HMM 學(xué)習(xí)問(wèn)題的一個(gè)近似的解決方法。

　　前向后向算法首先對(duì)于HMM 的參數(shù)進(jìn)行一個(gè)初始的估計(jì)，但這個(gè)很可能是一個(gè)錯(cuò)誤的猜測(cè)，然后通過(guò)對(duì)于給定的數(shù)據(jù)評(píng)估這些參數(shù)的的有效性并減少它們所引起的錯(cuò)誤來(lái)更新HMM 參數(shù)，使得和給定的訓(xùn)練數(shù)據(jù)的誤差變小，這其實(shí)是機(jī)器學(xué)習(xí)中的梯度下降的思想。

　　對(duì)于網(wǎng)格中的每一個(gè)狀態(tài)，前向后向算法既計(jì)算到達(dá)此狀態(tài)的“前向”概率，又計(jì)算生成此模型最終狀態(tài)的“后向”概率，這些概率都可以通過(guò)前面的介紹利用遞歸進(jìn)行高效計(jì)算?？梢酝ㄟ^(guò)利用近似的 HMM 模型參數(shù)來(lái)提高這些中間概率從而進(jìn)行調(diào)整，而這些調(diào)整又形成了前向后向算法迭代的基礎(chǔ)。

　　另外，前向后向算法是 EM 算法的一個(gè)特例，它避免了 EM 算法的暴力計(jì)算，而采用動(dòng)態(tài)規(guī)劃思想來(lái)解決問(wèn)題，Jelinek 在其書《Statistical Methods for Speech Recognition》中對(duì)前向后向算法與 EM 算法的關(guān)系進(jìn)行了詳細(xì)描述，有興趣的讀者可以參考這本書。

　　類似于上面講到的前向算法，我們也可以定義后向變量 β_t(i) 來(lái)計(jì)算給定當(dāng)前隱藏狀態(tài) i 時(shí)，部分觀察序列 o_t+1，o_t+2，…，o_T的概率，即：

　　與前向算法類似，我們也可以通過(guò)迭代算法有效計(jì)算 β_t(i)，計(jì)算公式如下：

　　其中

　　進(jìn)一步我們可以發(fā)現(xiàn)

　　因此

　　下面開(kāi)始介紹前向后向算法。

　　首先我們需要定義兩個(gè)輔助變量，這兩個(gè)變量可以用前文介紹過(guò)的前向變量和后向變量進(jìn)行定義。

　　第一個(gè)變量定義為 t 時(shí)狀態(tài) i 和 t+1 時(shí)狀態(tài) j 的概率，即

　　該變量在網(wǎng)格中所代表的關(guān)系如下圖所示：

　　該等式等價(jià)于

　　利用前向變量和后向變量，上式可以表示為

　　第二個(gè)變量定義為后驗(yàn)概率，也就是在給定觀察狀態(tài)序列和HMM 的情況下，t 時(shí)狀態(tài) i 的概率，即

　　利用前向變量和后向變量，上式可以表示為

　　因此，下式為在任意時(shí)刻狀態(tài) i 的期望，也就是從狀態(tài) i 轉(zhuǎn)移到觀察狀態(tài) o 的期望

　　同樣，下式也就是從狀態(tài) i 轉(zhuǎn)移到狀態(tài) j 的期望

　　我們可以發(fā)現(xiàn)定義的這兩個(gè)變量之間的關(guān)系為

　　下面介紹前向后向算法的參數(shù)學(xué)習(xí)過(guò)程，在學(xué)習(xí)的過(guò)程中，不斷更新 HMM 的參數(shù)，從而使得 P(O | λ) 最大。我們假設(shè)初始的HMM 參數(shù)為  λ={ π, A, B }，首先計(jì)算前向變量 α 和后向變量 β，再根據(jù)剛剛介紹的公式計(jì)算期望 ξ 和 ζ，最后，根據(jù)下面的3個(gè)重估計(jì)公式更新 HMM 參數(shù)。

　　如果我們定義當(dāng)前的HMM 模型為 λ={ π，A，B }，那么可以利用該模型計(jì)算上面三個(gè)式子的右端；我們?cè)俣x重新估計(jì)的 HMM 模型為，那么上面三個(gè)式子的左端就是重估的HMM 模型參數(shù)。Baum 及他的同事在70年代證明了，因此如果我們迭代地計(jì)算上面三個(gè)式子，由此不斷地重新估計(jì)HMM 的參數(shù)，那么在多次迭代后可以得到 HMM 模型的一個(gè)最大似然估計(jì)。不過(guò)需要注意的是，前向后向算法所得的這個(gè)最大似然估計(jì)是一個(gè)局部最優(yōu)解。

　　參考資料：

　　1. http://blog.csdn.net/eaglex/article/details/6376826

　　2. http://en./wiki/Markov_chain

　　3. http://en./wiki/Hidden_Markov_model

　　4. Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.Proceedings of the IEEE, 77 (2), p. 257–286, February 1989.

　　5. L. R. Rabiner and B. H. Juang, “An introduction to HMMs,”IEEE ASSP Mag., vol. 3, no. 1, pp. 4-16, 1986.

　　6. http://jedlik.phy./~gerjanos/HMM/node2.html

　　7. http://www.cs./research/ai/dynamics/tutorial/Documents/HiddenMarkovModels.html

　　8. 隱馬爾可夫模型簡(jiǎn)介，劉群