自然语言处理——5.3 语言模型（数据平滑）

基本思想

数据平滑的基本思想
调整最大似然估计的概率值,使零概率增值，使非零概率下调，“劫富济贫”，消除零概率，改进模型的整体正确率。
基本目标
测试样本的语言模型困惑度越小越好。

基本约束
$\sum\limits_{{\omega _i}} {p({\omega _i}|{\omega _1},{\omega _2},...,{\omega _{i - 1}})} = 1$

困惑度定义：

对于一个平滑的 n-gram，其概率为 $p({\omega _i}|\omega _{i - n + 1}^{i - 1})$ ，可以计算句子的概率: $p(s) = \mathop \prod \limits_{i = 1}^{m + 1} p({\omega _i}|\omega _{i - n + 1}^{i - 1})$
假定测试语料 $T$ 由 $l_T$ 个句子构成 $(t_1,...,t_{l_T})$ ,那么整个测试集的概率为： $p(T) = \mathop \prod \limits_{i = 1}^{{l_T}} p({t_i})$
模型 $p({\omega _i}|\omega _{i - n + 1}^{i - 1})$ 对于测试语料的交叉熵：
${H_p}(T) = - \frac{1}{{{W_T}}}{\log _2}p(T)$
其中， $W_T$ 是测试文本 $T$ 的词数。
模型 p 的困惑度 $PP_p(T)$ 定义为： $P{P_p}(T) = {2^{{H_p}(T)}}$
PS: n-gram 对于英语文本的困惑度范围一般为50～1000，对应于交叉熵范围为6～10 bits/word。

数据平滑方法1——加1法(Additive smoothing )

基本思想: 每一种情况出现的次数加1。
例如，对于 uni-gram，设 $w_1, w_2, w_3$ 三个词，概率分别为：1/3, 0, 2/3，加1后情况？
举例
<BOS>John read Moby Dick<EOS>
<BOS>Mary read a different book<EOS>
<BOS>She read a book by Cher<EOS>
词汇量：|V|＝11
平滑以后：
p(Cher|<BOS>) = (0+1)/(11+3) = 1/14
p(read|Cher) = (0+1)/(11+1) = 1/12
p(a|read) = (1+2)/(11+3) = 3/14
p(book|a) = (1+1)/(11+2) = 2/13
p(<EOS>|book)= (1+1)/(11+2) = 2/13
$p(Cher{\text{ read a book}}) = \frac{1}{{14}} \times \frac{1}{{12}} \times \frac{3}{{14}} \times \frac{2}{{13}} \times \frac{2}{{13}} \approx 0.00003$

数据平滑方法2——减值法/折扣法(Discounting)

1. 基本思想:

修改训练样本中事件的实际计数，使样本中(实际出现的)不同事件的概率之和小于1，剩余的概率量分配给未见概率。

2. Good-Turing 估计

基本思想

假设 $N$ 是原来训练样本数据的大小， $n_r$ 是在样本中正好出现 $r$ 次的事件的数目(此处事件为 n-gram)，即出现 1 次的n-gram有 $n_1$ 个，出现 2 次的 n-gram 有 $n_2$ 个, ……，出现 $r$ 次的有 $n_r$ 个。
那么： $N = \sum\limits_{r = 1}^\infty {{n_r}r} = \sum\limits_{r = 0}^\infty {{n_{r+1}}(r+1)}$
由于我们要减小r,记为： $r^*$ ： $N = \sum\limits_{r = 1}^\infty {{n_r}r^*}$ ，所以： $r^* = (r + 1)\frac{{{n_{r + 1}}}}{{{n_r}}}$
那么，Good-Turing估计在样本中出现r次的事件的概率为： ${p_r} = \frac{{{r^*}}}{N}$

举例说明

假设有如下英语文本，估计2-gram概率：
<BOS>John read Moby Dick<EOS>
<BOS>Mary read a different book<EOS>
<BOS>She read a book by Cher<EOS>
……
从文本中统计出不同 2-gram 出现的次数：
<BOS> John 15
<BOS> Mary 10
……
read Moby 5
……

假设要估计以 read 开始的 2-gram 概率，列出以read开始的所有 2-gram，并转化为频率信息：

得到 $r^*$ 后，便可计算概率： ${p_r} = \frac{{{r^*}}}{N}$

其中，N 为以 read 开始的bigram的总数(样本空间)，即read出现的次数。那么，以 read开始，没有出现过的 2-gram的概率总和为： ${p_0} = \frac{{{n_1}}}{N}$

以read作为开始，没有出现过的 2-gram的个数等于： ${n_0} = |{V_T}| - \sum\limits_{r > 0} {{n_r}}$ ，其中， $|V_T|$ 为语料的词汇量。

那么，没有出现过的那些以read为开始的概率平均为： $\frac{{{p_0}}}{{{n_0}}}$

注意：

\sum\limits_{r = 0}^7 {{\operatorname{P} _r}} \ne 1

因此，需要归一化处理：

{{\hat P}_r} = \frac{{{\operatorname{P} _r}}}{{\sum\nolimits_r {{\operatorname{P} _r}} }}

3. Back-off (后备/后退)方法

基本思想

S. M. Katz于1987年提出，所以又称Katz后退法。
当某一事件在样本中出现的频率大于阈值K (通常取K 为0 或1)时，运用最大似然估计的减值法来估计其概率，否则，使用低阶的，即(n-1)gram 的
概率替代n-gram 概率，而这种替代需受归一化因子 $\alpha$ 的作用。

Back-off 方法的另一种理解:

对于每个计数 r > 0 的n元文法的出现次数减值, 把因减值而节省下来的剩余概率根据低阶的(n-1)gram 分配给未见事件。

举例说明

4. 绝对减值法(Absolute discounting )

基本思想

从每个计数 $r$ 中减去同样的量，剩余的概率量由未见事件均分。
设 $R$ 为所有可能事件的数目(当事件为n-gram 时，如果统计基元为词，且词汇集的大小为 $L$ , 则 $R=L^n$ )。

那么，样本出现了r次的事件的概率可以由如下公式估计：

其中， $n_0$ 为样本中未出现的事件的数目。 $b$ 为减去的常量， $b ≤ 1$ 。 $b(R - n_0)/N$ 是由于减值而产生的剩余概率量。 $N$ 为样本中出现了 $r$ 次的事件总次数： $n_r \times r$ 。

$b$ 为自由参数，可以通过留存数据(heldout data)方法求得 $b$ 的上限为： $b \leqslant \frac{{{n_1}}}{{{n_1} + 2{n_2}}} < 1$

5. 线性减值法(Linear discounting )

基本思想

从每个计数 $r$ 中减去与该计数成正比的量(减值函数为线性的)，剩余概率量 $\alpha$ 被 $n_0$ 个未见事件均分。
${p_r} = \left\{ {\begin{array}{*{20}{c}} {\frac{{(1 - \alpha )r}}{N}{\text{ r > 0}}} \\ {\frac{\alpha }{{{n_0}}}{\text{ r = 0}}} \end{array}} \right.$
自由参数 $α$ 的优化值为： ${\frac{{{n_1}}}{N}}$

绝对减值法产生的n-gram 通常优于线性减值法。

6. 四种减值法的比较

数据平滑方法3——删除插值法(Deleted interpolation)

基本思想:
用低阶语法估计高阶语法，即当 3-gram 的值不能从训练数据中准确估计时，用 2-gram 来替代，同样，当 2-gram 的值不能从训练语料中准确估计时，可以用 1-gram 的值来代替。插值公式：
$p({\omega _3}|{\omega _1}{\omega _2}) = {\lambda _3}p'({\omega _3}|{\omega _1}{\omega _2}) + {\lambda _2}p'({\omega _3}|{\omega _2}) + {\lambda _1}p'({\omega _3})$
其中 $\lambda_1+\lambda_2+\lambda_3=1$
$\lambda_1，\lambda_2，\lambda_3$ 的确定

将训练语料分为两部分，即从原始语料中删除一部分作为留存数据(heldout data)。
第一部分用于估计 $p '(w_3 | w_1w_2 )，p '(w_3 | w_2 )$ 和 $p '(w_3)$ 。
第二部分用于计算 $\lambda_1，\lambda_2，\lambda_3$ ：使语言模型对留存数据的困惑度最小。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,670评论 5赞 460
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,928评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,926评论 0赞 320
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,238评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,112评论 4赞 356
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,138评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,545评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,232评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,496评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,596评论 2赞 310
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,369评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,226评论 3赞 313
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,600评论 3赞 299
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,906评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,185评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,516评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,721评论 2赞 335

自然语言处理——5.3 语言模型（数据平滑）

基本思想

困惑度定义：

数据平滑方法1——加1法(Additive smoothing )

数据平滑方法2——减值法/折扣法(Discounting)

1. 基本思想:

2. Good-Turing 估计

基本思想

举例说明

3. Back-off (后备/后退)方法

基本思想

Back-off 方法的另一种理解:

举例说明

4. 绝对减值法(Absolute discounting )

基本思想

5. 线性减值法(Linear discounting )

基本思想

绝对减值法产生的n-gram 通常优于线性减值法。

6. 四种减值法的比较

数据平滑方法3——删除插值法(Deleted interpolation)

推荐阅读更多精彩内容