1988-HMM詞性標記#

案件摘要#

1988 年，Bell Labs 的 Kenneth Church 發表 "A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text"（ANLP 1988），用隱馬可夫模型（HMM）做詞性標記，達到 96% 以上準確率，一舉突破規則法的天花板。同期 Steven DeRose 1988 也獨立發表 Viterbi 標記方法。本案的懸案是：TAGGIT 用 3300 條規則只做到 77%，規則越加越多、錯誤卻不減少，該怎麼辦？破案時刻在於：把「標記」重新定義為「機率推斷」——給定詞序列，找出最可能的詞性序列。

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

• 規則法詞性標記（如 TAGGIT 1971）累積了 3300 條規則，準確率停在 77%；每修一個錯誤可能引入新錯誤，是維護噩夢。
• Bell Labs 有深厚的語音識別傳統：HMM 與 Viterbi 演算法早在 1960s-1970s 就已成熟，用於語音的聲學模型。
• Brown Corpus（1961 年建構，100 萬詞、已做詞性標記）提供現成的訓練資料。
• Church 想證明一件事：統計法可以贏——不需要語言學家手寫規則，資料自己會說話。
• 真實文本（unrestricted text）充滿歧義與未登錄詞，規則法在乾淨語料外的表現崩潰。

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

HMM 模型#

HMM 把詞性標記建模成：狀態是詞性（tag），觀測是詞（word）。模型有兩組機率：

• 轉移機率： \(P(t_i \mid t_{i-1})\) —— 上一個詞性是名詞時，這個詞性是動詞的機率。
• 發射機率： \(P(w_i \mid t_i)\) —— 詞性是名詞時，觀測到詞 "dog" 的機率。

標記任務即找最可能的詞性序列：

Viterbi 演算法#

暴力窮舉所有詞性序列是指數複雜度 \(O(|T|^n)\) 。Viterbi 用動態規劃把複雜度降到 \(O(n|T|^2)\) ：

其中 \(\delta_t(s)\) 是「第 t 步處於狀態 s 的最佳路徑機率」， \(a\) 是轉移機率、 \(b\) 是發射機率。回溯指標 \(\psi_t(s) = \arg\max_{s'} \delta_{t-1}(s') a_{s',s}\) 記錄最佳前驅，用於還原路徑。

MLE 估計#

從 Brown Corpus 用最大概似估計（MLE）直接數次數：

未登錄詞用平滑（smoothing）處理。Church 的系統對無人看管的真實文本達到 96%+ 準確率，創下當時紀錄。

Python 實作 mini HMM 詞性標記#

import math

# 小語料：(word, tag) 序列；tag: N 名詞, V 動詞, D 限定詞
corpus = [
    [("the", "D"), ("dog", "N"), ("barks", "V")],
    [("the", "D"), ("cat", "N"), ("sleeps", "V")],
    [("a", "D"),  ("dog", "N"), ("sleeps", "V")],
    [("the", "D"), ("dog", "N"), ("runs", "V")],
    [("dogs", "N"), ("bark", "V")],
]

tags = ["N", "V", "D"]
words = sorted({w for s in corpus for w, _ in s})

def train(corpus):
    trans, emit, tag_count = {}, {}, {}
    for sent in corpus:
        prev = "<s>"
        for w, t in sent:
            trans[(prev, t)] = trans.get((prev, t), 0) + 1
            emit[(t, w)] = emit.get((t, w), 0) + 1
            tag_count[t] = tag_count.get(t, 0) + 1
            prev = t
    P_trans = {k: v / tag_count[k[0]] for k, v in trans.items()
               if k[0] in tag_count}                                  # MLE
    P_emit  = {k: v / tag_count[k[0]] for k, v in emit.items()}
    init_count = {k[1]: v for k, v in trans.items() if k[0] == "<s>"}
    P_init  = {t: init_count.get(t, 0) / sum(init_count.values())
               for t in tags}
    return P_trans, P_emit, P_init

def viterbi(sentence, P_trans, P_emit, P_init):
    """動態規劃：delta[t][s] = max_{s'} delta[t-1][s'] * a[s',s] * b[s,w]"""
    T, eps = len(sentence), 1e-10
    delta = [{s: math.log(P_init.get(s, eps) * P_emit.get((s, sentence[0]), eps))
              for s in tags}]
    back = [{}]
    for t in range(1, T):
        delta.append({})
        back.append({})
        for s in tags:
            best, best_prev = -math.inf, None
            for s_prev in tags:
                p = delta[t-1][s_prev] + math.log(P_trans.get((s_prev, s), eps))
                if p > best:
                    best, best_prev = p, s_prev
            delta[t][s] = best + math.log(P_emit.get((s, sentence[t]), eps))
            back[t][s] = best_prev
    # 回溯最佳路徑
    last = max(delta[T-1], key=delta[T-1].get)
    path, s = [last], last
    for t in range(T - 1, 0, -1):
        s = back[t][s]
        path.append(s)
    return path[::-1]

P_trans, P_emit, P_init = train(corpus)
print(viterbi(["the", "dog", "runs"], P_trans, P_emit, P_init))
# -> ['D', 'N', 'V']：限定詞-名詞-動詞
print(viterbi(["dogs", "sleeps"], P_trans, P_emit, P_init))
# -> ['N', 'V']

結案 -- 後果與影響#

• 統計法在 NLP 的第一場勝利：規則法開始退守，語言學家的角色從「寫規則」轉為「提供特徵直覺」。
• HMM 快速擴散到分詞、命名實體識別、語音識別，成為 1990 年代 NLP 的主力工具。
• 為 EM 演算法的應用鋪路：1988 年 IBM 統計機器翻譯同樣用機率模型 + 迭代估計。
• 「資料比規則重要」的哲學轉折確立，為日後的統計學習與深度學習鋪路。
• 對照 2018 年 BERT 的 98% 準確率：從 96%（HMM）到 98%（Transformer），30 年進步的起點正是這場勝利。

關鍵人物與文獻#

• Kenneth Church (1988). A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text. Proceedings of ANLP 1988, 136-143.
• Steven DeRose (1988). Grammatical Category Disambiguation by Statistical Optimization. Computational Linguistics 14(1), 31-39.
• Kenneth Church (1989). A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text. Bell Labs Technical Report.
• Henry Kucera & W. Nelson Francis (1967). Computational Analysis of Present-Day American English. Brown University Press（Brown Corpus）.
• Leonard Baum et al. (1970). A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains. Annals of Mathematical Statistics 41(1), 164-171.
• Lawrence Rabiner (1989). A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE 77(2), 257-286.