條件隨機場（CRF）和隱馬爾科夫模型（HMM）最大區別在哪裡？CRF的全局最優體現在哪裡？

01-06

最近在看HMM和CRF的介紹，感覺一直沒深入理解二者的區別，除了一個是有向圖一個是無向圖，一個是生成式模型一個是判別式模型。二者都用了前後向演算法和維特比演算法，差異在哪裡？CRF全局最優體現在哪裡？

逐個回答

1. 一圖流，最大區別就是一個是Generative Model，一個是Discriminative Model，而CRF並不止Linear-Chain這種形式（類似於HMM），既然題主已經知道就不再贅述了。

2. 全局最優體現在訓練的時候，我們用最大似然法做參數估計，所以要在訓練集上面最大化對數似然函數L：

一般來講，我們最後還要加上一項正則化懲罰項來防止overfitting。

公式可以重寫為：

好了，現在我們將對數似然函數拆成A，B和C三部分，B屬於Normalization，C屬於Regularization。然後分別對他們求關於Lambda-k（就是參數）的偏微分。

針對A：

針對B：

針對C：

所以，整個對數似然函數，其實是一個Concave函數，第一項A是線性的，第二項B屬於Normalization，不會改變其Concave的性質，最後一項C也是Concave的，所以ABC三項加起來就是整個對數使然函數都是Concave的，而在最優化中，若函數是Concave的，那麼每個局部最優都是全局最優，同時加上正則化項可以令對數似然函數嚴格Concave，意味著只有一個global optimum，以上。

Reference:

1. Classical Probabilistic Models and Conditional Random Fields

2. An Introduction to Conditional Random Fields for Relational Learning

直接來分析定義好了：

隱馬爾科夫模型中對觀測序列x與隱狀態序列y的聯合概率建模，描述的是一種從隱變數產生觀測的產生式過程。整個聯合概率P(x,y)定義為每個局部概率的乘積：

$P(mathbf{x},mathbf{y})=prod_i P(y_i|y_{i-1})P(x_i|y_i)$

概率在每個局部都會歸一化（即P(y_i|y_{i-1},x)=1）。利用特徵進行局部概率計算的最大熵馬爾科夫模型（MEMM，即把HMM圖模型中從y指向x的箭頭都反過來）同樣有類似的局部歸一化性質。這樣會帶來所謂的標記偏置（label bias）問題（最近太忙，這裡留個坑以後慢慢畫圖解釋吧……想了解詳情可以先讀CRF原始論文[Lafferty et al., ICML 2001]里的相關討論或者直接網搜）。

而條件隨機場直接定義了條件概率P(y|x)，概率是定義在整個序列上的：

$P(mathbf{y}|mathbf{x})=frac{1}{Z}exp{(mathbf{w}^ opmathbf{F}(mathbf{x},mathbf{y}))}(=frac{1}{Z}exp{(sum_isum_kmathbf{w_k}^ opmathbf{f_k}(mathbf{x},y_{i-1},y_i))})$

相應的圖模型表示中沒有局部的箭頭，統一用無向邊表示。這樣模型定義的概率對於整個序列進行歸一化，即所謂的「全局歸一」。直覺上，只看到局部信息的概率估計，一般是不夠準確的。只有序列完整的情況下定義概率才有意義。

由於HMM轉移概率（P(y_i|y_{i-1})）或者線性鏈CRF特徵定義（f(x,y_{i-1}),y_i）的局部性，二者都可以使用維特比演算法來進行解碼（即求出我們所關心的argmax_y P(y|x)），也都可以用前向後向演算法計算局部邊緣概率P(y_i,y_{i-1})。但局部邊緣概率的用法完全不一樣：HMM在利用大規模無標註數據做訓練的EM演算法（在HMM中也常稱作Baum-Welch）需要計算這些概率，而CRF的梯度對應於經驗期望和模型期望（一個指數級求和）的差，計算後者可以簡化為求局部邊緣概率。

============================= 更新 ===============================

簡單填一下原答案留下的標記偏置問題（時間有限圖就先不擺了）：

以詞性標註為例，假設待標記語句為All the students...，其中all在訓練語料中主要被標記為PDT（predeterminer）和DT（determiner），而且從出現頻次上看一般會有P(DT|all) &> P(PDT|all)。根據原始MEMM的概率表達，上面的語句最終被標記為(1) PDT DT NNS ... 還是(2) DT DT NNS ... 的主要差異在於

P(y_0=PDT|y_{-1}=&, x_0=All)P(y_1=DT|y_0=PDT, x_1=the) 和

P(y_0=DT|y_{-1}=&, x_0=All)P(y_1=DT|y_0=DT, x_1=the) 誰更大。

那麼問題來了：訓練語料里所有的the都是以定冠詞（DT）形式出現，所以P(y_1=DT|y_0=PDT, x_1=the) = P(y_1=DT|y_0=DT, x_1=the) = 1，於是無論x_1是the還是別的詞，由於P(DT|all) &> P(PDT|all)導致y_0都會被判定為DT。

喜歡圖示的可以參閱CRF原始論文或者Hanah Wallach給出的另一個例子（參見http://dirichlet.net/pdf/wallach02efficient.pdf，2.3.2節）。這些例子揭示的無非是一件事情：低熵（如P(DT|y_{t-1}=任何, x_t=the)=1）的局部狀態轉移概率分布會導致部分相關狀態y概率最大的取值同當前步輸入x_t直接沒關係了。而原罪就是局部歸一。

p.s. 標記偏置是MEMM在理論上存在的問題，但其重要程度可能和具體應用以及模型實現都有關係。02年EMNLP有篇文章（http://www.aclweb.org/anthology/W/W02/W02-1002.pdf ）表示，就詞性標註這個具體任務而言，影響條件馬爾科夫模型（MEMM）標註精度的根源在於模型的獨立性假設，而不是標記偏置問題。後者完全可以通過更好的特徵設計來避開。

Conditional random filed 是 discriminative approach, 用conditional probability P(y|x), 不關心x是怎麼generate的；

HMM是generative approach，用joint distribution P(x,y), 需要考慮x是怎麼generate的。

解法也不一樣，CRF用stochastic gradient descent，HMM可以求出exact solution。

CRF 充分考慮到了context，在考慮 $Y$ 的相關性時對條件概率 $P(Y|X)$ 建模，並且CRF與MMEM一樣具有maxent 的feature形式，用戶可以自己設計並擴展feature，這是HMM所做不到的。

兩者都是對實際概率圖模型的簡化，區別主要在於簡化程度強弱。

HMM的假設性太強，隱藏態對觀察值的獨立輸出假設和隱藏態序列的齊次一階馬爾科夫假設。

CRF去除了這兩種假設，但是也是對實際概率圖做了簡化。