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

1、a,1,最大熵模型与自然语言处理MaxEnt Model & NLP,laputa c- NLP Group, AI Lab, Tsinghua Univ,a,2,Topics,NLP与随机过程的关系（背景） 最大熵模型的介绍（熵的定义、最大熵模型） 最大熵模型的解决（非线性规划、对偶问题、最大似然率） 特征选取问题 应用实例 总结与启发,a,3,NLP与随机过程,NLP:已知一段文字：x1x2xn（n个词） 标注词性y1y2yn 标注过程,已知：x1x2xn求：y1 已知：x1x2xn y1求：y2 已知：x1x2xn y1 y2求：y3 已知：x1x2xn y1 y2 y3求：y4,a,4

2、,NLP与随机过程,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),a,5,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 y

3、3),问题： p(yi=a|x1x2xn y1y2yi-1)怎么求? yi与x1x2xn y1y2yi-1的关系,a,6,NLP与随机过程,问题： p(yi=a|x1x2xn y1y2yi-1)怎么求? yi与x1x2xn y1y2yi-1的关系,一个直观的解决,问题again! (x1x2xn y1y2yi-1),a,7,Whats Entropy,An Example： 假设有5个硬币：1,2,3,4,5，其中一个是假的，比其他的硬币轻。有一个天平，天平每次能比较两堆硬币，得出的结果可能是以下三种之一： 左边比右边轻 右边比左边轻 两边同样重 问：至少要使用天平多少次才能保证找到假硬币?

4、（某年小学生数学竞赛题目:P,a,8,称硬币(cont.,答案：2次 一种方法： Why最少2次,a,9,称硬币(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与之对应。根据鸽笼原理,a,10,称硬币(cont.,Let: x是假硬币的序号： Let: Yi是第i次使用天

5、平所得到的结果： 用y1 y2 yn表达x。即设计编码：x- y1 y2 yn X的“总不确定度”是： Y的“表达能力”是： 至少要多少个Y才能准确表示X,a,11,称硬币(cont.,Why? 为什么用log? “表达能力”与“不确定度”的关系,a,12,称硬币(cont.,为什么用log? 假设一个Y的表达能力是H(Y)。显然，H(Y)与Y的具体内容无关，只与|Y|有关。 两个Y(就是：y1y2)的表达能力是多少? y1可以表达三种情况，y2可以表达三种情况。两个并列，一共有：3*3=9种情况（乘法原理）。因此,a,13,称硬币(cont.,表达能力”与“不确定度”的关系？ 都表达了一个变

6、量所能变化的程度。在这个变量是用来表示别的变量的时候，这个程度是表达能力。在这个变量是被表示变量的时候，这个程度是不确定度。而这个可变化程度，就是一个变量的熵（Entropy）。 显然：熵与变量本身含义无关，仅与变量的可能取值范围有关,a,14,称硬币-Version.2,假设有5个硬币：1,2,3,5，其中一个是假的，比其他的硬币轻。已知第一个硬币是假硬币的概率是三分之一；第二个硬币是假硬币的概率也是三分之一，其他硬币是假硬币的概率都是九分之一。 有一个天平，天平每次能比较两堆硬币，得出的结果可能是以下三种之一： 左边比右边轻 右边比左边轻 两边同样重 假设使用天平n次找到假硬币。问n的期望

7、值至少是多少？ （不再是小学生问题:P,a,15,称硬币-Version.2,因为第一个、第二个硬币是假硬币的概率是三分之一，比其他硬币的概率大，我们首先“怀疑”这两个。第一次可以把这两个做比较。成功的概率是三分之二。失败的概率是三分之一。如果失败了，第二次称剩下的三个。所以，期望值是,a,16,称硬币-Version.2,数据结构：Huffman编码问题,a,17,称硬币-Version.2,数据结构：Huffman编码问题,a,18,称硬币-Version.2,数据结构：Huffman编码问题,用反证法可以证明，这个是最小值。 （假设第一个和第二个硬币中有一个要称两次的话,a,19,称硬币

8、-Version.2,数据结构：Huffman编码问题,a,20,称硬币-Version.3,4,更广泛地：如果一个随机变量x的可能取值为X=x1, x2, xk。要用n位y: y1y2yn表示（每位y有c种取值）n的期望值至少为,一般地，我们令c为2（二进制表示），于是，X的信息量为,a,21,Whats Entropy,定义: X的具体内容跟信息量无关，我们只关心概率分布，于是H(X)可以写成,a,22,熵的性质,第一个等号在X为确定值的时候成立（没有变化的可能） 第二个等号在X均匀分布的时候成立,a,23,熵的性质,证明,a,24,熵的性质,证明： 详细证明略。 求条件极值就可以证明了（

9、求偏导数，条件是：所有的概率之和为1） 结论：均匀分布的时候，熵最大,a,25,Conditional Entropy,有两个变量：x,y。它们不是独立的。已知y，x的不确定度又是多少呢,a,26,Conditional Entropy,Condition Reduces Entropy (C.R.E.) 知识（Y）减少不确定性（X） 证明（略）。用文氏图说明,a,27,已知与未知的关系,对待已知事物和未知事物的原则： 承认已知事物（知识）； 对未知事物不做任何假设，没有任何偏见,a,28,已知与未知的关系例子,已知： “学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语 令x1

10、表示“学习”被标为名词， x2表示“学习”被标为动词。 令y1表示“学习”被标为主语， y2表示被标为谓语， y3表示宾语， y4表示定语。得到下面的表示,如果仅仅知道这一点，根据无偏见原则，“学习”被标为名词的概率与它被标为动词的概率相等,a,29,已知与未知的关系例子,已知： “学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语 “学习”被标为定语的可能性很小，只有0.05,除此之外，仍然坚持无偏见原则,我们引入这个新的知识,a,30,已知与未知的关系例子,已知： “学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语 “学习”被标为定语的可能性很小，只有0.05

11、 当“学习”被标作动词的时候，它被标作谓语的概率为0.95,除此之外，仍然坚持无偏见原则，我们尽量使概率分布平均。 但问题是：什么是尽量平均的分布,引入这个新的知识,a,31,最大熵模型Maximum Entropy,概率平均分布=熵最大 我们要一个x和y的分布，满足： 同时使H(Y|X)达到最大值,a,32,最大熵模型Maximum Entropy,a,33,最大熵模型Maximum Entropy,What is Constraints? -模型要与已知知识吻合 What is known? -训练数据集合,一般模型,P=p|p是X上满足条件的概率分布,a,34,特征(Feature,特征

12、：(x,y) y:这个特征中需要确定的信息 x:这个特征中的上下文信息 注意一个标注可能在一种情况下是需要确定的信息，在另一种情况下是上下文信息,x1x2xnp(y1=a|x1x2xn) x1x2xn y1p(y2=a|x1x2xn y1,a,35,样本(Sample,关于某个特征(x,y)的样本-特征所描述的语法现象在标准集合里的分布： (xi,yi) pairs yi是y的一个实例 xi是yi的上下文 (x1,y1) (x2,y2) (x3,y3,a,36,特征与样本,已知： “学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语 “学习”被标为定语的可能性很小，只有0.05

13、特征：当“学习”被标作动词的时候，它被标作谓语的概率为0.95,x是什么? y是什么? 样本是什么,a,37,特征与样本,已知： “学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语 特征：“学习”被标为定语的可能性很小，只有0.05 当“学习”被标作动词的时候，它被标作谓语的概率为0.95,x是什么? y是什么? 样本是什么,a,38,特征与样本,特征函数：对于一个特征(x0,y0)，定义特征函数,特征函数期望值： 对于一个特征(x0,y0) ，在样本中的期望值是,是(x,y)在样本中出现的概率,a,39,条件（Constraints,条件： 对每一个特征(x,y)，模型所建立

14、的条件概率分布要与训练样本表现出来的分布相同,假设样本的分布是（已知,特征f在模型中的期望值,a,40,最大熵模型Maximum Entropy,NLP模型,P=p|p是y|x的概率分布并且满足下面的条件 对训练样本，对任意给定的特征fi,a,41,最大熵模型Maximum Entropy,NLP模型,a,42,最大熵模型的解决,问题： 已知若干条件，要求若干变量的值使到目标函数（熵）最大 数学本质： 最优化问题（Optimization Problem） 条件：线性、等式 目标函数：非线性 非线性规划（线性约束）(non-linear programming with linear cons

15、traints,a,43,非线性规划基本概念Nonlinear Programming,解决的思路： 非线性规划问题（带约束） （拉格朗日法）-非线性规划问题（不带约束Unconstrained Problem） （求偏导数法）-解决不带约束求解问题 （解方程）-求出原问题的解法,a,44,非线性规划基本概念Nonlinear Programming,p: m维向量；H(p): 关于p的非线性函数 A: n*m常数矩阵；b: n维向量,如何去掉约束？抽象问题,假设：A的行向量线性无关,确定了m维空间里面n个方向上（就是与Ap=b确定的m-n个方向“垂直”的n个方向）的取值。 p只能在剩下的r=

16、m-n个方向上面移动,a,45,非线性规划基本概念Nonlinear Programming,假设Z是跟Ap=b垂直的方向量。 Z: m*(m-n)常数矩阵,就是p能够自由活动的所有空间了。 v: m-n维变量 于是有,a,46,非线性规划基本概念Nonlinear Programming,p: m维向量；H(p): 关于p的非线性函数 A: n*m常数矩阵；b: n维向量,如何去掉约束？抽象问题,Z: m*(m-n)常数矩阵 v: m-n维变量,a,47,极值条件,Z: m*(m-n)常数矩阵 v: m-n维变量,极值条件,把 分解成Z方向向量和A方向向量,a,48,极值条件,Z: m*(m

17、-n)常数矩阵 v: m-n维变量,a,49,极值条件,p: m维向量；H(p): 关于p的非线性函数 A: n*m常数矩阵；b: n维向量,令,假设：A的行向量线性无关,a,50,拉格朗日算子Lagrange Multiplier,一般地，对于k个限制条件的Constrained Optimization问题,拉格朗日函数为,其中引入的拉格朗日算子,a,51,拉格朗日算子Lagrange Multiplier,a,52,拉格朗日函数,a,53,可能的最优解（Exponential,a,54,最优解的存在性,一阶导数为零， 二阶导数小于零， 所得到的是最大值,a,55,最优解形式（Expone

18、ntial,a,56,最优解（Exponential,a,57,最优解（Exponential,能不能找到另一种逼近？比如 等价成求某个函数 的最大/最小值,几乎不可能有解析解（包含指数函数） 近似解不代表接近驻点,a,58,对偶问题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钱）。矩阵如下,a,59,对偶问题Alice vs Bob,假设：Alice和

19、Bob都是聪明而贪得无厌的人。而且他们都清楚对方也很聪明和很贪心。 Alice的策略： 找一个x，无论Bob怎么挑y， Cx,y 要尽量大。 Bob的策略： 找一个y，无论Alice怎么挑x， Cx,y 要尽量小,双方都很聪明：双方都对对方有“最坏打算,a,60,对偶问题Alice vs Bob,Alice的选择：x*=2 Bob的选择：y*=2,a,61,Alice vs Bob Version.2,Alice的选择：x*=1 Bob的选择：y*=2,a,62,对偶问题Alice vs Bob,Version 1: Alice的估计=结果=Bob的估计 Version 2: Alice的估计

20、结果=Bob的估计 一般情况:Alice的估计=结果=Bob的估计,定理：当存在马鞍点（Saddle Point）的时候，等号成立。并且结果=马鞍点的值。 马鞍点,a,63,非线性规划中的对偶问题,拉格朗日函数,于是,因此，为了尽量大，p的选取必须保证,考虑,a,64,对偶问题与拉格朗日函数,同时,等价于,而,a,65,对偶问题与拉格朗日函数,a,66,梯度递减法,把p*代入L，得到： 令,a,67,梯度递减法,求导，计算-L的梯度,a,68,梯度递减法,递推公式,收敛问题,a,69,最大似然率 Maximum Likelihood,最大似然率：找出与样本的分布最接近的概率分布模型。 简单的例

21、子。10次抛硬币的结果是： 画画字画画画字字画画 假设p是每次抛硬币结果为“画”的概率。则： 得到这样的实验结果的概率是,a,70,最大似然率 Maximum Likelihood,最大似然率：找出与样本的分布最接近的概率分布模型,最优解是：p=0.7 似然率的一般定义,a,71,最大似然率 Maximum Likelihood,似然率的一般定义,似然率的对数形式,a,72,最大似然率 Maximum Likelihood,在NLP里面，要估计的是,似然率是,是常数，可以忽略,a,73,最大似然率 Maximum Likelihood,在NLP里面，要估计的是,似然率可以定义为,通过求值可以发

22、现，如果p(y|x)的形式是最大熵模型的形式的话，最大熵模型与最大似然率模型一致,a,74,最大似然率,为书写方便，令,a,75,最大似然率,a,76,最大似然率 Maximum Likelihood,结论：最大熵的解（无偏见地对待不确定性）同时是最吻合样本数据分布的解。进一步证明了最大熵模型的合理性,a,77,偶然？必然,It so happens that”? 熵：不确定度 似然率：与知识的吻合度 最大熵：对不确定度的无偏见分配 最大似然率：对知识的无偏见理解 知识不确定度的补集,a,78,特征选取问题,问题： 所有知识可信吗？所有知识都有用吗？ 太多知识怎么办,在NLP里面： 上下文信息

23、可以很多很多种，那些是有用呢,a,79,特征选取问题,Remind: “熵是描述不确定度的” “知识是不确定度的补集” 不确定度越小，模型越准确,直观的过程： 什么特征都不限定：熵最大 加一个特征：熵少一点（C.R.E.） 加的特征越多，熵越少,a,80,特征选取算法,目标：选择最有用的个特征（知识） “最”？全局的最优解几乎不可能 可行的方法：逐步选择最有用的信息。 每一步用“贪心”原则：挑选“现在看来”最有用的那个特征。 “有用？”使到走这一步后熵减少最多,a,81,算法步骤,有效特征集合E= /这个时候p均匀分布 计算最大熵H(p*)。显然： 对以下步骤循环K次： 对每个不在E里面的特征

24、fi，把E+fi作为有效特征，计算最大熵Hi(pi*)； 假设Hm(pm*)最小，则： E=E+fm,a,82,敏感度分析与特征提取Sensitivity,How to work on insufficient data set? 最终结论应该是约束条件越确定（_p(x)越大），lambda越大,a,83,应用实例,Adwait Ratnaparkhis “Learning to Parse Natural Language with Maximum Entropy Models” 创新点： 用MaxEnt模型辅助Shift-reduce Parsing,a,84,应用实例,Parser的特点

25、： 三层Parser K-BFS搜索每层只搜索最好的K个方案(derivations) “最好”：概率最大 概率：最大熵模型得到的概率分布,a,85,应用实例,数据流,a,86,应用实例,概率：最大熵模型得到的概率分布 事先对每类Parsing都训练一个最大熵模型。 得到概率分布：pX*(a|c)。a是action，c是上下文。X可能是： TAG, CHUNK, BUILD/CHECK 最优解求法：GIS（General Iterative Scaling Algorithm “一般梯度算法”？） 特征选取：只取出现次数大于等于5的所有特征（比较简单，但因此计算量也少多了,a,87,应用实例,实验结果： Upenn的Corpus作为训练集合 Wall Street Journal上的句子作为测试对象 准确率：90%左右,