機器學習之概率圖模型淺析
根據《機器學習》、《統計學習方法》、《統計自然語言處理》，關於HMM，CRF等演算法實現先跳過，等用到再補。
其中的一些內容，例如HMM，CRF在其他的文章中都有拓展，在專欄里找一下就能找到。
機器學習最重要的任務，是根據一些己觀察到的證據(例如訓練樣本)來對感興趣的未知變數(例如類別標記)進行估計和推測。
概率圖模型就是概率圖模型(probabilisticgraphicalmodel)是一類用圖來表達變數相關關係的概率模型.它以圖為表示工具，最常見的是用一個結點表示一個或一組隨機變數，結點之間的邊表示變數間的概率相關關係，即"變數關係圖"。
第一類是使用有向無環圖表示變數間的依賴關係，稱為有向圖模型或貝葉斯網(Bayesiannetwork);第二類是使用無向圖表示變數間的相關關係，稱為無向圖模型或馬爾可夫網(Markovnetwork)
生成式模型與稱判別式模型
判別式模型（DiscriminativeModel）是直接學習決策函數f(x)或者直接求得條件概率分布p(y|x;θ)。常見的判別式模型有線性回歸模型、支持向量機SVM等。
對條件分布進行建模。
生成式模型（GenerativeModel）由數據學習聯合概率分布p(x,y)，然後通過貝葉斯公式來求得p(yi|x)，然後選取使得p(yi|x)最大的yi。例如樸素貝葉斯模型和隱馬爾科夫模型。
對聯合分布進行建模。
自然語言處理中概率圖模型的演變
橫向：由點到線（序列結構）、到面（圖結構）。
縱向：在一定條件下生成式模型（genmodel）轉變為判別式模型（discriminativemodel）
貝葉斯網路
形式上，一個貝葉斯網路就是一個有向無環圖（directedacyclicgraph,DAG），結點表示隨機變數。結點之間的有向邊表示條件依存關係，箭頭指向的結點
依存於箭頭髮出的結點（父結點）。
三個事件的聯合概率函數為：
P（H，S，N）＝P（H|S，N）×P（S|N）×P（N）馬爾可夫模型
一個交通信號燈的顏色轉換，燈的顏色變化序列依次是紅色-黃色-綠色-紅色，這就是一個確定性模式下的狀態序列。例如天氣的變化，晴朗-多雲-雨天的狀態序列是非確定性模式下的一個狀態序列。
像交通信號燈一樣，某一個狀態只由前一個狀態決定，這就是一個一階馬爾可夫模型。像天氣這樣，天氣狀態間的轉移僅依賴於前n天天氣的狀態，即狀態間的轉移僅依賴於前n個狀態的過程。這個過程就稱為n階馬爾科夫模型。
不通俗的講，馬爾可夫模型（Markovmodel）描述了一類重要的隨機過程，隨機過程又稱隨機函數，是隨時間而隨機變化的過程。
如果在特定條件下，系統在時間t的狀態只與其在時間t-1的狀態相關，則該系統構成一個離散的一階馬爾可夫鏈（Markovchain）。
系統在時間t-1的狀態為si的情況下，時間t的狀態為sj的概率：P（qt＝sj|qt－1＝si）=aij，且：
則該隨機過程就是馬爾可夫模型。
有N個狀態的一階馬爾可夫過程有N^2次狀態轉移，其N^2個狀態轉移概率可以表示成一個狀態轉移矩陣。
根據狀態轉移方程，可以計算得到該狀態序列的概率，例如天氣的狀態轉移矩陣：
那麼以天氣為例，確定一個一階馬爾可夫模型需要：
1. pi向量：定義系統初始化時每一個狀態的概率
2. 狀態轉移矩陣：給定前一天天氣情況下的當前天氣概率。
隱馬爾可夫模型
在馬爾可夫模型中，每個狀態代表了一個可觀察的事件，所以，馬爾可夫模型有時又稱作可視馬爾可夫模型（visibleMarkovmodel，VMM），這在某種程度上限制了模型的適應性。
對於盲人來說也許不能夠直接獲取到天氣的觀察情況，但是他可以通過觸摸樹葉通過樹葉的乾燥程度判斷天氣的狀態。於是天氣就是一個隱藏的狀態，樹葉的乾燥程度是一個可觀察的狀態，於是我們就有了兩組狀態，一個是不可觀察、隱藏的狀態（天氣），一個是可觀察的狀態（樹葉），我們希望設計一種演算法，在不能夠直接觀察天氣的情況下，通過樹葉和馬爾可夫假設來預測天氣。
以此為例，一個一階的馬爾可夫過程描述：
在隱馬爾可夫模型（HMM）中，我們不知道模型所經過的狀態序列，只知道觀察到的事件在某狀態下的概率函數。因此，該模型是一個雙重的隨機過程，包括模型的狀態轉換和特定狀態下可觀察事件的隨機。
上圖中，Xi表示觀測變數，yi表示狀態變數。Xi是由yi決定的，並且t時刻的yt僅僅由t-n至t-1時刻的y決定。
一個隱馬爾可夫模型需要確定以下三方面內容：λ=[π,A，B]
1. 初始狀態概率π:模型在初始時刻各狀態出現的概率，通常記為π=(π1，π2，...，πN)，πi表示模型的初始狀態為Sí的概率.
2. 狀態轉移概率A:模型在各個狀態間轉換的概率，通常記為矩陣A[αij]N*N，其中αij=P(Yt+l=Sj|Yt=Si),
表示在任意時刻t，若狀態為Si，則在下一時刻狀態為Sj的概率.3. 輸出觀測概率B:模型根據當前狀態獲得各個觀測值的概率通常記為矩陣
B=[bij]N*M，。其中，N是狀態數量，M是觀測值的數量，bij=P(Xt=Oj|Yt=Si),表示在任意時刻t，若狀態為Si.，則觀測值Oj被獲取的概率.相對於馬爾可夫模型，隱馬爾可夫只是多了一個各狀態的觀測概率
給定隱馬爾可夫模型λ=[A，B，π]，它按如下過程產生觀測序列{X1,X2，...,Xn}:
(1) 設置t=1，並根據初始狀態概率π選擇初始狀態Yl;
(2) 根據狀態值和輸出觀測概率B選擇觀測變數取值Xt;
(3) 根據狀態值和狀態轉移矩陣A轉移模型狀態，即確定Yt+1;
一旦一個系統可以作為HMM被描述，就可以用來解決三個基本問題。
1. 評估（Evaluation）
給定HMM，即λ=[π,A，B]，求某個觀察序列的概率。
例如，給定一個天氣的隱馬爾可夫模型，包括第一天的天氣，天氣轉移概率矩陣，特定天氣下樹葉的濕度概率分布。求第一天濕度為1，第二天濕度為2，第三天濕度為3的概率。
2. 解碼（ Decoding）
給定HMM，即λ=[π,A，B]，以及某個觀察序列，求得天氣的序列。
例如，給定一個天氣的隱馬爾可夫模型，包括第一天的天氣，天氣轉移概率矩陣，特定天氣下樹葉的濕度概率分布。並且已知第一天濕度為1，第二天濕度為2，第三天濕度為3。求得這三天的天氣情況。
3. 學習（Learning）
給定一個觀察序列，得到一個隱馬爾可夫模型。
已知第一天濕度為1，第二天濕度為2，第三天濕度為3。求得一個天氣的隱馬爾可夫模型，包括第一天的天氣，天氣轉移概率矩陣，特定天氣下樹葉的濕度概率分布。
可夫隨機場MRF
馬爾可夫隨機場是典型的馬爾可夫網，即一個無向圖模型。
圖中的節點表示變數，結點之間的邊表示兩個變數之間的依賴關係.馬爾可夫隨機場有一組勢函數(potentialfunctions)，亦稱"因子"(factor)，這是定義在變數子集上的非負實函數，主要用於定義概率分布函數。
若其中任意兩結點間都有邊連接，則稱該結點子集為一個"團"(clique)（類似於一個全連通圖）。「極大團」類似於一個屬於全連通圖的圖的最大的子集。
在馬爾可夫隨機場中，多個變數之間的聯合概率分布能基於團分解為多個因子的乘積?每個因子僅與一個團相關.具體米說，對於n個變數X={Xl，x2，...，xn}，所有團構成的集合為C，與團Q(shuyu)C對應的變數集合記為XQ，則聯合概率P(X)定義為:
勢函數的累乘相加得到Z，Z為規範化因子，是為了確保P（X）是被正確定義的概率。
條件隨機場CRF
條件隨機場(ConditionalRandomField，簡稱CRF)是一種判別式無向圖模型.生成式模型是直接對聯合分布進行建模，麗判別式模型則是對條件分布進行建模.前面介紹的隱馬爾可夫模型和馬爾可夫隨機場都是生成式模型，而條件隨機場則是判別式模型.
CRF的特點是假設輸出隨機變數構成馬爾可夫隨機場。
條件隨機場試圖對多個變數在給定觀測值後的條件概率進行建模.具體來
說，若令X={Xl,X2,…,Xn}為觀測序列，y={y1，y2，...,Yn}為與之相應的標記序列，則條件隨機場的目標是構建條件概率模型P(y|X).馬爾可夫性（pairwiseMarkovproperty）
成對馬爾可夫性
設無向圖G中的任意兩個沒有邊連接的節點u、v，其他所有節點為O，成對馬爾可夫性指：給定YO的條件下，Yu和Yv條件獨立
局部馬爾可夫性
全局馬爾可夫性
令G=(V，E)表示結點與標記變數Y中元素一一對應的無向圖，Yv表示與結點v對應的標記變數，n(v)表示結點v的鄰接結點，若圖G的每個變數Yv都滿足馬爾可夫性（即給定變數Yv,兩個其他變數不是鄰接變數，且他們各自獨立），即
則(y，x)構成一個條件隨機場.
推薦閱讀：
