初識馬爾可夫和馬爾可夫鍊
作者：
白甯超2016年7月10日20:34:20
摘要：最早接觸馬爾可夫模型的定義源于吳軍先生《數學之美》一書，起初覺得深奧難懂且無什麼用場。直到學習自然語言處理時，才真正使用到隐馬爾可夫模型，并體會到此模型的妙用之處。馬爾可夫模型在處理序列分類時具體強大的功能，諸如解決：詞類标注、語音識别、句子切分、字素音位轉換、局部句法剖析、語塊分析、命名實體識别、資訊抽取等。另外廣泛應用于自然科學、工程技術、生物科技、公用事業、信道編碼等多個領域。本文寫作思路如下：第一篇對馬爾可夫個人簡介和馬爾科夫鍊的介紹；第二篇介紹馬爾可夫鍊（顯馬爾可夫模型）和隐馬爾可夫模型以及隐馬爾可夫模型的三大問題（似然度、編碼、參數學習）；第三至五篇逐一介紹三大問題相關算法：（向前算法、維特比算法、向前向後算法）；最後非常得益于馮志偉先生自然語言處理教程一書，馮老研究自然語言幾十餘載，在此領域别有建樹。（本文原創，轉載注明出處： )
目錄
【自然語言處理：馬爾可夫模型（一）】：
【自然語言處理：馬爾可夫模型（二）】：
馬爾可夫模型與隐馬爾可夫模型【自然語言處理：馬爾可夫模型（三）】：
向前算法解決隐馬爾可夫模型似然度問題【自然語言處理：馬爾可夫模型（四）】：
維特比算法解決隐馬爾可夫模型解碼問題（中文句法标注）【自然語言處理：馬爾可夫模型（五）】：
向前向後算法解決隐馬爾可夫模型機器學習問題1 馬爾可夫個人簡介
安德烈·馬爾可夫，俄羅斯人，實體-數學博士，聖彼得堡科學院院士，彼得堡數學學派的代表人物，以數論和機率論方面的工作著稱，他的主要著作有《機率演算》等。1878年，榮獲金質獎章，1905年被授予功勳教授稱号。馬爾可夫是彼得堡數學學派的代表人物。以數論和機率論方面的工作著稱。他的主要著作有《機率演算》等。在數論方面，他研究了連分數和二次不定式理論 ，解決了許多難題 。在機率論中，他發展了矩陣法，擴大了大數律和中心極限定理的應用範圍。馬爾可夫最重要的工作是在1906～1912年間，提出并研究了一種能用數學分析方法研究自然過程的一般圖式——馬爾可夫鍊。同時開創了對一種無後效性的随機過程——馬爾可夫過程的研究。馬爾可夫經多次觀察試驗發現，一個系統的狀态轉換過程中第n次轉換獲得的狀态常取決于前一次（第（n-1）次）試驗的結果。馬爾可夫進行深入研究後指出：對于一個系統，由一個狀态轉至另一個狀态的轉換過程中，存在着轉移機率，并且這種轉移機率可以依據其緊接的前一種狀态推算出來，與該系統的原始狀态和此次轉移前的馬爾可夫過程無關。馬爾可夫鍊理論與方法在現代已經被廣泛應用于自然科學、工程技術和公用事業中。
2 馬爾可夫鍊
2.1 馬爾科夫鍊的基本概念
序列分類器：序列分類器或序列标号器是給序列中的某個單元指派類或者标号的模型。馬爾可夫模型（又叫顯馬爾可夫模型VMM）和隐馬爾可夫模型（HMM）都是序列分類器。諸如：詞類标注、語音識别、句子切分、字素音位轉換、局部句法剖析、語塊分析、命名實體識别、資訊抽取都屬于序列分類。
【随機過程的兩層含義】
（1） 随機過程是一個時間函數，其随着時間變化而變化
（2） 随機過程的每個時刻上函數值是不确定的、随機的，即每個時刻上函數值按照一定的機率進行分布。
獨立鍊：随機過程中各個語言符合或者詞是獨立的，不互相影響，則稱這種鍊是獨立鍊。反之，各語言詞或者符号彼此有關則是非獨立鍊。
等機率獨立鍊與非等機率獨立鍊：在獨立鍊中，各個語言符合或者詞是等機率出現的是等機率獨立鍊，各個語言詞或者語言符号是非等機率出現的則為非等機率鍊。
【馬爾可夫鍊】
馬爾可夫過程：在獨立鍊中，前面語言符号對後面的語言符号無影響，是無記憶沒有後效的随機過程，在已知目前狀态下，過程的未來狀态與它的過去狀态無關，這種形式就是馬爾可夫過程。
馬爾可夫鍊：在随機過程中，每個語言符号的出現機率不互相獨立，每個随機試驗的目前狀态依賴于此前狀态，這種鍊就是馬爾可夫鍊。
鍊的解析：也可以當做一種觀察序列，諸如：“2016年是建黨95周年”，就可以看着一個字元串鍊。其中如上字元串中每個字元出現是随機的，其他如果每個字出現是獨立的就是獨立鍊，如果每個字元出現有前面字元相關，即不獨立具有依賴性則為馬爾科夫鍊。
N元馬爾科夫鍊：
考慮前一個語言符号對後一個語言符号出現機率的影響，這樣得出的語言成分的鍊叫做一重馬爾可夫鍊，也是二進制文法。
考慮前兩個語言符号對後一個語言符号出現機率的影響，這樣得出的語言成分的鍊叫做二重馬爾可夫鍊，也是三元文法。
考慮前三個語言符号對後一個語言符号出現機率的影響，這樣得出的語言成分的鍊叫做三重馬爾可夫鍊，也是四元文法。
類似的，考慮前（4,5，….,N-1）個語言符号對後一個語言符号出現機率的影響，這樣得出的語言成分的鍊叫做（4,5，….,N-1）重馬爾可夫鍊，也是（5，6，….,N）元文法。
馬爾科夫鍊在數學上描述了自然語言句子的生成過程，是一個早期的自然語言形式的模型，後來N元文法的研究，都是建立在馬爾科夫模型的基礎上，馬爾科夫鍊也就是顯性的馬爾科夫模型，馬爾科夫鍊和隐馬爾科夫模型都是有限自動機（狀态集合狀态之間的轉移集）的擴充。
權重有限狀态機：權重有限狀态機中每個弧與一個機率有關，這個機率說明通過這個弧的可能性，且某一個點出發的弧具有歸一化的性質，即某點出發的弧機率之和為1。
注意：馬爾科夫鍊不能表示固有歧義的問題，當機率指派給沒有歧義時，馬爾科夫鍊才有用。
2.2 馬爾可夫鍊描述
（1） 具有初始狀态和終結狀态的馬爾科夫鍊描述如下：
（2） 沒有初始狀态和終結狀态的馬爾科夫鍊描述如下：
在一個一階馬爾可夫鍊中，我們假設一個特定的機率隻與它前面一個狀态有關，馬爾可夫假設可以表示如下：
從一個狀态i出發的所有弧的機率之和為1，即：
2.3 馬爾可夫鍊應用執行個體
無初始狀态和終結狀态下，天氣事件（1）hot hot hot hot 和（2）cold hot cold hot的馬爾科夫鍊的序列機率：
（1） hot hot hot hot =0.5*0.5*0.5*0.5=0.0625
（2） cold hot cold hot=0.3*0.2*0.2*0.2=0.0024
如上機率差别告訴我們用馬爾科夫鍊編碼實作世界天氣事實是什麼？天氣事件的機率可以直接觀察到。
3 參考文獻
【1】統計自然語言處理基礎 Christopher.Manning等 著 宛春法等 譯
【2】自然語言處理簡明教程 馮志偉 著
【3】數學之美 吳軍 著
【4】Viterbi算法分析文章 王亞強
聲明：關于此文各個篇章，本人采取梳理扼要，順暢通明的寫作手法。一則參照相關資料二則根據自己了解進行梳理。避免冗雜不清，每篇文章讀者可理清核心知識，再找相關文獻系統閱讀。另外，要學會舉一反三，不要死盯着定義或者某個例子不放。諸如：此文章例子冰淇淋數量（觀察值）與天氣冷熱（隐藏值）例子，讀者不免問道此有何用？我們将冰淇淋數量換成中文文本或者語音（觀察序列），将天氣冷熱換成英文文本或者語音文字（隐藏序列）。把這個問題解決了不就是解決了文本翻譯、語音識别、自然語言了解等等。解決了自然語言的識别和了解，再應用到現在機器人或者其他裝置中，不就達到實用和聯系現實生活的目的了？本文原創，轉載注明出處：
http://www.cnblogs.com/baiboy