大熵模型与自然语言处理MaxEntModelampNL.pptVIP

最大熵模型 与 自然语言处理 MaxEnt Model & NLP,laputa NLP Group, AI Lab, Tsinghua Univ.,Topics,NLP与随机过程的关系（背景） 最大熵模型的介绍（熵的定义、最大熵模型） 最大熵模型的解决（非线性规划、对偶问题、最大似然率） 特征选取问题 应用实例 总结与启发,NLP与随机过程,NLP:已知一段文字：x1x2xn（n个词） 标注词性y1y2yn 标注过程：,已知：x1x2xn 求：y1 已知：x1x2xn y1 求：y2 已知：x1x2xn y1 y2 求：y3 已知：x1x2xn y1 y2 y3 求：y4 ,NLP与随机过程,yi可能有多种取值，yi被标注为a的概率有多少? 随机过程：一个随机变量的序列。,x1x2xn p(y1=a|x1x2xn) x1x2xn y1 p(y2=a|x1x2xn y1) x1x2xn y1 y2 p(y3=a|x1x2xn y1 y2) x1x2xn y1 y2 y3 p(y4=a|x1x2xn y1 y2 y3) ,NLP与随机过程,x1x2xn p(y1=a|x1x2xn) x1x2xn y1 p(y2=a|x1x2xn y1) x1x2xn y1 y2 p(y3=a|x1x2xn y1 y2) x1x2xn y1 y2 y3 p(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 yn y1 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 yn X的“总不确定度”是： 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 Entropy,Condition 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 Entropy,What is Constraints? -模型要与已知知识吻合 What is known? -训练数据集合,一般模型：,P=p|p是X上满足条件的概率分布,特征(Feature),特征：(x,y) y:这个特征中需要确定的信息 x:这个特征中的上下文信息 注意一个标注可能在一种情况下是需要确定的信息，在另一种情况下是上下文信息 ：,x1x2xn p(y1=a|x1x2xn) x1x2xn y1 p(y2=a|x1x2xn y1),样本(Sample),关于某个特征(x,y)的样本-特征所描述的语法现象在标准集合里的分布： (xi,yi) pairs yi是y的一个实例 xi是yi的上下文 (x1,y1) (x2,y2) (x3,y3),特征与样本,已知： “学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语 “学习”被标为定语的可能性很小，只有0.05 特征：当“学习”被标作动词的时候，它被标作谓语的概率为0.95,x是什么? y是什么? 样本是什么?,特征与样本,已知： “学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语 特征：“学习”被标为定语的可能性很小，只有0.05 当“学习”被标作动词的时候，它被标作谓语的概率为0.95,x是什么? y是什么? 样本是什么?,特征与样本,特征函数：对于一个特征(x0,y0)，定义特征函数：,特征函数期望值： 对于一个特征(x0,y0) ，在样本中的期望值是：,是(x,y)在样本中出现的概率,条件（Constraints）,条件： 对每一个特征(x,y)，模型所建立的条件概率分布要与训练样本表现出来的分布相同。,假设样本的分布是（已知）：,特征f在模型中的期望值：,最大熵模型 Maximum Entropy,NLP模型：,P=p|p是y|x的概率分布并且满足下面的条件 对训练样本，对任意给定的特征fi：,最大熵模型 Maximum Entropy,NLP模型：,最大熵模型的解决,问题： 已知若干条件，要求若干变量的值使到目标函数（熵）最大 数学本质： 最优化问题（Optimization Problem） 条件：线性、等式 目标函数：非线性 非线性规划（线性约束）(non-linear programming with linear constraints),非线性规划基本概念 Nonlinear Programming,解决的思路： 非线性规划问题（带约束） （拉格朗日法）-非线性规划问题（不带约束Unconstrained Problem） （求偏导数法）-解决不带约束求解问题 （解方程）-求出原问题的解法,非线性规划基本概念 Nonlinear Programming,p: 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 Programming,p: 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的游戏： 有一个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 Bob,Alice的选择：x*=2 Bob的选择：y*=2,Alice vs Bob Version.2,Alice的选择：x*=1 Bob的选择：y*=2,对偶问题 Alice vs Bob,Version 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。,敏感度分析与特征提取 Sensitivity,How 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的特点： 三层Parser K-BFS搜索每层只搜索最好的K个方案(derivations) “最好”：概率最大 概率：最大熵模型得到的概率分布,应用实例,数据流：,应用实例,概率：最大熵模型得到的概率分布 事先对每类Parsing都训练一个最大熵模型。 得到概率分布：pX*(a|c)。a是action，c是上下文。X可能是： TAG, CHUNK, BUILD/CHECK 最优解求法：GIS（General Iterative Scaling Algorithm “一般梯度算法”？） 特征选取：只取出现次数大于等于5的所有特征（比较简单，但因此计算量也少多了）,应用实例,实验结果： Upenn的Corpus作为训练集合 Wall Street Journal上的句子作为测试对象 准确率：90%左右,应用实例,分析