馬爾可夫鏈模型 - 隨機過程

馬爾可夫鏈，因安德烈·馬爾可夫（A.A.Markov，1856－1922）得名，是數(shù)學(xué)中具有馬爾可夫性質(zhì)的離散時間隨機過程。該過程中，在給 定當(dāng)前知識或信息的情況下，過去（即當(dāng)期以前的歷史狀態(tài)）對于猜測將來（即當(dāng)期以后的未來狀態(tài)）是無關(guān)的。馬爾可夫鏈?zhǔn)菨M足下面兩個假設(shè)的一種隨機過程：

1、t+l時刻系統(tǒng)狀態(tài)的概率分布只與t時刻的狀態(tài)有關(guān)，與t時刻以前的狀態(tài)無關(guān)；

2、從t時刻到t+l時刻的狀態(tài)轉(zhuǎn)移與t的值無關(guān)。一個馬爾可夫鏈模型可表示為=(S，P，Q)，其中各元的含義如下：

1）S是系統(tǒng)所有可能的狀態(tài)所組成的非空的狀態(tài)集，有時也稱之為系統(tǒng)的狀態(tài)空間，它可以是有限的、可列的集合或任意非空集。本文中假定S是可數(shù)集(即有限或可列)。用小寫字母i，j(或Si，Sj)等來表示狀態(tài)。

2）是系統(tǒng)的狀態(tài)轉(zhuǎn)移概率矩陣，其中Pij表示系統(tǒng)在時刻t處于狀態(tài)i，在下一時刻t+l處于狀態(tài)i的概率，N是系統(tǒng)所有可能的狀態(tài)的個數(shù)。對于任意i∈s，有。

3）是系統(tǒng)的初始概率分布，qi是系統(tǒng)在初始時刻處于狀態(tài)i的概率，滿足。

隱含馬爾可夫模型

自然語言是人類交流信息的工具。很多自然語言處理問題都可以等同于通信系統(tǒng)中的解碼問題--一個人根據(jù)接收到的信息，去猜測發(fā)話人要表達的意思。這 其實就象通信中，人們根據(jù)接收端收到的信號去分析、理解、還原發(fā)送端傳送過來的信息。右圖就表示了一個典型的通信系統(tǒng)：其中s1，s2，s3...表示信 息源發(fā)出的信號。o1,o2,o3...是接受器接收到的信號。通信中的解碼就是根據(jù)接收到的信號o1,o2,o3...還原出發(fā)送的信號 s1，s2，s3...。

其實人們平時在說話時，腦子就是一個信息源。人們的喉嚨（聲帶），空氣，就是如電線和光纜般 的信道。聽眾耳朵的就是接收端，而聽到的聲音就是傳送過來的信號。根據(jù)聲學(xué)信號來推測說話者的意思，就是語音識別。這樣說來，如果接收端是一臺計算機而不 是人的話，那么計算機要做的就是語音的自動識別。同樣，在計算機中，如果我們要根據(jù)接收到的英語信息，推測說話者的漢語意思，就是機器翻譯；如果我們要根 據(jù)帶有拼寫錯誤的語句推測說話者想表達的正確意思，那就是自動糾錯。

那么怎么根據(jù)接收到的信息來推測說話者想表達的意思呢？人們可以利用叫做“隱含馬爾可夫模型”（HiddenMarkovModel）來解決這些問 題。以語音識別為例，當(dāng)我們觀測到語音信號o1,o2,o3時，要根據(jù)這組信號推測出發(fā)送的句子s1,s2,s3。顯然，人們應(yīng)該在所有可能的句子中找最 有可能性的一個。用數(shù)學(xué)語言來描述，就是在已知o1,o2,o3,...的情況下，求使得條件概率
P(s1,s2,s3,...|o1,o2,o3....)達到最大值的那個句子s1,s2,s3,...

當(dāng)然，上面的概率不容易直接求出，于是人們可以間接地計算它。利用貝葉斯公式并且省掉一個常數(shù)項，可以把上述公式等價變換成

P(o1,o2,o3,...|s1,s2,s3....)*P(s1,s2,s3,...)
其中
P(o1,o2,o3,...|s1,s2,s3....)表示某句話s1,s2,s3...被讀成o1,o2,o3,...的可能性,而
P(s1,s2,s3,...)表示字串s1,s2,s3,...本身能夠成為一個合乎情理的句子的可能性，所以這個公式的意義是用發(fā)送信號為s1,s2,s3...這個數(shù)列的可能性乘以s1,s2,s3...本身可以一個句子的可能性，得出概率。

（讀者讀到這里也許會問，你現(xiàn)在是不是把問題變得更復(fù)雜了，因為公式越寫越長了。別著急，現(xiàn)在就來簡化這個問題。）人們們在這里做兩個假設(shè)：

第一，s1,s2,s3,...是一個馬爾可夫鏈，也就是說，si只由si-1決定(詳見系列一)；
第二，第i時刻的接收信號oi只由發(fā)送信號si決定（又稱為獨立輸出假設(shè),即P(o1,o2,o3,...|s1,s2,s3....)=P(o1|s1)*P(o2|s2)*P(o3|s3)...。
那么人們就可以很容易利用算法Viterbi找出上面式子的最大值，進而找出要識別的句子s1,s2,s3,...。

滿足上述兩個假設(shè)的模型就叫隱含馬爾可夫模型。我們之所以用“隱含”這個詞，是因為狀態(tài)s1,s2,s3,...是無法直接觀測到的。

隱含馬爾可夫模型的應(yīng)用遠不只在語音識別中。在上面的公式中，如果我們把s1,s2,s3,...當(dāng)成中文，把o1,o2,o3,...當(dāng)成對應(yīng)的英文，那么人們就能利用這個模型解決機器翻譯問題；如果我們把o1,o2,o3,...當(dāng)成掃描文字得到的圖像特征，就能利用這個模型解決印刷體和手寫體的識別。

P(o1,o2,o3,...|s1,s2,s3....)根據(jù)應(yīng)用的不同而又不同的名稱，在語音識別中它被稱為“聲學(xué)模型”(AcousticModel)，在機器翻譯中是“翻譯模型”(TranslationModel)而在拼寫校正中是“糾錯模型”(CorrectionModel)。而P(s1,s2,s3,...)就是我們在系列一中提到的語言模型。

在利用隱含馬爾可夫模型解決語言處理問題前，先要進行模型的訓(xùn)練。常用的訓(xùn)練方法由伯姆（Baum）在60年代提出的，并以他的名字命名。隱含馬爾可夫模型在處理語言問題早期的成功應(yīng)用是語音識別。七十年代，當(dāng)時IBM的FredJelinek(賈里尼克)和卡內(nèi)基·梅隆大學(xué)的 JimandJanetBaker(貝克夫婦，李開復(fù)的師兄師姐)分別獨立地提出用隱含馬爾可夫模型來識別語音，語音識別的錯誤率相比人工智能和模式匹配 等方法降低了三倍(從30%到10%)。八十年代李開復(fù)博士堅持采用隱含馬爾可夫模型的框架，成功地開發(fā)了世界上第一個大詞匯量連續(xù)語音識別系統(tǒng) Sphinx。

馬爾可夫鏈模型

上邊的圖示強調(diào)了HMM的狀態(tài)變遷。有時，明確的表示出模型的演化也是有用的，人們用x（t1）與x（t2）來表達不同時刻t1和t2的狀態(tài)。在這個圖中，每一個時間塊（x(t)，y(t)）都可以向前或向后延伸。通常，時間的起點被設(shè)置為t=0或t=1.

HMM有三個經(jīng)典(canonical)問題：

已知模型參數(shù)，計算某一特定輸出序列的概率，通常使用forward算法解決；
已知模型參數(shù)，尋找最可能的能產(chǎn)生某一特定輸出序列的隱含狀態(tài)的序列，通常使用Viterbi算法解決；
已知輸出序列，尋找最可能的狀態(tài)轉(zhuǎn)移以及輸出概率，通常使用Baum-Welch算法以及ReversedViterbi算法解決；另外，最近的一些方法使用Junctiontree算法來解決這三個問題。

具體實例
假設(shè)你有一個住得很遠的朋友，他每天跟你打電話告訴你他那天作了什么。你的朋友僅僅對三種活動感興趣：公園散步，購物以及清理房間，他選擇做什么事情只憑天氣，你對于他所住的地方的天氣情況并不了解，但是你知道總的趨勢。在他告訴你每天所做的事情基礎(chǔ)上，你想要猜測他所在地的天氣情況。

你認為天氣的運行就像一個馬爾可夫鏈，其有兩個狀態(tài)“雨”和“晴”，但是你無法直接觀察它們，也就是說，它們對于你是隱藏的，每天，你的朋友有一定 的概率進行下列活動：“散步”，“購物”或“清理”。因為你朋友告訴你他的活動，所以這些活動就是你的觀察數(shù)據(jù)。這整個系統(tǒng)就是一個隱馬爾可夫模型 HMM。

你知道這個地區(qū)的總的天氣趨勢，并且平時知道你朋友會做的事情，也就是說這個隱馬爾可夫模型的參數(shù)是已知的。你可以用程序語言（Python）寫下來：在這些代碼中，start_probability 代表了你對于你朋友第一次給你打電話時的天氣情況的不確定性（你知道的只是那個地方平均起來下雨多些）。在這里，這個特定的概率分布并非平衡的，平衡概率 應(yīng)該接近（在給定變遷概率的情況下）{'Rainy':0.571,'Sunny':0.429}<transition_probability 表示基于馬爾可夫鏈模型的天氣變遷，在這個例子中，如果今天下雨，那么明天天晴的概率只有30%。代碼emission_probability表示了你朋友每天作某件事的概率.如果下雨，有50%的概率他在清理房間；如果天晴，則有60%的概率他在外頭散步。

這個例子在Viterbi算法頁上有更多的解釋。

語音識別或光學(xué)字符識別
機器翻譯
生物信息學(xué)和基因組學(xué)
基因組序列中蛋白質(zhì)編碼區(qū)域的預(yù)測
對于相互關(guān)聯(lián)的DNA或蛋白質(zhì)族的建模
從基本結(jié)構(gòu)中預(yù)測第二結(jié)構(gòu)元素

馬爾可夫模型最初是在二十世紀六十年代后半期LeonardE.Baum和其它一些作者在一系列的統(tǒng)計學(xué)論文中描述的。HMM最初的應(yīng)用之一是開始 于二十世紀七十年代中期的語音識別。在二十世紀八十年代后半期，HMM開始應(yīng)用到生物序列尤其是DNA的分析中。從那時開始，在生物信息學(xué)領(lǐng)域它們已經(jīng)變 得無處不在。^[1]