《n-gram和数据平滑》由会员分享，可在线阅读，更多相关《n-gram和数据平滑（53页珍藏版）》请在金锄头文库上搜索。
1、n-gram和数据平滑 常宝宝 北京大学计算语言学研究所 chbb 语言建模(Language Modeling) 从统计角度看，自然语言中的一个句子s可以 由任何词串构成。不过P(s)有大有小。如： s1= 我 刚 吃 过 晚饭 s2= 刚 我 过 晚饭 吃 P(s1) P(s2) 对于给定的句子s而言，通常P(s)是未知的。 对于一个服从某个未知概率分布P的语言L， 根据给定的语言样本估计P的过程被称作语 言建模。 语言建模 根据语言样本估计出的概率分布P就称为语言L的语言模 型。 语言建模技术首先在语音识别研究中提出，后来陆续用 到OCR、手写体识别、机器翻译、信息检索等领域。 在语音识
2、别中，如果识别结果有多个，则可以根据语言 模型计算每个识别结果的可能性，然后挑选一个可能性 较大的识别结果。 汉语切分歧义消解？（借助语言模型） 1)(= Ls sP 语言建模 P(s) 可以有不同的形式，一般可以写成 P(s) = f(1, 2, n)，i是模型参数，一般未知 对于给定的句子s = w1w2wn，如何计算P(s)?(链式规 则 Chain rule) P(“JOHN READ A BOOK”) =p(“JOHN”)p(“READ|JOHN”) p(“A|JOHN READ”)p(“BOOK|JOHN READ A”) )()()()()( 11213121 = ll w.w|
3、wpww|wpw|wpwpsP = = l i ii w.w|wp 1 11 )( 谁是参数？ “猜猜下一个词会是哪个词” “John read a _” 给定一个句子中前面n-1个词，预测下面的 词是哪个词。 由于语言的规律性，句子中前面出现的词 对后面可能出现的词有很强的预示作用。 何谓n-gram？ p(wi|w1w2wi-1) 为了便于计算，通常考虑的历史不能太 长，一般只考虑前面n-1个词构成的历 史。即： p(wi|wi-n+1wi-1) n-gram 历史 n-gram “the large green _ .” ?“mountain”? “tree”? “Sue swallow
4、ed the large green _ .” ?“pill”? “broccoli”? 如果知道 “Sue swallowed ”会缩小可选择的下一 个词的范围。 如何选择n? n-gram n 较大时 ?提供了更多的语境信息，语境更具区别性 ?但是，参数个数多、计算代价大、训练语料 需要多、参数估计不可靠。 n 较小时 ?语境信息少，不具区别性 ?但是，参数个数少、计算代价小、训练语料 无需太多、参数估计可靠。 n-gram unigram (n=1) p(wi) 若语言中有20000个词，则需要估计20000个参 数 bigram (n=2) p(wi|wi-1) 若语言中有20000个
5、词，则需要估计200002 个参数 trigram (n=3) p(wi|wi-2wi-1) 若语言中有20000个词，则需要估计200003 个参数 four-gram(n=4) (有时也称为digram或quadrigram) 建立 n-gram 数据准备: ?确定训练语料 ?对语料进行tokenization 或切分 ?句子边界，增加两个特殊的词和 ?I eat . ? I eat . ?I sleep . ? I sleep . 参数估计 ?利用训练语料，估计模型参数 最大似然估计(MLE) 选择一组参数，使得训练样本的概率最大。 选择能使训练样本取得最大概率值的分布作为总体分布。选择
6、能使训练样本取得最大概率值的分布作为总体分布。 训练样本的概率如何定义？ 令 c(w1,wn) 表示 n-gram w1,wn在训练语料中出 现的次数。则 )( )( )( 11 1 11 n- n n-nMLE ,wwc ,wwc ,w|wwp= 最大似然估计 假定训练语料如下 JOHN READ MOBY DICK MARY READ A DIFFERENT BOOK SHE READ A BOOK BY CHER 则有 3 1 = )BOOK( c )EOSBOOK( c )BOOK|EOS(p 计算句子的概率 计算句子JOHN READ A BOOK的概率 P(JOHN READ A
7、BOOK)= p(JOHN|)p(READ|JOHN)p(A|READ)p(BOOK|A) p(|BOOK)=0.06 句子的概率表现为若干bigram参数的乘积，若句子太长， 计算时，会引起下溢(underflow)，可以采用取对数并相加 的方式。 Ln(P(JOHN READ A BOOK)= Ln(p(JOHN|)+Ln(p(READ|JOHN)+Ln(p(A|READ )+Ln(p(BOOK|A)+Ln(p(|BOOK) =Ln(1/3)+Ln(1)+Ln(2/3)+Ln(1/2)+Ln(1/2) =-2.8902 有什么用？ 数据稀疏问题(Data Sparsness) 考虑计算句子
8、CHER READ A BOOK的概率。 c(CHER READ)=0 ? p(READ|CHER)0 ? p(CHER READ A BOOK)=0 (有问题) MLE给训练样本中未观察到的事件赋以0概率。 若某n-gram在训练语料中没有出现,则该n-gram的概率必 定是0。 解决的办法是扩大训练语料的规模。但是无论怎样扩大训 练语料，都不可能保证所有的词在训练语料中均出现。 由于训练样本不足而导致所估计的分布不可靠的问题，称 为数据稀疏问题。 由于训练样本不足而导致所估计的分布不可靠的问题，称 为数据稀疏问题。 在NLP领域中，数据稀疏问题永远存在，不太可能有一个 足够大的训练语料，因
9、为语言中的大部分词都属于低频 词。 Zipf 定律 Zipf 定律描述了词频以及词在词频表中的位置之间的 关系。 针对某个语料库，若某个词w的词频是f，并且该词在 词频表中的序号为r(即w是所统计的语料中第r常用 词)，则 f r = k (k是一个常数) 若wi在词频表中排名50，wj在词频表中排名150，则wi 的出现频率大约是wj的频率的3倍。 例：马克吐温的小说 Tom Sawyer ?共 71,370 词 (word tokens) ?出现了 8,018 个不同的词 (word types) Zipf 定律 Tom Sawyer 大部分词是低频词，3993 (50%) 词(word
10、types)仅仅出现了一次 常用词极为常用，前100个高频词 占了整个文本的51% (word tokens) Zipf 定律 Zipf 定律 ?k 8000-9000 ?有例外 ?前3个最常用的词 ?r = 100 时 Zipf 定律 Tom Sawyer 第1-3章 Zipf 0 50 100 150 200 250 300 350 0500100015002000 Rank Freq Zipf定律 1998年1月 份人民日报 语料统计情 况，Zipf定 律对汉语而 言也大致成 立。 Zipf定律 Zipf定律告诉我们 ?语言中只有很少的常用词 ?语言中大部分词都是低频词(不常用的词) Z
11、ipf的解释是 Principle of Least effort (讲话的人和听话的人都想省力的平衡) ?说话人只想使用少量的常用词进行交流 ?听话人只想使用没有歧义的词(量大低频)进行交流 Zipf 定律告诉我们 ?对于语言中的大多数词，它们在语料中的出现是稀疏的 ?只有少量词语料库可以提供它们规律的可靠样本。 Balh 等人的工作 ?用150 万词的训练语料训练trigram模型 ?测试语料（同样来源）中23%的trigram没有在训练语料中 出现过。 对语言而言，由于数据稀疏的存在，MLE 不是一种很 好的参数估计办法。 解决办法: 平滑技术 ?把在训练样本中出现过的事件的概率适当减小
12、 ?把减小得到的概率密度分配给训练语料中没有出现过的事 件 ?这个过程有时也称为discounting(减值) 数据稀疏问题 平滑技术 目前已经提出了很多数据平滑技术，如： ?Add-one 平滑 ?Add-delta 平滑 ?Witten-Bell平滑 ?Good-Turing平滑 ?Church-Gale平滑 ?Jelinek-Mercer平滑 ?Katz平滑 ? Add-one 平滑(Laplaces law) 规定任何一个n-gram在训练语料至少出现一 次（即规定没有出现过的n-gram在训练语料 中出现了一次） 则:new_count(n-gram) = old_count(n-g
13、ram) + 1 没有出现过的n-gram的概率不再是0 Add-one 平滑 I want to eat Chinese food lunch Total (N) I 8 1087 0 13 0 0 0 3437 want 3 0 786 0 6 8 6 1215 to 3 0 10 860 3 0 12 3256 eat 0 0 2 0 19 2 52 938 Chinese 2 0 0 0 0 120 1 213 food 19 0 17 0 0 0 0 1506 lunch 4 0 0 0 0 1 0 459 未平滑的 bigram 频次 I want to eat Chinese f
14、ood lunch Total I .0023 (8/3437) .32 0 .0038 (13/3437) 0 0 0 1 want .0025 0 .65 0 .0049 .0066 .0049 1 to .00092 0 .0031 .26 .00092 0 .0037 1 eat 0 0 .0021 0 .020 .0021 .055 1 Chinese .0094 0 0 0 0 .56 .0047 1 food .013 0 .011 0 0 0 0 1 lunch .0087 0 0 0 0 .0022 0 1 未平滑的 bigram 概率 1stword 2ndword Add
15、-one 平滑 I want to eat Chinese food lunch Total (N+V) I 8 9 1087 1088 1 14 1 1 1 3437 5053 want 3 4 1 787 1 7 9 7 2831 to 4 1 11 861 4 1 13 4872 eat 1 1 23 1 20 3 53 2554 Chinese 3 1 1 1 1 121 2 1829 food 20 1 18 1 1 1 1 3122 lunch 5 1 1 1 1 2 1 2075 平滑后的 bigram 频次 I want to eat Chinese food lunch To
16、tal I .0018 (9/5053) .22 .0002 .0028 (14/5053) .0002 .0002 .0002 1 want .0014 .00035 .28 .00035 .0025 .0032 .0025 1 to .00082 .00021 .0023 .18 .00082 .00021 .0027 1 eat .00039 .00039 .0012 .00039 .0078 .0012 .021 1 Chinese .0016 .00055 .00055 .00055 .00055 .066 .0011 1 food .0064 .00032 .0058 .00032 .00032 .00032 .00032 1 lunch .0024 .00048 .00048 .00048 .00048 .0022 .00048 1 平滑后的 bigram 概率 p(w1|w2) Add
