最大熵理论及其应用

信息检索实验室信息检索实验室廖先桃IR_Lab2005.9.27最大熵理论及其应用信息检索实验室信息检索实验室提纲„最大熵理论„基于最大熵的统计建模„最大熵工具包的使用„最大熵模型与其他模型的比较信息检索实验室信息检索实验室最大熵理论（1）„让人困惑的概念z熵z信息熵z最大熵理论z最大熵模型z交叉熵z相对熵信息检索实验室信息检索实验室最大熵理论（2）„熵z物理学概念z宏观上：热力学定律——体系的熵变等于可逆过程吸收或耗散的热量除以它的绝对温度（克劳修斯，1865）z微观上：熵是大量微观粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数（波尔兹曼，1872）z结论：熵是描述事物无序性的参数，熵越大则无序性越强信息检索实验室信息检索实验室最大熵理论（3）„熵在自然界的变化规律——熵增原理z一个孤立系统的熵，自发性地趋于极大，随着熵的增加，有序状态逐步变为混沌状态，不可能自发地产生新的有序结构。z当熵处于最小值,即能量集中程度最高、有效能量处于最大值时,那么整个系统也处于最有序的状态,相反为最无序状态。z熵增原理预示着自然界越变越无序信息检索实验室信息检索实验室最大熵理论（4）„信息熵z和熵的联系——熵是描述客观事物无序性的参数。香农认为信息是人们对事物了解的不确定性的消除或减少，他把不确定的程度称为信息熵（香农，1948）z随机事件的信息熵：设随机变量ξ，它有A1，A2，A3，A4，……，An共n种可能的结局，每个结局出现的概率分别为p1，p2，p3，p4，……，pn，则其不确定程度，即信息熵为∑−=niippH1log)(ξ信息检索实验室信息检索实验室最大熵理论（5）„信息熵z信息熵是数学方法和语言文字学的结合z一个系统的熵就是它的无组织程度的度量z熵越大，事件越不确定z熵等于0，事件是确定的z举例：抛硬币熵值最大，正反面的概率相等，事件最不确定信息检索实验室信息检索实验室最大熵理论（6）„熵的图形信息检索实验室信息检索实验室最大熵理论（7）„最大熵理论z熵增原理z在无外力作用下，事物总是朝着最混乱的方向发展z事物是约束和自由的统一体z事物总是在约束下争取最大的自由权，这其实也是自然界的根本原则z在已知条件下，熵最大的事物，最可能接近它的真实状态信息检索实验室信息检索实验室最大熵理论（8）„最大熵原则下点的分布z对一随机过程，如果没有任何观测量，即没有任何约束，则解为均匀分布信息检索实验室信息检索实验室最大熵理论（9）„最大熵原则下点的分布z增加约束条件信息检索实验室信息检索实验室最大熵理论（10）„最大熵原则下点的分布信息检索实验室信息检索实验室最大熵理论（11）„最大熵原则下点的分布信息检索实验室信息检索实验室提纲„最大熵理论„基于最大熵的统计建模„最大熵工具包的使用„最大熵模型与其他模型的比较信息检索实验室信息检索实验室基于最大熵的统计建模（1）„建模理论„数学描述„数学推导过程信息检索实验室信息检索实验室基于最大熵的统计建模（2）„建模理论z以最大熵理论为基础的统计建模z为什么可以基于最大熵建模呢？zJaynes证明：对随机事件的所有相容的预测（相容预测是指符合已知的某些参数与随机事件相关条件的某种对随机事件分布的预测）中，熵最大的预测出现的概率占绝对优势zTribus证明，正态分布、伽玛分布、指数分布等，都是最大熵原理的特殊情况信息检索实验室信息检索实验室基于最大熵的统计建模（3）„建模理论z结论：最大熵统计建模是以最大熵理论为基础的一种选择模型的方法，即从符合条件的分布中选择熵最大的分布作为最优的分布z用公式表示：满足约束条件的所有分布选择熵最大的分布信息检索实验室信息检索实验室基于最大熵的统计建模（4）„建模理论z最大熵统计模型需要解决的问题：„特征空间的确定——问题域„特征选择——寻找约束条件„建立统计模型——基于最大熵理论建立熵最大的模型z系统输入：特征z系统输出：最优的熵最大的模型信息检索实验室信息检索实验室基于最大熵的统计建模（5）„数学描述z问题描述：设最终输出值构成的语言学类别有限集为Y，对于每个y∈Y，其生成均受上下文信息x的影响和约束。已知与y有关的所有上下文信息组成的集合为X，则模型的目标是：给定上下文x∈X，计算输出为y∈Y的条件概率p(y|x)。信息检索实验室信息检索实验室基于最大熵的统计建模（6）„数学推导过程z模型输入：从人工标注的训练数据中抽取的训练样本集T={(x1,y1)，(x2,y2)，……，(xn,yn)}，(xi,yi)表示在语料库中出现yi时其上下文信息为xi。z用概率分布的极大似然对训练语料表示如下，其中是(x,y)在语料中出现的次数，N为总词数。),(1),(~yxCountNyxp×=),(yxCount信息检索实验室信息检索实验室基于最大熵的统计建模（7）„数学推导过程z特征f是指x与y之间存在的某种特定关系，用二值函数函数表示：z特征的经验概率是所有满足特征要求的的经验概率之和，即：z（1）z∑=yxyxfyxpfp,),(),(~)(~信息检索实验室信息检索实验室基于最大熵的统计建模（8）„数学推导过程z特征的期望概率是特征在所学习的随机事件中的真实分布为：z（2）z其中：z是指x出现的情况下，y的经验概率z是指x出现的情况下，y的真实概率∑=yxyxfxypxpfp,),()|()(~)()|(~xyp)|(xyp信息检索实验室信息检索实验室基于最大熵的统计建模（9）„数学推导过程z特征的经验概率与期望概率应该一致，即：（3）z即：（4）z上面的式子即称为约束等式)(~)(fpfp=∑∑=yxyxyxfyxpyxfxypxp,,),(),(~),()|()(~信息检索实验室信息检索实验室基于最大熵的统计建模（10）„数学推导过程z设存在k个特征fi(i=1,2,…,k)，多个约束等式构成的集合叫约束集，可表示为：（5）z最大熵模型，是满足约束集条件的所有模型中熵最大的模型，即：p*=argmaxH(p)（6）其中p为满足约束集C条件的某一统计模型。信息检索实验室信息检索实验室基于最大熵的统计建模（11）„数学推导过程z特征fi的权重用相对应的参数表示，则满足最大熵的条件用指数形式表示为：（7）其中：（8）称为归一化因子。iλ)|(xyp∑Ζ=iiiyxfxxyp)),(exp()(1)|(λλλ∑∑=Ζyiiyxfx)),(exp()(λλ信息检索实验室信息检索实验室基于最大熵的统计建模（12）„最大熵模型的求解（参数估计方法）zGIS算法(GeneralizedIterativescaling)„DarrochandRatcliff,1972zIIS算法(ImprovedIterativeScaling)„DellaPietra1995zInput:特征函数特征分布zOutput:最优参数值最优模型信息检索实验室信息检索实验室基于最大熵的统计建模（14）„特征选择z在所有的特征中，选择最有代表性的特征，构造约束集合„参数估计z应用IIS算法，计算出每个特征对应的参数值信息检索实验室信息检索实验室提纲„最大熵理论„基于最大熵理论的统计建模„最大熵工具包的使用„最大熵模型与其他模型的比较信息检索实验室信息检索实验室最大熵工具包的使用（1）„MaximumEntropyModelingToolkitforPythonandC++，ZhangLe，2004.12.29„两种运行方式：z命令行形式z使用函数接口信息检索实验室信息检索实验室最大熵工具包的使用（2）„命令行方式运行z训练过程„输入从训练语料中提取的特征文件„输出训练模型z识别过程„输入从测试语料中提取的特征文件„输出类别预测的结果信息检索实验室信息检索实验室最大熵工具包的使用（3）„命令行方式运行z训练特征的格式信息检索实验室信息检索实验室最大熵工具包的使用（4）„命令行运行方式z特征事例：公式中的X公式中的y信息检索实验室信息检索实验室最大熵工具包的使用（5）„命令行形式运行z训练命令：z其中，maxent是运行命令；-m指示训练输出的模型的名字，由modelName给出；-i指示训练迭代的次数；train.txt是输入的特征文本。该形式不会有训练信息显示z例子1maxent–mmodelName–i30train.txt信息检索实验室信息检索实验室最大熵工具包的使用（6）„命令行形式运行z训练命令：z其中，-v将显示训练信息z例子2maxent–mmodelName–i30-vtrain.txt信息检索实验室信息检索实验室最大熵工具包的使用（7）„命令行形式运行z常用的选项(可用maxent–h列出)信息检索实验室信息检索实验室最大熵工具包的使用（8）„命令行方式z测试z将输出对每个事件的预测结果z将输出详细的概率信息信息检索实验室信息检索实验室最大熵工具包的使用（9）„使用函数接口z运行环境：VC7.0z加入头文件：#includemaxentmodel.hppz类名：MaxentModelz训练过程：„加入特征事件：„begin_add_event();„add_event(constvectorstring&context,constoutcome_type&outcome,size_tcount=1)„end_add_event()信息检索实验室信息检索实验室最大熵工具包的使用（10）„使用接口函数z训练：train(size_titer=15,conststd::string&method=lbfgs,doublesigma=0.0,doubletol=1E-05)z保存模型：save(conststring&model,boolbinary=false)z例子3信息检索实验室信息检索实验室最大熵工具包的使用（11）„使用接口函数z测试：„加载模型：load(conststring&model)„加入特征，方法同训练„模型估计：eval_all（(constvectorstring&context,std::vectorpairoutcome_type,double&outcomes,boolsort_result=true）„例子4信息检索实验室信息检索实验室提纲„最大熵理论„基于最大熵理论的统计建模„最大熵工具包的使用„最大熵模型与其他模型的比较信息检索实验室信息检索实验室最大熵模型与其他模型的比较（1）„最大熵方法的优点z建模时，试验者只需集中精力选择特征，而不需要花费精力考虑如何使用这些特征z特征选择灵活，且不需要额外的独立假定或内在约束z模型应用在不同领域时的可移植性强z可结合更丰富的信息信息检索实验室信息检索实验室最大熵模型与其他模型的比较（2）„最大熵方法的缺点z时空开销大z数据稀疏问题比较严重z对语料库依赖性较强信息检索实验室信息检索实验室最大熵模型与其他模型的比较（3）„HMM的优点z算法简单，易于实现z执行效率较高„HMM的缺点z不易于融合更多的语言信息z对于某些复杂问题的处理效果不好信息检索实验室信息检索实验室最大熵模型与其他模型的比较（4）„与HMM实验结果对比z训练：北大富士通语料24,994句z测试：北大富士通语料10,000句NE类型准确率(%)召回率(%)F值(%)人名(Ni)93.3093.3393.32地名(Ns)72.3189.7280.08机构名(Ni)76.4725.9238.71专有名词(Nz)59.2781.2468.53总的结果79.0077.2878.13信息检索实验室信息检索实验室最大熵模型与其他模型的比较（5）„与HMM+rule实验结果对比NE类型准确率(%)召回率(%)F值(%)人名(Ni)93.8686.8693.19地名(Ns)86.6985.8386.25机构名(Ni)77.2065.9071.10专有名词(Nz)77.1480.3278.70总的结果86.9383.6985.28信息检索实验室信息检索实验室最大熵模型与其他模型的比较（6）„基于最大熵的NE识别（BI