Maximum Entropy Model最大熵模型

Welcome To My Blog
最大熵模型(Maximum Entropy Model)属于对数线性模型,由最大熵原理推导实现.

最大熵原理

最大熵原理是概率模型学习的一个准则.
最大熵原理认为,学习概率模型时,在所有可能的概率模型(分布)中,熵最大的模型是最好的模型.
通常用约束条件来确定概率模型的集合,所以,最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型
Maximum Entropy Model最大熵模型
直观地,
+ 最大熵原理认为要选择的概率模型首先必须满足已有的事实,即约束条件,在没有更多信息的情况下,那些不确定的部分都是”等可能的”
+ 等概率表示了对事实的无知.因为没有更多信息,所以取等概率是合理的
+ 最大熵原理通过熵的最大化来表示等可能性
+ “等可能性”不容易操作,而熵则是一个可优化的数值指标

最大熵模型的定义

将最大熵原理应用到分类得到最大熵模型
假设分类模型是一个条件概率分布P(Y|X), Maximum Entropy Model最大熵模型
这个模型表示的是,对于给定的输入X,以条件概率P(Y|X)输出Y
给定一个训练集T={(x1,y1),…,(xn,yn)},学习的目标是用最大熵原理选择最好的分类模型
首先考虑模型应该满足的条件.给定训练数据集,可以确定联合分布P(X,Y)的经验分布和边缘分布P(X)的经验分布,表示为:
Maximum Entropy Model最大熵模型
引入约束

联合分布的期望:

期望作为约束:

最大熵模型的定义:

最大熵模型的学习

拉格朗日对偶性

最大熵模型的学习可形式化为约束最优化问题.
Maximum Entropy Model最大熵模型

由于拉格朗日函数L(P,w)是P的凸函数,等式约束是仿射的,所以原始问题的解与对偶问题的解是等价的.这样就可以通过求解对偶问题来求解原始问题

最大化Ψ(x)等价于MLE

下面证明对偶函数的极大化等价于最大熵模型的极大似然估计
Maximum Entropy Model最大熵模型

这样,最大熵模型的学习问题就转换为具体求解对数似然函数极大化或对偶函数极大化的问题
可以将最大熵模型写成更一般的形式

最大熵模型与logistic回归模型有类似的形式,它们又称为对数线性模型(log linear model).模型学习就是在给定的训练集下对模型进行极大似然估计或正则化的极大似然估计

模型学习的最优化算法

改进的迭代尺度法

改进的迭代尺度法(improved iterative scaling,IIS)的想法是:假设最大熵模型当前的参数向量是w=(w1,w2,…,wn)^T,我们希望找到一个新的参数向量w+δ=(w1+δ1,w2+δ2,…,wn+δn)^T,使得模型的对数似然函数值增大.如果能有这样一种参数向量更新的方法τ:w→w+δ,那么就可以重复使用这一方法,直至找到对数似然函数的最大值.

Jensen 不等式

先引出Jensen不等式,它是凸函数必满足的不等式,下面的推导过程会用到
Maximum Entropy Model最大熵模型

IIS推导过程

对数似然为:
Maximum Entropy Model最大熵模型

注意:Z_(w+δ)与Z_(w)之间有这样的关系:

推导似然函数改变量的下界:

如果能找到适当的δ使下界A(δ|w)提高,那么对数似然函数也会提高.然而,函数A(δ|w)中的δ是一个向量,含有多个变量,不易同时优化.
IIS试图一次只优化其中一个变量δi,而固定其它变量δj,j≠i.
为达到这一目的,IIS进一步降低下界A(δ|w),下降后方便提升.具体地,IIS引进一个量f^#(x,y)
Maximum Entropy Model最大熵模型
因为fi(x,y)是二值函数,故f^#(x,y)表示所有特征函数中fi(x,y)值为1的个数
将A(δ|w)改写为:

降低下界后:

这里,B(δ|w)是对数似然函数改变量的一个新的(相对不紧的)下界.