MIT自然语言处理第三讲：概率语言模型（第五部分）

自然语言处理：概率语言模型
Natural Language Processing: Probabilistic Language Modeling
作者：Regina Barzilay（MIT,EECS Department, November 15, 2004)
译者：我爱自然语言处理（www.52nlp.cn ，2009年2月10日）

五、 Good-Turing打折法（Good-Turing Discounting）
a) 你在将来看到一个新词的可能性有多大？用所看到的事件去估计未知事件的概率（How likely are you to see a new word type in the future? Use things you’ve seen once to estimate the probability of unseen things）
　i. n_r——频率为r的元素（n元语法）计数并且r>0（number of elements with r frequency and r>0）
　ii. n_0——总词汇规模减去观察到的词汇规模，既出现次数为0的n元语法（size of the total lexicon minus the size of observed lexicon）
　iii. 对于频率为r的元素，修正计数为（Modified count for elements with frequency r）：
　　　　　　　　r^* = (r+1)*{n_{r+1}/n_r}
b) 关于Good-Turing打折法的补充说明：
　i. Good(1953)首先描述了Good-Turing算法，而这种算法的原创思想则来自Turing 。
　ii. Good-Turing平滑的基本思想是：用观察较高的N元语法数的方法来重新估计概率量的大小，并把它指派给那些具有零计数或较低计数的N元语法。
c) 直观的Good-Turing打折法（Good-Turing Discounting: Intuition）
　i. 目的（Goal）: 估计训练数据中计数为r的单词在同样规模测试集中的出现频率（estimate how often word with r counts in training data occurs in test set of equal size）。
　ii. 我们使用删除估计（We use deleted estimation）：
　　1. 每次删除一个单词（delete one word at a time）
　　2. 如果单词“test”在所有的数据集中出现了r+1次（if “test” word occurs r +1 times in complete data set）：
　　——它在训练集中出现了r 次（it occurs r times in “training” set）
　　——对计数为r的单词加1（add one count to words with r counts）
　iii. r-count单词“桶”中的总的计数为（total count placed to bucket for r-count words is）:
　　　　　　　　　n_{r+1}*(r +1)
　iv. 平均计数为：
　　　　　　(avg-count of r count words) = {n_{r+1}*(r+1)}/n_r
d) Good-Turing打折法续（Good-Turing Discounting (cont.)）：
　i. 在Good-Turing中，分配给所有未知事件的总的概率等于n_1/N, 其中N是训练集的规模。它与分配给独立事件的相对频率公式相似。
　ii. In Good-Turing, the total probability assigned to all the unobserved events is equal to n_1/N , where N is the size of the training set. It is the same as a relative frequency formula would assign to singleton events.
e) 举例（Example: Good-Turing）
Training sample of 22,000,000 (Church&Gale’1991))
r 　　　N_r　　　　　　　heldout　　r^*
0 　　74,671,100,000　0.00027　0.00027
1 　　2,018,046　　　　0.448　　0.446
2 　　449,721　　　　　1.25　　　1.26
3 　　188,933　　　　　2.24　　　2.24
4 　　105,668　　　　　3.23　　　3.24
5 　　68,379　　　　　 4.21　　 　4.22
6 　　48,190　　　　　 5.23　　 　5.19
f) 补充说明：
　i. 根据Zipf定律,对于小的r, N_r比较大;对于大的r,N_r小,对于出现次数最多的n元组,r*=0!
　ii. 所以对于出现次数很多的n元组, GT估计不准,而MLE估计比较准,因此可以直接采用MLE. GT估计一般适用于出现次数为k(k<10)的n元组 　iii. 如果这样,考虑”劫富济贫”,这里的”富”就变成了”中产”阶级!呵呵,真正的富翁沾光了!（虽然富翁损一点也没什么）连打折法也不敢欺富人！这就是“为富不仁”，“一毛不拔”的来历。 未完待续：第六部分

附：课程及课件pdf下载MIT英文网页地址：
　　　http://people.csail.mit.edu/regina/6881/

注：本文遵照麻省理工学院开放式课程创作共享规范翻译发布，转载请注明出处“我爱自然语言处理”：www.52nlp.cn

本文链接地址：https://www.52nlp.cn/mit-nlp-third-lesson-probabilistic-language-modeling-fifth-part/