资源描述：
《最大熵模型与自然语言处理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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
