最大熵模型最大熵模型最大熵模型最大熵模型与与与与自然语言处理自然语言处理自然语言处理自然语言处理MaxEntMaxEnt Model & NLP Model & NLP laputalaputac-liu01mails.tsinghua.edu.cnc-liu01mails.tsinghua.edu.cnNLP Group, AI Lab, NLP Group, AI Lab, TsinghuaTsinghua Univ. Univ.TopicsNLP与随机过程的关系（背景）最大熵模型的介绍（熵的定义、最大熵模型）最大熵模型的解决（非线性规划、对偶问题、最大似然率）特征选取问题应用实例总结与启发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 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的关系?一个直观的解决：问题again!(x1x2xn y1y2yi-1)？Whats Entropy?An Example：假设有5个硬币：1,2,3,4,5，其中一个是假的，比其他的硬币轻。有一个天平，天平每次能比较两堆硬币，得出的结果可能是以下三种之一：左边比右边轻右边比左边轻两边同样重问：至少要使用天平多少次才能保证找到假硬币?（某年小学生数学竞赛题目:P）称硬币(cont.)答案：2次一种方法：Why最少2次?称硬币(cont.)Let: x是假硬币的序号：Let: yi是第i次使用天平所得到的结果：用天平称n次，获得的结果是：y1 y2 yny1 y2 yn的所有可能组合数目是3n我们要通过y1 y2 yn找出x。所以：每个y1 y2 yn组合最多可能有一个对应的x取值。因为x取X中任意一个值的时候，我们都要能够找出x，因此对于任意一个x的取值，至少要有一个y1 y2 yn与之对应。根据鸽笼原理称硬币(cont.)Let: x是假硬币的序号：Let: Yi是第i次使用天平所得到的结果：用y1 y2 yn表达x。即设计编码：x- y1 y2 ynX的“总不确定度”是：Y的“表达能力”是：至少要多少个Y才能准确表示X？称硬币(cont.)Why?为什么用log?“表达能力”与“不确定度”的关系？称硬币(cont.)为什么用log?假设一个Y的表达能力是H(Y)。显然，H(Y)与Y的具体内容无关，只与|Y|有关。两个Y(就是：y1y2)的表达能力是多少?y1可以表达三种情况，y2可以表达三种情况。两个并列，一共有：3*3=9种情况（乘法原理）。因此：称硬币(cont.)“表达能力”与“不确定度”的关系？都表达了一个变量所能变化的程度。在这个变量是用来表示别的变量的时候，这个程度是表达能力。在这个变量是被表示变量的时候，这个程度是不确定度。而这个可变化程度，就是一个变量的熵（Entropy）。显然：熵与变量本身含义无关，仅与变量的可能取值范围有关。称硬币-Version.2假设有5个硬币：1,2,3,5，其中一个是假的，比其他的硬币轻。已知第一个硬币是假硬币的概率是三分之一；第二个硬币是假硬币的概率也是三分之一，其他硬币是假硬币的概率都是九分之一。有一个天平，天平每次能比较两堆硬币，得出的结果可能是以下三种之一：左边比右边轻右边比左边轻两边同样重假设使用天平n次找到假硬币。问n的期望值至少是多少？（不再是小学生问题:P）称硬币-Version.2因为第一个、第二个硬币是假硬币的概率是三分之一，比其他硬币的概率大，我们首先“怀疑”这两个。第一次可以把这两个做比较。成功的概率是三分之二。失败的概率是三分之一。如果失败了，第二次称剩下的三个。所以，期望值是：称硬币-Version.2数据结构：Huffman编码问题。称硬币-Version.2数据结构：Huffman编码问题。称硬币-Version.2数据结构：Huffman编码问题。用反证法可以证明，这个是最小值。（假设第一个和第二个硬币中有一个要称两次的话）称硬币-Version.2数据结构：Huffman编码问题。称硬币-Version.3,4,更广泛地：如果一个随机变量x的可能取值为X=x1, x2, xk。要用n位y: y1y2yn表示（每位y有c种取值）n的期望值至少为：一般地，我们令c为2（二进制表示），于是，X的信息量为：Whats Entropy?定义:X的具体内容跟信息量无关，我们只关心概率分布，于是H(X)可以写成：熵的性质第一个等号在X为确定值的时候成立（没有变化的可能）第二个等号在X均匀分布的时候成立。熵的性质证明：熵的性质证明：详细证明略。求条件极值就可以证明了（求偏导数，条件是：所有的概率之和为1）结论：均匀分布的时候，熵最大Conditional Entropy有两个变量：x,y。它们不是独立的。已知y，x的不确定度又是多少呢?Conditional EntropyCondition Reduces Entropy (C.R.E.)知识（Y）减少不确定性（X）证明（略）。用文氏图说明：已知与未知的关系对待已知事物和未知事物的原则：承认已知事物（知识）；对未知事物不做任何假设，没有任何偏见已知与未知的关系例子已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语令x1表示“学习”被标为名词， x2表示“学习”被标为动词。令y1表示“学习”被标为主语， y2表示被标为谓语， y3表示宾语， y4表示定语。得到下面的表示：如果仅仅知道这一点，根据无偏见原则，“学习”被标为名词的概率与它被标为动词的概率相等。已知与未知的关系例子已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语“学习”被标为定语的可能性很小，只有0.05除此之外，仍然坚持无偏见原则：我们引入这个新的知识：已知与未知的关系例子已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语“学习”被标为定语的可能性很小，只有0.05当“学习”被标作动词的时候，它被标作谓语的概率为0.95除此之外，仍然坚持无偏见原则，我们尽量使概率分布平均。但问题是：什么是尽量平均的分布？引入这个新的知识：最大熵模型Maximum Entropy概率平均分布=熵最大我们要一个x和y的分布，满足：同时使H(Y|X)达到最大值最大熵模型Maximum Entropy最大熵模型Maximum EntropyWhat is Constraints?-模型要与已知知识吻合What is known?-训练数据集合一般模型：P=p|p是X上满足条件的概率分布特征(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)特征与样本已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语“学习”被标为定语的可能性很小，只有0.05特征：当“学习”被标作动词的时候，它被标作谓语的概率为0.95x是什么? y是什么?样本是什么?特征与样本已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语特征：“学习”被标为定语的可能性很小，只有0.05当“学习”被标作动词的时候，它被标作谓语的概率为0.95x是什么? y是什么?样本是什么?特征与样本特征函数：对于一个特征(x0,y0)，定义特征函数：特征函数期望值：对于一个特征(x0,y0) ，在样本中的期望值是：是(x,y)在样本中出现的概率条件（Constraints）条件：对每一个特征(x,y)，模型所建立的条件概率分布要与训练样本表现出来的分布相同。假设样本的分布是（已知）：特征f在模型中的期望值：最大熵模型Maximum EntropyNLP模型：P=p|p是y|x的概率分布并且满足下面的条件对训练样本，对任意给定的特征fi：最大熵模型Maximum EntropyNLP模型：最大熵模型的解决问题：已知若干条件，要求若干变量的值使到目标函数（熵）最大数学本质：最优化问题（Optimization Problem）条件：线性、等式目标函数：非线性非线性规划（线性约束）(non-linear programming with linear constraints)非线性规划基本概念Nonlinear Programming解决的思路：非线性规划问题（带约束）（拉格朗日法）-非线性规划问题（不带约束Unconstrained Problem）（求偏导数法）-解决不带约束求解问题（解方程）-求出原问题的解法非线性规划基本概念Nonlinear Programmingp: m维向量；H(p): 关于p的非线性函数A: n*m常数矩阵；b: n维向量如何去掉约束？抽象问题：假设：A的行向量线性无关。确定了m维空间里面n个方向上（就是与Ap=b确定的m-n个方向“垂直”的n个方向）的取值。p只能在剩下的r=m-n个方向上面移动。非线性规划基本概念Nonlinear Programming假设Z是跟Ap=b垂直的方向量。Z: m*(m-n)常数矩阵) 就是p能够自由活动的所有空间了。v: m-n维变量于是有：非线性规划基本概念Nonlinear Programmingp: m维向量；H(p): 关于p的非线性函数A: n*m常数矩阵；b: n维向量如何去掉约束？抽象问题：Z: m*(m-n)常数矩阵v: m-n维变量 极值条件Z: m*(m-n)常数矩阵v: m-n维变量极值条件：把 分解成Z方向向量和A方向向量： 极值条件Z: m*(m-n)常数矩阵v: m-n维变量 极值条件p: m维向量；H(p): 关于p的非线性函数A: n*m常数矩阵；b: n维向量令：假设：A的行向量线性无关。拉格朗日算子Lagrange Multiplier一般地，对于k个限制条件的Constrained Optimization问题：拉格朗日函数为：其中引入的拉格朗日算子：拉格朗日算子Lagrange Multiplier拉格朗日函数可能的最优解（Exponential）最优解的存在性一阶导数为零，二阶导数小于零，所得到的是最大值！最优解形式（Exponential）最优解（Exponential）最优解（Exponential）能不能找到另一种逼近？比如等价成求某个函数 的最大/最小值？几乎不可能有解析解（包含指数函数）近似解不代表接近驻点。对偶问题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钱）。矩阵如下：对偶问题Alice vs Bob假设：Alice和Bob都是聪明而贪得无厌的人。而且他们都清楚对方也很聪明和很贪心。Alice的策略：找一个x，无论Bob怎么挑y， Cx,y 要尽量大。Bob的策略：找一个y，无论Alice怎么挑x， Cx,y 要尽量小。双方都很聪明：双方都对对方有“最坏打算”对偶问题Alice vs BobAlice的选择：x*=2Bob的选择：y*=2Alice vs Bob Version.2Alice的选择：x*=1Bob的选择：y*=2对偶问题Alice vs BobVersion 1: Alice的估计=结果=Bob的估计Version 2: Alice的估计结果=Bob的估计一般情况:Alice的估计=结果=Bob的估计定理：当存在马鞍点（Saddle Point）的时候，等号成立。并且结果=马鞍点的值。马鞍点：非线性规划中的对偶问题拉格朗日函数：于是：因此，为了尽量大，p的选取必须保证考虑：对偶问题与拉格朗日函数：同时：等价于：而对偶问题与拉格朗日函数：梯度递减法把p*代入L，得到： 令：梯度递减法求导，计算-L的梯度：梯度递减法递推公式：收敛问题最大似然率 Maximum Likelihood最大似然率：找出与样本的分布最接近的概率分布模型。简单的例子。10次抛硬币的结果是：画画字画画画字字画画假设p是每次抛硬币结果为“画”的概率。则：得到这样的实验结果的概率是：最大似然率 Maximum Likelihood最大似然率：找出与样本的分布最接近的概率分布模型。最优解是：p=0.7似然率的一般定义：最大似然率 Maximum Likelihood似然率的一般定义：似然率的对数形式：最大似然率 Maximum Likelihood在NLP里面，要估计的是：似然率是：是常数，可以忽略最大似然率 Maximum Likelihood在NLP里面，要估计的是：似然率可以定义为：通过求值可以发现，如果p(y|x)的形式是最大熵模型的形式的话，最大熵模型与最大似然率模型一致。最大似然率 为书写方便，令：最大似然率 最大似然率 Maximum Likelihood结论：最大熵的解（无偏见地对待不确定性）同时是最吻合样本数据分布的解。进一步证明了最大熵模型的合理性。偶然？必然？“It so happens that”?熵：不确定度似然率：与知识的吻合度最大熵：对不确定度的无偏见分配最大似然率：对知识的无偏见理解知识不确定度的补集知识不确定度的补集特征选取问题问题：所有知识可信吗？所有知识都有用吗？太多知识怎么办？在NLP里面：上下文信息可以很多很多种，那些是有用呢？特征选取问题Remind:“熵是描述不确定度的”“知识是不确定度的补集”不确定度越小，模型越准确。直观的过程：什么特征都不限定：熵最大加一个特征：熵少一点（C.R.E.）加的特征越多，熵越少特征选取算法目标：选择最有用的个特征（知识）“最”？全局的最优解几乎不可能可行的方法：逐步选择最有用的信息。每一步用“贪心”原则：挑选“现在看来”最有用的那个特征。“有用？”使到走这一步后熵减少最多算法步骤有效特征集合E= /这个时候p均匀分布计算最大熵H(p*)。显然：对以下步骤循环K次：对每个不在E里面的特征fi，把E+fi作为有效特征，计算最大熵Hi(pi*)；假设Hm(pm*)最小，则： E=E+fm。敏感度分析与特征提取SensitivityHow to work on insufficient data set?最终结论应该是约束条件越确定（_p(x)越大），lambda越大。应用实例Adwait Ratnaparkhis “Learning to Parse Natural Language with Maximum Entropy Models”创新点：用MaxEnt模型辅助Shift-reduce Parsing应用实例Parser的特点：三层ParserK-BFS搜索每层只搜索最好的K个方案(derivations)“最好”：概率最大概率：最大熵模型得到的概率分布应用实例数据流：应用实例概率：最大熵模型得到的概率分布l事先对每类Parsing都训练一个最大熵模型。l得到概率分布：pX*(a|c)。a是action，c是上下文。X可能是：lTAG, CHUNK, BUILD/CHECKl最优解求法：GIS（General Iterative Scaling Algorithm “一般梯度算法”？）l特征选取：只取出现次数大于等于5的所有特征（比较简单，但因此计算量也少多了）应用实例实验结果：Upenn的Corpus作为训练集合Wall Street Journal上的句子作为测试对象准确率：90%左右应用实例分析：三层Parser功不可没（上层Parser看到的是下层Parser的所有信息包括处理点之前和之后的信息）MaxEnt模型提供了比较准确的评价模型（不然三层Parser会比单层Parser引起更大的误差累积，“失之毫厘谬以千里”）相关项目CMU: Adam BergerU Penn: Adwait RatnaparkhiSource Forge: opennlp. MAXENT总结与启发MaxEnt已经是比较成功的一个NLP模型，并获得广泛应用从信息论获得启发（1948-）：自然语言处理也是信息处理的一种。语法标注也可以看作一种编码的过程?对偶问题： 从另一个角度看问题可能从不同领域获得的启发。（概率论与随机过程、最优化问题、图形学）“All Models are wrong. Some are useful.”参考文献1.A maximum entropy approach to natural language processing (Adam Berger)2.A Brief MaxEnt Tutorial (Adam Berger)3.Learning to parse natural language with maximum entropy models (Adwait Ratnaparkhi)4.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)高等数学运筹学数据结构Q&AQ&A？Thank you!