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)$