最大熵模型简介 A Simple Introduction to the Maximum Entropy Models MLSA 最大熵模型简介 A Simple Introduction to the Maximum Entropy Models 王 斌 前瞻研究中心信息检索组 2007. 11. 27

Generative Model vs. Discriminative Model MLSA Generative Model vs. Discriminative Model Generative Model (GM): P(Y|X)=P(X|Y)P(Y)/P(X)，通过求解P(X|Y)和P(Y)来求解P(Y|X) Discriminative Model (DM): 对P(Y|X)直接建模 GM DM Gaussians Mixtures of Gaussians HMM Naïve Bayes Bayesian Network MRF(马尔科夫随机场) Logistic Regression SVMs kNN MaxEnt(最大熵模型) MEMM(最大熵马尔科夫模型) CRF(条件随机场模型) Voted Perceptron Neural Network

MLSA 纲要 最大熵原理 最大熵模型定义 最大熵模型中的一些算法 最大熵模型的应用 总结 思考题

MLSA 纲要 最大熵原理 最大熵模型定义 最大熵模型中的一些算法 最大熵模型的应用 总结 思考题

最大熵原理(Maximum Entropy Principle) MLSA 最大熵原理(Maximum Entropy Principle) 信息熵：熵的概念最先在1864年首先由克劳修斯提出， 1948年美国电器工程师香农(Shannon,C.E)在《通信的数学理论》中，把“熵”用来表示一个随机事件的“不确定性”或信息量的量度。 信息量 消除 概率分布 随机事件的不确定性

熵(Entropy) 一个离散随机变量X，其概率分布函数为p(x)，则X的熵定义为： 由于H只与p(x)有关，所以有时也写成H(p) MLSA 熵(Entropy) 一个离散随机变量X，其概率分布函数为p(x)，则X的熵定义为： 由于H只与p(x)有关，所以有时也写成H(p) 通常对数以2为底， H代表了X的信息量，也可以认为是对X进行二进制编码所需要的平均编码长度 性质： X只取某个确定值的时左边等号成立 X为均匀分布时右边等号成立

联合熵、条件熵、互信息 随机变量X、Y的联合分布是p(x,y)，它们的联合熵(Joint Entropy)为 MLSA 联合熵、条件熵、互信息 随机变量X、Y的联合分布是p(x,y)，它们的联合熵(Joint Entropy)为 条件熵(Conditional Entropy) 互信息(Mutual Information) 有人称红色方框内式子为互信息I(x,y)或者点互信息，将I(X,Y)称为平均互信息。一个是对变量的具体值求值，一个是对随机变量求值，请注意区分

一个例子 一个6面的骰子，各面的点数分别为1,2,…,6，令X表示抛出后朝上的点数。 MLSA 一个例子 一个6面的骰子，各面的点数分别为1,2,…,6，令X表示抛出后朝上的点数。 分布一p1：p(X=1)=p(X=2)=…=p(X=6)=1/6 分布二p2：p(X=1)=p(X=2)=1/4, p(X=3)=p(X=4)=p(X=5)=p(X=6)=1/8 分布三p3: 只有已知条件p(X=1)+p(X=2)=0.6 H(p1)=1/6*log6*6=log6≈2.58 H(p2)=2*1/4*log4+4*1/8*log8=2.5 p1vs p2: 分布一具有更大的熵(信息量)，即具有更大的不确定性。 p3*=argmax(H(p3)), 此时 p(X=1)=p(X=2)=0.3, p(X=3)=p(X=4)=p(X=5)=p(X=6)=0.1

最大熵原理 最大熵原理：1957 年由E.T.Jaynes 提出。 主要思想： 原理的实质： MLSA 最大熵原理 最大熵原理：1957 年由E.T.Jaynes 提出。 主要思想： 在只掌握关于未知分布的部分知识时，应该选取符合这些知识但熵值最大的概率分布。 原理的实质： 前提：已知部分知识 关于未知分布最合理的推断＝符合已知知识最不确定或最随机的推断。 这是我们可以作出的唯一不偏不倚的选择，任何其它的选择都意味着我们增加了其它的约束和假设，这些约束和假设根据我们掌握的信息无法作出。

一些现象 热力学：热学中一个重要的基本现象是趋向平衡态，这是一个不可逆过程，即朝熵增加的方向转变。 社会学：共产主义 经济学：消除垄断 MLSA 一些现象 热力学：热学中一个重要的基本现象是趋向平衡态，这是一个不可逆过程，即朝熵增加的方向转变。 社会学：共产主义 经济学：消除垄断 哲学：中庸 家庭：婆家、娘家 ……

最大熵原理 一个正确的概率分布p应该满足下面两个条件： （1）服从样本数据中的已知统计证据。 （2）使熵最大化。 MLSA 最大熵原理 一个正确的概率分布p应该满足下面两个条件： （1）服从样本数据中的已知统计证据。 （2）使熵最大化。 其中， ，P表示所有可能的概率分布。

最大熵原理 特征：用来表示从样本中获得的统计证据。也就是使得熵最大的概率分布p必须受到特征的限制。通常为一个二值函数。 MLSA 最大熵原理 特征：用来表示从样本中获得的统计证据。也就是使得熵最大的概率分布p必须受到特征的限制。通常为一个二值函数。 例如：在词性标注中，可定义特征如下：

MLSA 纲要 最大熵原理 最大熵模型定义 最大熵模型中的一些算法 最大熵模型的应用 总结 思考题

最大熵模型(Maximum Entropy Model) MLSA 最大熵模型(Maximum Entropy Model) 假设有一个样本集合 ，我们给出k个特征 ，特征j对p的制约可以表示为 , 表示在概率分布为p时特征 的期望。 表示特征 的样本期望值。

MLSA 最大熵模型 无任何先验知识： 存在先验知识：(求满足一组条件的最优解问题)

最大熵模型 例如： 给定一个词 在符合已知情况的前提下，使未知事件的概率分布尽可能 均匀 假定已知存在四种词性：名词、动词、介词、指代词 MLSA 最大熵模型 例如： 给定一个词 假定已知存在四种词性：名词、动词、介词、指代词 如果该词在语料库中出现过，并且属于名词的概率为70%，则判断该词属于名词的概率为0.7，属于其他三种词性的概率均为0.1 如果该词没有在语料库中出现，则属于四种词性的概率为0.25 在符合已知情况的前提下，使未知事件的概率分布尽可能 均匀

MLSA 最大熵模型－条件分布 假设有一个样本集合 ， 表示一个上下文， 表示对应的结果。假设我们给出k个特征 ，对每个特征给出条件限制：期望概率值等于经验概率值 其中：

MLSA 最大熵模型－条件分布 带约束非线性规划问题:拉格朗日乘子算法 是模型参数，可以看成是特征函数的权重。 模型训练：即求 的值。

MLSA 纲要 最大熵原理 最大熵模型定义 最大熵模型中的一些算法 最大熵模型的应用 总结 思考题

MLSA 最大熵模型中的一些算法 GIS(Generalized Iterative Scaling)算法、IIS(Improved Iterative Scaling)算法或者Quasi Newton算法 参数估计算法：用来得到具有最大熵分布的参数 的值。 FI 算法(特征引入算法，Feature Induction) 解决如何选择特征的问题：通常采用一个逐步增加特征的办法进行，每一次要增加哪个特征取决于样本数据。

MLSA Algorithms Generalized Iterative Scaling (GIS): (Darroch and Ratcliff, 1972) Improved Iterative Scaling (IIS): (Della Pietra et al., 1995)

GIS: setup Requirements for running GIS: MLSA GIS: setup Requirements for running GIS: Obey form of model and constraints: An additional constraint: Let Add a new feature fk+1:

GIS algorithm Compute dj, j=1, …, k+1 Initialize (any values, e.g., 0) MLSA GIS algorithm Compute dj, j=1, …, k+1 Initialize (any values, e.g., 0) Repeat until converge For each j Compute Update where

Approximation for calculating feature expectation MLSA Approximation for calculating feature expectation

Properties of GIS L(p(n+1)) >= L(p(n)) MLSA Properties of GIS L(p(n+1)) >= L(p(n)) The sequence is guaranteed to converge to p*. The converge can be very slow. The running time of each iteration is O(NPA): N: the training set size P: the number of classes A: the average number of features that are active for a given event (a, b).

IIS algorithm Compute dj, j=1, …, k+1 and MLSA IIS algorithm Compute dj, j=1, …, k+1 and Initialize (any values, e.g., 0) Repeat until converge For each j Let be the solution to Update

Calculating If Then Else GIS is the same as IIS MLSA Calculating If Then GIS is the same as IIS Else must be calculated numerically.

FI算法—特征引入 特征选取的衡量标准：信息增益 一个特征对所处理问题带来的信息越多，越适合引入到模型中。 MLSA FI算法—特征引入 特征选取的衡量标准：信息增益 一个特征对所处理问题带来的信息越多，越适合引入到模型中。 首先形式化一个特征空间，所有可能的特征都为候补特征。然后从候补特征集合中选取对模型最为有用的特征集合。

FI算法(续) 输入：候补特征集合F，经验分布 输出：模型选用的特征集合S，结合这些特征的模型Ps MLSA FI算法(续) 输入：候补特征集合F，经验分布 输出：模型选用的特征集合S，结合这些特征的模型Ps 初始化：特征集合S为空，它所对应的模型Ps均匀分布，n＝0 对于候补特征集合F中的每一个特征f，计算该特征加入模型后为模型带来的增益值Gf。 选择具有最大增益值的G(S,f)的特征fn。 把特征fn加入到集合S中，S=(f1,f2,…fn); 重新调整参数值，使用GIS算法计算模型Ps. n=n+1,返回步骤2。

FI算法(续) 计算增益量：Kullback-Leibler(KL)距离(也叫相对熵) 两个概率p、q的KL距离： MLSA FI算法(续) 计算增益量：Kullback-Leibler(KL)距离(也叫相对熵) 两个概率p、q的KL距离： 基本思想：距离越小，分布越接近。

MLSA FI算法(续) 引入第i个特征fi后的增益值： 选择的特征：

MLSA 纲要 最大熵原理 最大熵模型定义 最大熵模型中的一些算法 最大熵模型的应用 总结 思考题

最大熵模型的应用—词性标注 任务：根据上下文 ，求词 的词性 利用最大熵模型求 特征定义： MLSA 最大熵模型的应用—词性标注 任务：根据上下文 ，求词 的词性 利用最大熵模型求 特征定义： 即为语料库中词性为DET的that出现次数除以语料库中总词数

MLSA 纲要 最大熵原理 最大熵模型定义 最大熵模型中的一些算法 最大熵模型的应用 总结 思考题

总结 最大熵模型用途：进行概率估计。 在已知条件下，如何选择一个合适的分布来预测事件。 优点： MLSA 总结 最大熵模型用途：进行概率估计。 在已知条件下，如何选择一个合适的分布来预测事件。 优点： 只需集中精力选择特征，不需考虑如何使用这些特征。 特征选择灵活，容易更换。各个特征之间可以毫不相关。便于从多个角度来描述问题。 无需做独立性假设。

MLSA 纲要 最大熵原理 最大熵模型定义 最大熵模型中的一些算法 最大熵模型的应用 总结 思考题

思考 如何利用最大熵模型来进行中文文本分类？ MLSA 思考 如何利用最大熵模型来进行中文文本分类？ 参看：李荣陆等，使用最大熵模型进行中文文本分类，计算机研究与发展，2005，42(1):94-101

MLSA 参考文献 A maximum entropy approach to natural language processing (Adam Berger) A Brief MaxEnt Tutorial (Adam Berger) Learning to parse natural language with maximum entropy models (Adwait Ratnaparkhi) A simple Introduction to Maximum Entropy Models for Natural Language Processing (Adwait Ratnaparkhi)

MLSA 网上资源 http://homepages.inf.ed.ac.uk/s0450736/maxent_toolkit.html，一个用Python和C++写的ME工具包。 http://www.cs.cmu.edu/~aberger/maxent.html，一个学习ME的链接

MLSA 谢谢！