最大熵模型matlab应用课件.ppt

1、Topics NLP与随机过程的关系（背景）最大熵模型的介绍（熵的定义、最大熵模型）最大熵模型的解决（非线性规划、对偶问题、最大似然率）特征选取问题 应用实例 总结与启发NLP与随机过程NLP:已知一段文字：x1x2xn（n个词）标注词性y1y2yn标注过程：已知：x1x2xn求：y1已知：x1x2xn y1求：y2已知：x1x2xn y1 y2求：y3已知：x1x2xn y1 y2 y3求：y4NLP与随机过程yi可能有多种取值，yi被标注为a的概率有多少?随机过程：一个随机变量的序列。x1x2xnp(y1=a|x1x2xn)x1x2xn y1p(y2=a|x1x2xn y1)x1x2xn

2、y1 y2p(y3=a|x1x2xn y1 y2)x1x2xn y1 y2 y3p(y4=a|x1x2xn y1 y2 y3)NLP与随机过程x1x2xnp(y1=a|x1x2xn)x1x2xn y1p(y2=a|x1x2xn y1)x1x2xn y1 y2p(y3=a|x1x2xn y1 y2)x1x2xn y1 y2 y3p(y4=a|x1x2xn y1 y2 y3)问题：p(yi=a|x1x2xn y1y2yi-1)怎么求?yi与x1x2xn y1y2yi-1的关系?NLP与随机过程问题：p(yi=a|x1x2xn y1y2yi-1)怎么求?yi与x1x2xn y1y2yi-1的关系?)

3、.().,().|(111111nnnninniyyxxpyyxxaypyyxxayp一个直观的解决：问题again!(x1x2xn y1y2yi-1)？Whats Entropy?An Example：假设有5个硬币：1,2,3,4,5，其中一个是假的，比其他的硬币轻。有一个天平，天平每次能比较两堆硬币，得出的结果可能是以下三种之一：左边比右边轻 右边比左边轻 两边同样重问：至少要使用天平多少次才能保证找到假硬币?（某年小学生数学竞赛题目:P）称硬币(cont.)答案：2次 一种方法：Why最少2次?1+2?3+41?23?4514=23称硬币(cont.)Let:x是假硬币的序号：Let:

4、yi是第i次使用天平所得到的结果：用天平称n次，获得的结果是：y1 y2 yn y1 y2 yn的所有可能组合数目是3n 我们要通过y1 y2 yn找出x。所以：每个y1 y2 yn组合最多可能有一个对应的x取值。因为x取X中任意一个值的时候，我们都要能够找出x，因此对于任意一个x的取值，至少要有一个y1 y2 yn与之对应。根据鸽笼原理5,4,3,2,1 Xx表示；表示；表示其中321:3.1YyiXYn称硬币(cont.)Let:x是假硬币的序号：Let:Yi是第i次使用天平所得到的结果：用y1 y2 yn表达x。即设计编码：x-y1 y2 yn X的“总不确定度”是：Y的“表达能力”是：

5、至少要多少个Y才能准确表示X？5,4,3,2,1 Xx表示；表示；表示其中321:3.1Yyi5loglogXXH 3loglogYYH 46.13log5log)(YHXH称硬币(cont.)Why?为什么用log?“表达能力”与“不确定度”的关系？5loglogXXH 3loglogYYH 46.13log5log)(YHXH称硬币(cont.)为什么用log?假设一个Y的表达能力是H(Y)。显然，H(Y)与Y的具体内容无关，只与|Y|有关。两个Y(就是：y1y2)的表达能力是多少?y1可以表达三种情况，y2可以表达三种情况。两个并列，一共有：3*3=9种情况（乘法原理）。因此：YYYYY

6、YHYHYHyHyH注意：)()()(21称硬币(cont.)“表达能力”与“不确定度”的关系？都表达了一个变量所能变化的程度。在这个变量是用来表示别的变量的时候，这个程度是表达能力。在这个变量是被表示变量的时候，这个程度是不确定度。而这个可变化程度，就是一个变量的熵（Entropy）。显然：熵与变量本身含义无关，仅与变量的可能取值范围有关。46.13log5log)(YHXH称硬币-Version.2假设有5个硬币：1,2,3,5，其中一个是假的，比其他的硬币轻。已知第一个硬币是假硬币的概率是三分之一；第二个硬币是假硬币的概率也是三分之一，其他硬币是假硬币的概率都是九分之一。有一个天平，天平

7、每次能比较两堆硬币，得出的结果可能是以下三种之一：左边比右边轻 右边比左边轻 两边同样重假设使用天平n次找到假硬币。问n的期望值至少是多少？（不再是小学生问题:P）称硬币-Version.2因为第一个、第二个硬币是假硬币的概率是三分之一，比其他硬币的概率大，我们首先“怀疑”这两个。第一次可以把这两个做比较。成功的概率是三分之二。失败的概率是三分之一。如果失败了，第二次称剩下的三个。所以，期望值是：343log9log9133log3log3131称硬币-Version.2数据结构：Huffman编码问题。51/911/341/921/331/9称硬币-Version.2数据结构：Huffman

8、编码问题。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:y1y2yn表示（每位y有c种取

9、值）n的期望值至少为：kiiixxpxxpXH11log一般地，我们令c为2（二进制表示），于是，X的信息量为：cxxpxxpcxxpxxpkiiikiiilog1loglog1log11Whats Entropy?定义:X的具体内容跟信息量无关，我们只关心概率分布，于是H(X)可以写成：kiiixxpxxpXH11log XxxpxpXH1log熵的性质 第一个等号在X为确定值的时候成立（没有变化的可能）第二个等号在X均匀分布的时候成立。XXHlog0熵的性质 证明：)(0XH 001log01log01log1101:1logXHxpxpxpxpxpxpxpxxpxpXHXxXx即熵的性质

10、 证明：详细证明略。求条件极值就可以证明了（求偏导数，条件是：所有的概率之和为1）结论：均匀分布的时候，熵最大XXHlog)(Conditional Entropy 有两个变量：x,y。它们不是独立的。已知y，x的不确定度又是多少呢?YXyxyxpyxpYXH,|1log,|)()()|(YHXYHYXH)()|(XHYXHConditional Entropy Condition Reduces Entropy(C.R.E.)知识（Y）减少不确定性（X）证明（略）。用文氏图说明：)()|(XHYXHXY(X&Y)I:Complete KnowledgeSpace已知与未知的关系对待已知事物和

11、未知事物的原则：承认已知事物（知识）；对未知事物不做任何假设，没有任何偏见已知与未知的关系例子已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语令x1表示“学习”被标为名词，x2表示“学习”被标为动词。令y1表示“学习”被标为主语，y2表示被标为谓语，y3表示宾语，y4表示定语。得到下面的表示：5.0)()(21xpxp如果仅仅知道这一点，根据无偏见原则，“学习”被标为名词的概率与它被标为动词的概率相等。1)()(21xpxp1)(41iiyp25.0)()()()(4321ypypypyp已知与未知的关系例子已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、

12、宾语、定语“学习”被标为定语的可能性很小，只有0.055.0)()(21xpxp除此之外，仍然坚持无偏见原则：05.0)(4yp我们引入这个新的知识：1)()(21xpxp1)(41iiyp395.0)()()(321ypypyp已知与未知的关系例子已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语“学习”被标为定语的可能性很小，只有0.05当“学习”被标作动词的时候，它被标作谓语的概率为0.95除此之外，仍然坚持无偏见原则，我们尽量使概率分布平均。但问题是：什么是尽量平均的分布？05.0)(4yp引入这个新的知识：1)()(21xpxp1)(41iiyp95.0)|(1

13、2xyp最大熵模型Maximum Entropy 概率平均分布=熵最大 我们要一个x和y的分布，满足：同时使H(Y|X)达到最大值1)()(21xpxp1)(41iiyp05.0)(4yp95.0)|(12xyp最大熵模型Maximum Entropy95.0)|(05.0)(1)()()()(1)()()|(1log),()|(max124432121,432121xypypypypypypxpxpxypyxpXYHyyyyyxxx最大熵模型Maximum EntropyWhat is Constraints?-模型要与已知知识吻合What is known?-训练数据集合一般模型：P=p|

14、p是X上满足条件的概率分布yxPpxypyxpXYH,)|(1log),()|(max特征(Feature)特征：(x,y)y:这个特征中需要确定的信息x:这个特征中的上下文信息注意一个标注可能在一种情况下是需要确定的信息，在另一种情况下是上下文信息：x1x2xnp(y1=a|x1x2xn)x1x2xn y1p(y2=a|x1x2xn y1)样本(Sample)关于某个特征(x,y)的样本-特征所描述的语法现象在标准集合里的分布：(xi,yi)pairsyi是y的一个实例xi是yi的上下文(x1,y1)(x2,y2)(x3,y3)特征与样本已知：“学习”可能是动词，也可能是名词。可以被标为主语

15、、谓语、宾语、定语“学习”被标为定语的可能性很小，只有0.05特征：当“学习”被标作动词的时候，它被标作谓语的概率为0.95x是什么?y是什么?样本是什么?特征与样本已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语特征：“学习”被标为定语的可能性很小，只有0.05当“学习”被标作动词的时候，它被标作谓语的概率为0.95x是什么?y是什么?样本是什么?特征与样本特征函数：对于一个特征(x0,y0)，定义特征函数：特征函数期望值：对于一个特征(x0,y0)，在样本中的期望值是：其他情况而且：如果0 xy1),(00 xyyxfiiyxyxfyxpfp,),(),()(是(x

16、,y)在样本中出现的概率),(yxp条件（Constraints）条件：对每一个特征(x,y)，模型所建立的条件概率分布要与训练样本表现出来的分布相同。出现的概率xxp)(在样本中的期望值特征ffp)(假设样本的分布是（已知）：出现的概率xyyxp),(特征f在模型中的期望值：iiiiiiyxiiiiiyxiiiiiyxiiiiyxfxpxypyxfxpxypyxfyxpfp,|,|,)()()(fpfp最大熵模型Maximum Entropy)|(*maxargXYHpPpNLP模型：P=p|p是y|x的概率分布并且满足下面的条件对训练样本，对任意给定的特征fi：)()(iifpfp最大熵模

17、型Maximum Entropy yyxiyxiixypxyxfyxpyxfxpxypfxypP1|:),(,),(|:|,NLP模型：yxPpxypxpxypp,|1log|*maxarg最大熵模型的解决问题：已知若干条件，要求若干变量的值使到目标函数（熵）最大数学本质：最优化问题（Optimization Problem）条件：线性、等式 目标函数：非线性非线性规划（线性约束）(non-linear programming with linear constraints)非线性规划基本概念Nonlinear Programming 解决的思路：非线性规划问题（带约束）（拉格朗日法）-非线性

18、规划问题（不带约束Unconstrained Problem）（求偏导数法）-解决不带约束求解问题（解方程）-求出原问题的解法非线性规划基本概念Nonlinear Programmingp:m维向量；H(p):关于p的非线性函数A:n*m常数矩阵；b:n维向量bAppH)(max如何去掉约束？抽象问题：假设：A的行向量线性无关。bAp 确定了m维空间里面n个方向上（就是与Ap=b确定的m-n个方向“垂直”的n个方向）的取值。p只能在剩下的r=m-n个方向上面移动。非线性规划基本概念Nonlinear ProgrammingbAp 假设Z是跟Ap=b垂直的方向量。Z:m*(m-n)常数矩阵)bp

19、AZvpp就是p能够自由活动的所有空间了。v:m-n维变量于是有：00:AZZvAbZvpAv非线性规划基本概念Nonlinear Programmingp:m维向量；H(p):关于p的非线性函数A:n*m常数矩阵；b:n维向量bAppH)(max如何去掉约束？抽象问题：0AZbpAZvpp)(maxZvpHZ:m*(m-n)常数矩阵v:m-n维变量 极值条件)(maxZvpHZ:m*(m-n)常数矩阵v:m-n维变量是正定矩阵而且0)(0)(*2*vHvH0AZbpAZvpp极值条件：ZpHZvHpHZvHTT)()();()(*2*2*把 分解成Z方向向量和A方向向量：)(*pHTAZvp

20、H)(*极值条件Z:m*(m-n)常数矩阵v:m-n维变量0AZbpAZvpp0000ZvZvZAZAZZvZTTTT00)()()(*TTTTTAZZvZpHZvHAZvpHTTAxHZvAZvpH)(0)(*极值条件0)()(*pLApHT p:m维向量；H(p):关于p的非线性函数 A:n*m常数矩阵；b:n维向量bAppH)(max令：假设：A的行向量线性无关。AppHpL)()(*)()()(*AppHApHT拉格朗日算子Lagrange Multiplier 一般地，对于k个限制条件的Constrained Optimization问题：)(maxpH iibpCki:1 拉格朗日

21、函数为：kiiiibpCpHpL1,其中引入的拉格朗日算子：Tk,.,1拉格朗日算子Lagrange MultiplierTk,.,1bAppH)(max kiiiiibpCpHpL1,0pL拉格朗日函数1|),()()|(),()|(1log)()|(0),(),(yiyxiiyxxypyxpxpxypyxfxypxpxypL yyxiyxiixypxyxfyxpyxfxpxypfxypP1|:),(,),(|:|,yxPpxypxpxypp,|1log|*maxarg可能的最优解（Exponential）1|),()()|(),()|(1log)()|(01),(),(ykiyxiiyxx

22、ypyxpxpxypyxfxypxpxypLiiiyxfxpxypxpxypL0),()()1)|(1)(log()|(1)(),(0)|(*xpyxfiiiexyp最优解的存在性0),()()1)|(1)(log()|(0iiiyxfxpxypxpxypL1)(),(0)|(*xpyxfiiiexyp0)|()()|(22xypxpxypL一阶导数为零，二阶导数小于零，所得到的是最大值！最优解形式（Exponential）1)(),(0)|(*xpyxfiiiexypiiiyxfcexyp),()|(*yyxfiiiec),(1yyxfiiice1),(最优解（Exponential）iii

23、yxfcexyp),()|(*yyxfiiiec),(1iiiyxfexZxyp),()(1)|(*yyxfiiiexZ),()(?i最优解（Exponential）能不能找到另一种逼近？比如等价成求某个函数 的最大/最小值？?几乎不可能有解析解（包含指数函数）近似解不代表接近驻点。)(f对偶问题Duality对偶问题的引入。Alice和Bob的游戏：l 有一个2*2的矩阵。每次Alice挑一个数x(x=1或者2)，Bob也挑一个数y(y=1或者2)。两人同时宣布所挑的数字。然后看Cx,y是多少，Bob要付Alice Cx,y块钱。（如果Cx,y 是负数，Alice 给Bob钱）。矩阵如下：3

24、421C对偶问题Alice vs Bob假设：Alice和Bob都是聪明而贪得无厌的人。而且他们都清楚对方也很聪明和很贪心。Alice的策略：找一个x，无论Bob怎么挑y，Cx,y 要尽量大。Bob的策略：找一个y，无论Alice怎么挑x，Cx,y 要尽量小。yxCAliceBobyBobxAliceC,:3421双方都很聪明：双方都对对方有“最坏打算”yxxyC,maxminyxyxC,minmax对偶问题Alice vs BobyxCAliceBobyBobxAliceC,:3421yxxyCy,maxminarg*yxyxCx,minmaxarg*Alice的选择：x*=2 Bob的选择

25、：y*=231min,yxyC34max,yxxC3:2,2CAliceBobAlice vs Bob Version.2yxCAliceBobyBobxAliceC,:2421yxxyCy,maxminarg*yxyxCx,minmaxarg*Alice的选择：x*=1 Bob的选择：y*=221min,yxyC24max,yxxC2:2,1CAliceBob对偶问题Alice vs BobVersion 1:Alice的估计=结果=Bob的估计Version 2:Alice的估计结果=Bob的估计一般情况:Alice的估计=结果=Bob的估计yxxyyxyxCC,maxminminmax定

26、理：当存在马鞍点（Saddle Point）的时候，等号成立。并且结果=马鞍点的值。马鞍点：yxyxyxCCCyx*,*,*,|*)*,(非线性规划中的对偶问题)(maxpH iibpCki:1拉格朗日函数：kiiiibpCpHpL1,于是：,minmaxpLp iiiibpCibpCipHpL:,min因此，为了尽量大，p的选取必须保证满足约束ppHpLp|)(max,minmax iibpCki:1考虑：对偶问题与拉格朗日函数：)(maxpH iibpCki:1同时：kiiiipbpCpHpL1,minmax等价于：,maxmin,minmaxpLpLpp而*,maxpLpLpiiiyxf

27、exZxyp),()(1)|(*对偶问题与拉格朗日函数：*,min,maxmin,minmaxmaxppLpLpLpHpp满足约束iiiyxfexZxyp),()(1)|(*?梯度递减法 xyxyxyxyxkiyxiixZxpyxyxpyxyxpxZxypxpyxyxpyxxZyxxypxpyxyxpyxxypxypxpyxpxypxpyxfpHpLlog,log|,log,|,|log|,|,*,1,把p*代入L，得到：令：kiiiyxfyx1,梯度递减法求导，计算-L的梯度：xyxxZxpyxyxppLlog,*,kiiiyxfyx1,xyjipxyjyxfyxixiyxixyxkjjji

28、iyxfxypxpfEyxfexZxpyxfyxpxZxZxpyxfyxpxZxpyxfyxpLkjjj,|*,1,1,log,1,1yyxfiiiexZ),()(梯度递减法递推公式：yxjipiyxfxypxpfEL,|*yxjipniniyxfxypxpfEc,1,|*收敛问题最大似然率 Maximum Likelihood 最大似然率：找出与样本的分布最接近的概率分布模型。简单的例子。10次抛硬币的结果是：画画字画画画字字画画假设p是每次抛硬币结果为“画”的概率。则：得到这样的实验结果的概率是：371111ppppppppppppP最大似然率 Maximum Likelihood 最大似

29、然率：找出与样本的分布最接近的概率分布模型。371ppP37101maxmaxppPp 最优解是：p=0.7 似然率的一般定义：xxppxpL 是实验结果的分布模型是估计的概率分布xpxp最大似然率 Maximum Likelihood 似然率的一般定义：xxppxpL 似然率的对数形式：xxxppxpxpxpLloglog 是实验结果的分布模型是估计的概率分布xpxp最大似然率 Maximum Likelihood 在NLP里面，要估计的是：语法标注上下文:|yxxyp 似然率是：yxyxyxyxpxpyxpxypyxpxypxpyxpyxpyxppL,log,|log,|log,log,是

30、常数，可以忽略 yxxypxpyxp,|log,最大似然率 Maximum Likelihood 在NLP里面，要估计的是：语法标注上下文:|yxxyp 似然率可以定义为：yxpxypyxppL,|log,通过求值可以发现，如果p(y|x)的形式是最大熵模型的形式的话，最大熵模型与最大似然率模型一致。最大似然率 yxxyxyxyxyxyxpxZxpyxyxpxZeyxpxZeyxpxypyxppL,log,loglog,log,|log,kiiiyxfyx1,为书写方便，令：xZyxexZxyp,1|最大似然率 xyxyxyxyxkiyxiixZxpyxyxpyxyxpxZxypxpyxyxp

31、yxxZyxxypxpyxyxpyxxypxypxpyxpxypxpyxfpHpLlog,log|,log,|,|log|,|,*,1,最大似然率 Maximum Likelihood *,log,pLxZxpyxyxppLxyxp*,min*,maxmaxpLpLpLp 结论：最大熵的解（无偏见地对待不确定性）同时是最吻合样本数据分布的解。进一步证明了最大熵模型的合理性。偶然？必然？“It so happens that”?熵：不确定度似然率：与知识的吻合度最大熵：对不确定度的无偏见分配最大似然率：对知识的无偏见理解知识不确定度的补集知识不确定度的补集满足约束条件的模型集合P指数模型集合Q（

32、最大熵）最大似然率方向（满足约束条件）最大熵方向特征选取问题问题：所有知识可信吗？所有知识都有用吗？太多知识怎么办？在NLP里面：上下文信息可以很多很多种，那些是有用呢？特征选取问题Remind:“熵是描述不确定度的”“知识是不确定度的补集”不确定度越小，模型越准确。直观的过程：什么特征都不限定：熵最大 加一个特征：熵少一点（C.R.E.）加的特征越多，熵越少特征选取算法 目标：选择最有用的个特征（知识）“最”？全局的最优解几乎不可能 可行的方法：逐步选择最有用的信息。每一步用“贪心”原则：挑选“现在看来”最有用的那个特征。“有用？”使到走这一步后熵减少最多算法步骤 有效特征集合E=/这个时候

33、p均匀分布 计算最大熵H(p*)。显然：对以下步骤循环K次：对每个不在E里面的特征fi，把E+fi作为有效特征，计算最大熵Hi(pi*)；假设Hm(pm*)最小，则：E=E+fm。pHpH*敏感度分析与特征提取Sensitivity How to work on insufficient data set?最终结论应该是约束条件越确定（_p(x)越大），lambda越大。应用实例Adwait Ratnaparkhis“Learning to Parse Natural Language with Maximum Entropy Models”创新点：用MaxEnt模型辅助Shift-reduc

34、e Parsing应用实例Parser的特点：三层ParserK-BFS搜索每层只搜索最好的K个方案(derivations)“最好”：概率最大概率：最大熵模型得到的概率分布应用实例数据流：标注Part ofSpeach标注ChunkBuild或者Check原始文本POS原始文本POSChunk标注：Start X/Join X/Other原始文本最终的语块应用实例概率：最大熵模型得到的概率分布l 事先对每类Parsing都训练一个最大熵模型。l 得到概率分布：pX*(a|c)。a是action，c是上下文。X可能是：l TAG,CHUNK,BUILD/CHECKl 最优解求法：GIS（Gen

35、eral Iterative Scaling Algorithm“一般梯度算法”？）l 特征选取：只取出现次数大于等于5的所有特征（比较简单，但因此计算量也少多了）应用实例 实验结果：Upenn的Corpus作为训练集合Wall Street Journal上的句子作为测试对象准确率：90%左右应用实例分析：三层Parser功不可没（上层Parser看到的是下层Parser的所有信息包括处理点之前和之后的信息）MaxEnt模型提供了比较准确的评价模型（不然三层Parser会比单层Parser引起更大的误差累积，“失之毫厘谬以千里”）相关项目 CMU:Adam Berger U Penn:Adw

36、ait Ratnaparkhi Source Forge:opennlp.MAXENT 总结与启发 MaxEnt已经是比较成功的一个NLP模型，并获得广泛应用 从信息论获得启发（1948-）：自然语言处理也是信息处理的一种。语法标注也可以看作一种编码的过程?对偶问题：从另一个角度看问题 可能从不同领域获得的启发。（概率论与随机过程、最优化问题、图形学）“All Models are wrong.Some are useful.”参考文献A maximum entropy approach to natural language processing(Adam Berger)A Brief Ma

37、xEnt Tutorial(Adam Berger)Learning to parse natural language with maximum entropy models(Adwait Ratnaparkhi)A simple Introduction to Maximum Entropy Models for Natural Language Processing(Adwait Ratnaparkhi)参考文献(Cont)Elements of Information Theory(Cover&Thomas)Linear and Nonlinear Programming(Nash&Sofer)高等数学 运筹学 数据结构谢谢！