馬爾可夫鏈模型

馬爾可夫鏈模型

馬爾可夫模型是統計模型,它用來描述一個含有隱含未知參數的馬爾可夫過程。

隨機過程

馬爾可夫鏈,因安德烈·馬爾可夫(A.A.Markov,1856-1922)得名,是數學中具有馬爾可夫性質的離散時間隨機過程。該過程中,在給定當前知識或信息的情況下,過去(即當期以前的歷史狀態)對於猜測將來(即當期以後的未來狀態)是無關的。馬爾可夫鏈是滿足下面兩個假設的一種隨機過程:

1、t+l時刻系統狀態機率分布只與t時刻的狀態有關,與t時刻以前的狀態無關;

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

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

2)是系統的狀態轉移機率矩陣,其中Pij表示系統在時刻t處於狀態i,在下一時刻t+l處於狀態i的機率,N是系統所有可能的狀態的個數。對於任意i∈s,有。

3)是系統的初始機率分布,qi是系統在初始時刻處於狀態i的機率,滿足。

隱含馬爾可夫模型

馬爾可夫鏈模型隱含馬爾可夫模型
隱含馬爾可夫模型是一個數學模型,到目前為之,它一直被認為是實現快速精確的語音識別系統的最成功的方法。複雜的語音識別問題通過隱含馬爾可夫模型能非常簡單地被表述、解決,讓人們不由由衷地感嘆數學模型之妙。

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

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

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

當然,上面的機率不容易直接求出,於是人們可以間接地計算它。利用貝葉斯公式並且省掉一個常數項,可以把上述公式等價變換成

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,...本身能夠成為一個合乎情理的句子的可能性,所以這個公式的意義是用傳送信號為s1,s2,s3...這個數列的可能性乘以s1,s2,s3...本身可以一個句子的可能性,得出機率。

(讀者讀到這裡也許會問,你現在是不是把問題變得更複雜了,因為公式越寫越長了。別著急,現在就來簡化這個問題。)人們們在這裡做兩個假設:

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

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

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

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

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

演變

馬爾可夫鏈模型馬爾可夫鏈模型

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

套用

HMM有三個經典(canonical)問題:

已知模型參數,計算某一特定輸出序列的機率,通常使用forward算法解決;
已知模型參數,尋找最可能的能產生某一特定輸出序列的隱含狀態的序列,通常使用Viterbi算法解決;
已知輸出序列,尋找最可能的狀態轉移以及輸出機率,通常使用Baum-Welch算法以及ReversedViterbi算法解決;另外,最近的一些方法使用Junctiontree算法來解決這三個問題。

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

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

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

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

套用

語音識別或光學字元識別
機器翻譯
生物信息學和基因組學
基因組序列中蛋白質編碼區域的預測
對於相互關聯的DNA或蛋白質族的建模
從基本結構中預測第二結構元素

歷史

馬爾可夫模型最初是在二十世紀六十年代後半期LeonardE.Baum和其它一些作者在一系列的統計學論文中描述的。HMM最初的套用之一是開始於二十世紀七十年代中期的語音識別。在二十世紀八十年代後半期,HMM開始套用到生物序列尤其是DNA的分析中。從那時開始,在生物信息學領域它們已經變得無處不在。

管理學知識(四)

管理學是系統研究管理活動的基本規律和一般方法的科學。管理學是適應現代社會化大生產的需要產生的,它的目的是:研究在現有的條件下,如何通過合理的組織和配置人、財、物等因素,提高生產力的水平。管理學是一門綜合性的交叉學科。

相關詞條

相關搜尋

熱門詞條

聯絡我們