最大熵模型.pptVIP

熵导论与最大熵模型 北京10月机器学习班 邹博 2014年10月26日 本次目标 理解并掌握熵Entropy的定义 理解“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 副产品：了解数据分析、函数作图的一般步骤 温故知新 证明： -lnx ≥1-x , x0 f(x)=-lnx + x – 1, x0， 凸函数 在x=1处取极值 Jensen不等式：exp(p’x)≤p’ exp(x) 暂且记下这两个不等式，后面的内容会涉及到 拉格朗日对偶问题 举例说明最大熵模型的应用 对偶问题 一般优化问题的Lagrange乘子法 Lagrange函数 对固定的x，Lagrange函数L(x,λ,v)为关于λ和v的仿射函数 Lagrange对偶函数(dual function) Lagrange对偶函数 若没有下确界，定义： 根据定义，显然有：对?λ0，?v，若原优化问题有最优值p*，则 进一步：Lagrange对偶函数为凹函数。 从小学数学开始 假设有5个硬币：1,2,3,4,5，其中一个是假的，比其他的硬币轻。有一个天平，天平每次能比较两堆硬币，得出的结果可能是以下三种之一： 左边比右边轻 右边比左边轻 两边同样重 问：至少要使用天平多少次才能确保找到假硬币? 答案 一种可能的称量方法如右图所示 答案：2次 追问：为什么2次？ 分析 令x表示假硬币的序号： x∈X={1,2,3,4,5}； 令yi是第i次使用天平所得到的结果：y∈Y={1,2,3}； 1表示“左轻”，2表示“平衡”，3表示“右轻” 用天平称n次，获得的结果是：y1 y2… yn； y1 y2… yn的所有可能组合数目是3n； 根据题意，要求通过y1 y2… yn确定x。即建立影射map(y1y2…yn)=x； 从而：y1y2…yn的变化数目大于等于x的变化数目 即3n≥5 一般意义下： 进一步分析 用y1 y2… yn表达x。即设计编码：x- y1 y2… yn X的“总不确定度”是： Y的“表达能力”是： 至少要多少个Y才能准确表示X？ 题目的变种 假设有5个硬币：1,2,3,4,5，其中一个是假的，比其他的硬币轻。已知第一个硬币是假硬币的概率是三分之一；第二个硬币是假硬币的概率也是三分之一，其他硬币是假硬币的概率都是九分之一。 有一个天平，天平每次能比较两堆硬币，得出的结果可能是以下三种之一： 左边比右边轻 右边比左边轻 两边同样重 假设使用天平n次找到假硬币。问n的期望值至少是多少？ 解 1/3概率的硬币有2个，1/9概率的硬币有3个： 定义：-Σplogap为熵 用熵解释Huffman编码 用熵解释Huffman编码 Huffman编码 本质：高概率出现的字符用更短的编码 广泛的结论 如果一个随机变量x的可能取值为X={x1, x2,…, xk}。要用n位y: y1y2…yn表示（每位y有c种取值）n的期望值至少为： 一般地，我们令c为2（二进制表示），于是，X的信息量为： 熵 将P(x=xi)写成普适公式，就得到熵的定义： 研究函数f(x)=xlnx f(x)=xlnx，x∈[0,1] f’(x) = lnx + 1 f’’(x) = 1/x0(凸函数) 当f’(x)=0时，x=1/e，取极小值； lim f(0)=0 lim f(1)=1 离散采样 绘图 熵和不确定性 熵是随机变量不确定性的度量，不确定性越大，熵值越大；若随机变量退化成定值，熵为0 均匀分布是“最不确定”的分布 联合熵和条件熵 两个随机变量X，Y的联合分布，可以形成联合熵Joint Entropy，用H(X,Y)表示 H(X,Y) – H(Y) (X,Y)发生所包含的熵，减去Y单独发生包含的熵：在Y发生的前提下，X发生“新”带来的熵 该式子定义为Y发生前提下，X的熵： 条件熵H(X|Y) 推导条件熵的定义式 自封闭系统的运动总是倒向均匀分布 相对熵 相对熵，又称互熵，交叉熵，鉴别信息，Kullback熵