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

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

ID:35612434

大小:1.01 MB

页数:93页

时间:2019-04-01

最大熵模型与自然语言处理_第1页
最大熵模型与自然语言处理_第2页
最大熵模型与自然语言处理_第3页
最大熵模型与自然语言处理_第4页
最大熵模型与自然语言处理_第5页
资源描述:

《最大熵模型与自然语言处理》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、最大熵模型 与 自然语言处理MaxEntModel&NLPlaputac-liu01@mails.tsinghua.edu.cnNLPGroup,AILab,TsinghuaUniv.TopicsNLP与随机过程的关系(背景)最大熵模型的介绍(熵的定义、最大熵模型)最大熵模型的解决(非线性规划、对偶问题、最大似然率)特征选取问题应用实例总结与启发NLP与随机过程NLP:已知一段文字:x1x2…xn(n个词)标注词性y1y2…yn标注过程:已知:x1x2…xn求:y1已知:x1x2…xny1求:y2已知:x1x2…xny1y2求:

2、y3已知:x1x2…xny1y2y3求:y4…NLP与随机过程yi可能有多种取值,yi被标注为a的概率有多少?随机过程:一个随机变量的序列。x1x2…xnp(y1=a

3、x1x2…xn)x1x2…xny1p(y2=a

4、x1x2…xny1)x1x2…xny1y2p(y3=a

5、x1x2…xny1y2)x1x2…xny1y2y3p(y4=a

6、x1x2…xny1y2y3)…NLP与随机过程x1x2…xnp(y1=a

7、x1x2…xn)x1x2…xny1p(y2=a

8、x1x2…xny1)x1x2…xny1y2p(y3=a

9、x1x2…xny1y

10、2)x1x2…xny1y2y3p(y4=a

11、x1x2…xny1y2y3)…问题:p(yi=a

12、x1x2…xny1y2…yi-1)怎么求?yi与x1x2…xny1y2…yi-1的关系?NLP与随机过程问题:p(yi=a

13、x1x2…xny1y2…yi-1)怎么求?yi与x1x2…xny1y2…yi-1的关系?一个直观的解决:问题again!(x1x2…xny1y2…yi-1)?What’sEntropy?AnExample:假设有5个硬币:1,2,3,4,5,其中一个是假的,比其他的硬币轻。有一个天平,天平每次能比较两堆硬币,得出的

14、结果可能是以下三种之一:左边比右边轻右边比左边轻两边同样重问:至少要使用天平多少次才能保证找到假硬币?(某年小学生数学竞赛题目:P)称硬币(cont.)答案:2次一种方法:Why最少2次?称硬币(cont.)Let:x是假硬币的序号:Let:yi是第i次使用天平所得到的结果:用天平称n次,获得的结果是:y1y2…yny1y2…yn的所有可能组合数目是3n我们要通过y1y2…yn找出x。所以:每个y1y2…yn组合最多可能有一个对应的x取值。因为x取X中任意一个值的时候,我们都要能够找出x,因此对于任意一个x的取值,至少要有一个y

15、1y2…yn与之对应。根据鸽笼原理……称硬币(cont.)Let:x是假硬币的序号:Let:Yi是第i次使用天平所得到的结果:用y1y2…yn表达x。即设计编码:x->y1y2…ynX的“总不确定度”是:Y的“表达能力”是:至少要多少个Y才能准确表示X?称硬币(cont.)Why???为什么用log?“表达能力”与“不确定度”的关系?称硬币(cont.)为什么用log?假设一个Y的表达能力是H(Y)。显然,H(Y)与Y的具体内容无关,只与

16、Y

17、有关。两个Y(就是:y1y2)的表达能力是多少?y1可以表达三种情况,y2可以表达三种

18、情况。两个并列,一共有:3*3=9种情况(乘法原理)。因此:称硬币(cont.)“表达能力”与“不确定度”的关系?都表达了一个变量所能变化的程度。在这个变量是用来表示别的变量的时候,这个程度是表达能力。在这个变量是被表示变量的时候,这个程度是不确定度。而这个可变化程度,就是一个变量的熵(Entropy)。显然:熵与变量本身含义无关,仅与变量的可能取值范围有关。称硬币-Version.2假设有5个硬币:1,2,3,…5,其中一个是假的,比其他的硬币轻。已知第一个硬币是假硬币的概率是三分之一;第二个硬币是假硬币的概率也是三分之一,其

19、他硬币是假硬币的概率都是九分之一。有一个天平,天平每次能比较两堆硬币,得出的结果可能是以下三种之一:左边比右边轻右边比左边轻两边同样重假设使用天平n次找到假硬币。问n的期望值至少是多少?(不再是小学生问题:P)称硬币-Version.2因为第一个、第二个硬币是假硬币的概率是三分之一,比其他硬币的概率大,我们首先“怀疑”这两个。第一次可以把这两个做比较。成功的概率是三分之二。失败的概率是三分之一。如果失败了,第二次称剩下的三个。所以,期望值是:称硬币-Version.2《数据结构》:Huffman编码问题。称硬币-Version.

20、2《数据结构》:Huffman编码问题。称硬币-Version.2《数据结构》:Huffman编码问题。用反证法可以证明,这个是最小值。(假设第一个和第二个硬币中有一个要称两次的话……)称硬币-Version.2《数据结构》:Huffman编码问题。称硬币-Ve

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。