贝叶斯公式的应用

　　在输入英文单词的时候，经常会因为输入速度过快而产生单词拼写错误，例如将单词“smile”输入为“smilw”，此时就体现出拼写纠错的重要性，基于此我们将利用贝叶斯公式实现一个简单的拼写纠错程序。
　　python代码^[1]如下：

import re
from collections import Counter

def words(text): return re.findall(r'\w+', text.lower())

WORDS = Counter(words(open('largesample.txt').read()))

def P(word, N=sum(WORDS.values())): 
    return WORDS[word] / N

def correct(word): 
    return max(candidates(word), key=P)

def candidates(word): 
    return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])

def known(words): 
    return set(w for w in words if w in WORDS)

def edits1(word):
    letters    = 'abcdefghijklmnopqrstuvwxyz'
    splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
    deletes    = [L + R[1:]               for L, R in splits if R]
    transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
    replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]
    inserts    = [L + c + R               for L, R in splits for c in letters]
    return set(deletes + transposes + replaces + inserts)

def edits2(word): 
    return (e2 for e1 in edits1(word) for e2 in edits1(e1))

　　当用户调用函数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个部分：

1. 确定候选单词集合$I$
2. 求每个候选单词$c$在文章中出现的概率$P(c)$
3. 对每个候选单词$c$求用户输入为单词$w$的概率$P(w|c)$
4. 返回使$P(c)P(w|c)$最大的单词$c$

1.确定候选单词集合$I$

　　鉴于这只是一个简单的拼写纠错程序，我们假设常见的输入错误主要有“多输入了一个字母”、“单词中只有一组相邻两个字母顺序颠倒”、“某个字母被输入为另一字母”或“少输入了一个字母”，针对这四种错误，函数edits1(word)将会对单词w进行复原并返回所有可能的结果，即执行“删除任意一个字母”、“交换任意一组相邻两个字母顺序”、“替换任意一个位置的字母”或“将任意一个字母插入到任意位置”，于是有如下代码：

def edits1(word):
    letters    = 'abcdefghijklmnopqrstuvwxyz'
    splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
    deletes    = [L + R[1:]               for L, R in splits if R]
    transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
    replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]
    inserts    = [L + c + R               for L, R in splits for c in letters]
    return set(deletes + transposes + replaces + inserts)

　　事实上，通过edits1函数变换会产生大量不存在的单词，这就造成返回的集合有可能十分巨大且无意义，特别是当输入的单词比较长的时候。为了过滤这些不存在的单词，我们可以先设置一个名为WORDS的字典，对于返回的集合，只保留字典中存在的单词，于是定义konwn(words)函数来执行这样的操作：

def known(words): 
    return set(w for w in words if w in WORDS)

　　假如执行edits1后就进行过滤操作，集合往往会变得比较小，甚至是空集，所以我们可以考虑用户输入的单词和正确单词有两个字母存在问题，故设计edits2函数，让该函数对edits1的结果再进行变换：

def edits2(word): 
    return (e2 for e1 in edits1(word) for e2 in edits1(e1))

　　这样一来，对edits1和edits2的结果分别用known函数进行过滤，将会产生两个候选单词集合。然而，需要注意的一点是，可能用户输入的单词原本就是正确的，因此候选单词集合I还应考虑这样的情况。

2.求每个候选单词$c$在文章中出现的概率$P(c)$

　　由大数定律可知，当重复独立试验的次数n趋于无穷时，某事件出现的频率将无限接近于其发生的概率。因此，我们可以将某个单词在大量文章中出现的频率近似认为是其概率：

def words(text): return re.findall(r'\w+', text.lower())
WORDS = Counter(words(open('largesample.txt').read()))
def P(word, N=sum(WORDS.values())): 
    return WORDS[word] / N

并且大量文章集合“largesample.txt”中出现的所有单词可以作为字典WORDS

3.对每个候选单词$c$求用户输入为单词$w$的概率$P(w|c)$

　　为了简化工作量，我们做以下假设：用户输入的单词属于上述字典WORDS的可能性是最大的，并且这个可能性远远大于一个字母存在问题的可能性，而后者也远大于两个字母的可能性。作了上述假设后，我们不必再依赖P(w|c)具体值，而是首先根据“没有错误”、“存在一个字母的错误”或“存在两个字母的错误”顺序来判断P(c)P(w|c)的大小，并且同级别错误里每个备选单词c的P(w|c)都是一样的，因此我们有：

def candidates(word): 
    return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])

4.返回使$P(c)P(w|c)$最大的单词$c$

　　在步骤3的假设下，同级别错误里比较P(c)，可直接获得最大值：

def correct(word): 
    return max(candidates(word), key=P)

参考文献

[1]来源：http://norvig.com/spell-correct.html