D.3 噪声信道模型：最新方法

当前先进的噪声信道拼写纠错实现，对前面介绍的简单模型作了多项扩展。

第一，现代系统不再假设输入句子只有一个错误，而是逐词扫描输入，用噪声信道分别作出决定。然而，若只是对每个词运行基本噪声信道系统，很容易过度纠正，把正确但罕见的词——例如人名——替换成更常见的词（Whitelaw et al., 2009；Wilcox-O’Hearn, 2014）。因此，现代算法还要判断某个实词是否真的需要纠正。例如 Google 的系统（Whitelaw et al., 2009）使用黑名单，禁止修改数字、标点和单字母词等词元。

系统在决定是否信任候选纠正时也更加谨慎。它不会仅因为候选 $w$ 的 $P(w\mid x)$ 比原词本身更高就采用纠正，而是要求概率差足够大；只有满足下式才选择最佳纠正 $w$ ：

\log P(w\mid x)-\log P(x\mid x)>\theta

根据具体应用，拼写检查器可以自动纠正，也可以只标记错误并给出建议。该决定经常由另一个分类器完成；分类器利用候选之间的对数概率差等特征，判断最佳候选是否足够可靠。

现代系统还使用比早期系统大得多的词典。Ahmad and Kondrak（2005）发现，一个含 10 万词的 UNIX 词典只覆盖网络查询语料中 73% 的词类型，漏掉 pics、multiplayer、google、xbox、clipart 和 mallorca 等词。因此，现代系统经常根据 Google n-gram 语料等超大一元词列表自动构建更大的词典。Whitelaw 等人（2009）使用了大型网页样本中频率最高的一千万种词。由于该列表也会包含大量错误拼写，系统需要更复杂的错误模型。

真实词通常比错误拼写更频繁，这一事实可用于候选建议：先构建具有相似上下文的词及拼写变体集合，按频率排序，把最高频变体视为来源，再从差异中学习错误模型。数据可以来自网页文本（Whitelaw et al., 2009）或查询日志（Cucerzan and Brill, 2004）。用户拒绝纠正时，系统还可以自动把词加入词典；手机系统也可以自动从用户的通讯录或日历中加入词语。

改变先验与似然的组合方式，也能改善噪声信道模型。标准模型直接把二者相乘，但两种概率的量级可能并不相称；语言模型或信道模型的取值范围可能很不一样，某些任务或数据集也可能使我们更信任其中一个模型。因此，使用加权组合，把一个因子提高到 $\lambda$ 次幂：

\hat w=\arg\max_{w\in V}P(x\mid w)P(w)^\lambda\tag{D.9}

在对数空间中：

\hat w=\arg\max_{w\in V}\left[\log P(x\mid w)+\lambda\log P(w)\right]\tag{D.10}

参数 $\lambda$ 在开发集上调节。

最后，若只想对特定混淆集进行实词纠错，例如 peace/piece、affect/effect、weather/whether，乃至 among/between 一类语法纠错，可以训练监督分类器，利用多种上下文特征在两个候选间选择。对这些特定集合，分类器能够取得很高准确率，尤其是在采用大规模网络统计特征时（Golding and Roth, 1999；Lapata and Keller, 2004；Bergsma et al., 2009, 2010）。

D.3.1 改进的编辑模型：分区与发音¶

其他近期研究聚焦于改进信道模型 $P(t\mid c)$ 。一项重要扩展是计算多字母变换的概率。Brill and Moore（2000）提出一种信道模型：打字者先选择一个词，再选择该词字母的某种分区，最后逐个键入各分区，并可能产生错误。

例如，一个人选择词 physical，再把它分成若干相邻片段。生成错误字符串 fisikle 时，可以对应到 $ph\to f$ 、 $y\to i$ 、 $s\to s$ 、 $i\to i$ 、 $c\to k$ 、 $al\to le$ 等变换，其概率是各片段变换概率的乘积。与 Damerau–Levenshtein 编辑距离不同，Brill–Moore 信道模型可以表示 $P(f\mid ph)$ 、 $P(le\mid al)$ 或高概率的 $P(ent\mid ant)$ 等多字母编辑；每次编辑还以它在词中的位置——开头、中间或末尾——为条件。

形式上，令 $R$ 是把错误字符串 $x$ 划分为相邻、可以为空的子串所得分区， $T$ 是候选字符串的分区。Brill and Moore（2000）用单个最佳分区的概率近似总似然 $P(x\mid w)$ ，例如 $P(\text{fisikle}\mid\text{physical})$ ：

P(x\mid w)\approx\max_{\substack{R,T\\|T|=|R|}}\sum_{i=1}^{|R|}P(T_i\mid R_i,\text{position})\tag{D.11}

每个变换 $P(T_i\mid R_i)$ 可以从三元组训练集学习；三元组包含错误字符串、正确字符串及其出现次数。例如，对训练对 akgsual/actual 使用标准最小编辑距离得到对齐，再把每个非匹配替换扩展为最多包含 $N$ 个额外编辑的多字符变换。若 $N=2$ ，c→k 可扩展为 ac→ak、c→cg、ac→akg、ct→kgs 等。随后给每种多字符编辑分配分数计数，并用训练语料计数估计编辑概率。

另一条信道模型研究路线是在拼写之外利用发音。发音也是一些非噪声信道拼写纠错算法的重要特征，例如 GNU aspell（Atkinson, 2011）使用词的 Metaphone 发音（Philips, 1990）。Metaphone 用一系列规则把词映射为规范化发音表示，例如：

删除相邻重复字母，但 C 除外；
若词以 KN、GN、PN、AE 或 WR 开头，删除首字母；
若 B 位于 M 之后且在词末，则删除 B。

Aspell 与噪声信道模型的信道部分相似：在词典中寻找发音字符串与错误词只有较短编辑距离——1 或 2 个发音字母——的词，再用结合发音编辑距离和加权字母编辑距离的度量为候选评分。

发音也可以直接纳入噪声信道模型。Toutanova and Moore（2002）与 aspell 相似，对两个信道模型做插值：一个基于拼写，另一个基于发音。发音模型使用“字母到语音”模型，把输入词和每个词典词都转换为表示发音的音素序列。例如，actress 与 aktress 都会映射为音素串 ae k t r ix s。字母到语音或字素到音素任务见第 18 章。

还有一些字符串距离函数专门用于人名，主要服务于去重任务——判断人口普查名单或其他姓名表中的两个名字是否为同一人——而非拼写检查。

Soundex 算法（Odell and Russell, 1918/1922；Knuth, 1973）是一种最初用于人口普查记录的人名表示方法。它的优点是，轻微拼错的人名仍会与正确拼写得到相同表示，例如 Jurafsky、Jarofsky、Jarovsky 和 Jarovski 都映射为 J612。

function SOUNDEX(name) returns soundex-form
1. 保留 name 的首字母。
2. 删除不在首位的 a, e, h, i, o, u, w, y。
3. 把其余字母替换为数字：
   b,f,p,v → 1
   c,g,j,k,q,s,x,z → 2
   d,t → 3
   l → 4
   m,n → 5
   r → 6
4. 若连续相同数字来自原名中相邻的两个或更多字母，将其合并为一个数字。
5. 转成“字母＋三位数字”：删除第三位之后的数字，或在末尾补零。

图 D.7　Soundex 算法。

较新的工作常用 Jaro–Winkler 距离替代 Soundex。该编辑距离专为人名设计：在较长名字中允许字符移动更远的距离，并让首字符相同的字符串获得更高相似度（Winkler, 2006）。