最大熵模型与自然语言处理.ppt

最大熵模型 与 自然语言处理 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%左右,应用实例,分析