核心概念#

條件隨機場（Conditional Random Field, CRF）是計算聯合概率分布的有效模型，在自然語言處理中（特別是句子淺層分析）正確率可達 95%，應用範圍遠不止於此。

文法分析——計算機算法的演變#

  • 句法分析（Syntactic Parsing）是根據文法對句子建立語法樹；語義分析（Semantic Parsing）則得到嵌套框架或語義樹
  • 早期基於規則的方法（自底向上或自頂向下）在選擇規則時不可能一次選對，回溯導致計算複雜度極高，無法處理複雜句子
  • 1980 年代，布朗大學的尤金·查尼阿克（Eugene Charniack）引入統計方法——讓被分析句子的語法樹概率達到最大，大幅降低計算量並提高準確性
  • 拉納帕提（Ratnaparkhi）從全新角度看待文法分析——把它看成一個括括號的過程，從左到右掃描句子，每次判斷是否開始、繼續或結束一個括號
  • 拉納帕提建立統計模型 $P(A|prefix)$，用最大熵模型實現，算法複雜度與句子長度成正比，已是最優
  • 到 1990 年代，對「規矩」的語句（如《華爾街日報》），文法分析正確率已達 80% 以上

2000 年後網際網路內容品質參差不齊，傳統深層分析器正確率大幅下降。科學家轉而研究淺層分析（Shallow Parsing），只找出詞組及其關係，條件隨機場正是此領域的利器。

條件隨機場#

  • CRF 是隱馬爾可夫模型的擴展，保留了馬爾可夫鏈的特性，但觀察值 $x_i$ 不僅與當前狀態 $y_i$ 有關，也與前後狀態 $y_{i-1}$、$y_{i+1}$ 相關
  • 更廣義地說，CRF 是一種特殊的概率圖模型（Probabilistic Graph Model），與貝葉斯網絡相似但為無向圖
  • 模型的量化形式為聯合概率 $P(X,Y)$，透過邊緣分布和最大熵原則，得到指數模型：

$$P(x_1,…,x_n,y_1,…,y_m) = \frac{e^{f_1+f_2+…+f_k}}{Z}$$

  • 每個特徵函數 $f_i$ 的參數可用最大熵模型的訓練方法得到
  • 以「徐志摩喜歡林徽因」為例，可用信道模型來理解：觀察序列 $X$ 為各詞及詞性，狀態序列 $Y$ 為語法成分（名詞短語、動詞短語等）

條件隨機場在其他領域的應用#

  • 犯罪預測：加州大學洛杉磯分校為洛杉磯警察局建立基於 CRF 的模型，預測「何時、何地、發生何種犯罪」$P(l,t,c)$
  • 將城市劃分為 5m×5m 的小方格，以分鐘為單位計算，考慮人流、活動、天氣、失業率等多種因素作為特徵
  • 用 1300 萬個犯罪案件訓練模型，成功使該地區犯罪率降低 13%，被《時代》周刊譽為 2011 年度最優秀發明之一

和最大熵模型一樣，CRF 形式簡單但實現複雜。好在目前已有不少開源軟體可供使用，一般工程人員可以直接應用。

本章小結#

條件隨機場是一個非常靈活的預測統計模型，在模式識別、機器學習、生物統計，甚至預防犯罪等方面都有成功應用。

Backward Bayesian Network Viterbi Algorithm Forward