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

自然语言处理中的最大熵方法 马金山信息检索研究室 纲要 熵理论的发展信息熵最大熵理论最大熵理论的应用 什么是熵 什么是熵 没有什么问题在科学史的进程中曾被更为频繁地讨论过普里高津熵定律是自然界一切定律中的最高定律里夫金 霍华德 熵的提出 德国物理学家克劳修斯 RudolphJ Eclausius 于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算法 GeneralizedIterativescaling DarrochandRatcliff 1972IIS算法 ImprovedIterativeScaling DellaPietra1995Input 特征函数特征分布Output 最优参数值最优模型 IIS算法 1Startwithforall2DoforeachaLetbethesolutiontobUpdatethevalueof3Gotostep2ifnotallhaveconverged 词义消歧的例子 词义消歧确定多义词在一个句子中所表达的词义 打 的语义 S1 S2 S3 S4S1 打人S2 打酱油S3 打球S4 打电话他打完篮球后给我打了个电话 确定 打 的语义 没有任何先验知识概率分布 P S1 0 25P S2 0 25P S3 0 25P S4 0 25H p 4X 0 25log20 25 2熵值最大 最合理 确定 打 的语义 先验知识 取S1或S3的概率 0 6取S2或S4的概率 0 4概率分布 P S1 0 3P S2 0 2P S3 0 3P S4 0 2H p 2X 0 2log20 2 2X 0 3log20 3 符合约束的分布中 该分布熵值最大 最合理 不存在没有约束的自由 他了那个坏人打 S1他打了二两酒打 S2他喜欢打篮球打 S3他喜欢打电话打 S4他用手机打我打 S1他酒后打人打 S1一些人在打球打 S3 知识的获取 统计这些先验知识 约束 人 S1 狗 S1 酱油 S2 酒 S2 篮球 S3 冰球 S3 电话 S4 手机 S4 手机 S1 酒 S1 人 S3 知识的形式化表示 在这些约束下 计算P 打 Si 并满足模型的熵最大引入特征函数1ify S3andx 篮球0otherwise 模型的建立 特征选择在所有的特征中 选择最有代表性的特征 构造约束集合参数估计应用IIS算法 计算出每个特征对应的参数值 特征选择 1 最简单的方法 选择出现次数大于n的特征Forexample AdwaitRatnaparkhi1999 Discardfeaturesthatoccurlessthan5times代价最小 特征选择 2 原子特征算法 BasicFeatureSelection 1特征集合S 02任取一特征加入集合中3调用IIS 确定4在该约束集合下 计算熵的增量5选择使熵值增加最大的特征加到S中6调用IIS 计算在此特征集下的7执行2 特征选择 3 近似增益算法 ApproximateGains 已有特征对应参数增加特征对应的参数则增加的特征只影响当前参数 不变模型的形式 Reference A BergerS D PietraV D PietraAmaximumentropyapproachtonaturallanguageprocessingComputationallinguistics1996 V22 1 39 71S D Pietra V D PietraandJ LaffertyInducingfeaturesofrandomfieldsIEEETransactionsonPatternAnalysisandMachineIntelligence1997 V19 4 380 393R RosenfeldAdaptivestatisticallanguagemodeling AMaximumEntropyApproachPhdthesisCMU CS 94 1994 Thanks