文档介绍：熵导论与最大熵模型北京 10月机器学****班邹博 2014 年10月26日 2 /74 本次目标?理解并掌握熵E ntropy 的定义?理解“ Huffman 编码是所有编码中总编码长度最短的”熵含义?理解联合熵 H(X,Y) 、相对熵 D(X||Y) 、条件熵 H(X|Y) 、互信息 I(X,Y) 的定义和含义,并了解如下公式: ? H(X|Y) = H(X,Y) - H(Y)=H(X) - I(X,Y) ? H(Y|X) = H(X,Y) - H(X)=H(Y) – I(X,Y) ? I(X,Y) = H(X) - H(X|Y) = H(X) + H(Y) - H(X,Y) ≥0 ?掌握最大熵模型 Maxent ? Maximum Entropy Models ?了解最大熵在自然语言处理 NLP 中的应用? Natural Language Processing ?与前序知识的联系: 最大熵模型和极大似然估计 MLE 的关系? Maximum Likelihood Estimation ?副产品:了解数据分析、函数作图的一般步骤 3 /74 温故知新?证明: -lnx ≥ 1-x , x>0 ? f(x)=-lnx + x – 1, x>0 , ?凸函数?在 x=1 处取极值? Jensen 不等式: exp(p ’x)≤p’ exp(x) ?暂且记下这两个不等式,后面的内容会涉及到?拉格朗日对偶问题?举例说明最大熵模型的应用 4 /74 对偶问题?一般优化问题的 Lagrange 乘子法? Lagrange 函数?对固定的 x, Lagrange 函数 L(x, λ,v) 为关于λ和v 的仿射函数 5 /74 Lagrange 对偶函数(dual function) ? Lagrange 对偶函数?若没有下确界,定义: ?根据定义,显然有:对?λ>0 ,?v,若原优化问题有最优值 p*,则?进一步: Lagrange 对偶函数为凹函数。 6 /74 7 /74 8 /74 9 /74 从小学数学开始?假设有 5个硬币: 1,2,3,4,5 ,其中一个是假的, 比其他的硬币轻。有一个天平,天平每次能比较两堆硬币,得出的结果可能是以下三种之一: ?左边比右边轻?右边比左边轻?两边同样重?问:至少要使用天平多少次才能确保找到假硬币? 10 /74 答案?一种可能的称量方法如右图所示?答案: 2次?追问:为什么 2次? 1+2 ? 3+4 1 ? 2 3 ? 4 5 1 4 > = > <<23 < >