NLP 學習筆記（一）：文字處理與統計方法 - Bojin Li

這是我在墨大上 COMP90042 NLP 時的筆記，這一篇主要涵蓋文字前處理、BPE、N-gram 與平滑、文字分類，以及 POS、HMM 和 Viterbi。

1. 文字前處理

1.1 基本定義

術語	定義
Word 詞	具有意義和/或文法功能的一串字元（a sequence of characters with a meaning and/or function）
Sentence 句子	由詞按文法規則組織、表達一個完整意思的單位，以標點或結構邊界結束
Document 文件	一個連續的文字單元（如一篇新聞、一封郵件），由若干句子組成
Corpus 語料庫	用於訓練/評估的、成規模蒐集的文字集合（單數 corpus，複數 corpora）
Word token 詞元（詞例）	文字中每一次出現的詞例；"to be or not to be" 有 6 個 token
Word type 詞型	去重後的不同詞；"to be or not to be" 有 4 個 type
Lexicon 詞典	一個語言/領域中所有詞型（及詞條資訊）的集合

記憶點：token 數 ≥ type 數；語料規模常用 $\vert V\vert$ （詞表大小）和 token 總數描述。

1.2 為什麼需要前處理

Language is compositional. 人類可以把文件拆成一個個組成成分來理解；要讓電腦理解語言，就必須讓它做同樣的拆解。

前處理把原始字串逐步變成適合任務的表示。下面是一條用於傳統文字處理的示意流程：

TEXT

"<p> Hi there. I'm TARS. </p>"
  → 去格式      "Hi there. I'm TARS."
  → 分句        ["Hi there.", "I'm TARS."]
  → 分詞        [["Hi","there","."], ["I","'m","TARS","."]]
  → 正規化      [["hi","there","."], ["i","be","tars","."]]
  → 去停用詞    [["hi","tars","."]]        （範例）

1.3 前處理五步法

這些步驟依任務取捨，並非所有模型都要全部執行。語言模型通常需要保留標點、詞形和功能詞；現代預訓練模型也應使用與訓練時一致的 tokenizer。

圖 1-1　文字前處理五步流水線，以及同一句話在各步之後的形態。

步驟	英文	目標
1	Remove unwanted formatting	去掉 HTML/XML 標籤、Markdown 符號、多餘空白、跳脫字元
2	Sentence segmentation 分句	把文件切成句子
3	Word tokenisation 分詞	把句子切成 token；含子詞（BPE）方案
4	Word normalisation 詞正規化	統一大小寫、拼寫、詞形（lemmatisation / stemming）
5	Stopword removal 去停用詞	去掉高頻、低資訊量的功能詞

步驟 2：分句（Sentence Segmentation）

四種做法，由簡到難：

標點拆分：遇 . ! ? 斷句。
- 問題：縮寫（Dr. Smith）、小數（3.14）、網址（example.com）會被誤切。
正規表示式拆分：用模式匹配處理常見例外，如 (?<!\bDr)\.\s+、要求句號後接大寫字母。
字典法：維護縮寫/例外詞典（Mr., Dr., U.S.A., e.g.），命中則不切。
機器學習（序列標註）：
- Method：把每個候選邊界（通常是標點）當作一次二分類判斷 "此處是否真的是句子邊界"；也可整體視為序列標註問題。
- Model：邏輯迴歸 / 最大熵 / CRF / BiLSTM-CRF / 小型 Transformer 分類器。
- Features：
- - 當前標點符號本身（. vs ? vs !）
  - 標點前一個 token 及其形態（是否縮寫、是否數字、長度、是否大寫）
  - 標點後一個 token 是否大寫開頭、是否為常見句首詞
  - 標點後是否緊跟引號/括號等閉合符號
  - 上下文視窗內 token 的 n-gram 特徵、是否出現在縮寫詞典中

步驟 3：分詞（Word Tokenisation）

英文：先按空白切，再處理標點與縮寫（如 Penn Treebank 規則：don't → do + n't，U.S. → U.S. 保留為一個 token）。難點是 what's a word?（New York 是一個詞還是兩個？）
中文：中文無空格，需分詞。見 MaxMatch（最大匹配）。
子詞（Subword）：BPE 等，見第 2 節。

中文 MaxMatch（最大匹配）

思路：給定詞典，從左（或右）貪心地取詞典中最長的可匹配串作為詞。

範例：

TEXT

詞典：{去买新, 西兰花, 西兰花新}
句子：去买新西兰花

正向最大匹配（FMM，從左往右，最長優先）：
  位置 0：嘗試 "去买新"（長度 3，詞典中）→ 切出「去买新」
  位置 3：嘗試 "西兰花"（長度 3，詞典中）→ 切出「西兰花」
  結果：去买新 / 西兰花

要點與缺陷：

FMM（正向最大匹配）與 RMM（逆向最大匹配）結果可能不同；實務上常兩者都跑，再以規則消歧。
貪心策略不能保證全域最佳：遇到歧義串（如「新西兰/花」vs「新/西兰花」）容易切錯。
詞典未登錄詞（OOV）無法處理，需配合規則或統計模型（如 HMM/CRF 分詞、jieba）。
優點：實作極簡、速度快、無需訓練資料。

步驟 4：詞正規化（Word Normalisation）

目的：

減少詞表規模（USA / U.S.A. / usa → 同一個詞），緩解資料稀疏；
把不同詞形映射到同一語意單位，讓模型在有限資料上學到更穩定的統計量；
統一樣式（大小寫、全半角、拼寫變體）便於匹配與檢索。

怎麼做：

大小寫折疊（case folding）：The → the（注意專有名詞、縮寫會丟失資訊）
拼寫正規化：colour → color、organise → organize
數字/日期正規化：2024-01-01、3.14 統一標記為 <NUM>
詞形還原：Lemmatisation 或 Stemming（見下）

Removing Morphology：兩種詞形變化的區別

類型	Inflectional Morphology（屈折變化）	Derivational Morphology（派生變化）
含義	同一個詞、不同文法形態	由舊詞造出新詞
例子	名詞複數 +s；動詞三單 +s、時態 +ed/+ing；形容詞比較級 +er、最高級 +est	後綴改詞性：person → personally；前綴改詞義：write → rewrite
是否改詞性/詞義	不改	改變

Lemmatisation vs Stemming 對比

維度	Lemmatisation（詞形還原）	Stemming（詞幹擷取）
處理對象	去掉屈折變化，回到 lemma（詞典原形）	去掉後綴，保留詞幹
方式	Lexicon-based（依賴詞典 + 詞性）	Rule-based（一般是一套刪綴規則）
輸出	有意義、實際存在的詞	可能是無意義的詞幹（studies → studi）
速度	較慢（需查詞典/詞性）	較快
合適的任務	需要真實詞形、語意敏感的任務（如生成、可讀性要求高）	大規模統計、檢索、分類（只要詞形一致即可）

Porter Stemmer

最流行（most popular）的英文詞幹擷取演算法，1980 年 Porter 提出，規則 + 條件（measure $m$ ）驅動。
處理順序：先去掉屈折後綴（inflectional：-s, -es, -ed, -ing），再去掉派生後綴（derivational：-ational, -fulness, -ness, -ment）。
特點：快、無詞典；缺點是會過度/不足截斷（university → univers、generously → gener）。

步驟 5：停用詞去除（Stopword Removal）

定義：在語料中高頻出現、但幾乎不承載主題資訊的詞，如 the, a, of, is, and, to。
目的：
- 縮小特徵維度、降低計算與儲存成本；
- 去掉雜訊，讓模型聚焦實詞（內容詞）；
- 對檢索/主題分類類任務通常有益。
如何選擇：
1. 封閉類詞/功能詞：限定詞、介系詞、連詞、代詞、助動詞等（closed-class words，數量有限、幾乎不新增）。
2. 高頻詞：統計語料，取頻率最高的 top- $k$ （需人工檢查，避免誤刪 not, no 等否定詞）。
3. 現成詞表：NLTK 的 stopwords、spaCy 的停用詞表（可依語言載入）。
注意：情感分析、否定偵測、句法分析等任務不能直接套用停用詞表；例如 not good 去掉 not 就會改變語意。是否刪除應由任務和驗證結果決定。

2. 子詞切分 BPE

2.1 動機

詞表規模的兩難：詞表太大 → 參數爆炸、稀疏；詞表太小 → 大量 OOV（未登錄詞）。
子詞（subword）折衷：常用詞保持整詞，罕見詞拆成更小的有意義片段。
- Colourless green ideas sleep furiously → [colour] [less] [green] [idea] [s] [sleep] [furious] [ly]

2.2 演算法（Byte-Pair Encoding）

訓練（學習合併規則）

把所有詞拆成字元序列，詞尾加結束符 _（或 </w>），統計詞頻。
統計所有相鄰符號對（pair）的出現頻次。
把頻次最高的 pair 合併成一個新符號，加入詞表。
重複步驟 2–3，直到達到預設的合併次數 $k$ （或詞表大小）。
輸出：合併規則列表（依學習順序）＋最終子詞詞表。

編碼（對新文字分詞）

依學習到的合併順序依次套用合併規則；沒被任何規則覆蓋的部分保留為單字元。因此編碼是確定性的，不需要重新統計。

2.3 完整範例

語料（詞尾以 _ 標記）：

Corpus	Frequency
o l d _	7
o l d e r _	3
f i n e s t _	9
l o w e s t _	4

初始相鄰對頻次

Pair	Count	說明
(e, s)	13	finest_ 9 + lowest_ 4
(s, t)	13	finest_ 9 + lowest_ 4
(t, _)	13	finest_ 9 + lowest_ 4
(o, l)	10	old_ 7 + older_ 3
(l, d)	10	old_ 7 + older_ 3
(f, i)	9	finest_ 9
(i, n)	9	finest_ 9
(n, e)	9	finest_ 9
(d, _)	7	old_ 7
(l, o)	4	lowest_ 4
(o, w)	4	lowest_ 4
(w, e)	4	lowest_ 4
(d, e)	3	older_ 3
(e, r)	3	older_ 3
(r, _)	3	older_ 3

合併過程（頻次相同時依實作約定取其一，常見做法是取最先出現/字典序最小者）

輪次	合併	頻次	結果語料
1	e + s → es	13	o l d _(7) o l d e r _(3) f i n es t _(9) l o w es t _(4)
2	es + t → est	13	f i n est _(9) l o w est _(4)
3	est + _ → est_	13	f i n est_(9) l o w est_(4)
4	o + l → ol	10	ol d _(7) ol d e r _(3)
5	ol + d → old	10	old _(7) old e r _(3)
6	f + i → fi	9	fi n est_(9)
7	fi + n → fin	9	fin est_(9)
8	fin + est_ → finest_	9	finest_(9)
9	old + _ → old_	7	old_(7)

表中每輪只列出受本輪合併影響的詞，其他詞保持不變。

最終詞表（部分）：o, l, d, e, r, f, i, n, s, t, w, _, es, est, est_, ol, old, fi, fin, finest_, old_, …

圖 2-1　BPE 從語料中學到的合併操作（r · → r·、l o → lo、lo w → low、e r· → er·）。這裡使用論文中的原始範例。來源：Sennrich et al., Neural Machine Translation of Rare Words with Subword Units, ACL 2016, Figure 1。

2.4 要點與延伸

超參數：合併次數 / 目標詞表大小，決定"詞"與"字"的粒度權衡。
優點：詞表可控；高頻詞可以整詞保留，低頻詞可以拆成子詞，緩解稀疏。只要所需字元都在初始字元表中，就能繼續拆分；未覆蓋的字元仍可能變成未知符號，byte-level BPE 或 byte fallback 可以進一步處理這種情況。
缺點：切分基於頻次而非語意，邊界可能不自然；不同語料/領域學到的分詞不一致。
常見方案：BPE、WordPiece（BERT 使用）和 Unigram（T5 使用）。SentencePiece 是工具包，支援 BPE、Unigram 等演算法，可以直接處理原始文字而不要求先按空格分詞。不要把工具名與其中一種演算法當成同義詞。

3. N-gram 語言模型

3.1 任務

語言模型（Language Model, LM）給一個詞序列賦予機率 $P(w_1, w_2, \dots, w_m)$ 。

如何生成句子：從 $P(w_t \mid w_{<t})$ 逐步取樣/取 argmax，一次生成一個詞，直到 <eos>。
如何判斷一個句子比另一個更好：比較模型給出的整句機率（或對數機率、困惑度）。在同一模型、相同分詞規則下，較高機率通常表示更符合訓練資料的分布；跨長度比較時還需要注意長度正規化。

3.2 應用

拼寫糾錯 / 輸入法候選排序（I have a gu → guy? gun? gut?）
語音辨識（區分同音詞）
機器翻譯（選出更通順的譯文）
文字生成、摘要的流暢度評分

3.3 N-gram 是什麼

N-gram：連續的 $n$ 個 token 組成的片段。

$n$	名稱	例子（the dog barks）
1	unigram	the / dog / barks
2	bigram	the dog / dog barks
3	trigram	the dog barks

N-gram 語言模型假設：第 $t$ 個詞只依賴前面 $n-1$ 個詞。

3.4 三個推動 N-gram 的概念/假設

(a) 從聯合機率到條件機率（Chain Rule）

以 I like apple 為例：

聯合機率： $P(\text{I like apple}) = P(\text{I}) \cdot P(\text{like} \mid \text{I}) \cdot P(\text{apple} \mid \text{I like})$
鏈式法則（對任意長度成立）：

P(w_1, w_2, \dots, w_m) = \prod_{i=1}^{m} P(w_i \mid w_1, \dots, w_{i-1})

問題：越往後的條件項，條件部分越長，幾乎不可能從語料中統計到（資料稀疏）；句子一長，參數數量指數爆炸。
條件機率： $P(A\mid B) = \dfrac{P(A,B)}{P(B)}$ 。

(b) 馬可夫假設（Markov Assumption）

只依賴前 $n-1$ 個詞，而不是全部歷史：

P(w_1, \dots, w_m) \approx \prod_{i=1}^{m} P(w_i \mid w_{i-n+1}, \dots, w_{i-1})

$n$	模型	公式
1	unigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i)$
2	bigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i \mid w_{i-1})$
3	trigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i \mid w_{i-2}, w_{i-1})$

用相對頻次估計條件機率：

P(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})}, \qquad P(w_i) = \frac{C(w_i)}{M}

其中 $C(\cdot)$ 是計數， $M$ 是總 token 數。

手算範例

語料（兩句，句首句尾用 <s> <eos> 標記）：

TEXT

<s> yes no no no no yes <eos>
<s> no no no yes yes no <eos>

機率	計算	結果
$P(\text{yes} \mid \text{<s>})$	$1 / 2$	0.5
$P(\text{no} \mid \text{yes})$	$2 / 4$	0.5
$P(\text{no} \mid \text{no})$	$5 / 8$	0.625
$P(\text{yes} \mid \text{no})$	$2 / 8$	0.25
$P(\text{<eos>} \mid \text{yes})$	$1 / 4$	0.25
$P(\text{<eos>} \mid \text{no})$	$1 / 8$	0.125

語料中 yes 出現 4 次、no 出現 8 次。對同一個前詞，後繼詞還應包含句尾標記：例如 no 的後繼機率為 $5/8+2/8+1/8=1$ 。

3.5 N-gram 的三個問題

問題	現象	對策
a) 語言具有長距離影響	只看前 $n-1$ 個詞，忽略遠處上下文（"The trophy would not fit in the suitcase because it was too big" 中 it 指代要靠遠距離資訊）	增大 $n$ （但資料稀疏）、快取模型、RNN/Transformer
b) 機率通常很小	連乘幾十個 $<1$ 的數會下溢為 0	用對數機率相加： $\log P = \sum \log P(w_i\mid\cdot)$ ；計算困惑度時也先求平均負對數機率
c) 未出現過（零機率）	訓練集沒有的 n-gram 計數為 0 → 整句機率歸零	平滑（Smoothing），見第 4 節

4. 平滑 Smoothing

目標：給未出現的 n-gram 分配非零機率，同時保證所有機率之和仍為 1（機率質量守恆）。

4.1 Add-one（Laplace）平滑

基本想法：假裝每個 n-gram 都至少出現過一次，即給所有計數 $+1$ 。

P_{\text{add1}}(w_i) = \frac{C(w_i) + 1}{M + \vert V\vert } \qquad\text{(unigram)}

P_{\text{add1}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1} w_i) + 1}{C(w_{i-1}) + \vert V\vert } \qquad\text{(bigram)}

分母加 $\vert V\vert$ 正是為了讓機率之和仍為 1（ $\vert V\vert$ 個候選各多算了 1 次）。

問題： $+1$ 對低頻詞/稀疏語料來說"太多了"，把大量機率質量分給未見事件，明顯壓低已見 n-gram 的機率，效果偏差大。

4.2 Add-k（Lidstone）平滑

P_{\text{add-}k}(w_i \mid w_{i-2}, w_{i-1}) = \frac{C(w_{i-2}, w_{i-1}, w_i) + k}{C(w_{i-2}, w_{i-1}) + k\,\vert V\vert }

$k$ 是需要人為選擇的超參數， $0<k<1$ 通常優於 $k=1$ ；最佳 $k$ 需要透過實驗（驗證集）確定。
缺點：
1. 需要主動選 $k$ ，不同 $k$ 平滑效果差異明顯；
2. 給定同一上下文時，所有未見 n-gram 都得到相同的機率，0 與 0 之間沒有區別，無法區分"更可能未見"與"幾乎不可能"；
3. 破壞了原始計數的比例關係。

4.3 Absolute Discounting（絕對折扣）

想法：從每個見過的詞那裡"借"走固定的 $d$ （如 $d=0.1$ ），把這些機率質量分給沒見過的詞。

P_{\text{abs}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i) - d}{C(w_{i-1})}, \quad \text{若 } C(w_{i-1},w_i) > 0

範例（context = alleged，5 個已見 bigram、2 個未見 bigram）

詞	counts	未平滑機率	Add-α (α=0.1) 有效計數	Add-α 平滑機率	Discounting (d=0.1) 有效計數	Discounting 平滑機率
impropriety	8	0.4	7.826	0.391	7.9	0.395
offense	5	0.25	4.928	0.246	4.9	0.245
damage	4	0.2	3.961	0.198	3.9	0.195
deficiencies	2	0.1	2.029	0.101	1.9	0.095
outbreak	1	0.05	1.063	0.053	0.9	0.045
infirmity	0	0	0.097	0.005	0.25	0.013
alleged	0	0	0.097	0.005	0.25	0.013
合計	20	1.0	20	1.0	20	1.0

折扣後每個已見詞變成 $8-0.1=7.9$ 、 $5-0.1=4.9$ …，共"借出" $5\times0.1=0.5$ 的有效計數，對應 $0.5/20=0.025$ 的機率質量；
借來的 $0.5$ 個有效計數平均分給 2 個未見詞： $0.5/2 = 0.25$ （有效計數），正規化後為 $0.25/20=0.0125\approx0.013$ 。

4.4 Katz Backoff（回退）

想法：已見就用折扣後的機率；未見就按 lower-order model（低階模型）重新分配搶來的機率質量。

P_{\text{katz}}(w \mid h) = \begin{cases} \dfrac{C^*(h,w)}{C(h)}, & \text{if } C(h,w) > 0 \\[2mm] \alpha(h)\,P_{\text{lower}}(w), & \text{otherwise} \end{cases}

這裡 $h=w_{i-1}$ 是上下文， $C^*(h,w)$ 是折扣後的計數。Katz 通常使用基於 Good–Turing 的計數折扣，並非把所有已見計數統一減去同一個常數。回退權重為：

\alpha(h)=\frac{1-\sum_{w:C(h,w)>0}C^*(h,w)/C(h)}{\sum_{w:C(h,w)=0}P_{\text{lower}}(w)}

分子是高階模型留下的機率質量，分母是在當前上下文中未見詞的低階機率之和；兩者一起保證最終分布正規化。

Katz 的問題

回退只看低階模型的原始機率，而低階機率本身不能反映"這個詞有多容易被用作新上下文"。
示意例子：I can not see without my reading ______
- 直覺答案：glasses（reading glasses 眼鏡）
- 假設 reading glasses 和 reading Kong 都未出現過，而語料中 King Kong 很常見。只看 unigram 時， $P(\text{Kong})$ 可能高於 $P(\text{glasses})$ ，即使 Kong 幾乎總跟在 King 後面，也可能被錯誤地選中。
- 根因：unigram 機率高 ≠ 適合接在 reading 後面。Kneser-Ney 用**延續機率（continuation probability）**修正這一點。

4.5 Kneser-Ney 平滑

想法：不再按原始計數分配折扣質量，而按多樣性（versatility）——這個詞能跟在多少個不同的詞後面——來分配。

低多樣性（但高頻）：假如 Francisco 只跟在 San 後面，那麼即使總詞頻很高，延續計數也只有 1。用它補全一個從未見過的上下文時，不應僅憑高詞頻就給出很高的機率。
高多樣性：glasses 可以跟在 reading, sun, wine, beer, eye… 後面 → 延續計數高，回退時反而更容易被選中，從而修正 Katz 的錯誤。

公式：插值形式

下面使用常見的插值 Kneser–Ney：低階分布不只在高階計數為零時參與，而是與折扣後的高階機率相加。

P_{KN}(w_i \mid w_{i-1}) = \frac{\max(C(w_{i-1},w_i)-D,0)}{C(w_{i-1})} +\lambda(w_{i-1})\,P_{\text{cont}}(w_i)

P_{\text{cont}}(w_i)= \frac{\vert\{u:C(u,w_i)>0\}\vert}{\vert\{(u,v):C(u,v)>0\}\vert},\qquad \lambda(h)=\frac{D\,\vert\{v:C(h,v)>0\}\vert}{C(h)}

分子：有多少個不同的前詞後面出現過 $w_i$ （即 $w_i$ 的"上下文類型數"）；
分母：所有詞的上下文類型數之和（正規化）；
$\lambda(h)$ ：在上下文 $h$ 下被折扣掉的總機率質量； $0<D<1$ 時，每個已見後繼都貢獻 $D/C(h)$ 。高階分布與低階分布相加後，機率和仍為 1。

4.6 Interpolation（插值）

想法：不"二選一"地回退，而是把不同階的 n-gram 模型加權混合，權重透過調參（在 held-out 資料上學習）得到。

P_{IN}(w_i \mid w_{i-1}, w_{i-2}) = \lambda_3 P_3(w_i \mid w_{i-2}, w_{i-1}) + \lambda_2 P_2(w_i \mid w_{i-1}) + \lambda_1 P_1(w_i)

\sum_k \lambda_k = 1, \qquad \lambda_k \ge 0

$\lambda$ 在 held-out data 上學習（EM 或網格搜尋），不是憑直覺任意指定；
優點：既保留高階模型的精確性，又用低階模型提供補充，通常優於純 backoff。

4.7 平滑方法比較小結

方法	核心思想	優點	缺點
Add-1	所有計數 +1	最簡單，保證非零且已正規化	對稀疏資料加得太多，嚴重壓低已見機率
Add-k	所有計數 +k	比 add-1 溫和	需調 $k$ ；未見詞機率全相同；破壞原比例
Absolute Discounting	已見詞統一減 $d$ ，餘額給未見詞	簡單、效果好於 add-k	不區分低階上下文的資訊量
Katz Backoff	未見時回退到低階	保留高階精確性	回退依據是原始機率，忽略上下文多樣性（reading Kong 問題）
Kneser-Ney	用延續機率分配折扣質量	經典 n-gram 模型中的強基線	公式較複雜，需兩套計數
Interpolation	各階模型加權混合	穩定、常優於 backoff	需在 held-out 上調 $\lambda$

5. 文字分類

5.1 任務定義

輸入：一個文件 $d$ （通常表示為特徵向量 vector of features）＋一個固定的類別集合 $C=\{c_1, c_2, \dots, c_k\}$ （categorical，不是連續值也不是有序值）。
輸出：預測類別 $\hat{c} \in C$ 。

5.2 應用

Topic classification 主題分類（經濟/政治/體育）
Sentiment analysis 情感分析
Native-language identification 母語辨識（例如從外語寫作判斷作者的母語背景）
Natural language inference 自然語言推論（蘊含/矛盾/中立）
Automatic fact-checking 自動事實查核
Paraphrase 複述判定

5.3 標準流程

Identify a task of interest —— 明確任務
Collect an appropriate corpus —— 蒐集資料
Carry out annotation —— 人工標註
Select features —— 選特徵（詞袋、n-gram、TF-IDF、embedding…）
Choose a machine learning algorithm —— 選模型
Train model and tune hyper-parameters using held-out development data —— 用開發集調參
Repeat earlier steps as needed —— 迭代
Train final model —— 訓練最終模型
Evaluate model on held-out test data —— 在測試集上評估

5.4 選擇方法時要注意的維度

維度	含義
偏差 Bias	模型的限制或簡化假設造成的系統性誤差；假設與真實資料不符時，可能帶來較大的偏差
變異數 Variance	模型對訓練集的敏感程度。越敏感，換一批資料結果波動越大（易過擬合）
潛在假設	模型依賴的條件（如特徵獨立、線性邊界、距離有意義），偏離時可能影響效果
複雜度	訓練/推論的時間與空間成本，是否可擴展到大量資料
速度	訓練與預測延遲是否滿足線上要求

偏差–變異數取捨：高偏差常對應欠擬合，高變異數常對應過擬合。在平方損失下，期望預測誤差可以分解為偏差²、變異數與不可約雜訊；分類任務中也可借這個框架理解模型取捨。

5.5 常用演算法逐個比較

(1) Naïve Bayes

基本思想：在貝氏法則下選後驗機率最大的類：

P(C\mid F) \propto P(F\mid C)\,P(C)

即"類先驗 × 該類下出現這些特徵的機率"。

樸素假設：特徵之間條件獨立：

P(F \mid C) = \prod_{f \in F} P(f \mid C)

Pro：極快、訓練只需計數、對少量資料/高維稀疏特徵穩健、多分類天然支援、可增量更新。
Con：獨立性假設幾乎從不成立（詞之間有強相關），機率值校準差（常給出 0/1 極端值）；需平滑處理零機率。

(2) Logistic Regression（邏輯迴歸 / 最大熵）

名字裡有 regression，但它是分類器。
線性模型，用 softmax 把線性得分"壓"成合法機率：

P(y=c \mid x) = \frac{\exp(w_c^\top x + b_c)}{\sum_{c'} \exp(w_{c'}^\top x + b_{c'})}

訓練目標：最大化訓練資料機率（等價最小化交叉熵），同時加正則化鼓勵權重小或稀疏。
Pro：機率輸出可解釋、訓練快、可用 L1/L2 正則做特徵選擇、線性可擴展到大語料。
Con：只能學線性決策邊界（需人工特徵交叉才能表達非線性）；對特徵縮放敏感；類別極不平衡時需調權重。

(3) Support Vector Machine (SVM)

定義：找到能把訓練資料分開、且間隔（margin）最大的超平面。

\min_{w,b}\ \tfrac{1}{2}\Vert w\Vert ^2 \quad \text{s.t.}\quad y_i(w^\top x_i + b) \ge 1

Pro：在高維稀疏文字上表現強（文字分類的經典強基線）；最大間隔帶來好的泛化；可用核函數處理非線性。
Con：原生只做二分類（多分類需 one-vs-rest）；核 SVM 在大樣本上訓練成本高；不直接輸出校準機率。線性 SVM 可用更高效的優化方法，複雜度不能一概而論。

(4) K-Nearest Neighbour (KNN)

定義：在特徵空間中找最近的 $k$ 個訓練樣本，按它們的多數類分類。
"最近"的定義可變：歐氏距離、餘弦距離（文字常用，因為只看方向不看長度）。
Pro：無需訓練（lazy learning）、天然多分類、決策邊界可高度非線性、易實作。
Con：預測時要算全部距離，推論慢、佔記憶體；對特徵縮放和距離度量極敏感；高維下距離失效（維度災難）；類別不平衡時多數類佔優。

(5) Decision Tree

定義：建構一棵樹，內部節點是對單一特徵的測試，葉子是最終類別；依資訊增益、Gini 不純度等準則貪心選擇分裂。
Pro：可解釋（規則可讀）、無需特徵縮放、能處理非線性與特徵互動、訓練快。
Con：極易過擬合（需剪枝/限制深度）；貪心分裂只是局部最佳；對資料擾動不穩定（變異數大）；偏向取值多的特徵。

(6) Random Forest

定義：集成式分類器，由多棵在不同訓練子集（bootstrap）和不同特徵子集上訓練出的決策樹組成，最終結果由多數投票決定。
Pro：顯著降低變異數、抗過擬合、通常對雜訊較穩健、可給出特徵重要性；仍需依任務調整樹深、葉節點大小等參數，缺失值支援取決於實作。
Con：可解釋性下降（不再是一棵可讀的樹）；模型體積大、推論比單樹慢；對高維稀疏文字不如線性模型高效。

(7) Neural Network

定義：互連的節點集合，通常分層排列；輸入層（特徵）、輸出層（類別機率）、若干隱藏層；每個節點對上一層輸入做線性加權，再透過活化函數傳給下一層。
Pro：能自動學特徵表示、表達能力強、可端到端訓練、可擴展到大量資料與預訓練。
Con：需要大量資料與算力、超參數多、可解釋性差、易過擬合（需正則/dropout）、少量資料上不一定優於線性模型。

5.6 超參數調優與評估

Hold-out（留出法）：把資料分成 train / dev（validation）/ test。用 dev 選超參數，test 只用於最終報告一次。

混淆矩陣（二分類範例）

	Classified As A	Classified As B
True A	79 (TP)	13 (FN)
True B	8 (FP)	10 (TN)

指標計算

Accuracy 準確率

\text{Accuracy} = \frac{TP + TN}{N} = \frac{79+10}{110} = 0.809

Precision 精確率（查準）：預測為正的裡面有多少真的為正

P = \frac{TP}{TP + FP} = \frac{79}{79+8} = 0.908

Recall 召回率（查全）：真正為正的裡面有多少被找出來

R = \frac{TP}{TP + FN} = \frac{79}{79+13} = 0.859

F1-Score：精確率與召回率的調和平均

F_1 = \frac{2PR}{P+R} = \frac{2 \times 0.908 \times 0.859}{0.908 + 0.859} = 0.883

為什麼用調和平均而不是算術平均？因為調和平均會被較小的一方"拉低"——只有當 P 和 R 都高時 F1 才高，避免"只召回不精確"或"只精確不召回"拿高分。

多分類指標

指標	做法	特點
Macro-average	先對每個類別分別算 P/R/F1，再對類別取算術平均	每個類別同等權重，少數類影響被放大，能暴露長尾表現差
Micro-average	把所有類別的 TP/FP/FN 彙總後再算一次 P/R/F1	每個樣本同等權重，大類主導；單標籤多分類時 micro-F1 = accuracy

6. 詞性標註 POS Tagging

6.1 什麼是 POS

定義：給句子中每個詞標註其文法類別（詞性）。

例子：Janet/NNP will/MD back/VB the/DT bill/NN

注意 back 在這裡是動詞（支持），不是名詞/副詞——取決於上下文。

應用：

Constituency parsing（成分句法分析）的前置：知道詞性才能建構短語結構。
Information extraction（資訊抽取）的前置：辨識實體、關係時依賴詞性（如只抽 NN/NNP 短語）。
作為特徵：給其他任務（NER、情感、翻譯）提供語言學特徵。
語音合成（決定發音/重音）、詞典編纂、文字校對。

6.2 詞性分類

開放類（Open class）：可隨時添加新詞/淘汰舊詞

大類	細分
Nouns 名詞	Proper 專有（Melbourne）／Common 普通；Common 再分 Mass 不可數（water）／Count 可數（chair）
Lexical verbs 實義動詞	可有豐富的屈折變化（sing/sang/sung）；依用法區分及物/不及物
Adjectives 形容詞	Gradable 可分級（very tall）／Non-gradable 不可分級（dead）
Adverbs 副詞	Locative 處所（here, there）／Degree 程度（very, extremely）

封閉類（Closed class）：相對固定，不易增減

Preposition 介系詞（of, in, on）
Particles 小品詞（up, off，如 give up）
Determiners 限定詞（the, a, this）
Pronouns 代詞（he, they, who）
Conjunctions 連詞（and, but, because）
Auxiliary / Modal Verbs 助動詞與情態動詞（be, have, do, can, must, should；具體歸類依標籤體系）

6.3 挑戰：歧義（Ambiguity）

同一個詞形可以是多個詞性，且分布極不均衡：

back：名詞（背部）/ 動詞（支持）/ 副詞（向後）/ 形容詞
flies：名詞複數（蒼蠅）/ 動詞三單（飛）
like：介系詞（像）/ 動詞（喜歡）

一個簡單基線是：為每個詞選擇訓練集中最常見的詞性。它能利用詞性分布的不均衡，但無法根據當前上下文消歧；準確率取決於語料和未登錄詞的處理方式。

6.4 POS Tagsets 標籤集

標籤集	標籤數	特點
Brown	87	最早的語料庫標籤集之一，粒度細
Penn Treebank (PTB)	45	NLP 中最常用，含 NN, NNS, NNP, VB, VBD, VBG, JJ, RB, IN, DT, MD, CC, PRP…
CLAWS5 / BNC	61	CLAWS 的一個版本；不同版本的標籤數不同
早期 Universal Tagset	12	NOUN, VERB, ADJ, ADV, PRON, DET, ADP, NUM, CONJ, PRT, ., X；不要與 Universal Dependencies 的 17 類 UPOS 混淆

經典歧義範例（Penn Treebank 標註）

TEXT

Time  flies like an arrow
Time/NN  flies/VBZ  like/IN  an/DT  arrow/NN

Fruit flies like a banana
Fruit/NN  flies/NNS  like/VBP  a/DT  banana/NN

同一個 flies：第一句是動詞（時間飛逝），第二句是名詞（果蠅）。只能靠上下文判斷。

7. 隱藏式馬可夫模型 HMM

7.1 引入：為什麼需要 HMM

任務：POS tagging——給整個詞序列 $W = w_1 \dots w_n$ 找最佳標籤序列 $T = t_1 \dots t_n$ 。

已有方法的問題：逐詞獨立預測無法利用標籤之間的依賴；如果改成依賴前面預測標籤的貪心分類器，又可能出現錯誤傳播（error propagation），前一個標籤的錯誤會影響後面。

新想法：把整個句子丟給模型，讓它生成整條 tag 序列。

新問題：句子長度不固定；所有 tag 組合數是 $\vert T\vert ^n$ ，指數級，無法枚舉。

解決辦法：找一個模型，以詞為單位建模，但在學習與預測時把整句當作一個整體——這叫 sequence labelling，也叫 structured prediction。

HMM 的運作方式：給定句子（詞序列），在所有可能的 tag 序列中找機率最大的那一條。

優勢：

無需人工設計規則（資料驅動）
全域考慮最佳 tag 序列，而非貪心逐詞
可以是 data-informed（從標註語料學參數）

7.2 公式

\hat{T} = \arg\max_{T} P(T \mid W) = \arg\max_{T} \frac{P(W \mid T)\,P(T)}{P(W)} = \arg\max_{T} P(W \mid T)\,P(T)

（ $P(W)$ 與 $T$ 無關，可忽略——這就是 Bayes 法則去掉分母）

圖 7-1　HMM 的機率圖模型：實線為狀態轉移 $P(t_i\mid t_{i-1})$ （矩陣 A），虛線為發射 $P(w_i\mid t_i)$ （矩陣 O）。

7.3 兩個假設

假設	內容	作用
Output independence（輸出獨立）	第 $i$ 個詞只依賴第 $i$ 個 tag，與其他詞、其他 tag 無關： $P(W\mid T)=\prod_i P(w_i\mid t_i)$	把"整句給定標籤"分解為逐詞乘積
Markov assumption（馬可夫）	當前 tag 只與前一個 tag 有關： $P(T)=\prod_i P(t_i \mid t_{i-1})$	把標籤序列的機率分解為一階轉移乘積

於是：

\hat{T} = \arg\max_{T} \prod_{i=1}^{n} \underbrace{P(w_i \mid t_i)}_{\text{emission}} \cdot \underbrace{P(t_i \mid t_{i-1})}_{\text{transition}}

這也解釋了 HMM 是一個**生成式（generative）**模型：它建模聯合機率 $P(W,T) = P(T)P(W\mid T)$ 。

7.4 訓練：算兩個機率表

參數	名稱	含義
$P(w_i \mid t_i)$	Emission（發射/觀測）機率 O	某個 tag 生成某個詞的機率
$P(t_i \mid t_{i-1})$	Transition（轉移）機率 A	前一個 tag 後面接某個 tag 的機率

怎麼算：仍是最大概似估計（MLE），即數數：

P(w_i \mid t_i) = \frac{\text{Count}(w_i, t_i)}{\text{Count}(t_i)}, \qquad P(t_i \mid t_{i-1}) = \frac{\text{Count}(t_{i-1}, t_i)}{\text{Count}(t_{i-1})}

第一個 tag 的機率怎麼辦？在每句之前加一個特殊起始符號 <s>，於是第一項就是 $P(t_1 \mid \text{<s>})$ ：

P(t_1 \mid \text{<s>}) = \frac{\text{Count}(\text{<s>}, t_1)}{\text{Count}(\text{<s>})}

句尾同理加 </s>，讓 $P(\text{</s>} \mid t_n)$ 也成為一個可學的轉移。前面的乘積為簡潔省略了這個句尾因子；完整路徑機率應再乘上它。

沒見過的詞怎麼辦？仍用平滑（第 4 節）：對 emission 表加 k / 加 1；或用 <UNK> 把低頻詞折疊，讓 <UNK> 的發射機率由所有低頻詞共享。

7.5 預測

給定訓練好的 HMM（兩張表：轉移矩陣 A、發射矩陣 O），預測輸入句子的 tag 序列。

核心思路：取所有 tag 組合中聯合機率最高的那一條：

\hat{t} = \arg\max_{t} P(W \mid t)\,P(t) = \arg\max_{t} \prod_{i=1}^{n} P(w_i \mid t_i)\,P(t_i \mid t_{i-1})

為什麼不能一個詞一個詞地預測？（貪心解碼的缺陷）

逐詞取 argmax 是局部最佳：當前詞最佳的 tag 可能讓下一個詞的最佳 tag 機率極低；
整句最佳是一個全域問題，需要同時權衡前後；
但枚舉 $\vert T\vert ^n$ 不可行 → 用 Viterbi 動態規劃求全域最佳；標籤集大小固定時，執行時間隨句長線性增長。

7.6 生成式 vs 判別式

維度	Generative（HMM）	Discriminative（CRF / 分類器）
建模對象	聯合機率 $P(X, Y)$	條件機率 $P(Y \mid X)$ （或 $P(T\mid W)$ ）
典型用途	可用於生成語言；HMM 也能做無監督學習	分類、預測、序列標註
訓練方式	通常（半）監督，也可 EM 無監督	通常是監督學習
特徵	只能使用觀測本身的發射機率，特徵受限	可用任意豐富特徵（前後綴、詞形、上下文詞、外部詞典…）
資料量	簡單的結構假設可能有利於少量資料學習	資料和特徵充分時通常能取得更好的預測效果，仍取決於任務與模型
代表	Naïve Bayes、HMM；神經語言模型也可作生成式建模	邏輯迴歸、CRF、SVM、用於分類的神經網路

判別式模型直接優化"給定輸入判斷輸出"，不需要顯式建模輸入分布 $P(W)$ ，可以把重點放在預測任務上；是否更好仍由任務、資料和模型共同決定。

8. Viterbi 演算法

8.1 核心思想

不要只保留"當前詞的最佳標籤"，而是保留"每個可能標籤下的最佳路徑得分"，並在處理下一個詞時考慮所有組合。

即：對每個位置 $t$ 和每個標籤 $j$ ，記錄以 $j$ 結尾的最佳路徑的累計得分 $\delta_t(j)$ 及其回溯指標 $\psi_t(j)$ 。

8.2 遞推公式

\delta_1(j) = P(t_1 = j \mid \text{<s>}) \cdot P(w_1 \mid j)

\delta_t(j) = \max_{i \in T}\Big[\delta_{t-1}(i)\cdot P(j \mid i)\Big]\cdot P(w_t \mid j)

\psi_t(j) = \arg\max_{i \in T}\Big[\delta_{t-1}(i)\cdot P(j\mid i)\Big]

終止：

\hat{t}_n = \arg\max_{j}\big[\delta_n(j)\,P(\text{</s>}\mid j)\big], \qquad \hat{t}_{t} = \psi_{t+1}(\hat{t}_{t+1}) \ \text{（回溯）}

如果模型沒有顯式句尾狀態，終止時直接比較 $\delta_n(j)$ 即可；下面兩個範例均採用這一簡化。

直覺範例：Can Play

對 can，分別記錄 MD（情態動詞）的得分、NN（名詞）的得分；
處理 play 時，對每個候選標籤（VB、NN）：
- 結合"can 各標籤的得分 × 轉移機率 × 發射機率"；
- 找出整體機率最大的路徑；
最後比較句末各標籤的累計得分，取最大者並回溯出整條路徑。

8.3 例子 1：Janet will back the bill

轉移矩陣（Transition Matrix，節選，列為條件事件 $P(\cdot\mid \text{row})$ ）

	NNP	MD	VB	JJ	NN	RB	DT
<s>	0.2767	0.0006	0.0031	0.0453	0.0449	0.0510	0.2026
NNP	0.3777	0.0110	0.0009	0.0084	0.0584	0.0090	0.0025
MD	0.0008	0.0002	0.7968	0.0005	0.0008	0.1698	0.0041
VB	0.0322	0.0005	0.0050	0.0837	0.0615	0.0514	0.2231
JJ	0.0366	0.0004	0.0001	0.0733	0.4509	0.0036	0.0036
NN	0.0096	0.0176	0.0014	0.0086	0.1216	0.0177	0.0068
RB	0.0068	0.0102	0.1011	0.1012	0.0120	0.0728	0.0479
DT	0.1147	0.0021	0.0002	0.2157	0.4744	0.0102	0.0017

（資料來自 Jurafsky 與 Martin 的 Speech and Language Processing 第 18 章 Figure 18.12，基於 WSJ 語料、未平滑。這裡只列出部分標籤，所以表中每列之和不必等於 1；完整轉移分布才會正規化。）

發射矩陣（Emission Matrix，Speech and Language Processing，Figure 18.13）

	Janet	will	back	the	bill
NNP	0.000032	0	0	0.000048	0
MD	0	0.308431	0	0	0
VB	0	0.000028	0.000672	0	0.000028
JJ	0	0	0.000340	0	0
NN	0	0.000200	0.000223	0	0.002337
RB	0	0	0.010446	0	0
DT	0	0	0	0.506099	0

演算法流程：建一個 $\vert T\vert \times n$ 的格子（trellis），逐欄填 $\delta$ ，每格記下「從上一欄哪個標籤來」，最後從最末欄的最大值回溯。

8.4 例子 2：they fish（可手算驗證）

這是僅用於演示動態規劃的兩狀態玩具模型，數值人為設定；N、V 是狀態標籤，不應據此判斷真實英語中的 they 可以作動詞。

發射機率

	they	fish
N	0.7	0.3
V	0.4	0.6

轉移機率

	N	V
<s>	0.6	0.4
N	0.8	0.2
V	0.7	0.3

圖 8-1　they fish 的 Viterbi 網格：每格只保留「以該標籤結尾的最佳前綴得分」 $\delta$ ，紅色為回溯出的最佳路徑 they/N → fish/N。

枚舉全部 4 條路徑

路徑	計算	機率
N N	$0.6\times0.7 \times 0.8\times0.3$	0.1008 ✅ 最佳
N V	$0.6\times0.7 \times 0.2\times0.6$	0.0504
V N	$0.4\times0.4 \times 0.7\times0.3$	0.0336
V V	$0.4\times0.4 \times 0.3\times0.6$	0.0288

結論：they/N fish/N。只比較 fish 的發射機率，會看到 $P(\text{fish}\mid V)=0.6$ 大於 $P(\text{fish}\mid N)=0.3$ ；加入轉移機率後，最佳路徑卻以 N 結尾。發射機率不是標籤後驗，不能直接據此選標籤。這個例子展示了轉移資訊的作用，但不構成「逐步考慮轉移的貪心解碼一定失敗」的反例。

8.5 演算法特性

特性	說明
時間複雜度	$O(T^2 N)$ ： $T$ = 標籤集大小， $N$ = 序列長度。每個位置 $N$ ，每個標籤 $T$ ，每個標籤要與前一位置所有 $T$ 個標籤比較
空間複雜度	只求最佳得分時可輪替保留兩欄，空間為 $O(T)$ ；要恢復整條路徑，則需保存 $O(TN)$ 個回溯指標
為什麼正確（why it works）	最佳子結構：到位置 $t$ 標籤 $j$ 的最佳路徑，其前綴必然是到位置 $t-1$ 某標籤的最佳路徑（否則替換前綴可得更佳解）；無後效性：給定當前標籤，未來與更早的歷史無關（馬可夫性）。因此可以只保留每格的"最佳前綴得分"，安全地丟棄次佳路徑
數值下溢	機率連乘很快變成 0，實際實作全部用 log 機率（乘法變加法， $O(T^2N)$ 不變）
更高階變體	用 tag trigram（二階 HMM）： $P(t_i \mid t_{i-2}, t_{i-1})$ ，配合 interpolation 平滑；複雜度升為 $O(T^3 N)$