最大熵模型(matlab应用)课件

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

2、n y1 y2 y3求：y4,最大熵模型(matlab应用,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),最大熵模型(matlab应用,NLP与随机过程,x1x2xnp(y1=a|x1x2xn) x1x2xn y1p(y2=a|x1x2xn y1) x1x2xn y1 y2p(y3=a|x1x2xn y1

3、y2) x1x2xn y1 y2 y3p(y4=a|x1x2xn y1 y2 y3),问题： p(yi=a|x1x2xn y1y2yi-1)怎么求? yi与x1x2xn y1y2yi-1的关系,最大熵模型(matlab应用,NLP与随机过程,问题： p(yi=a|x1x2xn y1y2yi-1)怎么求? yi与x1x2xn y1y2yi-1的关系,一个直观的解决,问题again! (x1x2xn y1y2yi-1),最大熵模型(matlab应用,Whats Entropy,An Example： 假设有5个硬币：1,2,3,4,5，其中一个是假的，比其他的硬币轻。有一个天平，天平每次能比较两堆

4、硬币，得出的结果可能是以下三种之一： 左边比右边轻 右边比左边轻 两边同样重 问：至少要使用天平多少次才能保证找到假硬币? （某年小学生数学竞赛题目:P,最大熵模型(matlab应用,称硬币(cont.,答案：2次 一种方法： Why最少2次,最大熵模型(matlab应用,称硬币(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

5、，因此对于任意一个x的取值，至少要有一个y1 y2 yn与之对应。根据鸽笼原理,最大熵模型(matlab应用,称硬币(cont.,Let: x是假硬币的序号： Let: Yi是第i次使用天平所得到的结果： 用y1 y2 yn表达x。即设计编码：x- y1 y2 yn X的“总不确定度”是： Y的“表达能力”是： 至少要多少个Y才能准确表示X,最大熵模型(matlab应用,称硬币(cont.,Why? 为什么用log? “表达能力”与“不确定度”的关系,最大熵模型(matlab应用,称硬币(cont.,为什么用log? 假设一个Y的表达能力是H(Y)。显然，H(Y)与Y的具体内容无关，只与|Y|

6、有关。 两个Y(就是：y1y2)的表达能力是多少? y1可以表达三种情况，y2可以表达三种情况。两个并列，一共有：3*3=9种情况（乘法原理）。因此,最大熵模型(matlab应用,称硬币(cont.,表达能力”与“不确定度”的关系？ 都表达了一个变量所能变化的程度。在这个变量是用来表示别的变量的时候，这个程度是表达能力。在这个变量是被表示变量的时候，这个程度是不确定度。而这个可变化程度，就是一个变量的熵（Entropy）。 显然：熵与变量本身含义无关，仅与变量的可能取值范围有关,最大熵模型(matlab应用,称硬币-Version.2,假设有5个硬币：1,2,3,5，其中一个是假的，比其他的硬

7、币轻。已知第一个硬币是假硬币的概率是三分之一；第二个硬币是假硬币的概率也是三分之一，其他硬币是假硬币的概率都是九分之一。 有一个天平，天平每次能比较两堆硬币，得出的结果可能是以下三种之一： 左边比右边轻 右边比左边轻 两边同样重 假设使用天平n次找到假硬币。问n的期望值至少是多少？ （不再是小学生问题:P,最大熵模型(matlab应用,称硬币-Version.2,因为第一个、第二个硬币是假硬币的概率是三分之一，比其他硬币的概率大，我们首先“怀疑”这两个。第一次可以把这两个做比较。成功的概率是三分之二。失败的概率是三分之一。如果失败了，第二次称剩下的三个。所以，期望值是,最大熵模型(matlab

8、应用,称硬币-Version.2,数据结构：Huffman编码问题,最大熵模型(matlab应用,称硬币-Version.2,数据结构：Huffman编码问题,最大熵模型(matlab应用,称硬币-Version.2,数据结构：Huffman编码问题,用反证法可以证明，这个是最小值。 （假设第一个和第二个硬币中有一个要称两次的话,最大熵模型(matlab应用,称硬币-Version.2,数据结构：Huffman编码问题,最大熵模型(matlab应用,称硬币-Version.3,4,更广泛地：如果一个随机变量x的可能取值为X=x1, x2, xk。要用n位y: y1y2yn表示（每位y有c种取值

9、）n的期望值至少为,一般地，我们令c为2（二进制表示），于是，X的信息量为,最大熵模型(matlab应用,Whats Entropy,定义: X的具体内容跟信息量无关，我们只关心概率分布，于是H(X)可以写成,最大熵模型(matlab应用,熵的性质,第一个等号在X为确定值的时候成立（没有变化的可能） 第二个等号在X均匀分布的时候成立,最大熵模型(matlab应用,熵的性质,证明,最大熵模型(matlab应用,熵的性质,证明： 详细证明略。 求条件极值就可以证明了（求偏导数，条件是：所有的概率之和为1） 结论：均匀分布的时候，熵最大,最大熵模型(matlab应用,Conditional Entr

10、opy,有两个变量：x,y。它们不是独立的。已知y，x的不确定度又是多少呢,最大熵模型(matlab应用,Conditional Entropy,Condition Reduces Entropy (C.R.E.) 知识（Y）减少不确定性（X） 证明（略）。用文氏图说明,最大熵模型(matlab应用,已知与未知的关系,对待已知事物和未知事物的原则： 承认已知事物（知识）； 对未知事物不做任何假设，没有任何偏见,最大熵模型(matlab应用,已知与未知的关系例子,已知： “学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语 令x1表示“学习”被标为名词， x2表示“学习”被标为动词

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

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

13、的概率分布,最大熵模型(matlab应用,特征(Feature,特征：(x,y) y:这个特征中需要确定的信息 x:这个特征中的上下文信息 注意一个标注可能在一种情况下是需要确定的信息，在另一种情况下是上下文信息,x1x2xnp(y1=a|x1x2xn) x1x2xn y1p(y2=a|x1x2xn y1,最大熵模型(matlab应用,样本(Sample,关于某个特征(x,y)的样本-特征所描述的语法现象在标准集合里的分布： (xi,yi) pairs yi是y的一个实例 xi是yi的上下文 (x1,y1) (x2,y2) (x3,y3,最大熵模型(matlab应用,特征与样本,已知： “学习

14、”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语 “学习”被标为定语的可能性很小，只有0.05 特征：当“学习”被标作动词的时候，它被标作谓语的概率为0.95,x是什么? y是什么? 样本是什么,最大熵模型(matlab应用,特征与样本,已知： “学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语 特征：“学习”被标为定语的可能性很小，只有0.05 当“学习”被标作动词的时候，它被标作谓语的概率为0.95,x是什么? y是什么? 样本是什么,最大熵模型(matlab应用,特征与样本,特征函数：对于一个特征(x0,y0)，定义特征函数,特征函数期望值： 对于一个特征(x

15、0,y0) ，在样本中的期望值是,是(x,y)在样本中出现的概率,最大熵模型(matlab应用,条件（Constraints,条件： 对每一个特征(x,y)，模型所建立的条件概率分布要与训练样本表现出来的分布相同,假设样本的分布是（已知,特征f在模型中的期望值,最大熵模型(matlab应用,最大熵模型Maximum Entropy,NLP模型,P=p|p是y|x的概率分布并且满足下面的条件 对训练样本，对任意给定的特征fi,最大熵模型(matlab应用,最大熵模型Maximum Entropy,NLP模型,最大熵模型(matlab应用,最大熵模型的解决,问题： 已知若干条件，要求若干变量的值使

16、到目标函数（熵）最大 数学本质： 最优化问题（Optimization Problem） 条件：线性、等式 目标函数：非线性 非线性规划（线性约束）(non-linear programming with linear constraints,最大熵模型(matlab应用,非线性规划基本概念Nonlinear Programming,解决的思路： 非线性规划问题（带约束） （拉格朗日法）-非线性规划问题（不带约束Unconstrained Problem） （求偏导数法）-解决不带约束求解问题 （解方程）-求出原问题的解法,最大熵模型(matlab应用,非线性规划基本概念Nonlinear P

17、rogramming,p: m维向量；H(p): 关于p的非线性函数 A: n*m常数矩阵；b: n维向量,如何去掉约束？抽象问题,假设：A的行向量线性无关,确定了m维空间里面n个方向上（就是与Ap=b确定的m-n个方向“垂直”的n个方向）的取值。 p只能在剩下的r=m-n个方向上面移动,最大熵模型(matlab应用,非线性规划基本概念Nonlinear Programming,假设Z是跟Ap=b垂直的方向量。 Z: m*(m-n)常数矩阵,就是p能够自由活动的所有空间了。 v: m-n维变量 于是有,最大熵模型(matlab应用,非线性规划基本概念Nonlinear Programming,

18、p: m维向量；H(p): 关于p的非线性函数 A: n*m常数矩阵；b: n维向量,如何去掉约束？抽象问题,Z: m*(m-n)常数矩阵 v: m-n维变量,最大熵模型(matlab应用,极值条件,Z: m*(m-n)常数矩阵 v: m-n维变量,极值条件,把 分解成Z方向向量和A方向向量,最大熵模型(matlab应用,极值条件,Z: m*(m-n)常数矩阵 v: m-n维变量,最大熵模型(matlab应用,极值条件,p: m维向量；H(p): 关于p的非线性函数 A: n*m常数矩阵；b: n维向量,令,假设：A的行向量线性无关,最大熵模型(matlab应用,拉格朗日算子Lagrange

19、Multiplier,一般地，对于k个限制条件的Constrained Optimization问题,拉格朗日函数为,其中引入的拉格朗日算子,最大熵模型(matlab应用,拉格朗日算子Lagrange Multiplier,最大熵模型(matlab应用,拉格朗日函数,最大熵模型(matlab应用,可能的最优解（Exponential,最大熵模型(matlab应用,最优解的存在性,一阶导数为零， 二阶导数小于零， 所得到的是最大值,最大熵模型(matlab应用,最优解形式（Exponential,最大熵模型(matlab应用,最优解（Exponential,最大熵模型(matlab应用,最优解（

20、Exponential,能不能找到另一种逼近？比如 等价成求某个函数 的最大/最小值,几乎不可能有解析解（包含指数函数） 近似解不代表接近驻点,最大熵模型(matlab应用,对偶问题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钱）。矩阵如下,最大熵模型(matlab应用,对偶问题Alice vs Bob,假设：Alice和Bob都是聪明而贪得无厌的人。而

21、且他们都清楚对方也很聪明和很贪心。 Alice的策略： 找一个x，无论Bob怎么挑y， Cx,y 要尽量大。 Bob的策略： 找一个y，无论Alice怎么挑x， Cx,y 要尽量小,双方都很聪明：双方都对对方有“最坏打算,最大熵模型(matlab应用,对偶问题Alice vs Bob,Alice的选择：x*=2 Bob的选择：y*=2,最大熵模型(matlab应用,Alice vs Bob Version.2,Alice的选择：x*=1 Bob的选择：y*=2,最大熵模型(matlab应用,对偶问题Alice vs Bob,Version 1: Alice的估计=结果=Bob的估计 Versi

22、on 2: Alice的估计结果=Bob的估计 一般情况:Alice的估计=结果=Bob的估计,定理：当存在马鞍点（Saddle Point）的时候，等号成立。并且结果=马鞍点的值。 马鞍点,最大熵模型(matlab应用,非线性规划中的对偶问题,拉格朗日函数,于是,因此，为了尽量大，p的选取必须保证,考虑,最大熵模型(matlab应用,对偶问题与拉格朗日函数,同时,等价于,而,最大熵模型(matlab应用,对偶问题与拉格朗日函数,最大熵模型(matlab应用,梯度递减法,把p*代入L，得到： 令,最大熵模型(matlab应用,梯度递减法,求导，计算-L的梯度,最大熵模型(matlab应用,梯度

23、递减法,递推公式,收敛问题,最大熵模型(matlab应用,最大似然率 Maximum Likelihood,最大似然率：找出与样本的分布最接近的概率分布模型。 简单的例子。10次抛硬币的结果是： 画画字画画画字字画画 假设p是每次抛硬币结果为“画”的概率。则： 得到这样的实验结果的概率是,最大熵模型(matlab应用,最大似然率 Maximum Likelihood,最大似然率：找出与样本的分布最接近的概率分布模型,最优解是：p=0.7 似然率的一般定义,最大熵模型(matlab应用,最大似然率 Maximum Likelihood,似然率的一般定义,似然率的对数形式,最大熵模型(matlab

24、应用,最大似然率 Maximum Likelihood,在NLP里面，要估计的是,似然率是,是常数，可以忽略,最大熵模型(matlab应用,最大似然率 Maximum Likelihood,在NLP里面，要估计的是,似然率可以定义为,通过求值可以发现，如果p(y|x)的形式是最大熵模型的形式的话，最大熵模型与最大似然率模型一致,最大熵模型(matlab应用,最大似然率,为书写方便，令,最大熵模型(matlab应用,最大似然率,最大熵模型(matlab应用,最大似然率 Maximum Likelihood,结论：最大熵的解（无偏见地对待不确定性）同时是最吻合样本数据分布的解。进一步证明了最大熵模

25、型的合理性,最大熵模型(matlab应用,偶然？必然,It so happens that”? 熵：不确定度 似然率：与知识的吻合度 最大熵：对不确定度的无偏见分配 最大似然率：对知识的无偏见理解 知识不确定度的补集,最大熵模型(matlab应用,特征选取问题,问题： 所有知识可信吗？所有知识都有用吗？ 太多知识怎么办,在NLP里面： 上下文信息可以很多很多种，那些是有用呢,最大熵模型(matlab应用,特征选取问题,Remind: “熵是描述不确定度的” “知识是不确定度的补集” 不确定度越小，模型越准确,直观的过程： 什么特征都不限定：熵最大 加一个特征：熵少一点（C.R.E.） 加的特征

26、越多，熵越少,最大熵模型(matlab应用,特征选取算法,目标：选择最有用的个特征（知识） “最”？全局的最优解几乎不可能 可行的方法：逐步选择最有用的信息。 每一步用“贪心”原则：挑选“现在看来”最有用的那个特征。 “有用？”使到走这一步后熵减少最多,最大熵模型(matlab应用,算法步骤,有效特征集合E= /这个时候p均匀分布 计算最大熵H(p*)。显然： 对以下步骤循环K次： 对每个不在E里面的特征fi，把E+fi作为有效特征，计算最大熵Hi(pi*)； 假设Hm(pm*)最小，则： E=E+fm,最大熵模型(matlab应用,敏感度分析与特征提取Sensitivity,How to w

27、ork on insufficient data set? 最终结论应该是约束条件越确定（_p(x)越大），lambda越大,最大熵模型(matlab应用,应用实例,Adwait Ratnaparkhis “Learning to Parse Natural Language with Maximum Entropy Models” 创新点： 用MaxEnt模型辅助Shift-reduce Parsing,最大熵模型(matlab应用,应用实例,Parser的特点： 三层Parser K-BFS搜索每层只搜索最好的K个方案(derivations) “最好”：概率最大 概率：最大熵模型得到的概

28、率分布,最大熵模型(matlab应用,应用实例,数据流,最大熵模型(matlab应用,应用实例,概率：最大熵模型得到的概率分布 事先对每类Parsing都训练一个最大熵模型。 得到概率分布：pX*(a|c)。a是action，c是上下文。X可能是： TAG, CHUNK, BUILD/CHECK 最优解求法：GIS（General Iterative Scaling Algorithm “一般梯度算法”？） 特征选取：只取出现次数大于等于5的所有特征（比较简单，但因此计算量也少多了,最大熵模型(matlab应用,应用实例,实验结果： Upenn的Corpus作为训练集合 Wall Street Journal上的