初涉自然语言处理(五):平滑处理

这个项目前前后后拖了得有三个月时间吧,中间放寒假完全没管。前一阵开学了,在寝室闲得天昏地暗,索性花几天时间把它弄完。

先上一下效果图:

Powered by Vkki's Spell Checker

话说这个长时间不看代码造成的后果就是自己也不知道自己当初写的是些什么鬼,基本上第一天我都在回忆当初为什么要写成这种鸟样 —— 看不顺眼顺手一改 —— 出错了 —— 看来必须得这么写……

因为这个项目的代码太多太杂,这里就先不放代码了,仅整理一下相关的流程。毕竟是要作为毕业设计拿去答辩的,还是要理一理思路。

本项目的 Intuition 是:

  1. 将文本中的每个单词与词典向比较,若不在词典中,则认为是拼写错误
  2. 通过 Levenshtein 算法从词典中选出与错误单词最接近的一组候选词
  3. 将错误单词的前一个单词和后一个单词拿出来,对每个候选词分别计算 $P_{KN}( w_i | w_{i-1} )$ (Kneser-Ney Smoothing)
  4. 将 3 中得到的两个结果相乘得到 Confidence
  5. 选出 Confidence 最高的几个结果。

这里讲一下 Kneser-Ney 的平滑处理算法,这个算法是 Good-Turing 算法的改进,而后者又是 Add-One 算法的改进。这里先介绍一下平滑处理:

由于我们在统计 Bigram 的时候,受限于语料库的大小,一定会有一些组合是没有出现过的(频率为 0),那么这些没出现过的组合如果带入到 $$P_{MLE}(w_i|w_{i-1}) = \frac{c(w_{i-1},w_i)}{c(w_{i-1})}$$ (MLE: Maximum Liklihood Estimates)这条公式进行计算,很明显会得到 0 的结果,也就是说这些组合将永远不会被程序所执行。为了规避这种情况,我们对 Bigram 数据做一些处理,称为平滑处理(Smoothing)。


Add One

最简单的一个想法是,我们给每个组合的频率加 1,即假装我们对每个组合都多看见了一次。

于是公式变成:

$$P_{Add-1}(w_i|w_{i-1})=\frac{c(w_{i-1},w_i)+1}{c(w_{i-1})+V}$$

这里的 $V$ 是跟在 $w_{i-1}$ 后的单词的个数,因为我们给所有 Bigram 都加了 1,所以分母也要相应增加「那么多」个 1。

Add-One 平滑处理后的对比

可以看到原先统计为 0 的数据现在都变为了相应的非零数,然而由于分母增大了很多,可以看到原先的数据发生了极大的改变。如 Chinese food : 82 -> 8.2,缩小了 10 倍。由于数据变动过大,因此这一方法虽然简单但却不是最好的方法。


Good Turing

考虑如下假设:

假设你正在钓鱼,并且钓上了 10 条鲤鱼,3 条鲈鱼,2 条鳟鱼, 1 条鲑鱼,1 条三文鱼,1 条鳗鱼,共计 18 条鱼。

下一条是鲑鱼的概率是多少?

  • $1/18$

下一条是新物种(如鲶鱼)的概率是多少?

  • 我们使用出现次数为 1 的物种数来预测

  • 1 条鲑鱼,1 条三文鱼,1 条鳗鱼

  • $ 3/18(N_1=3)$

即我们可以用「出现 1 次的」频率来估计「没有出现」的概率,同理,可以用「出现 N+1 次的」频率来估计「出现 N 次的」概率。基于以上假设,我们有:

$$P_{GT}^*(things\:with\:zero\:frequency)=\frac{N_1}{N}$$

$$C^*=\frac{(c+1)N_{c+1}}{N_c}$$

回到钓鱼的问题,那么此时没有出现过的鱼的频率变成了 3/18,出现 1 次的(鲑鱼)的频率必然比 1/18 要低:

$$\begin{align}
C^*(trout) & =2* \frac{N_2}{N_1} \\
& = 2 * \frac{1}{3} \\
& = \frac{2}{3}
\end{align} $$

$$\begin{align}
P^*_{GT}(trout)&=\cfrac{\cfrac{2}{3}}{18} \\
&=\frac{1}{27}
\end{align}$$

可以看到 鲑鱼: 1/18 -> 1/27 起码没有量级上的改变,是可以接受的。

Good Turing Result from Church and Gale (1991)<br>22 million words of AP Newswire

上面是别人计算的数据,跟我自己计算的差异很大,可能是 corpus 的原因吧。可以看到,除了前两个,基本上重新计算的 count 等于原本的 count 减去 0.75。


Kneser-Ney

由 Good Turing 可知,我们只需要给原本的统计数据减去 0.75 就能基本满足需要,而不需要每次都计算一下 $C^*$,因此提出如下公式:

$$P_{AbsoluteDiscounting}(w_i|w_{i-1})=\frac{c(w_{i-1},w_i)-d}{c(w_{i-1})}+\lambda(w_{i-1})P(w)$$

这里的 $P(w)$ 是 Unigram,即 $w$ 出现的频率。$\lambda$ 是一个常数,代表着我们减掉的概率。

但是我们发现仅仅使用 Unigram 是不够的,因为一个单词使用得越频繁不代表它就会在所有场合都容易出现(如 Francisco 只会跟在 San 后面)因此又提出 跟随概率:

$$ P_{CONTINUATION}(w) \propto \left | \{w_{i-1}:c(w_{i-1},w)>0\} \right | $$

意思是 $w$ 的跟随概率正比于出现在它前面的单词的个数。

而我们所有的 bigram 条数可表示为

$$\left |\{(w_{j-1},w_j):c(w_{j-1},w_j)>0\} \right |$$

因此

$$
P_{CONTINUATION}(w) =
\frac{\left | \{w_{i-1}:c(w_{i-1},w)>0\} \right | }{\left |\{(w_{j-1},w_j):c(w_{j-1},w_j)>0\} \right |}
$$

最终我们所采用的平滑公式为:

$$\mathbf{ P_{KN}(w_i|w_{i-1}) = \frac{max(c(w_{i-1},w_i) - d, 0)}{c(w_{i-1})}+ \lambda(w_{i-1})P_{CONTINUATION}(w_i) }$$ $$\mathbf{ \lambda(w_{i-1})= \frac{d}{c(w_{i-1})} \left | \{w:c(w_{i-1},w)>0\} \right | }$$

有了这个公式,我们只需要把统计的数据带进去,就能求出第三步的 $P_{KN}$,进而完成整个流程。

写到这里整个项目也差不多结束了,梳理了一遍流程,看似容易,个中辛苦只有自己知道。

以后可能不会再经常写技术类博文了,想转换一下风格。

愿付出的努力都有所回报。
写于 2016/03/19 03:00 AM