最大熵模型

最大熵模型与自然语言处理MaxEntModel&[e-mail],AILab,TsinghuaUniv.Topics•NLP与随机过程的关系（背景）•最大熵模型的介绍（熵的定义、最大熵模型）•最大熵模型的解决（非线性规划、对偶问题、最大似然率）•特征选取问题•应用实例•总结与启发NLP与随机过程NLP:已知一段文字：x1x2…xn（n个词）标注词性y1y2…yn标注过程：已知：x1x2…xn求：y1已知：x1x2…xny1求：y2已知：x1x2…xny1y2求：y3已知：x1x2…xny1y2y3求：y4…NLP与随机过程yi可能有多种取值，yi被标注为a的概率有多少?随机过程：一个随机变量的序列。x1x2…xnp(y1=a|x1x2…xn)x1x2…xny1p(y2=a|x1x2…xny1)x1x2…xny1y2p(y3=a|x1x2…xny1y2)x1x2…xny1y2y3p(y4=a|x1x2…xny1y2y3)…NLP与随机过程x1x2…xnp(y1=a|x1x2…xn)x1x2…xny1p(y2=a|x1x2…xny1)x1x2…xny1y2p(y3=a|x1x2…xny1y2)x1x2…xny1y2y3p(y4=a|x1x2…xny1y2y3)…问题：•p(yi=a|x1x2…xny1y2…yi-1)怎么求?•yi与x1x2…xny1y2…yi-1的关系?NLP与随机过程问题：•p(yi=a|x1x2…xny1y2…yi-1)怎么求?•yi与x1x2…xny1y2…yi-1的关系?)....()....,()....|(111111nnnninniyyxxpyyxxaypyyxxayp一个直观的解决：问题again!•(x1x2…xny1y2…yi-1)？What’sEntropy?AnExample：•假设有5个硬币：1,2,3,4,5，其中一个是假的，比其他的硬币轻。有一个天平，天平每次能比较两堆硬币，得出的结果可能是以下三种之一：•左边比右边轻•右边比左边轻•两边同样重问：至少要使用天平多少次才能保证找到假硬币?（某年小学生数学竞赛题目:P）称硬币(cont.)•答案：2次•一种方法：•Why最少2次?1+2?3+41?23?4514=23称硬币(cont.)•Let:x是假硬币的序号：•Let:yi是第i次使用天平所得到的结果：•用天平称n次，获得的结果是：y1y2…yn•y1y2…yn的所有可能组合数目是3n•我们要通过y1y2…yn找出x。所以：每个y1y2…yn组合最多可能有一个对应的x取值。•因为x取X中任意一个值的时候，我们都要能够找出x，因此对于任意一个x的取值，至少要有一个y1y2…yn与之对应。根据鸽笼原理……5,4,3,2,1Xx表示；表示；表示其中321:3..1YyiXYn称硬币(cont.)•Let:x是假硬币的序号：•Let:Yi是第i次使用天平所得到的结果：•用y1y2…yn表达x。即设计编码：x-y1y2…yn•X的“总不确定度”是：•Y的“表达能力”是：•至少要多少个Y才能准确表示X？5,4,3,2,1Xx表示；表示；表示其中321:3..1Yyi5loglogXXH3loglogYYH46.13log5log)(YHXH称硬币(cont.)•Why???•为什么用log?•“表达能力”与“不确定度”的关系？5loglogXXH3loglogYYH46.13log5log)(YHXH称硬币(cont.)为什么用log?•假设一个Y的表达能力是H(Y)。显然，H(Y)与Y的具体内容无关，只与|Y|有关。•两个Y(就是：y1y2)的表达能力是多少?•y1可以表达三种情况，y2可以表达三种情况。两个并列，一共有：3*3=9种情况（乘法原理）。因此：YYYYYYHYHYHyHyH注意：)()()(21称硬币(cont.)“表达能力”与“不确定度”的关系？•都表达了一个变量所能变化的程度。在这个变量是用来表示别的变量的时候，这个程度是表达能力。在这个变量是被表示变量的时候，这个程度是不确定度。而这个可变化程度，就是一个变量的熵（Entropy）。•显然：熵与变量本身含义无关，仅与变量的可能取值范围有关。46.13log5log)(YHXH称硬币-Version.2假设有5个硬币：1,2,3,…5，其中一个是假的，比其他的硬币轻。已知第一个硬币是假硬币的概率是三分之一；第二个硬币是假硬币的概率也是三分之一，其他硬币是假硬币的概率都是九分之一。有一个天平，天平每次能比较两堆硬币，得出的结果可能是以下三种之一：•左边比右边轻•右边比左边轻•两边同样重假设使用天平n次找到假硬币。问n的期望值至少是多少？（不再是小学生问题:P）称硬币-Version.2因为第一个、第二个硬币是假硬币的概率是三分之一，比其他硬币的概率大，我们首先“怀疑”这两个。第一次可以把这两个做比较。成功的概率是三分之二。失败的概率是三分之一。如果失败了，第二次称剩下的三个。所以，期望值是：343log9log9133log3log3131称硬币-Version.2《数据结构》：Huffman编码问题。51/911/341/921/331/9称硬币-Version.2《数据结构》：Huffman编码问题。3?51/351/911/341/921/331/9称硬币-Version.2《数据结构》：Huffman编码问题。1?23?51/351/911/341/921/331/9用反证法可以证明，这个是最小值。（假设第一个和第二个硬币中有一个要称两次的话……）称硬币-Version.2《数据结构》：Huffman编码问题。1?23?51/351/911/341/921/331/91/91/91/91/91/91/9343log9log9133log3log3131称硬币-Version.3,4,…∞更广泛地：如果一个随机变量x的可能取值为X={x1,x2,…,xk}。要用n位y:y1y2…yn表示（每位y有c种取值）n的期望值至少为：kiiixxpxxpXH11log一般地，我们令c为2（二进制表示），于是，X的信息量为：cxxpxxpcxxpxxpkiiikiiilog1loglog1log11What’sEntropy?•定义:•X的具体内容跟信息量无关，我们只关心概率分布，于是H(X)可以写成：kiiixxpxxpXH11logXxxpxpXH1log熵的性质•第一个等号在X为确定值的时候成立（没有变化的可能）•第二个等号在X均匀分布的时候成立。XXHlog0熵的性质•证明：)(0XH001log01log01log1101:1logXHxpxpxpxpxpxpxpxxpxpXHXxXx即熵的性质•证明：详细证明略。求条件极值就可以证明了（求偏导数，条件是：所有的概率之和为1）结论：均匀分布的时候，熵最大XXHlog)(ConditionalEntropy•有两个变量：x,y。它们不是独立的。已知y，x的不确定度又是多少呢?YXyxyxpyxpYXH,|1log,|)()()|(YHXYHYXH)()|(XHYXHConditionalEntropy•ConditionReducesEntropy(C.R.E.)•知识（Y）减少不确定性（X）•证明（略）。用文氏图说明：)()|(XHYXHXY(X&Y)I:CompleteKnowledgeSpace已知与未知的关系对待已知事物和未知事物的原则：•承认已知事物（知识）；•对未知事物不做任何假设，没有任何偏见已知与未知的关系—例子已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语……令x1表示“学习”被标为名词，x2表示“学习”被标为动词。令y1表示“学习”被标为主语，y2表示被标为谓语，y3表示宾语，y4表示定语。得到下面的表示：5.0)()(21xpxp如果仅仅知道这一点，根据无偏见原则，“学习”被标为名词的概率与它被标为动词的概率相等。1)()(21xpxp1)(41iiyp25.0)()()()(4321ypypypyp已知与未知的关系—例子已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语……“学习”被标为定语的可能性很小，只有0.055.0)()(21xpxp除此之外，仍然坚持无偏见原则：05.0)(4yp我们引入这个新的知识：1)()(21xpxp1)(41iiyp395.0)()()(321ypypyp已知与未知的关系—例子已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语……“学习”被标为定语的可能性很小，只有0.05当“学习”被标作动词的时候，它被标作谓语的概率为0.95除此之外，仍然坚持无偏见原则，我们尽量使概率分布平均。但问题是：什么是尽量平均的分布？05.0)(4yp引入这个新的知识：1)()(21xpxp1)(41iiyp95.0)|(12xyp最大熵模型MaximumEntropy•概率平均分布〈=〉熵最大•我们要一个x和y的分布，满足：•同时使H(Y|X)达到最大值1)()(21xpxp1)(41iiyp05.0)(4yp95.0)|(12xyp最大熵模型MaximumEntropy95.0)|(05.0)(1)()()()(1)()()|(1log),()|(max124432121,,,,432121xypypypypypypxpxpxypyxpXYHyyyyyxxx最大熵模型MaximumEntropyWhatisConstraints?--模型要与已知知识吻合Whatisknown?--训练数据集合一般模型：P={p|p是X上满足条件的概率分布}yxPpxypyxpXYH,)|(1log),()|(max特征(Feature)特征：(x,y)y:这个特征中需要确定的信息x:这个特征中的上下文信息注意一个标注可能在一种情况下是需要确定的信息，在另一种情况下是上下文信息：x1x2…xnp(y1=a|x1x2…xn)x1x2…xny1p(y2=a|x1x2…xny1)样本(Sample)关于某个特征(x,y)的样本--特征所描述的语法现象在标准集合里的分布：(xi,yi)pairsyi是y的一个实例xi是yi的上下文(x1,y1)(x2,y2)(x3,y3)……特征与样本已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语……“学习”被标为定语的可能性很小，只有0.05特征：当“学习”被标作动词的时候，它被标作谓语的概率为0.95x是什么?y是什么?样本是什么?特征与样本已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语……特征：“学习”被标为定语的可能性很小，只有0.05当“学习”被标作动词的时候，它被标作谓语的概率为0.95x是什么?y是什么?样本是什么?特征与样本特征函数：对于一个特征(x0,y0)，定义特征函数：特征函数期望值：对于一个特征(x0,y0)，在样本中的期望值是：：其他情况而且：如果0xy1),(00xyyxfiiyxyxfyxpfp,),(),()(是(x,y)在样本中出现的概率),(yxp条件（Constraints）条件：对每一个特征(x,y)，模型所建立的条件概率分布要与训练样本表现出来的