拼写错误介绍
在输入过程中，会存在拼写错误。拼写错误分为两类：
- 非单词拼写错误（non-word spelling error），即需要纠错的单词不在现有词典中，如把success 输错成succest 。
- 实单词拼写错误（real word spelling error），即需要纠错的单词存在现有词典中，如把there 输错成three 。
拼写错误一般由字母增删改、字母调换顺序等错误造成。在手机输入中，由于键盘小，手指大(fat fingure problem)而造成多、错、漏输入等情况。另一方面，由于发音相同或相似，容易造成实单词拼写错误。在汉语中表现为n、l不分，f、h不分，前后鼻音不分，平翘舌音不分等。
拼写纠错通用框架
拼写纠错一般分为三大步：
- 拼写错误检测（检测）
- 纠错候选生成（召回）
- 纠错候选排序（排序）
对于非单词拼写错误，可以通过字典进行检测。如果待纠错词不在字典中，那么这个词是需要纠错的。而对于实单词错误，无法通过字典形式检测。
正确单词和待纠错单词通常有着相似的字符序列。所以使用编辑距离来产生纠错候选。对待纠错单词，通过变换可以得到编辑距离为$n$ 的单词候选，判断新单词候选是否在字典中，若在则成为带纠错单词的纠错候选，添加到候选集合$C$ 中。$n$ 通常取1-2 。
最后，如何排序上一步生成的纠错候选。已知用户错误拼写记为$x$ ，第$i$ 个纠错候选单词为$w_i$ ，那么$p(w_i|x)$ 为$w_i$错输成$x$ 的概率，作为各个$w_i$ 的权重。对于同一个$x$ ，$p(w_i|x)$ 越大， $w_i$ 越有可能是$x$ 的正确单词。所以有：
\begin{equation}
\begin{aligned}
\hat{w}=\arg\max_{w \in C}p(x|w)p(w)
\end{aligned}
\end{equation}
噪声信道模型(Noisy Channel Model)
根据贝叶斯公式：
\begin{equation}
\begin{aligned}
p(w|x) = \frac{p(x|w) * p(w)}{p(x)}
\end{aligned}
\end{equation}
对于所有的纠错候选词$w$ ，$x$ 是一样的。所以$p(x)$ 可以去掉。得：
\begin{equation}
\begin{aligned}
p(w|x) = p(x|w) * p(w)
\end{aligned}
\end{equation}
$p(x|w)$ 为$w$ 错输成$x$ 的概率，亦称作似然或者$w$ 转化成$x$ 的信道模型。$p(w)$ 为纠错候选的先验概率，从语料中统计得到，p(w) 可以是unigram 、bigram 或者trigram 。
影响$p(x|w)$ 的因素有很多。一般我们转化为字符错误类型。错误类型分为：增、删、改以及交换（Damerau-Levenshtein)。通过统计字符四种错误类型的混淆矩阵来近似$p(x|w)$ 。举个例子：$p(acress|across)$ 可以使用大语料中字符o 被e 替换的概率$p(e|o)$ 代替。
实单词拼写错误
实单词拼写错误依然遵循通用框架的后两步。 首先，通过编辑距离召回候选，然后根据先验概率和信道噪声模型进行排序。 在召回候选时，一般编辑距离小于等于1，这里和非单词错误不一样，需要纠错单词本身也是候选词之一。信道噪声模型首先要考虑需要纠错的单词其实是没有错误，即$p(w|w)$ 的概率$\alpha$ 会根据不同任务设定不同的值。通常为$.95$。那么，剩下的候选词分摊$1-\alpha$ 。
\begin{equation}
\begin{aligned}
p(x|w) = \begin{cases}
\alpha & \text{if } x=w \\
\frac{1-\alpha}{\left | C(x) \right |} & \text{if } x\subset C(x) \\
0 & \text{otherwise }
\end{cases}
\end{aligned}
\end{equation}
除了使用均匀分布，更精确的做法是：按照字符混淆矩阵的概率分配。先验概率$p(w)$ 依然采用语言模型，bigram 或者trigram。
改进点
- 不再假设一句话只有一处错误。对每个单词进行检查。如果仅使用简单的纠错模型，会造成很多误纠错。特别是不常见的单词。
- 使用不纠错白名单
- 使用$logP(w|x) - log(x|x) > \theta$ 代替$logP(w|x) - log(x|x) > 0$
- 使用额外分类器决定是否纠错是否可靠
- 使用更大的词表，特别是在互联网场景下。
- 改进纠错模型：使用加权方式平衡似然和先验概率。
\begin{equation}
\begin{aligned}
\hat{w}=\arg\max_{w \in C}p(x|w){p(w)}^{\lambda}
\end{aligned}
\end{equation} - 对于实单词拼写错误中的固定错误形式，考虑监督算法
参考资料：