條件隨機場

條件隨機場 (conditional random field, CRF) 是給定一組隨機變量\(\mathbf{X}\)條件下，另一組隨機變量\(\mathbf{Y}\)的條件概率分布模型。并假設隨機變量\(\mathbf{Y}\)構成馬爾可夫隨機場（稍后介紹）。一般在NLP中，特別是在標注、分詞、命名實體識別等中提到的CRF，是線性鏈條件隨機場。

在介紹CRF之前，需要先了解下其依賴的理論基礎。

概率無向圖模型

概率無向圖模型(probabilistic undirected graphical model), 又稱為馬爾可夫隨機場(Markov random field， MRF), 是可由無向圖表示的聯合概率分布。這里面涉及概率圖的多個概念，我們從圖(graph)開始漸進介紹。

圖是由節點（node）及連接結點的（edge）組成的集合，無向圖是指邊沒有方向的圖，用無向圖表示的分布，也被稱為馬爾可夫網(Markov network )。概率圖模型（probabilistic graphical model，PGM）則是由圖表示的概率分布。其中的結點表示隨機變量，邊表示隨機變量之間的依賴關系。要讓PGM成為MRF還需要滿足變量之間的一些馬爾可夫獨立性假設(Markov independent assumptions)，具體地是成對馬爾可夫性，局部馬爾可夫性，全局馬爾可夫性。

成對（pairwise）馬爾可夫性：指在無向圖（如G）上沒有邊連接的兩個結點(如，u,v分別對應隨機變量，如\(Y_u,Y_v\)，下同)在其他所有結點(如用O表示)給定的情況下，相互獨立, 具體地：

局部（local）馬爾可夫性: 設\(v\)是無向圖G中的一個結點，\(W\)表示與\(v\)有邊連接的所有的結點集合，\(W\)有時也稱為馬爾可夫毯（Markov Blanket)，在給定W， \(v\)與無向圖上其所他所有結點(如用集\(O\)表示)，條件獨立:

圖1. 在給定圖中橙色結點時，綠色結點與黃色結點條件獨立。

全局(global)馬爾可夫性：設結點集合A，B在無向圖G中被結點集合C分開，那么：

圖2. 在給定圖中橙色結點時，綠色結點與黃色結點條件獨立。

即在給定C的情況下，A、B兩集合對應的隨機變量條件獨立。此時稱結點集C在G中分離A與B，記為\(sep_{H_G}(A;B|C)\).

設聯合概率分布\(P(Y)\)，由無向圖G=(V,E)表示，如果\(P(Y)\)滿足成對、局部與全局馬爾可夫性，那么，就稱此聯合概率為概率無向圖模型(probabilistic undirected graphical model), 又稱為馬爾可夫隨機場(Markov random field， MRF)。

設X與Y是隨機變量，\(P(Y|X)\)是在給定X的條件下Y的條件概率分布。若隨機變量Y構成一個由無向圖G=（V，E）表示的馬爾可夫隨機場， 即:

對任意結點v成立，則稱條件概率分布\(P(Y|X)\)為條件隨機場。其中，\(w\neq v\)表示G上除v的所有點， \(w \sim v\)表示結點v的馬爾可夫毯，即與v連接的結點的集合。

上式表達，在考慮G圖上任意結點v的條件概率只需要考慮與其相連的結點集合與X即可。

一般我們假定X與Y有相同的圖結構，而且在一般應用上，特別是NLP當中， 目前主要常用的是線性鏈條件隨機場。

團（clique）無向圖G中的結點子集C， 若C中任意兩結點間均有邊連接，則稱C為G的一個團，如果C不能再加G中任一結點使用其使其成為更大（“大”指結點數量多）的團，則稱C為最大團(maximal clique).

將概率無向圖模型的聯合概率分布表示其所有最大團上的隨機變量的函數（也稱因子 factor)乘積的形式的操作，稱為概率無向圖模型的因子分解(factorization)

設C表示無向圖G上的一個最大團, \(Y_C\)表示C對應的隨機變量，那概率無向圖模型的聯合概率分布\(P(Y)\)：

此式由(Hammersley-Clifford定理)保證（此定理要求P(Y)為正分布，即隨機變量的概率均大于0）。其中Z稱為規范化因子（normalization factor), 或配分函數(partition function)：

因子\(\Psi_C(Y_C)\) 稱為也稱勢函數(potential function)，因C是G上的團，則也稱為團勢函數(clique potential function). 這里要求勢函數要嚴格正的，即率無向圖模型的聯合概率分布\(P(Y)\)要滿足正分布, 通常定義團勢函數為指數函數:

則\(P(Y)\)表示:

條件承機場的參數化形式:

其中，

\(t_k,s_l\)分別為邊上的特征函數與結點上的特征函數，\(\lambda_k,\mu_l\)為對應的權值。注意，特征函數的中\(x\)是整個序列，而不只是第\(k\)個或第\(l\)個.