自然语言处理中的最大熵方法.ppt

自然语言处理中的最大熵方法 马金山 信息检索研究室 纲 要 熵理论的发展 信息熵 最大熵理论 最大熵理论的应用 什么是熵 什么是熵？ 没有什么问题在科学史的进程中曾被更为频繁地讨论过 普里高津 熵定律是自然界一切定律中的最高定律 里夫金霍华德 熵的提出 德国物理学家克劳修斯（Rudolph J.E clausius） 于1865提出熵的概念 其经典意义定义为： R表示可逆过程，即体系的熵变等于可逆过程吸收或耗散的热量除以它的绝对温度。 熵原理的形象比喻 一滴墨水滴入一杯清水中，墨水扩散后均匀地分布在清水中 比喻热力体系的自发过程总是趋于温度均匀分布， 反之不行。 微观世界中熵的含义 热力学定律都是对物质宏观性质进行考察得到的经验定律 宏观物体是大量微观粒子构成的 1872年，波尔兹曼（L．Boltzmann）指出熵是大量微观粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数 熵值高意味着无序性强 ! 熵增原理 一个孤立系统的熵，自发性地趋于极大，随着熵的增加，有序状态逐步变为混沌状态，不可能自发地产生新的有序结构。 当熵处于最小值, 即能量集中程度最高、有效能量处于最大值时, 那么整个系统也处于最有序的状态,相反为最无序状态。 熵增原理预示着自然界越变越无序 熵的普遍性 熵概念的泛化 熵理论是存在问题的， 需要发展和完善 熵与信息 1948年电气工程师香农( Shannon)创立了信息论，将信息量与熵联系起来。 他用非常简洁的数学公式定义了信息时代的基本概念：熵 H(p) = -p(x)logp(x) 单位：bits 通信中的熵 表示“是” 和 “否” 1 = 是 0 =否 表示“是” 、“否”和“可能是” 11 =是 00 = 否 10(01) = 可能是 一条消息的熵就是编码这条消息所需二进制位即比特的个数。 随机事件的熵 熵定量的描述事件的不确定性 设随机变量 ，它有A1，A2，…，An共n个可能的结局，每个结局出现的机率分别为p1,p2 ，...，pn，则 的不确定程度，即信息熵为: 熵越大，越不确定 熵等于0，事件是确定的 例子 抛硬币 掷色子（32个面） 不公平的硬币 熵的图形 信息熵的意义 信息熵概念为测试信息的多少找到了一个统一的科学定量计量方法，是信息论的基础。 信息熵将数学方法和语言学相结合 最大熵理论 熵增原理 在无外力作用下，事物总是朝着最混乱的方向发展 事物是约束和自由的统一体 事物总是在约束下争取最大的自由权，这其实也是自然界的根本原则。 在已知条件下，熵最大的事物，最可能接近它的真实状态 最大熵原则下点的分布 最大熵原则下点的分布 最大熵原则下点的分布 最大熵原则下点的分布 选择最好的模型 研究某个随机事件，根据已知信息，预测其未来行为。 当无法获得随机事件的真实分布时，构造统计模型对随机事件进行模拟。 满足已知信息要求的模型可能有多个。 基于最大熵原理选择模型 选择熵最大的模型 Jaynes证明：对随机事件的所有相容的预测中，熵最大的预测出现的概率占绝对优势 Tribus证明，正态分布、伽玛分布、指数分布等，都是最大熵原理的特殊情况 基于最大熵的统计建模 特征空间的确定 特征选择 建立统计模型 基于最大熵的统计建模即发现满足已知条件的熵最大的模型 基于最大熵的统计建模 已有特征 f1(x,y), f2(x,y)…, fn(x,y) 特征的经验概率： 特征的期望概率： 如果样本足够多，可信度高的特征的经验概率与真实概率一致的 由训练样本习得的模型,对可信度高的特征的估计应满足约束等式: 基于最大熵的统计建模 事件的熵 计算模型的最大熵 得 其中 最大熵模型求解 参数估计 GIS算法(Generalized Iterative scaling) Darroch and Ratcliff,1972 IIS算法(Improved Iterative Scaling) Della Pietra 1995 Input: 特征函数 特征分布 Output: 最优参数值 最优模型 IIS算法 1 Start with for all 2 Do for each a Let be the solution to b Update the value of 3