相信大家都看過上一節(jié)我講得貝葉斯網(wǎng)絡(luò)，都明白了概率圖模型是怎樣構(gòu)造的，如果現(xiàn)在還沒明白，請看我上一節(jié)的總結(jié)：貝葉斯網(wǎng)絡(luò)
這一節(jié)我們重點來講一下馬爾可夫，正如題目所示，看了會一臉蒙蔽，好在我們會一點一點的來解釋上面的概念，請大家按照順序往下看就會完全弄明白了，這里我給一個通俗易懂的定義，后面我們再來一個個詳解。
以下共分六點說明這些概念，分成條目只是方便邊閱讀邊思考，這6點是依次遞進的，不要跳躍著看。
將隨機變量作為結(jié)點，若兩個隨機變量相關(guān)或者不獨立，則將二者連接一條邊；若給定若干隨機變量，則形成一個有向圖，即構(gòu)成一個網(wǎng)絡(luò)。
如果該網(wǎng)絡(luò)是有向無環(huán)圖，則這個網(wǎng)絡(luò)稱為貝葉斯網(wǎng)絡(luò)。
如果這個圖退化成線性鏈的方式，則得到馬爾可夫模型；因為每個結(jié)點都是隨機變量，將其看成各個時刻(或空間)的相關(guān)變化，以隨機過程的視角，則可以看成是馬爾可夫過程。
若上述網(wǎng)絡(luò)是無向的，則是無向圖模型，又稱馬爾可夫隨機場或者馬爾可夫網(wǎng)絡(luò)。
如果在給定某些條件的前提下，研究這個馬爾可夫隨機場，則得到條件隨機場。
如果使用條件隨機場解決標(biāo)注問題，并且進一步將條件隨機場中的網(wǎng)絡(luò)拓撲變成線性的，則得到線性鏈條件隨機場。
馬爾可夫過程（Markov process）是一類隨機過程。它的原始模型馬爾可夫鏈，由俄國數(shù)學(xué)家A.A.馬爾可夫于1907年提出。該過程具有如下特性：在已知目前狀態(tài)（現(xiàn)在）的條件下，它未來的演變（將來）不依賴于它以往的演變 (過去 )。例如森林中動物頭數(shù)的變化構(gòu)成——馬爾可夫過程。在現(xiàn)實世界中，有很多過程都是馬爾可夫過程，如液體中微粒所作的布朗運動、傳染病受感染的人數(shù)、車站的候車人數(shù)等，都可視為馬爾可夫過程。
每個狀態(tài)的轉(zhuǎn)移只依賴于之前的n個狀態(tài)，這個過程被稱為1個n階的模型，其中n是影響轉(zhuǎn)移狀態(tài)的數(shù)目。最簡單的馬爾可夫過程就是一階過程，每一個狀態(tài)的轉(zhuǎn)移只依賴于其之前的那一個狀態(tài)，這個也叫作馬爾可夫性質(zhì)。用數(shù)學(xué)表達式表示就是下面的樣子：
假設(shè)這個模型的每個狀態(tài)都只依賴于之前的狀態(tài)，這個假設(shè)被稱為馬爾科夫假設(shè)，這個假設(shè)可以大大的簡化這個問題。顯然，這個假設(shè)可能是一個非常糟糕的假設(shè)，導(dǎo)致很多重要的信息都丟失了。
假設(shè)天氣服從馬爾可夫鏈：
從上面這幅圖可以看出：
假如今天是晴天，明天變成陰天的概率是0.1
假如今天是晴天，明天任然是晴天的概率是0.9，和上一條概率之和為1，這也符合真實生活的情況。
| 晴 | 陰 | |
|---|---|---|
| 晴 | 0.9 | 0,1 |
| 陰 | 0.5 | 0.5 |
由上表我們可以得到馬爾可夫鏈的狀態(tài)轉(zhuǎn)移矩陣：
因此，一階馬爾可夫過程定義了以下三個部分：
狀態(tài)：晴天和陰天
初始向量：定義系統(tǒng)在時間為0的時候的狀態(tài)的概率
狀態(tài)轉(zhuǎn)移矩陣：每種天氣轉(zhuǎn)換的概率
馬爾可夫模型（Markov Model）是一種統(tǒng)計模型，廣泛應(yīng)用在語音識別，詞性自動標(biāo)注，音字轉(zhuǎn)換，概率文法等各個自然語言處理等應(yīng)用領(lǐng)域。經(jīng)過長期發(fā)展，尤其是在語音識別中的成功應(yīng)用，使它成為一種通用的統(tǒng)計工具。到目前為止，它一直被認(rèn)為是實現(xiàn)快速精確的語音識別系統(tǒng)的最成功的方法。
在某些情況下馬爾科夫過程不足以描述我們希望發(fā)現(xiàn)的模式?；氐街澳莻€天氣的例子，一個隱居的人可能不能直觀的觀察到天氣的情況，但是有一些海藻。民間的傳說告訴我們海藻的狀態(tài)在某種概率上是和天氣的情況相關(guān)的。在這種情況下我們有兩個狀態(tài)集合，一個可以觀察到的狀態(tài)集合（海藻的狀態(tài)）和一個隱藏的狀態(tài)（天氣的狀況）。我們希望能找到一個算法可以根據(jù)海藻的狀況和馬爾科夫假設(shè)來預(yù)測天氣的狀況。
而這個算法就叫做隱馬爾可夫模型(HMM)。
隱馬爾可夫模型 (Hidden Markov Model) 是一種統(tǒng)計模型，用來描述一個含有隱含未知參數(shù)的馬爾可夫過程。它是結(jié)構(gòu)最簡單的動態(tài)貝葉斯網(wǎng)，這是一種著名的有向圖模型，主要用于時序數(shù)據(jù)建模，在語音識別、自然語言處理等領(lǐng)域有廣泛應(yīng)用。
給定模型，如何有效計算產(chǎn)生觀測序列的概率？換言之，如何評估模型與觀測序列之間的匹配程度？
給定模型和觀測序列，如何找到與此觀測序列最匹配的狀態(tài)序列？換言之，如何根據(jù)觀測序列推斷出隱藏的模型狀態(tài)？
給定觀測序列，如何調(diào)整模型參數(shù)使得該序列出現(xiàn)的概率最大？換言之，如何訓(xùn)練模型使其能最好地描述觀測數(shù)據(jù)？
前兩個問題是模式識別的問題：1) 根據(jù)隱馬爾科夫模型得到一個可觀察狀態(tài)序列的概率(評價)；2) 找到一個隱藏狀態(tài)的序列使得這個序列產(chǎn)生一個可觀察狀態(tài)序列的概率最大(解碼)。第三個問題就是根據(jù)一個可以觀察到的狀態(tài)序列集產(chǎn)生一個隱馬爾科夫模型（學(xué)習(xí)）。
對應(yīng)的三大問題解法：
向前算法(Forward Algorithm)、向后算法(Backward Algorithm)
維特比算法(Viterbi Algorithm)
鮑姆-韋爾奇算法(Baum-Welch Algorithm) (約等于EM算法)
下面我們以一個場景來說明這些問題的解法到底是什么？
小明現(xiàn)在有三天的假期，他為了打發(fā)時間，可以在每一天中選擇三件事情來做，這三件事情分別是散步、購物、打掃衛(wèi)生(對應(yīng)著可觀測序列)，可是在生活中我們所做的決定一般都受到天氣的影響，可能晴天的時候想要去購物或者散步，可能下雨天的時候不想出門，留在家里打掃衛(wèi)生。而天氣(晴天、下雨天)就屬于隱藏狀態(tài)，用一幅概率圖來表示這一馬爾可夫過程：
那么，我們提出三個問題，分別對應(yīng)馬爾可夫的三大問題：
已知整個模型，我觀測到連續(xù)三天做的事情是：散步，購物，收拾。那么，根據(jù)模型，計算產(chǎn)生這些行為的概率是多少。
同樣知曉這個模型，同樣是這三件事，我想猜，這三天的天氣是怎么樣的。
最復(fù)雜的，我只知道這三天做了這三件事兒，而其他什么信息都沒有。我得建立一個模型，晴雨轉(zhuǎn)換概率，第一天天氣情況的概率分布，根據(jù)天氣情況選擇做某事的概率分布。
下面我們就依據(jù)這個場景來一一解答這些問題。
遍歷算法：
這個是最簡單的算法了，假設(shè)第一天(T=1 時刻)是晴天，想要購物，那么就把圖上的對應(yīng)概率相乘就能夠得到了。
第二天(T=2 時刻)要做的事情，在第一天的概率基礎(chǔ)上乘上第二天的概率，依次類推，最終得到這三天(T=3 時刻)所要做的事情的概率值，這就是遍歷算法，簡單而又粗暴。但問題是用遍歷算法的復(fù)雜度會隨著觀測序列和隱藏狀態(tài)的增加而成指數(shù)級增長。
復(fù)雜度為： 
于是就有了第二種算法
前向算法：
假設(shè)第一天要購物，那么就計算出第一天購物的概率(包括晴天和雨天)；假設(shè)第一天要散步，那么也計算出來，依次枚舉。
假設(shè)前兩天是購物和散步，也同樣計算出這一種的概率；假設(shè)前兩天是散步和打掃衛(wèi)生，同樣計算，枚舉出前兩天行為的概率。
第三步就是計算出前三天行為的概率。
細心的讀者已經(jīng)發(fā)現(xiàn)了，第二步中要求的概率可以在第一步的基礎(chǔ)上進行，同樣的，第三步也會依賴于第二步的計算結(jié)果。那么這樣做就能夠節(jié)省很多計算環(huán)節(jié)，類似于動態(tài)規(guī)劃。
這種算法的復(fù)雜度為：
后向算法
跟前向算法相反，我們知道總的概率肯定是1，那么B_t=1，也就是最后一個時刻的概率合為1，先計算前三天的各種可能的概率，在計算前兩天、前一天的數(shù)據(jù)，跟前向算法相反的計算路徑。
維特比算法(Viterbi)
說起安德魯·維特比（Andrew Viterbi），通信行業(yè)之外的人可能知道他的并不多，不過通信行業(yè)的從業(yè)者大多知道以他的名字命名的維特比算法（ViterbiAlgorithm）。維特比算法是現(xiàn)代數(shù)字通信中最常用的算法，同時也是很多自然語言處理采用的解碼算法?？梢院敛豢鋸埖刂v，維特比是對我們今天的生活影響力最大的科學(xué)家之一，因為基于CDMA的3G移動通信標(biāo)準(zhǔn)主要就是他和厄文·雅各布（Irwin Mark Jacobs）創(chuàng)辦的高通公司（Qualcomm）制定的，并且高通公司在4G時代依然引領(lǐng)移動通信的發(fā)展。
維特比算法是一個特殊但應(yīng)用最廣的動態(tài)規(guī)劃算法。利用動態(tài)規(guī)劃，可以解決任何一個圖中的最短路徑問題。而維特比算法是針對一個特殊的圖—籬笆網(wǎng)絡(luò)（Lattice）的有向圖最短路徑問題而提出的。它之所以重要，是因為凡是使用隱含馬爾可夫模型描述的問題都可以用它來解碼，包括今天的數(shù)字通信、語音識別、機器翻譯、拼音轉(zhuǎn)漢字、分詞等。
維特比算法一般用于模式識別，通過觀測數(shù)據(jù)來反推出隱藏狀態(tài)，下面一步步講解這個算法。
因為是要根據(jù)觀測數(shù)據(jù)來反推，所以這里要進行一個假設(shè)，假設(shè)這三天所做的行為分別是：散步、購物、打掃衛(wèi)生，那么我們要求的是這三天的天氣(路徑)分別是什么。
初始計算第一天下雨和第一天晴天去散步的概率值：
)表示第一天下雨的概率
表示中間的狀態(tài)(下雨)s概率
)表示下雨并且散步的概率
表示下雨天到下雨天的概率
=\pi_Rb_R(O_1=w)=0.60.1=0.06)
=\pi_Sb_S(O_1=w)=0.40.6=0.24)
初始路徑為：
=Rainy)
=Sunny)
計算第二天下雨和第二天晴天去購物的概率值：
對應(yīng)路徑為：
計算第三天下雨和第三天晴天去打掃衛(wèi)生的概率值：
對應(yīng)路徑為：
比較每一步中 $\bigtriangleup$ 的概率大小，選取最大值并找到對應(yīng)的路徑，依次類推就能找到最有可能的隱藏狀態(tài)路徑。
第一天的概率最大值為 ，對應(yīng)路徑為Sunny，
第二天的概率最大值為 ，對應(yīng)路徑為Sunny，
第三天的概率最大值為 ，對應(yīng)路徑為Rainy。
合起來的路徑就是Sunny->Sunny->Rainy，這就是我們所求。
以上是比較通俗易懂的維特比算法，如果需要嚴(yán)謹(jǐn)表述，可以查看《數(shù)學(xué)之美》這本書的第26章，講的就是維特比算法，很詳細。附：《數(shù)學(xué)之美》下載地址，點擊下載
鮑姆-韋爾奇算法(Baum-Welch Algorithm) (約等于EM算法)，詳細講解請見：監(jiān)督學(xué)習(xí)方法與Baum-Welch算法
wikipedia上是這樣定義因子圖的：將一個具有多變量的全局函數(shù)因子分解，得到幾個局部函數(shù)的乘積，以此為基礎(chǔ)得到的一個雙向圖叫做因子圖（Factor Graph）。
通俗來講，所謂因子圖就是對函數(shù)進行因子分解得到的一種概率圖。一般內(nèi)含兩種節(jié)點：變量節(jié)點和函數(shù)節(jié)點。我們知道，一個全局函數(shù)通過因式分解能夠分解為多個局部函數(shù)的乘積，這些局部函數(shù)和對應(yīng)的變量關(guān)系就體現(xiàn)在因子圖上。
舉個例子，現(xiàn)在有一個全局函數(shù)，其因式分解方程為：
=f_A(x_1)f_B(x_2)f_C(x1,x2,x3)f_D(x_3,x_4)f_E(x_3,x_5))
其中fA,fB,fC,fD,fE為各函數(shù)，表示變量之間的關(guān)系，可以是條件概率也可以是其他關(guān)系。其對應(yīng)的因子圖為：
我們已經(jīng)知道，有向圖模型，又稱作貝葉斯網(wǎng)絡(luò)，但在有些情況下，強制對某些結(jié)點之間的邊增加方向是不合適的。使用沒有方向的無向邊，形成了無向圖模型（Undirected Graphical Model,UGM）, 又被稱為馬爾可夫隨機場或者馬爾可夫網(wǎng)絡(luò)（Markov Random Field, MRF or Markov network）。
設(shè)X=(X1,X2…Xn)和Y=(Y1,Y2…Ym)都是聯(lián)合隨機變量，若隨機變量Y構(gòu)成一個無向圖 G=(V,E)表示的馬爾可夫隨機場（MRF），則條件概率分布P(Y|X)稱為條件隨機場（Conditional Random Field, 簡稱CRF，后續(xù)新的博客中可能會闡述CRF）。如下圖所示，便是一個線性鏈條件隨機場的無向圖模型：
在概率圖中，求某個變量的邊緣分布是常見的問題。這問題有很多求解方法，其中之一就是把貝葉斯網(wǎng)絡(luò)或馬爾可夫隨機場轉(zhuǎn)換成因子圖，然后用sum-product算法求解。換言之，基于因子圖可以用sum-product 算法高效的求各個變量的邊緣分布。
詳細的sum-product算法過程，請查看博文：從貝葉斯方法談到貝葉斯網(wǎng)絡(luò)
一個通俗的例子
假設(shè)你有許多小明同學(xué)一天內(nèi)不同時段的照片，從小明提褲子起床到脫褲子睡覺各個時間段都有（小明是照片控?。，F(xiàn)在的任務(wù)是對這些照片進行分類。比如有的照片是吃飯，那就給它打上吃飯的標(biāo)簽；有的照片是跑步時拍的，那就打上跑步的標(biāo)簽；有的照片是開會時拍的，那就打上開會的標(biāo)簽。問題來了，你準(zhǔn)備怎么干？
一個簡單直觀的辦法就是，不管這些照片之間的時間順序，想辦法訓(xùn)練出一個多元分類器。就是用一些打好標(biāo)簽的照片作為訓(xùn)練數(shù)據(jù)，訓(xùn)練出一個模型，直接根據(jù)照片的特征來分類。例如，如果照片是早上6:00拍的，且畫面是黑暗的，那就給它打上睡覺的標(biāo)簽;如果照片上有車，那就給它打上開車的標(biāo)簽。
乍一看可以！但實際上，由于我們忽略了這些照片之間的時間順序這一重要信息，我們的分類器會有缺陷的。舉個例子，假如有一張小明閉著嘴的照片，怎么分類？顯然難以直接判斷，需要參考閉嘴之前的照片，如果之前的照片顯示小明在吃飯，那這個閉嘴的照片很可能是小明在咀嚼食物準(zhǔn)備下咽，可以給它打上吃飯的標(biāo)簽；如果之前的照片顯示小明在唱歌，那這個閉嘴的照片很可能是小明唱歌瞬間的抓拍，可以給它打上唱歌的標(biāo)簽。
所以，為了讓我們的分類器能夠有更好的表現(xiàn)，在為一張照片分類時，我們必須將與它相鄰的照片的標(biāo)簽信息考慮進來。這——就是條件隨機場(CRF)大顯身手的地方！這就有點類似于詞性標(biāo)注了，只不過把照片換成了句子而已，本質(zhì)上是一樣的。
如同馬爾可夫隨機場，條件隨機場為具有無向的圖模型，圖中的頂點代表隨機變量，頂點間的連線代表隨機變量間的相依關(guān)系，在條件隨機場中，隨機變量Y 的分布為條件機率，給定的觀察值則為隨機變量 X。下圖就是一個線性連條件隨機場。
條件概率分布P(Y|X)稱為條件隨機場。
EM算法是用于含有隱變量模型的極大似然估計或者極大后驗估計，有兩步組成：E步，求期望（expectation）；M步，求極大（maxmization）。本質(zhì)上EM算法還是一個迭代算法，通過不斷用上一代參數(shù)對隱變量的估計來對當(dāng)前變量進行計算，直到收斂。注意：EM算法是對初值敏感的，而且EM是不斷求解下界的極大化逼近求解對數(shù)似然函數(shù)的極大化的算法，也就是說EM算法不能保證找到全局最優(yōu)值。對于EM的導(dǎo)出方法也應(yīng)該掌握。
隱馬爾可夫模型是用于標(biāo)注問題的生成模型。有幾個參數(shù)（π，A，B）：初始狀態(tài)概率向量π，狀態(tài)轉(zhuǎn)移矩陣A，觀測概率矩陣B。稱為馬爾科夫模型的三要素。馬爾科夫三個基本問題：
概率計算問題：給定模型和觀測序列，計算模型下觀測序列輸出的概率。–》前向后向算法
學(xué)習(xí)問題：已知觀測序列，估計模型參數(shù)，即用極大似然估計來估計參數(shù)。–》Baum-Welch(也就是EM算法)和極大似然估計。
預(yù)測問題：已知模型和觀測序列，求解對應(yīng)的狀態(tài)序列。–》近似算法（貪心算法）和維比特算法（動態(tài)規(guī)劃求最優(yōu)路徑）
條件隨機場CRF，給定一組輸入隨機變量的條件下另一組輸出隨機變量的條件概率分布密度。條件隨機場假設(shè)輸出變量構(gòu)成馬爾科夫隨機場，而我們平時看到的大多是線性鏈條隨機場，也就是由輸入對輸出進行預(yù)測的判別模型。求解方法為極大似然估計或正則化的極大似然估計。
之所以總把HMM和CRF進行比較，主要是因為CRF和HMM都利用了圖的知識，但是CRF利用的是馬爾科夫隨機場（無向圖），而HMM的基礎(chǔ)是貝葉斯網(wǎng)絡(luò)（有向圖）。而且CRF也有：概率計算問題、學(xué)習(xí)問題和預(yù)測問題。大致計算方法和HMM類似，只不過不需要EM算法進行學(xué)習(xí)問題。
HMM和CRF對比：其根本還是在于基本的理念不同，一個是生成模型，一個是判別模型，這也就導(dǎo)致了求解方式的不同。
聯(lián)系客服
