crackcell's dustbin home projects
首页 > 数据平滑小结 > 正文

数据平滑小结

1 问题的引入

数据平滑(Smoothing)问题的一个引入点是在语言模型里面。回顾一下语言模型的定义:

\[ \begin{eqnarray} p(s) &=& p(w_1)p(w_2|w_1)p(w_3|w_{1}w_{2})...p(w_1|w_1...w_{i-1})\\ &=& \prod_{i=1}^{l}p(w_{i}|w_{1}...w(i-1)) \end{eqnarray} \]

n-gram模型是对上述问题的简化,即只考虑长度为n的窗口中的词的概率。它简单直接,但需要引入数据平滑来解决因为数据缺乏导致的零概率问题。平滑的基本思想就是降低高高概率,给零概率事件也赋予一定的概率值,尽量使分布区域均匀。

2 平滑方法

2.1 加法平滑(Additive Smoothing)

要解决零概率问题,最朴素的思想就是对所有事件的出现次数加1。加法平滑是对这种思想的通用化,假设所有事件多发生 δ 次:

\[ p_{add}(w_{i}|w_{i-n+1}^{i-1})=\frac{\delta+c(w_{i-n+1}^{i})}{\delta|V|+\sum_{w_{i}}c(w_{i-n+1}^{i})} \]

2.2 古德-图灵(Good-Turing)估计

对于一个发生r次n-gram,都假设它发生 r* 次:

\[ r^{*}=(r+1)\frac{n_{r+1}}{n_r} \]

nr是语料库中发生r次的n-gram的数目。

  • 当nr+1=nr,r*就是加1法
  • 当nr+1>nr,r*比加1法发生次数多,反之,就少

直观感觉是将实际发生次数往r+1上去靠,如果nr+1多,就多靠一点,反之就少靠一点。这样将r+1的发生次数往r次上去延伸的目的是为了引出如何度量r=0的情况

接下来计算总次数:

\[ N=\sum_{r=0}^{\infty}n_{r}r^{*}=\sum_{r=0}^{\infty}(r+1)n_{r+1}=\sum_{r=1}^{\infty}n_{r}r \]

也就是说,N等于分布中最初的总数。

计算出现次数为r的n-gram的概率:

\[ p_r=\frac{r^*}{N} \]

对于r=0,它出线的概率为:

\[ r^{0}=n_{1} \]

进而:

\[ \sum_{r>0}n_{r}p_{r}=1-\frac{n_{1}}{N}<1 \]

也就是将 \(\frac{n_{1}}{N}\) 的概率分配给了没有出现过的事件。

Good-Turing估计对于n-gram平滑不能单独使用,而是作为一个工具被其它平滑技术使用。

2.3 Katz平滑

扩展了Good-Turning估计,加入了高阶模型与低阶模型的结合。

以bi-gram举例,对于一个出现次数为 \(r=c(w_{i-1}^{i})\) 的二元语法 \(w_{i-1}^{i}\) ,使用如下公式调整计数:

\[ C_{katz}(w_{i-1}^{i})= \begin{cases} d_{r}r& \text{r>0}\\ \alpha(w_{i-1})p_{ML}(w_{i})& \text{r=0} \end{cases} \]
  • 对于非零计数的bi-gram都按照折扣率d打折了,d近似地等于 \(\frac{r^{*}}{r}\) 。由Good-Turning估算出来
  • \(p_{ML}\) 是极大似然概率

Katz平滑属于后备(back-off)平滑,中心思想是,当某一事件出现的概率大于k,运用最大似然估计经过减值来估算概率。当小于k时,使用低阶的语法模型作为代替高阶模型的后备。

2.4 Jelinek-Mercer平滑

拿bi-gram举例,如果一个bi-gram没有出现过,一个朴素的思想是退一步,看一下uni-gram的概率,然后大概推测一下bi-gram的概率。

考虑uni-gram的最大似然:

\[ p_{ML}(w_{i})=\frac{c(w_{i})}{\sum_{w_{i}}c(w_{i})} \]

对bi-gram进行线性插值:

\[ p_{interp}(w_{i}|w_{i-1})=\lambda p_{ML}(w_{i}|w_{i-1})+(1-\lambda)p_{ML}(w_{i}) \]

一般来讲,使用低阶的π元模型向高阶n元模型插值是有效的,因为当没有足够的语料估计高阶模型的概率时,低阶模型往往可以提供有用的信。1

后来有人将插值方法通用化了:

\[ p_{interp}(w_{i}|w_{i-n+1}^{i-1})=\lambda_{w_{i-n+1}^{i-1}}p_{ML}(w_{i}|w_{i-n+1}^{i-1})+(1-\lambda_{w_{i-n+1}^{i-1}})p_{interp}(w_{i}|w_{i-n+1}^{i-1}) \]

递归定义了n阶模型由n-1阶模型插值得到,对于1阶模型,或者用均匀分布作为平滑的0阶模型。

2.5 贝叶斯平滑

贝叶斯平滑在广告点击率预估中广泛应用2

Footnotes:

1

统计自然语言处理

2

Practical Lessons from Predicting Clicks on Ads at Facebook

Date: Thu Nov 9 21:19:20 2017

Author: Menglong TAN

Created: 2018-01-01 Mon 17:24

Emacs 24.5.1 (Org mode 8.2.10)

Validate

Modified theme and code from Tom Preston-Werner.