[白話解析] 用水滸傳為例學習條件隨機場

本文將盡量使用易懂的方式，盡可能不涉及數學公式，而是從整體的思路上來看，運用感性直覺的思考來解釋條件隨機場。并且用水滸傳為例學習。并且從名著中找了具體應用場景來幫助大家深入這個概念。

[白話解析] 用水滸傳為例學習條件隨機場

0x00 摘要

在機器學習過程中，會遇到很多晦澀的概念，相關數學公式很多，大家理解起來很有困難。遇到類似情況，我們應該多從直覺角度入手思考，用類別或者舉例來附會，這樣往往會有更好的效果。

我在講解論述過程中給自己的要求是：在生活中或者名著中找一個例子，然后用自己的話語闡述出來。

0x01 HMM 隱馬爾可夫

首先還是需要大概介紹下HMM和MEMM，這樣才能知道為什么要引入CRF。

其中HMM在前文[白話解析]以水滸傳為例學習隱馬爾可夫模型中也詳細介紹。這里主要講講其推導過程和其缺點。

1. HMM 模型

HMM模型中存在兩個假設：一是輸出觀察值之間嚴格獨立，二是狀態的轉移過程中當前狀態只與前一狀態有關(一階馬爾可夫模型)。下面我們就講講這兩個假設是如何應用在推導過程中的。

單樣本樸素貝葉斯分類任務中 (其中 x 是觀測值，y 是隱藏狀態) ：

\[P(y|x)=\frac{P(x|y)*P(y)}{P(x)} \]

擴展到序列化樣本分類問題任務中為：

\[P(y_1^n ∣x_1^n)= \frac{P(x_1^n∣y_1^n)?P(y_1^n)}{P(x_1^n)} \]

其中n表示的是序列的長度，這就是我們計算某個標簽序列在序列分類中的概率得分。

我們以詞性標注這一序列化分類問題進行后面的講解。對于一個給定的句子x_i^n=(x_1,x_2,...,x_n)，我們的目的是為其找到一個得分最高的標簽序列 (y?1,y?2,...,y?n )，則該問題轉化為:

\[\hat y_1^n = arg_{y_1^n} \ max \frac{P(x_1^n∣y_1^n)?P(y_1^n)}{P(x_1^n)} \]

對于同一個句子的標注，分母是相同的，所以該問題可以轉化為:

\[\hat y_1^n = arg_{y_1^n} \ max P(x_1^n∣y_1^n)?P(y_1^n) \]

回憶下聯合分布的公式

\[P(X = x \ and \ Y = y) = \ P(Y=y|X=x)P(X=x) = \ P(X=x|Y=y)P(Y=y) \]

所以上述問題轉化后的公式就是 P(X,Y)。即 HMM 試圖去擬合 X,Y 的聯合分布 P(X,Y)，所以它是一種生成式模型。

現在我們需要引入HMM的兩個基本假設，才能計算 P：

齊次馬爾可夫性假設。即假設隱藏的馬爾科夫鏈在任意時刻 t 的狀態只依賴于其前一時刻的狀態，與其他時刻的狀態及觀測無關，也與時刻t觀測無關。
觀測獨立性假設。即假設任意時刻的觀測只依賴于該時刻的馬爾科夫鏈的狀態，與其他觀測及狀態無關。

以上這兩個假設是 HMM 的核心，之后的公式推導都是依賴這兩個假設成立的基礎上進行的。

這兩個假設分別可以用于計算上。

\[假設1 \ 用于求解 \ 當前狀態 \ P(y_1^n) \\ 假設2 \ 用于求解 \ 當前觀測值 \ P(x_1^n∣y_1^n) \]

原始情況下，根據有向圖模型計算方式：

\[P(y_1^n)=P(y_1)?P(y_2∣y_1)?P(y_3∣y_1,y_2)?...?P(y_n∣y_1,y_2,...,y_{n?1}) \]

我們先把 假設1 用于求解，則其計算方式變為:

\[P(y_1^n)=P(y_1)?P(y_2∣y_1)?P(y_3∣y_2)?...?P(y_n∣y_{n?1}) \]

根據 假設2 ，當前觀測值僅僅與當前狀態有關，與其他時刻狀態和觀測值無關，所以

\[P(x_1^n∣y_1^n)=P(x_1∣y_1)?P(x_2∣y_2)?...?P(x_n∣y_n) \]

即

假設1 使用bi-gram近似得到轉移概率 Transition probability。
假設2 就得到發射概率 emission probability。

最后合并起來：

\[\hat y_1^n = arg \ max_{y_1^n} ∏_{t=1}^nP(x_t∣y_t)?P(y_t∣y_{t?1}) \]

HMM的學習過程就是在訓練集中學習這兩個概率矩陣 (大小為 (y, y)，(x, y) )

2. HMM有哪些缺點

HMM 擁有以下幾個缺陷：

在很多序列化標注任務中，尤其當不能枚舉觀測值時，需要用大量的特征來刻畫觀察序列。如在文本識別中識別一個未見的公司名字時，除了傳統的單詞識別方法以外，還需要用到很多特征信息，如大寫字母、結尾詞、詞性等信息。也就是，我們需要用特征對觀測值進行參數化，而HMM中直接利用觀測值本身。
在命名實體識別的任務中，由于實體本身結構所具有的復雜性，利用簡單的特征函數往往無法涵蓋所有的特性，這時HMM的假設前提使得它無法使用復雜特征(它無法使用多于一個標記的特征)。
在很多自然語言處理任務中，需要解決的問題是在已知觀測序列的情況下求解狀態序列，HMM采用的生成式的聯合概率分布P(x_1^n,y_1n)來求解條件概率P(y_1^n|x_1n)，這種方法不適合處理很多特征描述觀測序列的情況。為此MEMM直接采用條件概率模型P(y_1^n|x_1n)。

0x02 MEMM

1. 最大熵模型

其中最大熵模型在前文 [白話解析] 深入淺出最大熵模型以及 [白話解析]用水滸傳為例學習最大熵馬爾科夫模型中也有介紹。

假設離散隨機變量 x 的分布是P(x)，則關于分布P的熵定義為：

\[H(P) = -\sum_xP(x)logP(x) \]

可以看出當 x 服從均勻分布時對應的熵最大，也就是不確定性最高。

給定離散隨機變量和上的條件概率分布P(y|x)，定義在條件概率分布上的條件熵為：

\[H(P) = -\sum_{x,y}\hat{P}(x)P(y|x)logP(y|x) \]

其中，p?(x) 是樣本在訓練集熵的經驗分布，也就是 x 的各個取值在樣本中出現的頻率統計。

最大熵模型就是，在 "滿足事先已約束" 的條件下，學習適合的 P(y|x) ，使得條件熵 H(P) 的取值最大。

我們使用特征函數來表示約束條件，即特征函數也就是用來指示元素是否屬于某一個子集。

2. 最大熵馬爾科夫模型

最大熵馬爾科夫模型把HMM模型和maximum-entropy模型的優點集合成一個產生式模型，這個模型允許狀態轉移概率依賴于序列中彼此之間非獨立的特征上，MEMM是這樣的一個概率模型，即在給定的觀察狀態和前一狀態的條件下，出現當前狀態的概率。

最大熵馬爾科夫模型利用判別式模型的特點，直接對每一個時刻的狀態建立一個分類器，然后將所有的分類器的概率值連乘起來。為了實現是對整個序列進行的分類。在每個時刻t時，它的特征不僅來自當前觀測值x_t，而且還來自前一狀態值y_{t?1} 。所以MEMM中，給定觀測序列 i1,...in 后，某個狀態序列 in 的條件概率是可以直接學習的。就是

HMM下一個隱藏狀態 Y + 1 只是由目前隱藏標簽狀態 Y 決定。
MEMM下一個隱藏狀態 Y + 1 只是由目前隱藏標簽狀態 Y 和觀察狀態 X 共同決定。

MEMM的序列標注問題定義為，給定觀測序列 x_1^n，求解某個狀態序列 y_1^n ，并且使得條件概率最大，而且該條件概率滿足馬爾科夫假設，也就是條件概率依賴于當前時刻的觀察狀態和前一時刻的標簽狀態：

\[P(y_1^n|x_1^n) = \prod_{t=1}^n P(y_t|y_{t-1},x_t) \]

MEMM貪心地取當前時刻概率分布中最大對應的標簽作為當前時刻的解碼標簽。

其中對于前一時刻可能的狀態取值y_{t?1} 和當前觀測值x_t，當前狀態取值y_t 的概率通過最大熵分類器建模為：

\[P(y_t|y_{t-1},x_t) = \frac{1}{Z(x_t,y^t)}exp(\sum_aλ_af_a(x_t,y_{t-1})) \]

其中a, λ_a, f_a 分別表示特征函數數量，特征函數權重和第 a個特征函數，Z() 這部分是歸一化。

3. MEMM有哪些缺點

通過上面的公式，你會發現最大熵模型在每一個時刻，針對不同的前一狀態y′ 進行歸一化操作，這是一種局部的歸一化操作，會存在標簽偏置問題。即，最大熵馬爾科夫模型雖然結合了隱馬爾科夫模型和最大熵模型的最大特點，但是仍然忽略了標簽之間的約束關系，只求在當前時刻的最大條件概率。

這里有個網上常見的論斷：

當前狀態是 S1，假設下一個狀態 S2 有兩個選擇，一個是p, 一個是c。經過局部歸一化之后，因為p的轉出狀態比較少，導致 p 的轉移概率*發射概率相對于轉出狀態多的c而言是比較大的，這會使模型更傾向選擇狀態p。

針對這個論斷，我們可以寫代碼實驗下 (如果哪位兄弟知道如何數學論證，還請告訴我，謝謝) 。

# 以下就是MEMM的viterbi算法

def predict_viterbi(x, f_map, tags_s, word_t_map, lib_model):
    """
    For each word in vector x predict his tag. Prediction is done by viterbi algorithm. Check all tags options/globally.
    :param x: X vector of all words to be tagged.
    :param f_map: Features map.
    :param tags_s: Tags set.
    :param word_t_map: Word to tags map.
    :param lib_model: Liblinear model.
    :return: Return best predicted list of tags for each word in x respectively.
    """
    for ind, word in enumerate(x):
        # Calculate for each word best scores/probabilities and best tags for each word.
        for pp_t, p_t in v[ind]:
            for curr_tag in available_tags:
                word_features = extract.generate_word_features(is_rare, p_t, pp_t, word, ind, x)
                features_vec = features_to_vec(word_features, f_map)
                scores = lib_model.predict(features_vec)
                score = np.amax(scores)
                if (p_t, curr_tag) not in max_score or score > max_score[(p_t, curr_tag)]:
                    max_score[(p_t, curr_tag)] = score
                    max_tags[(p_t, curr_tag)] = pp_t

# 預測代碼，可以修改這個以測試  
def predict(self, feature_ids):
    weights = self.weights
    scores = np.zeros(len(self.labels))
    for f in feature_ids:
        if f in weights:
            scores += weights[f]
    scores = 1/(1+np.exp(-scores))
    scores = scores/np.sum(scores)
    return scores

#把上述代碼修改下，自己傳入feature或者直接傳入weight就知道了。
#比如分別傳入weight 
#[1, 2, 6, 1, 2]
#[1, 2, 9]
#就會發現，如果傳入的列表中item的個數越少，則np.amax(scores)越大。

#所以這就與之前的論斷相一致：
#經過局部歸一化之后，因為 狀態 p 的轉出狀態比較少，導致 “轉移概率 x 發射概率” 相對于轉出狀態多的 狀態 c 而言是比較大的，這會使模型傾向于更多的選擇 狀態 p 。

#其實 S2 選擇 p 節點還是 c 節點只取決于 P(p|S1)、P(c|S1)，即只與 “S1” 的上下文有關，與 “S2” 的上下文無關，這就是MEMM產生偏置的一種情況。

因為MEMM有缺點，所以人們引入了CRF。CRFs與最大熵模型的本質區別是：最大熵模型在每個狀態都有一個概率模型，在每個狀態轉移時都要進行歸一化。如果某個狀態只有一個后續狀態，那么該狀態到后續狀態的跳轉概率即為1。這樣，不管輸入為任何內容，它都向該后續狀態跳轉。而CRFs是在所有的狀態上建立一個統一的概率模型，這樣在進行歸一化時，即使某個狀態只有一個后續狀態，它到該后續狀態的跳轉概率也不會為1，從而解決了“label bias”問題。

0x03 CRF相關知識

1. 什么是場

看到這個概念，估計很多同學會懵圈。這不是物理學概念嘛，我們都學過電場，磁場。怎么這里也出來了一個場。

其實這是從物理學借鑒來的概念，這也不奇怪。比如熵這個概念就是物理學借鑒過來的。這說明數學物理是自然科學的基礎。

下面是我從網上或者其他地方找到的關于“場”的解釋。希望能對大家理解有幫助。

闡釋1

這個論斷是一個傳媒學者講藝術表演創作時候提到的。你可以認為她說的不精確，但是不能否認從其他行業的角度來看，反而更容易理解場這個概念。

場就是互相影響。電影表演不需要場。戲劇表演需要場，因為戲劇需要和大量觀眾互動必須對觀眾產生影響。

闡釋2

這是借用的物理里的概念。理論物理里提出用蒙特卡羅算法求解體系可能結構的方法，每個結構出現的概率和exp(-betaE)成正比，-beta和溫度的倒數有關，E是體系每個部分的勢能之和，和系統所有可能構型的這個因子之和成反比，這個和就是配分函數，而勢函數就是用來計算體系每個部分間不同位置關系下可能的勢能的理論假設的函數形式。機器學習就是借用這種模型來產生概率罷了，或者說它是我們要考察的物理量的一個因子，而且這個被考察物理量不僅取值和這個因子有關，其變化規律也和這個因子有關。這是借用的物理里的概念。理論物理里提出用蒙特卡羅算法求解體系可能結構的方法，每個結構出現的概率和exp(-betaE)成正比，-beta和溫度的倒數有關，E是體系每個部分的勢能之和，和系統所有可能構型的這個因子之和成反比，這個和就是配分函數，而勢函數就是用來計算體系每個部分間不同位置關系下可能的勢能的理論假設的函數形式。機器學習就是借用這種模型來產生概率罷了，或者說它是我們要考察的物理量的一個因子，而且這個被考察物理量不僅取值和這個因子有關，其變化規律也和這個因子有關。

2. 隨機場

隨機場是由若干個位置組成的整體，當給每一個位置中按照某種分布隨機賦予一個值之后，其全體就叫做隨機場。舉詞性標注的例子：假如我們有一個十個詞形成的句子需要做詞性標注。這十個詞每個詞的詞性可以在我們已知的詞性集合（名詞，動詞...) 中去選擇。當我們為每個詞選擇完詞性后，這就形成了一個隨機場。

舉梁山為例子：
  
比如梁山好漢一起去聚義廳開會。
每把椅子是一個位置。給每個椅子賦予一個好漢。這個好漢如何分配? 
每次從梁山上各個小團體(三山派，潯陽幫，宋江嫡系......)中隨機取出一人安排到椅子上。

3. 馬爾可夫隨機場

馬爾可夫隨機場（Markov random field)又稱為概率無向圖模型，是一個可以由無向圖表示的聯合概率分布。

概率無向圖模型: 設有聯合概率分布 P(Y) ，由無向圖 G=(V,E) 表示，在圖 G 中，結點表示隨機變量，邊表示隨機變量之間的依賴關系。如果聯合概率分布 P(Y) 滿足成對、局部或全局馬爾可夫性，就稱此聯合概率分布為概率無向圖模型或馬爾可夫隨機場。分別介紹一下三個概念：

成對馬爾可夫性：給定所有其他變量，兩個非鄰接變量條件獨立。這是因為兩個節點沒有直接路徑，并且所有其他路徑上都有確定的觀測節點，因此這些路徑也將被阻隔。其實意思就是說沒有直連邊的任意兩個節點是獨立的。
局部馬爾可夫性：給定變量 v 的所有鄰接變量 w，則該變量 v 條件獨立于其他變量 o。即在給定某個變量的鄰接變量的取值條件下，該變量的取值將于其他變量無關。就是說，v 的取值只和它所有鄰接變量w相關。
全局馬爾可夫性：設節點集合A，B是在無向圖G中被節點集C分開的任意節點集合，如下圖所示。全局馬爾可夫性是指在給定x_C的條件下，x_A和x_B條件獨立。也就是說，在A和B被C分開時候，A和B條件獨立，這時候才說是滿足全局馬爾可夫。

\[A ------ C ------- B \]

總的說來，馬爾可夫隨機場假設隨機場中某一個位置的賦值僅僅與和它相鄰的位置的賦值有關，和與其不相鄰的位置的賦值無關。

因此，聯合概率分布的分解一定要讓 xi 和 xj 不出現在同一個劃分中，從而讓屬于這個圖的所有可能概率分布都滿足條件獨立性質。讓非鄰接變量不出現在同一個劃分中，即每一個劃分中節點都是全連接的。這將我們引向了圖的一個概念，團（clique）。

4. 最大團

CRF是通過團以及勢函數的概念來定義條件概率P（y|x）。所以我們要學習最大團。

馬爾可夫隨機場中，對于圖中結點一個子集，若其中任意兩結點間都有邊連接，則稱該結點子集為一個團，若在一個團中，加入另外任何一個結點都不再形成團，則稱該團為極大團，換言之，極大團就是不能被其他團所包含的團。

比如梁山好漢一起去聚義廳開會。你就會發現，同一個小集團的人會主動聚在一起。

比如打虎將李忠就必然在三山幫這一個小集團中。而九尾龜陶宗旺則必然在黃門山（摩云金翅歐鵬、神算子蔣敬、鐵笛仙馬麟、九尾龜陶宗旺）小集團中。

李忠和陶宗旺兩個人在私下不會有什么交集。而黃門山這四人，每個人和每個人之間都是全聯接，都互相熟悉。

如果往黃門山四人中加入其他任何一個梁山好漢之后變成五人團體，則這個五人團體就不再算是黃門山這個小集團了。所以黃門山四人就是極大團。

顯然，最簡單的團就是兩個節點以及一條邊，而我們最開始就針對兩節點之間的相關關系（每條邊）定義了勢函數。

5. 勢函數

勢函數的作用是定量刻畫變量集 Q 中變量之間的相關關系。比如句首幾個字的關系。

數學定義

給定概率無向圖模型，設其無向圖為G，C為G上的最大團，Y_C表示C對應的隨機變量（是最大團的所有結點）。

φ(Y_C)是一個最大團 C 上隨機變量們的聯合概率，是用于對團C中的變量之間的關系進行建模，是定義概率分布的函數。

φ(Y_C)被稱為與團C對應的「勢函數（potential function）」。一般而言，你要為圖中的每個極大團（maximal clique）定義一個勢函數。

具體形式

無向圖模型中勢函數的具體形式通常定義為特征函數的帶權加和, 也即這些方法通常將條件隨機字段中的勢函數定義為某些人工設計的特征函數的線性組合，這些函數是啟發式的。

勢函數是一個表示其對應的團(clique)狀態的非負實值函數，表征的是該clique的狀態。對于一個圖中的每一個clique來講，它有一個狀態，用勢函數表示，狀態則是由多個feature的加權和構成，因為一個clique是包含多個節點的，每個節點其對應的隨機變量，都會對應一個feature。

因此，馬爾可夫隨機場中，多個變量的聯合概率分布能基于團分解為多個勢函數的乘積，每一個團對應一個勢函數。所以可以將聯合概率分布分解為其極大團上的勢函數的乘積。

從最大熵的角度來看勢函數

熵用來表示任何一種能量在空間中分布的均勻程度，能量分布得越均勻，熵就越大。

對于勢函數，我們換一種理解方式，定義將potential function表示成指數函數

\[φ_C(Y_C) = exp \{-E(Y_C)\} \]

這樣p(x)就可以表示成一系列E(Yc)的和的指數形式。E(Yc)叫做能力函數。

這樣轉化之后，可以將圖理解為一個能力的集合，他的值等于各個最大團的能量的和。CRF要做的就是最小化這些能量，以達到穩定的結果。均勻分布就是最穩定的，熵就達到了最大值。即，用能量最小化表示整個系統達到穩態時各個變量的狀態滿足的條件。

比如梁山上，有各種小團體。每一個團體對應一個勢函數。
比如 生辰綱七人組，登州幫，三山幫，揭陽幫，降將幫，大名府幫，黃門山幫，清風山....
  
那么梁山就可以理解為一個能力的集合，他的值就等于各個小團體能量的和。
CRF就是要最小化這些能量，這樣梁山才能穩定，最好能均勻分布，這樣熵就達到了最大值。

6. 特征函數

特征函數是一些經驗的特性，我們使用特征函數來表示約束條件。特征函數在前文[白話解析]用水滸傳為例學習最大熵馬爾科夫模型也有詳述。

勢函數是定義場里面所有變量關系的的一個函數，而因子是為了或者描述簡化場里面變量關系所限定的一個假設，例如同時考慮兩個相鄰的因子或者所有相鄰的因子。

特征函數用來表示因子內的變量的關系，例如構成因子的變量的某些特征是相似的。比如在詞性標注中，特征函數可能是：前一個詞是動詞，當前詞的觀察狀態[是不是句首，是不是句尾，是不是數字]

CRF中，特征（feature）是一系列把我們觀測到的 d 和我們想要預測的類別 c 聯系到一起的證據(evidence)。特征是在實數范圍內一個函數 f。這些特征是怎么表達的呢？有兩種特征：

一種是轉移特征，就是涉及到兩個狀態之間的特征。
另一種就是簡單的狀態特征，就是只涉及到當前狀態的特征。

特征表達形式比較簡單，就是你是否滿足我特征所說的這個配置，是就是1，不是就是0。

模型會給每個特征分配一個權重，我們最后要學的就是這些權重：

正權重說明這種結構很可能是正確的
正權重說明這種結構很可能是不正確的

我們通過引入兩類特征函數便可以定義出目標條件概率：

表示定義在觀測序列的兩個相鄰標記位置上的轉移特征函數，用于刻畫相鄰標記變量之間的相關關系以及觀測序列對他們的影響，
表示在觀測序列的標記位置i上的狀態特征函數，用于刻畫觀測序列對標記變量的影響。

例如詞性標注，如何判斷給出的標注序列靠譜不靠譜，轉移特征函數主要判定兩個相鄰的標注是否合理，例如，動詞+動詞語法不通。狀態特征函數判定觀測值與對應的標注是否合理，例如：ly結尾的詞-->副詞較合理。

因此我們可以定義一個特征函數集合，用這個特征函數集合來為一個標準序列打分，根據此選出靠譜的標注序列。每一個特征函數都可以用來為一個標準序列評分，把集合中所有特征函數對同一個標注序列的評分綜合起來，就是這個標注序列最終的評分值。條件隨機場完全由特征函數和對應的權值確定。

和HMM不同的是，CRF并沒有做出HMM的假設，CRF使用feature function來更抽象地表達特征，使得他不再局限于HMM的兩類特征。特征函數可以表示當前的state與任意一個observation或者 state甚至future state的關系。也就是說，特征方程的存在允許CRF有十分自由的特征表達。這也就是條件隨機場中場所代表的意義。舉例如下：

func1 = if (output = B-NP and feature="U01:DT") return 1 else return 0
func2 = if (output = I-NP and feature="U01:DT") return 1 else return 0
func3 = if (output = O and feature="U01:DT") return 1 else return 0
...
funcXX = if (output = B-NP and feature="U01:NN") return 1 else return 0
funcXY = if (output = O and feature="U01:NN") return 1 else return 0

一個特征函數模板會生成 L x N 個特征函數, 其中 L 輸出類別的情況數目，N 是expanded feature的所有可能的情況數目。

7. 概率無向圖模型聯合概率分布

實際上，我們更關心的是如何求概率無向圖模型聯合概率分布。對給定的概率無向圖模型，我們希望將整體的聯合概率寫成若干子聯合概率的乘積的形式，也就是將聯合概率進行因子分解，這樣便于模型的學習與計算。事實上，概率無向圖模型的最大特點就是易于因子分解。所以我們將概率無向圖模型的聯合概率分布表示為其最大團上的隨機變量的函數的乘積形式的操作，稱為概率無向圖模型的因子分解。

對于概率分布函數而言，我們也希望能夠這樣做，即給定概率無向圖模型，設無向圖為 G ， C 為 G 上的最大團， YC 表示 C 對應的隨機變量。那么概率無向圖模型的聯合概率分布 P(Y) 可分解為圖中所有最大團 C 上的函數 ΨC(YC) 的乘積形式。

總結一下,便得到 Hammersley-Clifford定理，那么整個概率無向圖模型的聯合概率分布P(Y)可寫作圖中所有最大團C上的勢函數φ(Y_C)的乘積形式。即

\[P(Y) = \frac{1}{Z}\prod_Cφ_C(Y_C) 　\\Z = \sum_Y\prod_Cφ_C(Y_C) \]

其中，C 是無向圖的最大團， YC 是 C 的結點對應的隨機變量， ΨC(YC) 是 C 上定義的嚴格正函數，乘積是在無向圖所有的最大團上進行的。Z表示規范化因子，以確保P(x)是被正確定義的概率。

另外一種考慮最大團的思路

盡管在給定每個節點的條件下，分配給某節點一個條件概率是可能的，但條件隨機場的無向性很難保證每個節點在給定它的鄰接點條件下得到的條件概率和以圖中其它節點為條件得到的條件概率一致。因此導致我們不能用條件概率參數化表示聯合概率，而要從一組條件獨立的原則中找出一系列局部函數的乘積來表示聯合概率。

個人理解就是：因為crf希望過計算整個標記序列 Y 的聯合概率分布，而不是在給定當前狀態條件下定義下一個狀態的分布。但是從每個節點角度講，很難保持條件概率一致。所以選取最大團這個具有獨立性的小群體。

選擇局部函數時，必須保證能夠通過分解聯合概率使沒有邊的兩個節點不出現在同一局部函數中。最簡單的局部函數是定義在圖結構中的最大團(clique)上的勢函數(Potential function)，并且是嚴格正實值的函數形式。

但是一組正實數函數的乘積并不能滿足概率公理，則必須引入一個歸一化因子 Z ，這樣可以確保勢函數的乘積滿足概率公理，且是無向圖中節點所表示的隨機變量的聯合概率分布。

這樣出來的圖是等價于吉布斯分布的，就是說，你可以只在每個最大子團上定義一個聯合分布（而不需要對每個邊定義一個聯合分布），整個圖的聯合概率分布就是這些最大子團的聯合概率分布的乘積。當然這里最大子團的聯合概率并不是標準的聯合概率形式，是沒歸一化的聯合概率，叫factor（因子），整個圖的聯合概率乘完之后下面再除一個歸一化因子和就歸一化了，最終是一個聯合概率，每個子團記載的都是因子，是沒歸一化的概率，嚴格大于零，可以大于一。但關鍵是依賴關系、這些相關關系已經encode在里面了。

8. 從水滸傳角度看

從水滸傳角度看，可以這么定義特征函數和勢函數。對了，這里的勢函數就可以看成是勢力

三山幫指的是二龍山、桃花山和少華山。這個派系一共13人，頭領是魯智深。下面人是：二龍山的魯智深、楊志、武松、施恩、曹正、張青和孫二娘；桃花山的周通、李忠；少華山的史進、朱武、陳達，楊春。
  
定義特征函數如下  
*********************** 特征函數 之 節點屬性
s_1 = 是不是倒拔垂楊柳的僧人
s_2 = 是不是打虎英雄
s_3 = 是不是黑旋風  
s_4 = 是不是五虎將  
s_5 = 是不是八驃騎
s_6 = 是不是小彪將  
s_7 = 是不是一同參贊軍務頭領  
s_8 = 是不是步軍將校一十七員
s_9 = ......

  
*********************** 特征函數 之 邊屬性  
t_1 = 是不是親兄弟
t_2 = 是不是叔侄
t_3 = 是不是夫妻
t_4 = 是不是表親  
t_5 = 是不是師徒
t_6 = 是不是主仆  
t_7 = 是不是曾經共過生死
t_8 = 是不是一起經歷過尷尬事
t_9 = 是不是同鄉
t_10 = 是不是 "聚會之前就是結拜兄弟" 
t_11 = 是不是同僚  
t_12 = 是不是有同地工作經歷    
t_13 = ...... 

定義勢函數如下：
*********************** 勢函數  
φ = λ1t1 + λ2t2 + λ3t3 + λ4t4 + λ5f5 + ...... + w1t1 + w2t2 + w3t3 + w4t4 + w5t5 + ...... 
  
計算結果如下：
*********************** 計算結果  
s_1 = 魯智深 ————————————— 倒拔垂楊柳的僧人
s_2 = 武松 ——————————————— 打虎英雄
s_3 = 0
s_4 = 0  
s_5 = 楊志 史進 ——————————— 八驃騎
s_6 = 陳達，楊春，周通 ——————  小彪將
s_7 = 朱武 ————————————————   一同參贊軍務頭領
s_8 = 李忠，施恩———————————— 步軍將校一十七員
......
  
t_1 = 0
t_2 = 0
t_3 = 張青&孫二娘 —————————— 夫妻
t_4 = 0  
t_5 = 0
t_6 = 0  
t_7 = 武松&施恩, 魯智深&史進, 史進&朱武&陳達&楊春, 武松&張青&孫二娘, 楊志&魯智深&曹正 ———— 共生死
t_8 = 魯智深&李忠&周通 ———— 共尷尬
t_9 = 張青&孫二娘&施恩&曹正(河南)，楊志&楊春(山西)，周通&武松(山東)，朱武&李忠(定遠縣) ———— 老鄉
t_10 = 武松&施恩, 魯智深&史進, 史進&朱武&陳達&楊春, 武松&張青&孫二娘, 周通&李忠  ———— 老兄弟
t_11 = 0  
t_12 = 魯智深&楊志&史進 (都有延安府相關履歷)     
t_13 = ......    
  
  
這里如果按照影響力計算，則 s_1 ~ s_7，t_3，t_7 的權重都相當大。
由此可見三山幫的勢函數有多大，有猛人，有幫閑，有主將，有副將，有馬軍，有步兵，甚至還有軍師。他們彼此之間關系則是盤根錯節。
其在梁山內部絕對是第二大勢力。

0x04 條件隨機場 (conditional random field，CRF)

1. 條件隨機場

當隨機變量之間有依賴關系的時候就是條件隨機場。比如：

三山派的好漢不能和宋江嫡系挨著坐。

條件隨機場接收一個輸入序列 (觀察序列)如 X = (x1 ,x2, ..., xn)，

給出一個輸出目標序列( 隱藏狀態序列 ) Y = (y1 ,y2, ..., yn)，這里使用大寫 X,Y 表示序列。

一般地，輸入序列 X 被稱為 observations (觀測值) , 輸出序列 Y 叫作 states (隱藏狀態)。Random 指的是隨機變量 X and Y。 Conditional 指的是條件概率 Conditional probability。

HMM、MEMM屬于有向圖模型，貝葉斯網絡一般屬于有向圖。而CRF屬于馬爾科夫網絡屬于無向圖。

CRF是馬爾科夫隨機場的特例，條件隨機場沒有隱馬爾可夫模型那樣嚴格的獨立性假設條件，因而可以容納任意的上下文信息，可以靈活地設計特征。同時，條件隨機場具有表達長距離依賴性和交疊性特征的能力，而且所有特征可以進行全局歸一化，能夠求得全局的最優解，還克服了最大熵馬爾可夫模型標記偏置的缺點。

2. 數學定義

條件隨機場準確的數學語言描述是：設X與Y是隨機變量，P(Y|X)是給定X時Y的條件概率分布，若隨機變量Y構成的是一個馬爾科夫隨機場，則稱條件概率分布P(Y|X)是條件隨機場。

條件隨機場是在給定需要標記的觀察序列 X 的條件下計算整個標記序列 Y 的聯合概率分布，而不是在給定當前狀態條件下定義下一個狀態的分布。

\[P(Y|X) = \frac{exp (w.φ(x,y))}{Z_x} \]

注意Z(x)是遍歷所有 y 的全局歸一化，如果Z(x)寫在乘積符號里面的則就是local歸一化，那樣得到的是MEMM。

CRF本質上就是一個softmax，只是它不是在單樣本上面做的，而是序列化樣本；為了保證是整個序列做的分類，在CRF中考慮了相鄰狀態之間的轉換特征函數。

CRF損失函數由兩部分組成，真實路徑的分數和所有路徑的總分數。真實路徑的分數應該是所有路徑中分數最高的。

3. linear-CRF

在CRF的定義中，我們并沒有要求X和Y有相同的結構。而實現中，我們一般都假設X和Y有相同的結構，即:

\[??=(??1,??2,...????), ??=(??1,??2,...????) \]

線性的CRF，每個Y都只和前一個或后一個隨機變量相連，如 Y1——Y2——Y3——...Yn。每個最大團都是鄰近的兩個隨機變量，如(Y1, Y2)、(Y2、Y3)等

CRF也和MEMM一樣做了一階馬爾科夫假設，即當前狀態只與上一狀態有關，但是區別在于CRF的特征采用了全局特征，它把觀測序列當做整體來看所以它的特征函數是全局的。

線性Linear-CRF對比HMM把箭頭（轉移方向）變成了直線。最直白的感官體驗是每個圓圈（向量）都可以肆無忌憚暢通無阻的相鄰的圓圈相連了，交互多了，模型也變復雜了，每個圓圈之間的關系從“局部”也變成“全局”。線性Linear-CRF是CRF很多結構中比較常用的一種，只要保證狀態序列滿足馬爾科夫性都是CRF。

4. 例子

網上關于CRF有兩個比較好的例子，摘錄如下：

例子1

假設你有許多小明同學一天內不同時段的照片，從小明提褲子起床到脫褲子睡覺各個時間段都有（小明是照片控！）。現在的任務是對這些照片進行分類。比如有的照片是吃飯，那就給它打上吃飯的標簽；有的照片是跑步時拍的，那就打上跑步的標簽；有的照片是開會時拍的，那就打上開會的標簽。問題來了，你準備怎么干？

一個簡單直觀的辦法就是，不管這些照片之間的時間順序，想辦法訓練出一個多元分類器。就是用一些打好標簽的照片作為訓練數據，訓練出一個模型，直接根據照片的特征來分類。例如，如果照片是早上6:00拍的，且畫面是黑暗的，那就給它打上睡覺的標簽;如果照片上有車，那就給它打上開車的標簽。

這樣可行嗎？

乍一看可以！但實際上，由于我們忽略了這些照片之間的時間順序這一重要信息，我們的分類器會有缺陷的。舉個例子，假如有一張小明閉著嘴的照片，怎么分類？顯然難以直接判斷，需要參考閉嘴之前的照片，如果之前的照片顯示小明在吃飯，那這個閉嘴的照片很可能是小明在咀嚼食物準備下咽，可以給它打上吃飯的標簽；如果之前的照片顯示小明在唱歌，那這個閉嘴的照片很可能是小明唱歌瞬間的抓拍，可以給它打上唱歌的標簽。

所以，為了讓我們的分類器能夠有更好的表現，在為一張照片分類時，我們必須將與它相鄰的照片的標簽信息考慮進來。這——就是條件隨機場(CRF)大顯身手的地方！

例子2

RF是隨機場，MRF是馬爾可夫隨機場，又稱概率圖模型，CRF是條件隨機場，Linear Chain CRF是線性鏈CRF

拿“一個群體中人的性格，群體中一個人的性格可能會影響另一個的性格”舉例：
定義“我從小到大所有認識的人+我女朋友從小到大所有認識的人”就是這個空間，“空間里每個人的性格”都是一個變量，那么：

RF ：這個空間里每個人的性格變量都是隨機的，所有人的性格變量的集合就是一個RF

MRF ：假設現在有這么個條件，我不認識的人根本不影響我的性格（成對馬爾可夫性），那么就是MRF了。

CRF：剛才只說了性格變量互相影響，說的很虛，因為你需要有一些東西衡量性格呀，所以我又假設了一個條件，假設我能觀測到“所有人在認識的人和她接觸時她的笑的時間”，那么這時候的性格影響就不是那么不可描述了，我說她天生笑的多就是天生就是性格樂觀，這個人和這個人一起跟她說話他笑得比平均高，那就是這兩個人對他性格樂觀的影響大，這時候你把笑聲考慮進去研究性格，出現了條件概率，那就是CRF了。

線性鏈CRF：上面說的每個人可能認識很多人，這個情況就很復雜，你現在在假設一種情況，每個人都有編號，你只認識比你大一號或者比你小一號的那兩個人，于是你的性格就只受那兩個人的性格影響，而不管什么人，他們發出笑聲還是能或多或少影響你，那就是線性鏈CRF

如果再嚴格一點，不是所有人的笑聲影響你，就你自己真的笑了才影響你，那就是X和Y結構相同的線性鏈CRF，這樣的好處在于最大團的定義的話就是任意被連接兩個點都是最大團，比較好計算圖概率

M就是馬爾可夫的意思，代表具有三種馬爾可夫性（等價的，滿足一個另外兩個自然滿足），就是和我沒關系的點根本不影響我的概率分布（成對馬爾可夫性）；只有和我有關系的才能影響我的概率分布，整個群體對我的概率分布就是周圍人影響下的我的概率分布（局部馬爾可夫性），我的高中同學和大學同學，這兩撥同學之間互不認識，那么我對這兩撥同學的概率分布的影響是獨立的（全局馬爾可夫性）
C就是條件，沒有C就是意味著探討P(Y)的分布，有了C就是探討P(Y|X)，所以這個C是條件概率下的那個條件的意思。`

5. HMM vs MEMM vs CRF

假設

HMM模型中存在兩個假設：一是輸出觀察值之間嚴格獨立，二是狀態的轉移過程中當前狀態只與前一狀態有關(一階馬爾可夫模型)。其中，輸出獨立性假設要求序列數據嚴格相互獨立才能保證推導的正確性，而事實上大多數序列數據不能被表示成一系列獨立事件。
MEMM模型克服了觀察值之間嚴格獨立產生的問題，但是由于狀態之間的假設理論，使得該模型存在標注偏置問題。
CRF模型使用一種概率圖模型，解決了標注偏置問題，去除了HMM中兩個不合理的假設。因而可以容納任意的上下文信息，可以靈活地設計特征。同時，條件隨機場具有表達長距離依賴性和交疊性特征的能力，而且所有特征可以進行全局歸一化，能夠求得全局的最優解，還克服了最大熵馬爾可夫模型標記偏置的缺點。

預測輸出

其中HMM中，Yi只與Yi-1有關，而Xi輸出只與Yi有關。在MEMM中，Yi 是由Xi和Yi-1確定的，在CRF中，確定某個Yi，它會考慮整個Y及Xi的。

序列標注模型

這三個模型都可以用來做序列標注模型。但是其各自有自身的特點。

HMM模型：假設出變量間的概率分布，建模一切觀察到的變量的聯合分布。在Y變量間做了markov假設。對轉移概率和表現概率直接建模，統計共現概率。
MEMM模型：是對轉移概率和表現概率建立聯合概率，統計時統計的是條件概率。MEMM容易陷入局部最優，是因為MEMM只在局部做歸一化，
CRF模型：最大熵準則建模條件概率p(Y|X)。 統計了全局概率，在做歸一化時，考慮了數據在全局的分布，而不是僅僅在局部歸一化，這樣就解決了MEMM中的標記偏置的問題。要先把CRF約束成linear chain CRF，然后linear chain CRF和HMM的區別：是判別式模型和生成模型的區別，是函數擬合和概率模型的區別。

HMM是建立generative model ，即p(x,y) ，轉化為建立noisy-channel model，即求arg max p(y) p(x|y) ，繼而轉化為狀態轉移概率p(yi|yi-1) 和發射概率p(xi|yi) 之積，注意這個發射概率，與crf的發射概率不一樣。建模是對狀態轉移概率和發射概率進行參數估計，從大量的文檔數據中根據統計學來統計。decode過程是使用vertibe算法，利用狀態轉移概率和發射概率計算最優解答，這是一個生成模型。

MEMM是建立conditional model，即 p(y|x) ，轉化為狀態轉移概率p(yi|x1, ..., xi, yi-1) 。利用這個依賴關系建立Log-Linear Tagging Model，和HMM相比這樣可以捕捉到更多的feature，而在log linear的過程中使用局部歸一化，就是針對每一個yi, 都要求 exp(θ . f(hi, yi)) / ∑ exp(θ . f(hi, yi)) 。注意歸一化式子的分母對于不同的 yi 是不一樣的，因為不同的yi 依賴的 hi 不一樣。hi 是 yi 的依賴關系，即x1, ..., xi, yi-1。這也就代表在使用vertibe算法decode過程中，每一時步求的 yi 多多少少有點局部最優的味道，并不一定是全局最優。建模過程是對 θ 進行參數估計，即求結構化的最大似然估計。

crf是建立conditional model，即 p(y|x) ，crf也是Log-Linear Tagging Model，但是依賴關系變成了整個 y 序列依賴整個 x 序列，也就是全局歸一化，優點就是在decode過程中，那個歸一化式子的分母是一樣的，最后求得的一定是全局最優，所以decode時只需要求各種狀態轉移概率和發射概率之和就好了，在decode過程中HMM和MEMM都是求積，為什么crf是各種求和呢，因為它不用求分母，log 分子其實就是各種狀態轉移概率和發射概率之和。

6. 源碼閱讀

以下源碼出自 CRF++: Yet Another CRF toolkit ，分析主要摘錄 CRF++代碼分析

計算代價

計算每個節點和每條邊的代價（也就是特征函數乘以相應的權值，簡稱代價），就是勢函數。

其中fvector是當前命中特征函數的起始id集合，對于每個起始id，都有連續標簽個數種y值；n->y是當前時刻的標簽，由于每個特征函數都必須同時接受x和y才能決定輸出1或0，所以要把兩者加起來才能確定最終特征函數的id。用此id就能在alpha向量中取到最終的權值，將權值累加起來，乘以一個倍率（也就是所謂的代價參數cost_factor），得到最終的代價cost。

對于邊來說，也是類似的，只不過對每個起始id，都有連續標簽個數平方種y值組合。

struct Node {
  unsigned int         x;
  unsigned short int   y;
  double               alpha;
  double               beta;
  double               cost;
  double               bestCost;
  Node                *prev;
  const int           *fvector;
  std::vector<Path *>  lpath;
  std::vector<Path *>  rpath;
}

struct Path {
  Node      *rnode;
  Node      *lnode;
  const int *fvector;
  double     cost;
}

//計算節點的特征函數的代價
void FeatureIndex::calcCost(Node *n) const {
  n->cost = 0.0;

  // 遍歷節點對應的所有特征函數，因為一個特征函數可能會對應多個輸出類別，所以要將目前節點的 y 代入，得到 *f + n->y，就是當前 y 在 f 輸出類別中對應的位置。然后就可以從alpha向量中取到最終的權值, 再將權值累加。
#define ADD_COST(T, A)                                                        \
  do { T c = 0;                                                               \
    for (const int *f = n->fvector; *f != -1; ++f) { c += (A)[*f + n->y];  }  \
    n->cost =cost_factor_ *(T)c; } while (0)

  if (alpha_float_) {
    ADD_COST(float,  alpha_float_);
  } else {
    ADD_COST(double, alpha_);
  }
#undef ADD_COST
}

//計算每條邊的狀態特征函數的代價
void FeatureIndex::calcCost(Path *p) const {
  p->cost = 0.0;

#define ADD_COST(T, A)                                          \
  { T c = 0.0;                                                  \
    for (const int *f = p->fvector; *f != -1; ++f) {            \
      c += (A)[*f + p->lnode->y * y_.size() + p->rnode->y];     \
    }                                                           \
    p->cost =cost_factor_*(T)c; }

  if (alpha_float_) {
    ADD_COST(float,  alpha_float_);
  } else {
    ADD_COST(double, alpha_);
  }
}
#undef ADD_COST
}

前向后向算法

void TaggerImpl::forwardbackward() {
  if (x_.empty()) {
    return;
  }

  //計算所有節點的前向概率
  for (int i = 0; i < static_cast<int>(x_.size()); ++i) {
    for (size_t j = 0; j < ysize_; ++j) {
      node_[i][j]->calcAlpha();
    }
  }

  //計算所有節點的后向概率
  for (int i = static_cast<int>(x_.size() - 1); i >= 0;  --i) {
    for (size_t j = 0; j < ysize_; ++j) {
      node_[i][j]->calcBeta();
    }
  }

  //計算規范化因子
  Z_ = 0.0;
  for (size_t j = 0; j < ysize_; ++j) {
    Z_ = logsumexp(Z_, node_[0][j]->beta, j == 0);
  }

  return;
}

//其中cost是我們剛剛計算的當前節點的M_i(x)，而alpha則是當前節點的前向概率。lpath是入邊，一個頂點可能有多個入邊。
void Node::calcAlpha() {
  alpha = 0.0;
  for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
    alpha = logsumexp(alpha,
                      (*it)->cost +(*it)->lnode->alpha,
                      (it == lpath.begin()));
  }
  alpha += cost;
}

void Node::calcBeta() {
  beta = 0.0;
  for (const_Path_iterator it = rpath.begin(); it != rpath.end(); ++it) {
    beta = logsumexp(beta,
                     (*it)->cost +(*it)->rnode->beta,
                     (it == rpath.begin()));
  }
  beta += cost;
}

void Node::calcExpectation(double *expected, double Z, size_t size) const {
  const double c = std::exp(alpha + beta - cost - Z);
  for (const int *f = fvector; *f != -1; ++f) {
    expected[*f + y] += c;
  }
  for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
    (*it)->calcExpectation(expected, Z, size);
  }
}

#define MINUS_LOG_EPSILON  50
// log(exp(x) + exp(y));
//    this can be used recursivly
// e.g., log(exp(log(exp(x) + exp(y))) + exp(z)) =
// log(exp (x) + exp(y) + exp(z))
inline double logsumexp(double x, double y, bool flg)
{
    if (flg)
        return y;  // init mode
    const double vmin = std::min(x, y);
    const double vmax = std::max(x, y);
    if (vmax > vmin + MINUS_LOG_EPSILON)
    {
        return vmax;
    }
    else
    {
        return vmax + std::log(std::exp(vmin - vmax) + 1.0);
    }
}

全局歸一化

其中前后向概率都有了之后，計算規范化因子，此處能看出來是進行全局歸一化：

Z_ = 0.0;
for (size_t j = 0; j < ysize_; ++j) {
  // 注意，這里是用 node_[0] 位置的 beta 數值，就是說，這個已經是用后向概率的最終結果來計算 Z，這個就已經是考慮了全局情況，如果是用 alpha 計算，也得取最終數值，那就需要取 node_[n][j]->alpha 了
	Z_ = logsumexp(Z_, node_[0][j]->beta, j == 0); 
}

推導過程如下：

我們定義βi(yi|x)表示序列位置i的標記是yi時，在位置i之后的從i+1到n的部分標記序列的非規范化概率。

這樣，我們很容易得到序列位置i+1的標記是yi+1時，在位置??i之后的部分標記序列的非規范化概率βi(yi|x)的遞推公式：

\[??_??(??_??|??)=??_{??+1}(??_??,??_{??+1}|??)??_{??+1}(??_{??+1}|??) \]

在終點處，我們定義：

\[??_{??+1}(??_{??+1}|??)= \begin{cases} 1 \ ??_{??+1}=????????\\ 0 \ ???????? \end{cases} \]

如果用向量表示，則有：

\[??_??(??)=??_{??+1}(??)??_{??+1}(??) \]

對應著規范化因子Z(x)的表達式是：

\[??(??)=∑_{??=1}^????_??(????_|??)=∑_{??=1}^????_1(??_??|??) \]

也可以用向量來表示Z(x):

\[\\Z(x) = \alpha_n^T(x) . 1 = 1^T . \beta_1(x) \]

其中，1是 m維全1向量。

期望值的計算

所謂的節點期望值指的是節點對應的狀態特征函數關于條件分布P(y|x)的數學期望。

/**
 * 計算節點期望
 * @param expected 輸出期望
 * @param Z 規范化因子
 * @param size 標簽個數
 */
void Node::calcExpectation(double *expected, double Z, size_t size) const {

  const double c = std::exp(alpha + beta - cost - Z);

  // 概率求和意味著得到期望
  for (const int *f = fvector; *f != -1; ++f) {
    expected[*f + y] += c;
  }

  // 對應邊的期望值
  for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
    (*it)->calcExpectation(expected, Z, size);
  }
}

所謂邊的期望指的是邊對應的轉移特征函數關于條件分布P(y|x)的數學期望。

/**
 * 計算邊的期望
 * @param expected 輸出期望
 * @param Z 規范化因子
 * @param size 標簽個數
 */
void Path::calcExpectation(double *expected, double Z, size_t size) const
{
    const double c = std::exp(lnode->alpha + cost + rnode->beta - Z);
    for (const int *f = fvector; *f != -1; ++f)
    {
        expected[*f + lnode->y * size + rnode->y] += c;
    }
}

viterbi算法

void TaggerImpl::viterbi() {
  for (size_t i = 0;   i < x_.size(); ++i) {
    for (size_t j = 0; j < ysize_; ++j) {
      double bestc = -1e37;
      Node *best = 0;
      const std::vector<Path *> &lpath = node_[i][j]->lpath;
      for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
        double cost = (*it)->lnode->bestCost +(*it)->cost +
            node_[i][j]->cost;
        if (cost > bestc) {
          bestc = cost;
          best  = (*it)->lnode;
        }
      }
      node_[i][j]->prev     = best;
      node_[i][j]->bestCost = best ? bestc : node_[i][j]->cost;
    }
  }

  double bestc = -1e37;
  Node *best = 0;
  size_t s = x_.size()-1;
  for (size_t j = 0; j < ysize_; ++j) {
    if (bestc < node_[s][j]->bestCost) {
      best  = node_[s][j];
      bestc = node_[s][j]->bestCost;
    }
  }

  for (Node *n = best; n; n = n->prev) {
    result_[n->x] = n->y;
  }

  cost_ = -node_[x_.size()-1][result_[x_.size()-1]]->bestCost;
}

0x05 水滸傳例子

還是擴展之前的例子

梁山好漢在聚義廳開會，大家共聚一堂，討論招安事宜。但是群體中好漢會彼此影響投票的選擇。

隨機場 ：假定不是按照座次排序，而是隨意坐，這樣大家座位分布是隨機的。

最大團 ：雖然是隨機場，但是好漢們會自動按照小團體站在一起，比如黃門山四人站在一起，三山幫站在一起。這就形成了很多最大團。

馬爾可夫隨機場 ：假設現在有這么個條件，彼此不挨著的好漢不能影響彼此的投票決定（成對馬爾可夫性），這就是MRF。

條件隨機場：假設有一些其他條件需要考慮，比如如果鐵笛仙馬麟雖然屬于黃門山這個最大團，但是他的位置不小心挨著李逵，那么他在投票時候，勢必得考慮鐵牛兄弟的意見，不然鐵牛的拳頭不是吃素的。比如曹正雖然屬于三山幫，但是林沖是他師傅，所以他投票也得考慮豹子頭的意見，這就構成了條件場.....