最大熵模型与自然语言处理MaxEntModelNLP.ppt
《最大熵模型与自然语言处理MaxEntModelNLP.ppt》由会员分享,可在线阅读,更多相关《最大熵模型与自然语言处理MaxEntModelNLP.ppt(93页珍藏版)》请在三一文库上搜索。
1、最大熵模型 与 自然语言处理 MaxEnt Model & NLP,laputa c- 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与随
2、机过程,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 y
3、3) ,问题: 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,其中一个是假的,比其他的硬币轻。有一个天平,天平每次能比较两堆硬币,得出的结果可能是以下三种之一: 左边比右边轻 右边比左边轻 两边同样重 问:至少要使用天平多少次才能保证找到假硬币? (某
4、年小学生数学竞赛题目: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次使用天平所得到的结果: 用
5、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.),“表达能力”与“不确定度”的关系? 都表达了一个变量所能变化的程度。在这个变量是用来表
6、示别的变量的时候,这个程度是表达能力。在这个变量是被表示变量的时候,这个程度是不确定度。而这个可变化程度,就是一个变量的熵(Entropy)。 显然:熵与变量本身含义无关,仅与变量的可能取值范围有关。,称硬币-Version.2,假设有5个硬币:1,2,3,5,其中一个是假的,比其他的硬币轻。已知第一个硬币是假硬币的概率是三分之一;第二个硬币是假硬币的概率也是三分之一,其他硬币是假硬币的概率都是九分之一。 有一个天平,天平每次能比较两堆硬币,得出的结果可能是以下三种之一: 左边比右边轻 右边比左边轻 两边同样重 假设使用天平n次找到假硬币。问n的期望值至少是多少? (不再是小学生问题:P),称
7、硬币-Version.2,因为第一个、第二个硬币是假硬币的概率是三分之一,比其他硬币的概率大,我们首先“怀疑”这两个。第一次可以把这两个做比较。成功的概率是三分之二。失败的概率是三分之一。如果失败了,第二次称剩下的三个。所以,期望值是:,称硬币-Version.2,数据结构:Huffman编码问题。,称硬币-Version.2,数据结构:Huffman编码问题。,称硬币-Version.2,数据结构:Huffman编码问题。,用反证法可以证明,这个是最小值。 (假设第一个和第二个硬币中有一个要称两次的话),称硬币-Version.2,数据结构:Huffman编码问题。,称硬币-Version.
8、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,有两个变
9、量:x,y。它们不是独立的。已知y,x的不确定度又是多少呢?,Conditional Entropy,Condition Reduces Entropy (C.R.E.) 知识(Y)减少不确定性(X) 证明(略)。用文氏图说明:,已知与未知的关系,对待已知事物和未知事物的原则: 承认已知事物(知识); 对未知事物不做任何假设,没有任何偏见,已知与未知的关系例子,已知: “学习”可能是动词,也可能是名词。可以被标为主语、谓语、宾语、定语 令x1表示“学习”被标为名词, x2表示“学习”被标为动词。 令y1表示“学习”被标为主语, y2表示被标为谓语, y3表示宾语, y4表示定语。得到下面的表示
10、:,如果仅仅知道这一点,根据无偏见原则,“学习”被标为名词的概率与它被标为动词的概率相等。,已知与未知的关系例子,已知: “学习”可能是动词,也可能是名词。可以被标为主语、谓语、宾语、定语 “学习”被标为定语的可能性很小,只有0.05,除此之外,仍然坚持无偏见原则:,我们引入这个新的知识:,已知与未知的关系例子,已知: “学习”可能是动词,也可能是名词。可以被标为主语、谓语、宾语、定语 “学习”被标为定语的可能性很小,只有0.05 当“学习”被标作动词的时候,它被标作谓语的概率为0.95,除此之外,仍然坚持无偏见原则,我们尽量使概率分布平均。 但问题是:什么是尽量平均的分布?,引入这个新的知识
11、:,最大熵模型 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)
12、 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是什么? 样本是什么?,特征与样本,已知: “学习”可能是动词,也可能是名词。可以被标为主语、谓语、宾语、定语 特征:“
13、学习”被标为定语的可能性很小,只有0.05 当“学习”被标作动词的时候,它被标作谓语的概率为0.95,x是什么? y是什么? 样本是什么?,特征与样本,特征函数:对于一个特征(x0,y0),定义特征函数:,特征函数期望值: 对于一个特征(x0,y0) ,在样本中的期望值是:,是(x,y)在样本中出现的概率,条件(Constraints),条件: 对每一个特征(x,y),模型所建立的条件概率分布要与训练样本表现出来的分布相同。,假设样本的分布是(已知):,特征f在模型中的期望值:,最大熵模型 Maximum Entropy,NLP模型:,P=p|p是y|x的概率分布并且满足下面的条件 对训练样本
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最大 模型 自然语言 处理 MaxEntModelNLP
链接地址:https://www.31doc.com/p-3390999.html