最大熵理论及其应用
廖先桃 IR_Lab 2005.9.27
信息检索实验室
提纲
最大熵理论 基于最大熵的统计建模 最大熵工具包的使用 最大熵模型与其他模型的比较
信息检索实验室
最大熵理论（1）
让人困惑的概念
熵 信息熵 最大熵理论 最大熵模型 交叉熵 相对熵
信息检索实验室
最大熵理论（2）
熵
物理学概念 宏观上：热力学定律——体系的熵变等于可逆过程 吸收或耗散的热量除以它的绝对温度（克劳修斯， 1865） 微观上：熵是大量微观粒子的位置和速度的分布概 率的函数，是描述系统中大量微观粒子的无序性的 宏观参数（波尔兹曼，1872） 结论：熵是描述事物无序性的参数，熵越大则无序 性越强
信息检索实验室
最大熵工具包的使用（6）
命令行形式运行
训练命令： maxent –m modelName –i 30 -v train.txt 其中，-v将显示训练信息 例子2
信息检索实验室
最大熵工具包的使用（7）
命令行形式运行
常用的选项(可用maxent –h列出)
信息检索实验室
最大熵工具包的使用（8）
信息检索实验室
基于最大熵的统计建模（7）
数学推导过程
特征f是指x与y之间存在的某种特定关系，用二 值函数函数表示：
特征的经验概率是所有满足特征要求的的经验 概率之和，即： ~( f ) = ~ ( x, y ) f ( x, y ) （1） p p
∑
x, y
信息检索室
最大熵理论（9）
最大熵原则下点的分布
增加约束条件
信息检索实验室
最大熵理论（10）
最大熵原则下点的分布
信息检索实验室
最大熵理论（11）
最大熵原则下点的分布
信息检索实验室
提纲
最大熵理论 基于最大熵的统计建模 最大熵工具包的使用 最大熵模型与其他模型的比较
信息检索实验室
基于最大熵的统计建模（1）
信息检索实验室
最大熵工具包的使用（10）
使用接口函数
训练：train(size_t iter=15, const std::string &method="lbfgs", double sigma=0.0, double tol=1E-05) 保存模型：save(const string &model, bool binary=false) 例子3
基于最大熵的统计建模（9）
数学推导过程
特征的经验概率与期望概率应该一致，即： （3） p( f ) = ~( f ) p 即：
p p ∑ ~( x) p( y | x) f ( x, y) = ∑ ~( x, y) f ( x, y) （4）
x, y x, y
上面的式子即称为约束等式
信息检索实验室
信息检索实验室
最大熵工具包的使用（11）
使用接口函数
测试：
加载模型：load (const string &model) 加入特征，方法同训练 模型估计：eval_all（(const vector< string > &context, std::vector< pair< outcome_type, double > > &outcomes, bool sort_result=true） 例子4
信息检索实验室
最大熵理论（4）
信息熵
和熵的联系——熵是描述客观事物无序性的参 数。香农认为信息是人们对事物了解的不确定 性的消除或减少 ，他把不确定的程度称为信息 熵（香农，1948 ） 随机事件的信息熵：设随机变量ξ，它有A1， A2，A3，A4，……，An共n种可能的结局，每 个结局出现的概率分别为p1，p2，p3， p4，……，pn，则其不确定程度，即信息熵为
信息检索实验室
最大熵理论（3）
熵在自然界的变化规律——熵增原理
一个孤立系统的熵，自发性地趋于极大，随着熵的增 加，有序状态逐步变为混沌状态，不可能自发地产生 新的有序结构。 当熵处于最小值, 即能量集中程度最高、有效能量处 于最大值时, 那么整个系统也处于最有序的状态,相反 为最无序状态。 熵增原理预示着自然界越变越无序
基于最大熵的统计建模（10）
数学推导过程
设存在k个特征fi(i=1,2,…,k)，多个约束等式构 成的集合叫约束集，可表示为： （5） 最大熵模型，是满足约束集条件的所有模型中 熵最大的模型，即： p*=argmaxH(p) （6） 其中p为满足约束集C条件的某一统计模型。
信息检索实验室
基于最大熵的统计建模（11）
命令行方式
测试
将输出对每个事件的预测结果
将输出详细的概率信息
信息检索实验室
最大熵工具包的使用（9）
使用函数接口
运行环境：VC7.0 加入头文件：#include <maxentmodel.hpp> 类名：MaxentModel 训练过程：
加入特征事件： begin_add_event(); add_event(const vector< string > &context, const outcome_type &outcome, size_t count=1) end_add_event()
信息检索实验室
最大熵模型与其他模型的比较（6）
基于最大熵的NE识别（BIO标注集）
NE类型 人名(Ni) 地名(Ns) 机构名(Ni) 专有名词(Nz) 时间 日期 数量短语 总的结果
信息检索实验室
最大熵工具包的使用（1）
Maximum Entropy Modeling Toolkit for Python and C++ ，Zhang Le，2004.12.29 两种运行方式：
命令行形式 使用函数接口
信息检索实验室
最大熵工具包的使用（2）
命令行方式运行
训练过程
输入从训练语料中提取的特征文件 输出训练模型
信息检索实验室
基于最大熵的统计建模（3）
建模理论
结论：最大熵统计建模是以最大熵理论为基础 的一种选择模型的方法，即从符合条件的分布 中选择熵最大的分布作为最优的分布 满足约束条件 的所有分布 用公式表示：
选择熵最大 的分布
信息检索实验室
基于最大熵的统计建模（4）
建模理论
最大熵统计模型需要解决的问题：
Input: 特征函数 特征分布 Output: 最优参数值 最优模型
信息检索实验室
基于最大熵的统计建模（14）
特征选择
在所有的特征中，选择最有代表性的特征，构 造约束集合
参数估计
应用IIS算法，计算出每个特征对应的参数值
信息检索实验室
提纲
最大熵理论 基于最大熵理论的统计建模 最大熵工具包的使用 最大熵模型与其他模型的比较
信息检索实验室
最大熵理论（7）
最大熵理论
熵增原理 在无外力作用下，事物总是朝着最混乱的方向 发展 事物是约束和自由的统一体 事物总是在约束下争取最大的自由权，这其实 也是自然界的根本原则 在已知条件下，熵最大的事物，最可能接近它 的真实状态
信息检索实验室
最大熵理论（8）
最大熵原则下点的分布
对一随机过程，如果没有任何观测量，即没有 任何约束，则解为均匀分布
建模理论 数学描述 数学推导过程
信息检索实验室
基于最大熵的统计建模（2）
建模理论
以最大熵理论为基础的统计建模 为什么可以基于最大熵建模呢？ Jaynes证明：对随机事件的所有相容的预测 （相容预测是指符合已知的某些参数与随机事 件相关条件的某种对随机事件分布的预测 ） 中，熵最大的预测出现的概率占绝对优势 Tribus证明，正态分布、伽玛分布、指数分布 等，都是最大熵原理的特殊情况
y
（8）
称为归一化因子。
信息检索实验室
基于最大熵的统计建模（12）
最大熵模型的求解（参数估计方法）
GIS算法(Generalized Iterative scaling)
Darroch and Ratcliff,1972
IIS算法(Improved Iterative Scaling)
Della Pietra 1995
与HMM实验结果对比
训练：北大富士通语料24,994句 测试：北大富士通语料10,000句
NE类型 准确率(%) 召回率(%) F值(%) 人名(Ni) 93.30 93.33 93.32 地名(Ns) 72.31 89.72 80.08 机构名(Ni) 76.47 25.92 38.71 专有名词(Nz) 59.27 81.24 68.53 79.00 77.28 78.13 总的结果
信息检索实验室
基于最大熵的统计建模（6）
数学推导过程
模型输入：从人工标注的训练数据中抽取的训 练样本集T={(x1, y1)，(x2, y2)， ……，(xn, yn)}，(xi, yi)表示在语料库中出现yi时其上下文 信息为xi。 用概率分布的极大似然对训练语料表示如下， 其中 Count ( x, y )是(x, y)在语料中出现的次数，N 为总词数。 ~ ( x, y ) = 1 × Count ( x, y ) p N
信息检索实验室
最大熵模型与其他模型的比较（5）
与HMM+rule实验结果对比 NE类型 准确率(%) 召回率(%) F值(%) 人名(Ni) 93.86 86.86 93.19 地名(Ns) 86.69 85.83 86.25 机构名(Ni) 77.20 65.90 71.10 专有名词(Nz) 77.14 80.32 78.70 86.93 83.69 85.28 总的结果
特征空间的确定——问题域 特征选择——寻找约束条件 建立统计模型——基于最大熵理论建立熵最大的模 型