贝叶斯公式的应用
在输入英文单词的时候,经常会因为输入速度过快而产生单词拼写错误,例如将单词“smile”输入为“smilw”,此时就体现出拼写纠错的重要性,基于此我们将利用贝叶斯公式实现一个简单的拼写纠错程序。
python代码[1]如下:
1 | import re |
当用户调用函数correct(word)时,该函数会根据传入的参数,即需要拼写检查的单词w,返回最有可能的正确单词c。比如,用户输入单词w为“thaw”,那么该函数将会从候选单词集合I={the, thaw,...}中挑取可能性最大的单词c。用数学公式来表示返回值:
$$
c={c|max_{c \in I}P(c|w)}
$$
根据贝叶斯公式,上述等式可改写为:
$$
c={c|max_{c \in I}\frac{P(c)P(w|c)}{P(w)}}
$$
由于单词c永远是当前单词w的最有可能的正确拼写,也就是说对于任意一个给定的单词w,$P(w)$是定值,因此它可以被同时约去,于是我们得到:
$$
c={c|max_{c \in I}{P(c)P(w|c)}}
$$
基于这样的式子,拼写纠错程序按照执行顺序共分为如下4个部分:
- 确定候选单词集合$I$
- 求每个候选单词$c$在文章中出现的概率$P(c)$
- 对每个候选单词$c$求用户输入为单词$w$的概率$P(w|c)$
- 返回使$P(c)P(w|c)$最大的单词$c$
1.确定候选单词集合$I$
鉴于这只是一个简单的拼写纠错程序,我们假设常见的输入错误主要有“多输入了一个字母”、“单词中只有一组相邻两个字母顺序颠倒”、“某个字母被输入为另一字母”或“少输入了一个字母”,针对这四种错误,函数edits1(word)将会对单词w进行复原并返回所有可能的结果,即执行“删除任意一个字母”、“交换任意一组相邻两个字母顺序”、“替换任意一个位置的字母”或“将任意一个字母插入到任意位置”,于是有如下代码:
1 | def edits1(word): |
事实上,通过edits1函数变换会产生大量不存在的单词,这就造成返回的集合有可能十分巨大且无意义,特别是当输入的单词比较长的时候。为了过滤这些不存在的单词,我们可以先设置一个名为WORDS的字典,对于返回的集合,只保留字典中存在的单词,于是定义konwn(words)函数来执行这样的操作:
1 | def known(words): |
假如执行edits1后就进行过滤操作,集合往往会变得比较小,甚至是空集,所以我们可以考虑用户输入的单词和正确单词有两个字母存在问题,故设计edits2函数,让该函数对edits1的结果再进行变换:
1 | def edits2(word): |
这样一来,对edits1和edits2的结果分别用known函数进行过滤,将会产生两个候选单词集合。然而,需要注意的一点是,可能用户输入的单词原本就是正确的,因此候选单词集合I还应考虑这样的情况。
2.求每个候选单词$c$在文章中出现的概率$P(c)$
由大数定律可知,当重复独立试验的次数n趋于无穷时,某事件出现的频率将无限接近于其发生的概率。因此,我们可以将某个单词在大量文章中出现的频率近似认为是其概率:
1 | def words(text): return re.findall(r'\w+', text.lower()) |
3.对每个候选单词$c$求用户输入为单词$w$的概率$P(w|c)$
为了简化工作量,我们做以下假设:用户输入的单词属于上述字典WORDS的可能性是最大的,并且这个可能性远远大于一个字母存在问题的可能性,而后者也远大于两个字母的可能性。作了上述假设后,我们不必再依赖P(w|c)具体值,而是首先根据“没有错误”、“存在一个字母的错误”或“存在两个字母的错误”顺序来判断P(c)P(w|c)的大小,并且同级别错误里每个备选单词c的P(w|c)都是一样的,因此我们有:
1 | def candidates(word): |
4.返回使$P(c)P(w|c)$最大的单词$c$
在步骤3的假设下,同级别错误里比较P(c),可直接获得最大值:
1 | def correct(word): |