1、最大熵方法及其在自然语言处理中的应用吕先超2015年1月21日2熵信息熵最大熵理论最大熵模型参数估计特征选择最大熵模型的应用最大熵理论熵：物理学中的熵物理学概念：宏观上：热力学定律体系的熵变等于可逆过程吸收或耗散的热量除以它的绝对温度（克劳修斯，1865）微观上：熵是大量微观粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数（波尔兹曼，1872）结论：熵是描述事物无序性的参数，熵越大则无序性越强。熵：自然界中的熵增原理熵增原理是熵在自然界的变化规律一个孤立系统的熵，自发性地趋于极大，随着熵的增加，有序状态逐步变为混沌状态，不可能自发的产生新的有序结构。当熵处于最小值，
2、即能量集中程度最高、有效能量处于最大值时，那么整个系统也处于最有序的状态，相反为最无序状态。熵增原理预示着自然界越变越无序。熵：信息熵和熵的联系熵是描述客观事物无序性的参数。香农认为信息是人们对事物了解的不确定性的消除或减少，他把不确定的程度称为信息熵（香农，1948）随机事件的信息熵：设随机变量，他有A1,A2,An共n种可能的结局每个结局出现的概率分别为p1,p2,pn，则其不确定程度，即信息熵为:对熵的感性认识熵就是不确定性的变化程度。熵与变量本身含义或值无关，只和变量的可能取值范围有关。例子举个例子，一个快餐店提供3种食品：汉堡(B)、鸡肉(C)、鱼(F)。价格分别是1元、2元、3元。
3、已知人们在这家店的平均消费是1.75元，求顾客购买这3种食品的概率。如果你假设一半人买鱼另一半人买鸡肉，那么根据熵公式，这不确定性就是1位（熵等于1）。但是这个假设很不合适，因为它超过了你所知道的事情。我们已知的信息是：p(B)+p(C)+p(F)=11p(B)+2p(C)+3p(F)=1.75以及关于对概率分布的不确定性度量，熵：H=-p(B)log(p(B)-p(C)log(p(C)-p(F)log(p(F)对前两个约束，两个未知概率可以由第三个量来表示，可以得到： p(C)=0.75-2p(F) p(B)=0.25+p(F) 把上式代入熵的表达式中，熵就可以用单个概率p(F)来表示,对这
4、个单变量优化问题，很容易求出当p(F)=0.216时，有最大熵H=1.517总结一下。以上，我们根据未知的概率分布表示了约束条件，用这些约束条件消去了两个变量，用剩下的变量表示熵，最后求出了熵最大时剩余变量的值，结果就求出了一个符合约束条件的概率分布，它有最大不确定性，我们在概率估计中没有引入任何偏差。熵公式的理解：熵的性质0H(X)log|X|第一个等号在X为确定值的时候成立（没有变化的可能）第二个等号在X均匀分布的时候成立最大熵理论：熵增原理在无外力作用下，事物总是朝着最混乱的方向发展事物是约束和自由的统一体事物总是在约束下争取最大的自由权，这其实也是自然界的根本原则在已知条件下，熵最大的
5、事物，最可能接近它的真实状态最大熵原则下最大熵原则下点点的分布：的分布：对一随机过程，如果没有任何观测量，即没有任何约束，则解为均匀分布。增加约束条件继续增加约束条件以最大熵理论为基础的统计建模为什么可以基于最大熵建模呢？Jaynes证明：对随机事件的所有相容的预测中，熵最大的预测出现的概率占绝对优势Tribus证明，正态分布、伽玛分布、指数分布等，都是最大熵原理的特殊情况。基于最大熵的统计建模：建模理论基于最大熵的统计建模：建模理论结论：最大熵统计建模是以最大熵理论为基础的一种选择模型的方法，即从符合条件的分布中选择熵最大的分布作为最优的分布基于最大熵的统计建模：建模理论最大熵统计模型需要解
6、决的问题：特征空间的确定问题域特征选择寻找约束条件建立统计模型基于最大熵理论建立熵最大的模型问题描述：设最终输出值构成的语言学类别有限集为Y，对于每个yY，其生成均受上下文信息x的影响和约束。已知与y有关的所有上下文信息组成的集合为X，则模型的目标是：给定上下文xX，计算输出为yY的条件概率p(y|x)。基于最大熵的统计建模：数学描述最大熵模型建模框架图训练样例例子：我们的任务是为词“打”的词性标注过程建立模型，标注模型为p，每个可能的词性为p(t)。“打”的可能词性：动词，量词，介词由此，模型p的第一个约束：p(动词)+p(量词)+p(介词)=1训练样例在训练最大熵模型时，任务选连系统通过数
7、据转换程序或者模式识别中通常所说的特征抽取器，把真实世界的，原始训练数据通过特定的方法或者算法转化为多维特征或属性表示的训练样例。条件最大熵方法是一种有监督的机器学习方法，所以每个训练样例由一个实例x以及他的目标概念类y组成。训练样例：例子每个样例将包含“打”周围的词语x，如图，以及在此场合下“打”的词性y。（1）模型输入：从人工标注的训练数据中抽取的训练样本集T=(x1,y1)，(x2,y2)，(xn,yn)，(xi,yi)表示在语料库中出现yi时其上下文信息为xi。（ 2 ） 从 训 练 样 例 中 得 到 经 验 概 率 分 布 ： 其 中Count(x,y)是(x,y)在语料中出现的次
8、数，N为总词数。则基于最大熵的统计建模：数学推导（3）特征f是指x与y之间存在的某种特定的关系，用二值函数表示：（4）特征的经验概率期望值是所有满足特征要求的的经验概率之和，即：基于最大熵的统计建模：数学推导引入特征：例子引入1个特征：（5）特征的期望概率是特征在所学习的随机事件中的真实分布为：其中，(y|x)是指x出现的情况下，y的经验概率p(y|x)是指x出现的情况下，y的真实概率基于最大熵的统计建模：数学推导（6）特征的经验概率与期望概率应该一致，即：p(f)=(f)即：上面的式子即称为约束等式基于最大熵的统计建模：数学推导（7）设存在k个特征fi(i=1,2,k)，多个约束等式构成的集
9、合叫做约束集，可表示为：C=pP|p(f)=(f),ii=1,2,，k（8）最大熵模型，是满足约束条件的所有模型中熵最大的模型，即：p*=argmaxH(p)其中p为满足约束集C条件下的某一统计模型。argmax表示寻找具有最大评分的参量。基于最大熵的统计建模：数学推导（9）于是我们可以把这个最大熵模型表示成：在满足约束条件中选择熵最大的那个。这是一个有约束的优化问题：基于最大熵的统计建模：数学推导我们可以用拉格朗日乘数法来解决这个优化问题。具体步骤如下：为每一个特征引入一个参数(称为拉格朗日算子)，另外由于p(y|x)是条件概率，所以有，所以也要为每个实例x引入一个参数k(x)。那么拉格朗日
10、函数可以定义为：(p,)=H(p)+然后对它求导，就可以求出(p,)最大时(y|x)。基于最大熵的统计建模：数学推导（9）特征fi的权重用相对应的参数i表示，则满足最大熵的条件p(y|x)用指数形式表示为：其中：称为归一化因子。基于最大熵的统计建模：数学推导(10)此时，最大值()=-(11)称为归一化因子，它的引入是为了保证(12)这样我们就把一个有约束的优化问题转化为一个没有约束优化的问题。基于最大熵的统计建模：数学推导最大熵模型的求解许多自然语言处理问题都可以归结为分类问题，其任务是估计目标概念类y在实例或上下文或条件x的概率，即p(y|x).最大熵模型有两个基本的任务：特征选择和模型选
11、择。特征选择：选择一个能表达随机过程的统计特征的特征集合。模型选择：即模型估计或者参数估计，就是为每个入选的特征估计权重。Input：特征函数集合f，特征经验分布Output：最优参数值集合，最优模型基于最大熵的统计建模：参数估计GIS算法（GeneralizedIterativeScaling）DarrochandRatcliff,1972IIS算法（ImprovedIterativeScaling）DellaPietra,1995SCGIS算法Goodman,2002其他算法基于最大熵的统计建模：参数估计在所有的特征中选择最有代表性的特征，构造约束集合数据稀疏的问题特征选择的步骤： 特征模
12、板候选特征 候选特征选择特征特征选择的方法： 增量式特征选择算法：基本算法和近似算法 基于频数阀值的特征选择算法基于最大熵的统计建模：特征选择最大熵模型的优缺点最大熵模型的优点：建模时，试验者只需集中精力选择特征，而不需要花费精力考虑如何使用这些特征。特征选择灵活，且不需要额外的独立假定或者内在约束模型应用在不同领域时的可移植性强可结合更丰富的信息时空开销大数据稀疏问题严重对语料库的依赖性较强最大熵模型的优缺点最大熵模型的应用最大熵模型已经成功应用于自然语言处理的许多领域，比如： 词性标注(Pos Tagging)Ratnapakrhi 1996 短语识别（Chunking）Koeling 2002 指代消解（Co-reference Resolution）Luo et al 2003 语法分析（Syntactic Parsing）Ratnaparkhi 1999最大熵模型的应用 机器翻译（Machine Translation）Berger et al 1996 文本分类（Text Classification）Nigam 1999 问题回答（Question Answering）Ittycheriah 2002 语言模型（Language Modeling）Rosenfeld 1994等最大熵模型的应用文本分类中文指代消解汉语语义消歧不良文本识别分词词性标注机器翻译其他谢谢！
