Ngrams 语言模型与拼写校正

在上一篇文章中，我翻译了 Peter Norvig 的 How to Write a Spelling Corrector，其中的拼写校正器主要依赖编辑距离和词频，并不利用上下文信息，因此在 real-word error 这类问题上效果有限。本文继续沿着这个话题往前走，介绍 NLP 中最经典的一类语言模型：Ngrams 模型，以及如何把它接入一个基于编辑距离的拼写校正器中，使校正器具备感知上下文 (context-sensitive) 的能力。

---

语言模型

语言模型 (Language Model, LM) 解决的是一个基础问题：给定一个词序列，如何衡量它是否像一句自然语言。

更形式化一点，给定一个词序列：

w_1, w_2, ..., w_n

语言模型希望估计这个序列出现的概率：

P(w_1, w_2, ..., w_n)

如果模型认为句子 A 的概率高于句子 B，那么我们就说 A 在模型看来更自然，也更符合训练语料中的语言分布。

比如：

1. I love natural language processing.
2. Language natural processing love I.

对于英语来说，第一个句子的概率显然应该高于第二个句子。语言模型的作用，就是把这种“通顺度”转化为一个可计算的分数。

根据概率论中的链式法则，一个句子的概率可以分解为：

P(w_1, w_2, ..., w_n) = ∏_{i=1}^{n} P(w_i | w_1, ..., w_{i-1})

例如：

P(I love natural language processing)
= P(I)
  P(love | I)
  P(natural | I love)
  P(language | I love natural)
  P(processing | I love natural language)

这个公式在数学上完全正确，但直接用于工程实现并不现实。因为我们几乎不可能从有限语料中，准确估计“任意长历史条件下下一个词的概率”。

假设我们要估计：

P(processing | I love natural language)

前者还可以靠统计估计；但如果我们要估计：

P(processing | Yesterday in the lab I suddenly realized that I love natural language)

这样的长上下文在语料中很可能根本没有出现过。于是语言建模里就有一个经典矛盾：

• 上下文越长，信息越充分
• 模型越复杂，数据稀疏问题越严重

Ngrams 模型就是这个矛盾下的一个经典工程折中。

---

Ngrams 语言模型

Ngrams 模型的核心思想是一个很强但很实用的假设：一个词的出现只依赖于前面有限个词，而不是依赖于全部历史。

如果只看前面 1 个词，就是 bigram 模型：

P(w_i | w_1, ..., w_{i-1}) ≈ P(w_i | w_{i-1})

如果只看前面 2 个词，就是 trigram 模型：

P(w_i | w_1, ..., w_{i-1}) ≈ P(w_i | w_{i-2}, w_{i-1})

更一般地，N-gram 模型假设：

P(w_i | w_1, ..., w_{i-1}) ≈ P(w_i | w_{i-n+1}, ..., w_{i-1})

也就是说，在 n-gram 模型中，当前词的条件概率只依赖于前面的 n - 1 个词。

于是整句概率可以近似写成：

P(w_1, ..., w_n) ≈ ∏_{i=1}^{n} P(w_i | w_{i-n+1}, ..., w_{i-1})

一个简单例子

假设我们有下面两个句子：

1. I love natural language processing
2. I love natural processing language

如果使用 bigram 模型，这两个句子的分数分别由以下概率相乘得到：

P(I love natural language processing) ∝
P(I)
P(love | I)
P(natural | love)
P(language | natural)
P(processing | language)

P(I love natural processing language) ∝
P(I)
P(love | I)
P(natural | love)
P(processing | natural)
P(language | processing)

这两个句子前三项都一样，差别主要出现在后两个 bigram。由于在语料中：

P(language | natural) 和 P(processing | language)

往往都会显著高于：

P(processing | natural) 和 P(language | processing)

因此模型会更偏好 “I love natural language processing”。

参数估计

Ngrams 模型通常直接用最大似然估计 (Maximum Likelihood Estimation, MLE) 来统计条件概率。

比如在 bigram 模型中：

P(w_i | w_{i-1}) = Count(w_{i-1}, w_i) / Count(w_{i-1})

在 trigram 模型中：

P(w_i | w_{i-2}, w_{i-1}) = Count(w_{i-2}, w_{i-1}, w_i) / Count(w_{i-2}, w_{i-1})

这背后的直觉很直接：某个词在某个上下文中出现得越多，它在这个上下文下的条件概率就越高。

但问题也很直接。如果某个 ngram 在训练语料中从来没有出现过，那么它的概率就会被估计为 0。这样一来，只要句子里包含一个未见过的 ngram，整句概率就会直接变成 0。

所以，Ngrams 模型几乎总是要和“平滑算法”一起使用。

为什么 Ngrams 适合做拼写校正

在继续往下之前，先简单回顾一下上一篇文章里的编辑距离 (edit distance)。

对于一个输入词，我们通常允许 4 类基础编辑操作：

• 删除一个字符
• 插入一个字符
• 替换一个字符
• 交换两个相邻字符

如果一个单词经过 1 次这样的编辑可以变成另一个单词，那么我们就说它们的编辑距离为 1。上一篇文章里的 edits1 和 edits2，本质上就是在为一个错误输入词生成“编辑距离为 1 或 2 的候选词集合”。

因此，一个基于编辑距离的拼写校正器通常包含两个阶段：

1. 候选生成：用编辑距离找出可能的修正词
2. 候选排序：从这些候选词中选出最合理的那个

上一篇文章主要解决的是第 1 步以及一个很简单的排序问题，也就是直接用词频排序；本文要做的事情，就是用 Ngrams 语言模型把第 2 步做得更好。

在拼写校正任务里，我们通常并不要求模型完整理解整句话的语义，只需要它回答一个更局部的问题：

在当前位置，哪个候选词与周围上下文的搭配最自然？

这恰好是 Ngrams 最擅长的事情。

例如下面这句话：

I filled out the form at home.

如果把 form 视为待修正词，那么编辑距离可能会生成这些候选项：

• form
• from
• found
• forum

其中 form 和 from 都是合法单词，单看词表和词频并不能可靠地区分它们；但如果看上下文，模型会发现：

• “filled out the form” 是高概率片段
• “at home” 也是高概率片段

而 “filled out the from at home”、”filled out the found at home” 这类组合都明显不自然。通过局部上下文打分，我们就可以把候选词排出一个更合理的顺序。

使用 SRILM 训练 Ngrams 语言模型

我当时使用的是 SRILM 来训练语言模型。虽然现在 KenLM 这类工具更常见，但 SRILM 仍然很适合理解 Ngrams 模型的训练流程，也足够支撑本文里的实验。

1. 语料预处理

训练语言模型首先需要一份尽可能干净的大规模文本语料。常见的预处理步骤包括：

1. 分句
2. 分词
3. 统一大小写（如果任务不关心大小写）
4. 清理异常符号
5. 在每个句子前后加入句子边界标记 <s> 和 </s>

例如：

<s> I love natural language processing </s>

句子边界标记非常重要，因为模型需要显式学习：

• 哪些词适合出现在句首
• 哪些词后面适合结束句子

2. 用 ngram-count 训练模型

假设预处理后的语料文件为 train.txt，训练一个 trigram 模型可以写成：

ngram-count -text train.txt -order 3 -lm lm.arpa

这条命令会：

• 读取 train.txt
• 统计 1-gram / 2-gram / 3-gram 的频次
• 生成一个 ARPA 格式的语言模型文件 lm.arpa

如果要训练一个带 Kneser-Ney 平滑的 5-gram 模型，可以写成：

ngram-count -text train.txt -order 5 -kndiscount -interpolate -lm lm.arpa

其中：

• -order 5 表示训练 5-gram
• -kndiscount 表示使用 Kneser-Ney discounting
• -interpolate 表示使用插值版本，而不是纯 backoff

对于实际工程任务，5-gram 是一个很常见的选择：上下文足够长，同时模型规模和效果通常也比较平衡。

3. 用 ngram 给句子打分

模型训练好之后，可以用下面的命令在测试集上计算 perplexity：

ngram -lm lm.arpa -ppl test.txt

如果只是想查看一个具体句子的概率分解，也可以这样：

ngram -lm lm.arpa -ppl sentence.txt -debug 2

-debug 2 会打印出每一步 ngram 命中的概率，调试时非常方便。

4. ARPA 文件里有什么

SRILM 默认输出 ARPA 格式模型。这个文件本质上是一个文本格式的概率表，里面保存了：

• 各阶 ngram 的数量
• 每个 ngram 的对数概率
• 对应的 backoff weight

例如你会看到类似下面的内容：

\1-grams:
-1.23    <s>   -0.45
-0.82    I     -0.37

对于拼写校正器来说，通常不需要自己解析这些细节，只需要把候选句子交给 SRILM 打分即可。

平滑算法与回退策略

数据稀疏问题

Ngrams 模型最大的工程问题就是数据稀疏 (data sparsity)。

语料再大，也不可能覆盖所有可能的词序列。特别是在 n 增大之后，绝大多数高阶 ngram 都会变成低频甚至未见事件。

例如语料里可能出现过：

• in the morning
• in the evening

但没有出现过：

• in the auditorium

如果直接使用 MLE，那么：

P(auditorium | in the) = 0

这显然不合理，因为 “in the auditorium” 完全可能出现在真实文本中。

平滑的作用

平滑 (smoothing) 的目的，就是把一部分概率质量从高频事件上拿出来，重新分配给低频事件和未见事件。

直观理解就是：

• 高频 ngram 依然应该高
• 低频 ngram 不能太自信
• 未见 ngram 也不能直接判为 0

最朴素的 Add-One smoothing 在语言模型里通常效果很差，因为它会给未见事件分配过多概率。更常见也更有效的方法包括：

• Good-Turing
• Katz Backoff
• Kneser-Ney
• Interpolated Kneser-Ney

其中 Kneser-Ney，尤其是插值版 Kneser-Ney，通常是传统 Ngrams 语言模型中效果最稳定的一类方法。

Backoff

回退 (backoff) 的思想非常直接：

• 如果高阶 ngram 可靠，就用高阶概率
• 如果高阶 ngram 不可靠或没见过，就退回到低阶概率

以 trigram 为例，要计算：

P(w_i | w_{i-2}, w_{i-1})

那么：

• 如果 (w_{i-2}, w_{i-1}, w_i) 出现过，就优先用 trigram
• 如果没出现过，就退回到 bigram P(w_i | w_{i-1})
• 如果 bigram 也不可靠，再退回到 unigram P(w_i)

这样即使高阶统计缺失，模型也不至于完全失效。

Interpolation

插值 (interpolation) 比 backoff 更平滑一些。它不是“高阶失败才退低阶”，而是把不同阶模型按权重混合起来：

P(w_i | w_{i-2}, w_{i-1}) =
λ_3 P_3(w_i | w_{i-2}, w_{i-1}) +
λ_2 P_2(w_i | w_{i-1}) +
λ_1 P_1(w_i)

这样做有几个直接的好处：

• 高阶模型利用更强的局部上下文
• 低阶模型提供稳健性
• 分数变化不会因为某个高阶统计太稀疏而剧烈抖动

如果只是想给拼写校正器接一个效果不错的传统语言模型，那么直接使用 interpolated Kneser-Ney 通常就够了。

---

感知上下文的拼写校正器

上一篇文章中的拼写校正器，本质上是在做下面这件事：

argmax_{c in candidates(word)} P(c)

也就是说，给定一个错别字，在候选词集合中选一个词频最高的词。

这种方法对非词错误 (non-word error) 很有效，比如：

• speling -> spelling
• peotry -> poetry

但它处理不了真实词错误 (real-word error)。例如下面这句话：

I study natural language process.

这里的 process 本身是合法单词，仅靠词表它不会被当成错误；但从上下文看，natural language processing 才是更合理的搭配。

如果把例子换成一个更典型的 non-word error：

I study natural language processsing.

这时编辑距离可以负责生成候选词，而语言模型可以利用上下文，判断 processing 比其他候选词更合理。换句话说，语言模型的价值在于它不只看“词像不像一个词”，还看“词放在这个上下文里是否合理”。

用语言模型给候选句子打分

做法很直接，就是把“给候选词打分”升级成“给候选句子打分”。

假设原句是：

I study natural language processsing.

对 processsing 生成候选词：

• processing
• processor
• processes

然后把它们放回原句：

1. I study natural language processing.
2. I study natural language processor.
3. I study natural language processes.

接着用语言模型分别计算这些候选句子的分数，选择分数最高的那个。形式上可以写成：

argmax_{c in candidates(x_i)} P(w_1, ..., w_{i-1}, c, w_{i+1}, ..., w_n)

如果还想把上一篇文章中的误差模型也考虑进来，可以写成：

score(c) = log P_LM(sentence(c)) + λ log P_channel(error | c)

其中：

• P_LM 是候选句子的语言模型概率
• P_channel 是误差模型，也就是“正确词 c 变成当前错误形式的概率”
• λ 是调节权重

如果没有真实的拼写错误日志，完全可以继续使用一个简单的启发式误差模型：

• 编辑距离 1 的候选词优先于编辑距离 2
• 在同一编辑距离下，用语言模型排序

在多数 baseline 系统里，这一步已经能明显提高效果。

一个简单实现流程

一个上下文敏感的拼写校正器，大致可以按下面的流程实现：

1. 对句子分词
2. 逐个扫描每个位置的词
3. 用编辑距离生成候选词集合
4. 过滤掉不在词表中的候选词
5. 把每个候选词替换回原句，构造候选句子
6. 用语言模型给候选句子打分
7. 选出分数最高的候选词

伪代码如下：

def correct_word_in_context(tokens, idx, candidate_words, lm):
    best_word = tokens[idx]
    best_score = float('-inf')

    for cand in candidate_words:
        new_tokens = tokens[:]
        new_tokens[idx] = cand
        sentence = ' '.join(new_tokens)
        score = lm.score(sentence)
        if score > best_score:
            best_score = score
            best_word = cand

    return best_word

如果你已经实现了上一篇文章中的 edits1、edits2 和 known，那么把 Ngrams 接进来并不复杂。核心变化只有一句话：

不要只给单词打分，要给单词所在的句子打分。

局部窗口优化

严格来说，每替换一个词都重算整句分数会比较慢。但由于 Ngrams 只依赖局部上下文，所以很多时候只需要重算受影响的局部片段。

例如在 trigram 模型下，替换第 i 个词，只会影响少量 trigram：

• (w_{i-2}, w_{i-1}, w_i)
• (w_{i-1}, w_i, w_{i+1})
• (w_i, w_{i+1}, w_{i+2})

因此完全可以只比较这些局部 ngram 的分数，而不必每次都重新计算整句得分。

这类方法的优缺点

优点：

• 实现简单
• 可解释性强
• 对局部搭配错误非常有效
• 不需要复杂模型也能达到不错效果

缺点：

• 很难建模长距离依赖
• 强依赖语料覆盖度
• 只能提供局部“通顺性”，不真正理解语义

尽管如此，在很多工程场景中，Ngrams 语言模型依然是一个很强的 baseline。尤其当你已经有了一个基于编辑距离的候选生成器时，用它来做 reranking，几乎是最自然的一步。

---

References

• How to Write a Spelling Corrector, Peter Norvig
• SRILM - The SRI Language Modeling Toolkit
• Speech and Language Processing, Dan Jurafsky and James H. Martin