本章涉及到的概率論的知識(shí)較多。前方高能。

前方高能。

前方高能。。。。

馬爾科夫模型在前兩章統(tǒng)計(jì)語言模型中已經(jīng)有介紹了，這里不再贅述。

在通信中，如何根據(jù)接收端的觀測(cè)信號(hào)來推測(cè)信號(hào)源發(fā)送的信息呢？這就需要從所有的源信息中找到最可能產(chǎn)生觀測(cè)信號(hào)的那一個(gè)信號(hào)。用概率論的語言，就是在已知接收到的信號(hào)o的情況下，求得令條件概率P(s|o)達(dá)到最大值的那個(gè)信息串s。

先別暈。因?yàn)楹竺鏁?huì)更暈。

根據(jù)貝葉斯公式轉(zhuǎn)換一下，

P（s|o）=P(o|s)*P(s)/P(o)

即為求解P(s|o)*P(s)/P(o)最大值的過程。

這時(shí)候就會(huì)發(fā)現(xiàn)一個(gè)問題，求解這樣一個(gè)方程，是個(gè)復(fù)雜度極高的事情。隱含馬爾科夫模型就要登場(chǎng)了。

隱含馬爾科夫模型是馬爾科夫鏈的一個(gè)擴(kuò)展：假設(shè)任一時(shí)刻t的狀態(tài)st是不可見的。這樣就沒法通過s序列去推測(cè)轉(zhuǎn)移概率等參數(shù)。（為什么要這樣假設(shè)？因?yàn)閷?duì)于骰子的輸出163245來說，我們不僅僅有一串可見狀態(tài)鏈，還有一串隱含狀態(tài)鏈?？梢姞顟B(tài)鏈?zhǔn)谴_定的概率，如6個(gè)面骰子點(diǎn)數(shù)的概率；而隱含狀態(tài)鏈?zhǔn)遣淮_定概率，如選擇的骰子是6個(gè)面的還是4個(gè)面）

那這樣還怎么玩？別急。

隱含馬爾科夫模型在每個(gè)時(shí)刻t會(huì)輸出一個(gè)符號(hào)ot，而且ot跟且僅跟st相關(guān)。這是一個(gè)獨(dú)立輸出假設(shè)。

基于馬爾科夫假設(shè)和獨(dú)立輸出假設(shè)，我們就可以計(jì)算出某個(gè)特定的狀態(tài)序列s產(chǎn)生出輸出符號(hào)序列o的概率。

要找到這個(gè)概率的最大值，可以使用維特比算法。這是個(gè)解碼算法。

維特比算法說白了就是動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)最短路徑，只要知道“動(dòng)態(tài)規(guī)劃可以降低復(fù)雜度”這一點(diǎn)就能輕松理解維特比算法?！袄脛?dòng)態(tài)規(guī)劃，可以解決任何一個(gè)圖中的最短路徑問題。而維特比算法是針對(duì)一個(gè)特殊的圖——籬笆網(wǎng)絡(luò)的有向圖（Lattice )的最短路徑問題而提出的。 它之所以重要，是因?yàn)榉彩鞘褂秒[含馬爾可夫模型描述的問題都可以用它來解碼?！?br>

維特比算法的精髓就是，既然知道到第i列所有節(jié)點(diǎn)Xi{j=123…}的最短路徑，那么到第i+1列節(jié)點(diǎn)的最短路徑就等于到第i列j個(gè)節(jié)點(diǎn)的最短路徑+第i列j個(gè)節(jié)點(diǎn)到第i+1列各個(gè)節(jié)點(diǎn)的距離的最小值。復(fù)雜度驟減為O（ND2），遠(yuǎn)遠(yuǎn)小于窮舉O（DN）。

總的來說，

圍繞著隱含馬爾科夫模型有三個(gè)基本問題：

1. 給定一個(gè)模型，如何計(jì)算某個(gè)特定的輸出序列的概率；

2. 給定一個(gè)模型和某個(gè)特定的輸出序列，如何找打最可能產(chǎn)生這個(gè)輸出的狀態(tài)序列；

3. 給定足夠量的觀測(cè)數(shù)據(jù)，如何估計(jì)隱含馬爾科夫模型的參數(shù)。

解：

第一個(gè)問題，對(duì)應(yīng)的算法是Forward-Backward算法。

前向-后向算法首先對(duì)于隱馬爾科夫模型的參數(shù)進(jìn)行一個(gè)初始的估計(jì)（這很可能是完全錯(cuò)誤的），然后通過對(duì)于給定的數(shù)據(jù)評(píng)估這些參數(shù)的的價(jià)值并減少它們所引起的錯(cuò)誤來重新修訂這些HMM參數(shù)（即隱含馬爾科夫參數(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ǔ)。

第二個(gè)問題，對(duì)應(yīng)的算法是維特比算法（解碼算法），不再贅述。

第三個(gè)問題，是模型訓(xùn)練的問題。無監(jiān)督模型對(duì)應(yīng)的算法是Baum-Welch Algorithm（訓(xùn)練算法）。

Baum-Welch Algorithm的基本思想是，隨便找到一組能夠產(chǎn)生輸出序列o的模型參數(shù)，那就可以算出這個(gè)模型產(chǎn)生輸出序列o的概率和這個(gè)模型產(chǎn)生o的所有可能的路徑以及這些路徑的概率，因此可以將這些視為“標(biāo)注的訓(xùn)練數(shù)據(jù)”，根據(jù)最優(yōu)解，計(jì)算出一組新的模型參數(shù)，從而不斷迭代，直到使得輸出概率達(dá)到最大化。這個(gè)過程稱為期望最大化，也就是EM過程。

解析完畢。

暈了吧？

要是已經(jīng)暈了也沒關(guān)系。

不就是分詞嘛，成熟工具多得是。我們又不專業(yè)搞算法研究，這種“輪子”的制造技術(shù)，知道個(gè)大概就好。把“車”開好才是王道。

嗚~~~~~