Lecture 02: N-gram 语言模型
核心主题：数据分布与KL散度、N-gram MLE、平滑技术、Perplexity 评价指标
1. 语言模型的动机
语言模型的根本任务：为句子赋予概率。
应用场景：
- 语音识别：P("recognize speech") > P("wreck a nice beach")
- 机器翻译：选择更自然的翻译
- 拼写纠正：P("fifteen minutes") > P("fifteen minuets")
核心问题：给定一个句子 $w_1, w_2, \ldots, w_n$，如何计算 $p(w_1, w_2, \ldots, w_n)$？
2. 数据分布框架
2.1 问题设定
- 真实分布 $p_{\text{data}}$ 未知
- 我们只观测到语料（样本）：$D = \{w^{(i)}\}_{i=1}^N$，$w^{(i)} \sim p_{\text{data}}$ i.i.d.
- 目标：训练模型 $p_\theta$ 使得 $p_\theta \approx p_{\text{data}}$
2.2 训练目标：最小化 KL 散度
$$\theta^* = \arg\min_\theta \text{KL}(p_{\text{data}} \| p_\theta)$$
2.3 关键定理：KL 最小化 = 最大期望对数似然
定理：
$$\arg\min_\theta \text{KL}(p_{\text{data}}\|p_\theta) \Longleftrightarrow \arg\max_\theta \mathbb{E}_{w \sim p_{\text{data}}}[\log p_\theta(w)]$$
证明：
$$\text{KL}(p_{\text{data}}\|p_\theta) = \underbrace{\mathbb{E}[\log p_{\text{data}}(w)]}_{\text{关于}\theta\text{为常数}} - \mathbb{E}[\log p_\theta(w)]$$
第一项关于 $\theta$ 为常数，所以最小化 KL = 最大化 $\mathbb{E}[\log p_\theta(w)]$。
实践近似（蒙特卡洛）：
$$\max_\theta \frac{1}{N}\sum_{i=1}^N \log p_\theta(w^{(i)})$$
2.4 KL 散度性质
- 不对称：$D_{KL}(p\|q) \neq D_{KL}(q\|p)$
- 非负：$D_{KL}(p\|q) \geq 0$
- 等于零的条件：$D_{KL}(p\|q) = 0$ 当且仅当 $p = q$
3. N-gram 语言模型
3.1 形式化定义
词汇表：$V = \{v_1, v_2, \ldots, v_{|V|}\}$
特殊符号：$v_0 = \text{BOS}$（句首），$v_{|V|+1} = \text{EOS}$（句尾）
语言模型定义：概率分布 $p(w_{1:t})$，满足：
- $p(w_{1:t}) \geq 0$
- $\sum_{w_{1:t}} p(w_{1:t}) = 1$
链式法则分解：
$$p(w_{1:t}) = \prod_{i=1}^t p(w_i \mid w_{1:i-1})$$
3.2 N-gram 马尔可夫假设
$$p(w_i \mid w_{1:i-1}) \approx p(w_i \mid w_{i-N+1:i-1})$$
| N | 名称 | 模型 |
|---|---|---|
| 1 | Unigram | $p(w_{1:t}) = \prod_i q(w_i)$ |
| 2 | Bigram | $p(w_{1:t}) = \prod_i q(w_i \mid w_{i-1})$ |
| 3 | Trigram | $p(w_{1:t}) = \prod_i q(w_i \mid w_{i-2}, w_{i-1})$ |
参数量：$\sim |V|^N$（例：|V|=10000, N=3 → 约 $10^{12}$ 参数）
3.3 为什么需要 EOS
句子长度 $t$ 本身是随机变量。EOS 标记使模型能学到何时终止生成，保证所有长度的句子概率之和为 1。
4. 最大似然估计 (MLE)
4.1 Unigram MLE
$$\hat{\theta}_i = \frac{C(v_i)}{\sum_j C(v_j)} = \frac{\text{该词出现次数}}{\text{总token数}}$$
推导：使用 Lagrange 乘子法，约束 $\sum_i \theta_i = 1$
4.2 Bigram MLE
$$q(v_j \mid v_i) = \frac{C(v_i, v_j)}{\sum_k C(v_i, v_k)} = \frac{C(v_i, v_j)}{C(v_i)}$$
4.3 一般 N-gram MLE
通用公式：
$$q(x_N \mid x_{1:N-1}) = \frac{C(x_{1:N})}{C(x_{1:N-1})}$$
本质：相对频率估计 — N-gram 出现次数除以前缀出现次数。
5. 平滑技术
5.1 稀疏性问题
问题：即使在 3800 万词的语料中，1/3 的测试 trigram 从未出现。MLE 对未见 N-gram 赋予零概率 → 灾难性后果！
5.2 Add-δ (Laplace) 平滑
$$q_{\text{Add}}(x_N \mid x_{1:N-1}) = \frac{\delta + C(x_{1:N})}{\delta(|V|+1) + C(x_{1:N-1})}$$
$\delta = 1$：Laplace 平滑（加一平滑）。简单但通常效果不佳，分配给未见事件的概率过多。
5.3 线性插值
混合各阶估计：
$$q_{\text{Int}}(x_3|x_{1:2}) = \lambda_1 \cdot q_{\text{ML}}(x_3) + \lambda_2 \cdot q_{\text{ML}}(x_3|x_2) + \lambda_3 \cdot q_{\text{ML}}(x_3|x_{1:2})$$
约束 $\lambda_1 + \lambda_2 + \lambda_3 = 1$（从验证集学习最优权重）
5.4 Katz 回退 (Discounting)
$$q_{\text{Katz}}(x_2|x_1) = \begin{cases} \frac{C^*(x_1,x_2)}{C(x_1)} & \text{if } C(x_1,x_2) > 0 \\ \alpha(x_1) \cdot \frac{q_{\text{ML}}(x_2)}{\sum_{x_2 \in B(x_1)} q_{\text{ML}}(x_2)} & \text{otherwise} \end{cases}$$
其中 $C^* = C - \beta$（折扣计数，通常 $\beta = 0.5$）。对见过的 N-gram 打折，将省下的概率质量分配给未见的 N-gram。
5.5 Kneser-Ney 平滑 SOTA
Kneser-Ney 公式：
$$q_{\text{KN}}(x_2|x_1) = \frac{\max\{C(x_1 x_2) - \delta, 0\}}{C(x_1)} + \lambda_{x_1} \cdot q_{\text{KN}}(x_2)$$
续接概率（Continuation Probability）：词 $x_2$ 在多少不同上下文中出现：
$$q_{\text{KN}}(x_2) = \frac{|\{x: C(x, x_2) > 0\}|}{|\{(a,b): C(a,b) > 0\}|}$$
核心思想：低阶分布不应该基于词频，而应基于"该词能在多少不同上下文中出现"。例如 "Francisco" 频率很高，但几乎只跟在 "San" 后面 → 续接概率低。
Modified Kneser-Ney 是 N-gram 的 SOTA，实现在 KenLM 中。
5.6 Stupid Back-off
非正式概率分布，简单高效（适用于大规模 Web 数据）：
$$S(x_N|x_{1:N-1}) = \begin{cases} \frac{C(x_{1:N})}{C(x_{1:N-1})} & \text{if } C(x_{1:N}) > 0 \\ 0.4 \cdot S(x_N|x_{2:N-1}) & \text{otherwise} \end{cases}$$
不保证概率和为 1，但在海量数据上效果与 KN 接近。
5.7 Good-Turing 平滑
- $N_r$ = 恰好出现 $r$ 次的类型数（frequency of frequency）
- 调整计数：$r^* = (r+1) \cdot N_{r+1} / N_r$
- Good-Turing 概率：$P^*_{GT}(w) = r^* / N$
直觉：用"出现 $r+1$ 次的词有多少"来估计"出现 $r$ 次的词的真实概率"。
6. Perplexity (困惑度)
6.1 定义
设测试集 $s_1, \ldots, s_m$ 总词数 $M = \sum_i |s_i|$：
Perplexity 公式：
$$\ell = \frac{1}{M} \sum_{i=1}^m \log_2 p(s_i)$$
$$\text{PPL}(s_{1:m}) = 2^{-\ell}$$
6.2 直觉：平均分支因子 (Average Branching Factor)
"模型平均需要从多少个候选中随机选择才能选对正确词"
- PPL 越低 = 模型越好
- 词表 |V| 上的均匀模型：PPL = |V|
- |V| = 1,000,000 且 PPL = 30 → 模型有效搜索空间仅 30 个候选
6.3 与熵/交叉熵的关系
$$H(p,q) = H(p) + D_{KL}(p\|q) \geq H(p)$$
$$\text{PPL} = 2^{H(p,q)}$$
交叉熵是真实熵的上界，PPL 是其指数形式。模型越接近真实分布，交叉熵越接近真实熵，PPL 越低。
6.4 实验结果
GPT-2 on WikiText-2: PPL = 24.38
KenLM N-gram on WikiText-103 (Modified KN smoothing):
| 模型 | PPL |
|---|---|
| 2-gram | 518.82 |
| 3-gram | 347.78 |
| 4-gram | 302.27 |
对比结论：GPT-2 (PPL~24) 远优于 N-gram (PPL~300+)，体现了神经语言模型相对于传统统计方法的巨大优势。
7. KenLM 实战流程
训练 N-gram 模型：
# 训练不同阶的 N-gram 模型 (Modified Kneser-Ney smoothing)
lmplz -o 2 --text train_bpe.txt --arpa wikitext103_o2.arpa
lmplz -o 3 --text train_bpe.txt --arpa wikitext103_o3.arpa
lmplz -o 4 --text train_bpe.txt --arpa wikitext103_o4.arpaPython 使用：
import kenlm
# 加载模型
model = kenlm.Model("wikitext103_o3.arpa")
# 计算句子的 log10 概率
sentence = "this is a sentence"
log10_prob = model.score(sentence, bos=True, eos=True)
print(f"log10 P('{sentence}') = {log10_prob:.4f}")
# 逐词概率
for i, (prob, length, oov) in enumerate(model.full_scores(sentence)):
print(f" word {i}: log10_prob={prob:.4f}, ngram_length={length}, oov={oov}")
# 计算 perplexity
import math
words = sentence.split()
ppl = 10 ** (-log10_prob / (len(words) + 1)) # +1 for EOS
print(f"PPL = {ppl:.2f}")8. N-gram 文本生成示例
从 N-gram 模型生成文本（质量较差）：
| 模型 | 生成示例 | 评价 |
|---|---|---|
| 2-gram | "He is] = Week 15 pm guitar..." | 完全不连贯 |
| 3-gram | "He is the angle bis: 23 women..." | 略有改善但仍很差 |
| 4-gram | （较连贯的短语片段） | 局部有意义但整体无逻辑 |
结论：N-gram 模型无法生成连贯的长文本。固定上下文窗口 (N-1 个词) 严重限制了表达能力，无法捕捉长距离依赖关系。这正是后续神经语言模型 (L04-L06) 要解决的核心问题。
核心要点总结
- KL 最小化 = MLE：最大化对数似然等价于最小化与真实分布的 KL 散度
- N-gram MLE 就是计数：相对频率 $C(x_{1:N})/C(x_{1:N-1})$
- 平滑必不可少：即使 3800 万词语料，1/3 测试 trigram 从未出现
- Kneser-Ney 是 N-gram SOTA：Modified KN (KenLM) 是实用金标准
- 更高 N 通常更好但收益递减：2→3→4-gram PPL: 518→348→302
- PPL 是语言模型的标准评价指标：越低越好，$\text{PPL} = 2^{H(p,q)}$