Good‐Turing Discounting浅析 2019-04-26

Discounting类包括：

Add-One Smoothing（加法平滑）

Good-Turing Discounting（图灵平滑）

加法平滑太简单就不说了。

图灵平滑。看了统计自然语言处理和数学之美对这部分的解析。

先看个例子：

训练集合：T={<s>what is it what is small?}|T|=8

验证集合：V={what is it small ? <s> flying birds are a bird.}, |V|=12

在训练集合上，我们得到：p(<s>)=p(it)=p(small)=p(?)=0.125, p(what)=p(is)=0.25，其他为0

如果不经过平滑处理，则验证集上两句子的概率分别为：

p(what is it?)=（0.25*2）*（0.125*2）≈0.001

p(it is flying.)=0.125*0.25*（0*2）=0

但是实际上it is flying是有可能出现的。现在用古德-图灵算法进行平滑处理，如下：

首先计算，各发生 r 次 N 元组类别的数目，依次为N(0)=6,N(1)=4,N(2)=2,N(i)=0 ,i>2:

其次，重新估计各概率值。

对于发生0次的事件概率：

Pr(.)=p(flying)=p(birds)=p(are)=p(bird)=p(a)=(0+1)*N(0+1)/(8*N(0))=1*4/(8*6)≈0.083

对于发生1次的时间概率：Pr(it)=p(<s>)=p(small)=p(?)=(1+1)*N(1+1)/(8*N(1))=2*2/(8*4)=0.125

对于发生两次的时间概率：Pr(what)=Pr(is)=(2+1)*N(2+1)/(8*N(2))=3*0/(8*2)=0: 保持原值0.25

注意计算时候最高次的P的公式里面有 $n_{r+1}$ ，但是已经是最高次了这个值一定是零，那个最高位保持他原有的概率就可以了。

归一化处理，6* $p_{0}$ +4* $p_{1}$ +2* $p_{2}$ =1.5。这里的 $p_{2}=0.25$

所以，归一化处理后：

发生1次的时间概率：p’(it)=p’(<s>)=p’(small)=p’(?)=0.125/1.5 ≈0.08 (原概率0.125) -0.045

发生2次的时间概率：p’(what)=p’(is)= 0.25/1.5 ≈ 0.17 (原概率0.25） -0.08

发生0次的时间概率：p’(.)=p’(birds)=p’(are)=p’(bird)=p’(a) = 0.083/1.5 ≈0.06（原概率是0）

因此：

p’(what is it?)=(0175*2)*(0.08*2) ≈ 0.0002 [原 p(what is it?)=（0.25*2）*（0.125*2）≈ 0.001]

p’(it is flying.) ≈ 0.08*0.17*（0.06*2）≈ 0.00004 [ 原 p(it is flying.)=0.125*0.25*（0*2）=0 ]

大概就是这么个情况。

下面开始看原理：

比如一个text文本

1 今天天气不错

2 北京今天堵车

3 今天天气很棒

4 今天天气还好

5 今天天气很棒

6 你好你好

7 你好先生

8 你好图灵

9 你好小姐

10 你好宝宝

11 .... ....

出现r次的n元语法的数目，一共有 $N_{r}$ 个。

其中三元语法有5次，二元语法有5次。这样的5次一共有 $N_{r}=2$

不管几元语法，只考虑这个语法的出现次数r，剪掉的也是这个次数。

总词数 $N = \sum_{r=0}^\propto n_{r} r^*$ 从出现0次的语法到出现最大次数的语法的总和就是总词数。

$r^* = (r+1)\frac{n_{r+1} }{n_{r}}$ 原始= $r$ ，现在是 $r^*$ ，剪掉的部分是 $r-r^*$ 。剪掉的部分次数给了出现零次的增加次数。

5-A的公式可以看到如果是正常计算的话 $\sum_{r=1}^\propto n_{r} r$ ，现在用 $\sum_{r=0}^\propto n_{r} r^*$

现在的概率如果不算r=0的部分的（r>0）话概率是 $1-\frac{n_1}{N}$

$\frac{n_1}{N}$ 是匀给出现r=0的总次数、剩余量。 $\frac{n_1}{N}$ 的计算就是用到了（5-10）得出的。

END