Welcome To My Blog
最大熵模型(Maximum Entropy Model)属于对数线性模型,由最大熵原理推导实现.
最大熵原理
最大熵原理是概率模型学习的一个准则.
最大熵原理认为,学习概率模型时,在所有可能的概率模型(分布)中,熵最大的模型是最好的模型.
通常用约束条件来确定概率模型的集合,所以,最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型
1.png
直观地,
- 最大熵原理认为要选择的概率模型首先必须满足已有的事实,即约束条件,在没有更多信息的情况下,那些不确定的部分都是"等可能的"
- 等概率表示了对事实的无知.因为没有更多信息,所以取等概率是合理的
- 最大熵原理通过熵的最大化来表示等可能性
- "等可能性"不容易操作,而熵则是一个可优化的数值指标
最大熵模型的定义
将最大熵原理应用到分类得到最大熵模型
假设分类模型是一个条件概率分布P(Y|X),
2.png
这个模型表示的是,对于给定的输入X,以条件概率P(Y|X)输出Y
给定一个训练集T={(x1,y1),...,(xn,yn)},学习的目标是用最大熵原理选择最好的分类模型
首先考虑模型应该满足的条件.给定训练数据集,可以确定联合分布P(X,Y)的经验分布和边缘分布P(X)的经验分布,表示为:
3.png
引入约束
4.png
联合分布的期望:
5.png
期望作为约束:
6.png
最大熵模型的定义:
7.png
最大熵模型的学习
拉格朗日对偶性
最大熵模型的学习可形式化为约束最优化问题.
8.png
9.png
10.png
11.png
由于拉格朗日函数L(P,w)是P的凸函数,等式约束是仿射的,所以原始问题的解与对偶问题的解是等价的.这样就可以通过求解对偶问题来求解原始问题
12.png
13.png
14.png
15.png
16.png
最大化Ψ(x)等价于MLE
下面证明对偶函数的极大化等价于最大熵模型的极大似然估计
17.png
18.png
19.png
20.png
21.png
这样,最大熵模型的学习问题就转换为具体求解对数似然函数极大化或对偶函数极大化的问题
可以将最大熵模型写成更一般的形式
22.png
最大熵模型与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不等式,它是凸函数必满足的不等式,下面的推导过程会用到
24.png
25.png
IIS推导过程
对数似然为:
23.png
26.png
注意:Z_(w+δ)与Z_(w)之间有这样的关系:
27.png
推导似然函数改变量的下界:
28.png
如果能找到适当的δ使下界A(δ|w)提高,那么对数似然函数也会提高.然而,函数A(δ|w)中的δ是一个向量,含有多个变量,不易同时优化.
IIS试图一次只优化其中一个变量δi,而固定其它变量δj,j≠i.
为达到这一目的,IIS进一步降低下界A(δ|w),下降后方便提升.具体地,IIS引进一个量f^#(x,y)
29.1.png
因为fi(x,y)是二值函数,故f^#(x,y)表示所有特征函数中fi(x,y)值为1的个数
将A(δ|w)改写为:
29.png
降低下界后:
30.png
这里,B(δ|w)是对数似然函数改变量的一个新的(相对不紧的)下界.
31.png
IIS算法流程
32.png
33.png
关于牛顿法,可参考之前的文章,牛顿法
拟牛顿法
最大熵模型学习还可以应用拟牛顿法.关于拟牛顿法,可参考之前的文章,拟牛顿法
34.png
35.png
36.png
算法流程
37.png
参考:
李航,统计学习方法
