跳轉到

2001-CRF條件隨機場#

案件摘要#

2001 年，CMU 的 John Lafferty、Andrew McCallum 與 Fernando Pereira 發表《Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data》（ICML 2001），破解了纏擾序列標記多年的「標記偏誤」懸案。他們發現兇手不是資料，而是 HMM 與最大熵標記器中「局部正規化」的結構性缺陷：每個狀態各自做 softmax，分母會把整體機率質量吃掉。破案關鍵是反轉建模方向——改用判別式模型直接建模 \(P(y|x)\) ，並以「全域正規化」取代局部正規化。條件隨機場（CRF）就此誕生，成為深度學習之前序列標記的王者。

前因 -- 為什麼會有這個案子#

  • HMM 詞性標記自 1970-80 年代以來是序列標記主力，但它是生成式模型：建模 \(P(x,y) = P(y)P(x|y)\) ，被迫對觀察序列 \(x\) 的所有分佈做假設，且難以加入重疊的長距離特徵。
  • 1998 年 Léon Bottou 的分析指出 label bias problem：當狀態轉移機率是局部正規化（每個狀態的後繼轉移分數和為 1）時，低分數的轉移分支不會被懲罰，模型偏好「分支少」的狀態，導致偏向低熵的標記路徑。
  • 生成式 vs 判別式的辯論白熱化：naive Bayes 在文字分類上常輸給 logistic regression，理由正是後者直接建模 \(P(y|x)\) 、可自由加入重疊特徵。大家想把這個優勢搬進序列標記。
  • 1996 年 Ratnaparkhi 的最大熵（MaxEnt）詞性標記器成功把重疊特徵放進單步標記，但「MaxEnt 的序列版」遲遲難產——若對每一步做局部正規化，就重蹈 label bias 的覆轍；全域正規化的學習又看似難解。
  • McCallum 陣營急需一個能做資訊抽取（命名實體識別、分段）的工具，同時容納拼字、大小寫、詞彙、上下文等大量互相重疊的特徵。

線索與推理 -- 數學式、程式、理論#

線索一：標記偏誤的數學解剖#

局部正規化的 HMM/MaxEnt 標記器在每個狀態做 softmax：

\[ P(y_t = s | x, y_{t-1}) = \frac{\exp(w \cdot f(s, x, t))}{\sum_{s'} \exp(w \cdot f(s', x, t))} \]

整條路徑的機率是各步的乘積。問題在分母：若狀態 \(s'\) 只有一個後繼，則分母只有一項， \(P = \exp(w \cdot f)/\exp(w \cdot f) = 1\) ——無論該轉移分數多低，機率都是 1，梯度恆為零，學不到任何東西。乘積之下，高熵（分支多）狀態的分母會壓低經過它的所有路徑，模型因此系統性地偏向「經過分支少的狀態」的路徑，與觀察證據無關。

線索二：破案時刻——全域正規化的判別式模型#

Lafferty 等人反轉思路：不對每步局部正規化，而是對「整條標記序列」定義一個條件機率，分母只出現一次：

\[ P(y \mid x) = \frac{1}{Z(x)} \exp\Big( \sum_{k=1}^{K} \lambda_k F_k(y, x) \Big), \qquad F_k(y,x) = \sum_{t=1}^{T} f_k(y_{t-1}, y_t, x, t) \]

其中 \(Z(x) = \sum_{y'} \exp(\sum_k \lambda_k F_k(y', x))\) 是全域配分函數， \(f_k\) 是在位置 \(t\) 上以（前一標記、當前標記、整個觀察序列）為輸入的特徵函數。這是線性鏈 CRF。因為正規化是全域的，單一後繼的狀態不再有「機率恆為 1」的漏洞；因為是判別式的，特徵可以是任意重疊函數——拼字、前後詞、詞綴互不衝突。

線索三：學習與解碼#

訓練以最大概似估計 \(\lambda\) ，對數概似是凹函數，可用（廣義）迭代縮放或 LBFGS 求解。梯度透過前向-後向演算法計算邊際期望：

\[ \alpha_t(s) = \sum_{s'} \alpha_{t-1}(s') \exp(\lambda \cdot f(s', s, x, t)), \qquad \frac{\partial \log P(y|x)}{\partial \lambda_k} = F_k(y,x) - \mathbb{E}_{P(y'|x)}[F_k(y',x)] \]

解碼（預測最可能標記序列）用 Viterbi 動態規劃，複雜度仍是 \(O(T |S|^2)\) ——與 HMM 相同，結構上的破案並未犧牲效率。

程式：label bias 的對照與 mini 線性鏈 CRF#

以下 Python 程式先示範 label bias（局部正規化下分支少的狀態「吃掉」機率），再實作一個可執行的簡化線性鏈 CRF（窮舉全域正規化 + 梯度上升）：

import itertools, math

# --- Part 1: label bias 示範 ---
# 兩條路徑 rib=1: A(分支多, 局部分數低) -> B ; A' -> B'
# 路徑1: A->B, A 有兩個後繼, 轉移分數 [0.5, 0.5]
# 路徑2: A'->B', A' 只有一個後繼, 轉移分數 [0.1]
local = {
    ("A","B"): 0.5, ("A","C"): 0.5,   # A 分支多
    ("A2","B"): 0.1,                  # A2 分支少, 分數低
}
def local_prob(path):
    p = 1.0
    for (a,b) in zip(path, path[1:]):
        z = sum(v for (x,y),v in local.items() if x==a)
        p *= local.get((a,b), 0.0)/z
    return p
print("P(A->B) =", local_prob(["A","B"]))    # 0.5
print("P(A2->B)=", local_prob(["A2","B"]))   # 1.0 <- 分數低卻是 1, label bias!

# --- Part 2: mini 線性鏈 CRF (全域正規化) ---
# 觀察 x_t 取值 {'c','v'}(子音/母音), 標記 S = {N, V}
S = ["N", "V"]
data = [  # (x 序列, y 序列) 極小語料: 母音多為 V, 子音多為 N
    (list("cvc"), list("NVV")),
    (list("vvc"), list("VVN")),
    (list("ccv"), list("NNV")),
]

def feats(x, y):
    f = {}
    for t in range(len(y)):
        f[("emit", y[t], x[t])] = f.get(("emit", y[t], x[t]), 0) + 1
        if t > 0:
            f[("trans", y[t-1], y[t])] = f.get(("trans", y[t-1], y[t]), 0) + 1
    return f

keys = sorted({k for x,y in data for k in feats(x,y)})
w = {k: 0.0 for k in keys}

def path_score(f):
    return sum(w.get(k,0.0)*v for k,v in f.items())

def Z(x):
    return sum(math.exp(path_score(feats(x, list(y))))
               for y in itertools.product(S, repeat=len(x)))

for epoch in range(300):
    grad = {k: 0.0 for k in keys}
    for x, y in data:
        fy = feats(x, y)
        zx = Z(x)
        # 模型期望: 加權所有路徑的特徵
        for yy in itertools.product(S, repeat=len(x)):
            p = math.exp(path_score(feats(x, list(yy)))) / zx
            for k, v in feats(x, list(yy)).items():
                grad[k] = grad.get(k, 0.0) - p * v
        for k, v in fy.items():
            grad[k] += v
    for k in keys:
        w[k] += 0.5 * grad[k]

x_test = list("cvc")
best = max((math.exp(path_score(feats(x_test, list(y))))/Z(x_test), "".join(y))
           for y in itertools.product(S, repeat=len(x_test)))
print("學到的權重:", {k: round(v,2) for k,v in w.items()})
print("最可能標記:", best[1], "P =", round(best[0],3))

執行後可見：局部正規化讓「分數 0.1 的轉移」機率變成 1（label bias 鐵證），而 mini CRF 以全域正規化正確學到「母音→V、子音→N」的標記規則。

結案 -- 後果與影響#

  • CRF 迅速成為命名實體識別（NER）、中文分詞、詞性標記、淺層剖析的標準工具，2000s 到 2010s 中葉是序列標記的王者。
  • 它是深度學習之前序列標記的最後一代巔峰：几乎所有 CoNLL 共享任務的優勝系統都以 CRF 為核心。
  • 2015 年 BiLSTM-CRF（Huang, Xu, Yu）把雙向 LSTM 的表示能力與 CRF 的全域正規化解碼結合，成為神經序列標記的經典架構——CRF 的血脈延續至今。
  • log-linear 模型傳統確立：CRF 的全域 softmax 形式正是今天神經網路輸出層 softmax 的直系祖先。
  • 「判別式優於生成式」的方法論在序列標記上獲得決定性勝利，影響了後續整個 NLP 建模取向。

關鍵人物與文獻（條列）#

  • John Lafferty, Andrew McCallum, Fernando Pereira. "Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data." ICML 2001, pp. 282-289.
  • Léon Bottou. "Une Approche théorique de l'apprentissage connexionniste: Applications à la reconnaissance de la parole." PhD thesis, Université de Paris XI, 1991（label bias 的分析；英文整理見 Bottou 2009）.
  • Léon Bottou. "On the ailment of learning with local normalization." 2009（http://leon.bottou.org/papers/bottou-2009）.
  • Adwait Ratnaparkhi. "A Maximum Entropy Model for Part-Of-Speech Tagging." EMNLP 1996, pp. 133-142.
  • Andrew McCallum, Dayne Freitag, Fernando Pereira. "Maximum Entropy Markov Models for Information Extraction and Segmentation." ICML 2000, pp. 591-598（MEMM，label bias 的實際受害者）.
  • Zhiheng Huang, Wei Xu, Kai Yu. "Bidirectional LSTM-CRF Models for Sequence Tagging." arXiv:1508.01991, 2015.
  • Lawrence R. Rabiner. "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition." Proceedings of the IEEE 77(2), 1989, pp. 257-286.