最大熵原理

最⼤熵模型原理介绍与python实现

1.引⾔

    最⼤熵原理认为，学习概率模型时，在满⾜约束条件的模型集合中，熵最⼤的模型是最好的模型，因为在没有更多信息的情况下，我们

⼀般会认为不确定的部分都是等可能的，⽽在前⾯决策树的介绍时我们知道，熵最⼤时刚好是要求概率的分布满⾜均匀分布，即等可能分

布，因此，可以通过熵的最⼤化来表⽰等可能分布。

2.最⼤熵模型原理介绍

2.1最⼤熵模型的定义

    对于分类模型，假设我们要学习的模型是⼀个条件概率分布，表⽰输⼊，表⽰输出。则对于⼀个训练数

据集，我们可以确定联合分布和边缘分布的经验分布，分别记为和

，其计算公式具体如下：

其中，和分别表⽰样本中和出现的频数，表⽰样本数量。

    ⽤特征函数表⽰输⼊与输出之间的⼀个事实，⽤公式表⽰如下：

即当和满⾜这个事实时，取值为1，否则取值为0。

    特征函数关于经验分布的期望值为：

    特征函数关于模型和经验分布的期望值为：

    如果模型能够获取训练数据中的信息，那么就可以假设这两个期望值相等，即：

或者：

将上式作为模型学习的约束条件，假设有个特征函数，那么就有个约束条件。

P(Y∣X)X∈X⊆RnY∈Y

T=x,y,x,y,⋯,x,y{(11)(22)(NN)}P(X,Y)P(X)(X,Y)P

~

(X)P

~

(X=x,Y=y)=P

~

N

ν(X=x,Y=y)

(X=x)=P

~

N

v(X=x)

v(X=x,Y=y)v(X=x)(x,y)xN

f(x,y)xy

f(x,y)={

1,x和y满⾜某⼀事实

0,否则

xy

f(x,y)(X,Y)P

~

E(f)=p

~(x,y)f(x,y)x,y

∑

P

~

f(x,y)P(Y∣X)(X)P

~

E(f)=P(x)P(y∣x)f(x,y)x,y

∑

P

~

E(f)=PE(f)P

~

(x)P(y∣x)f(x,y)=x,y

∑

P

~

(x,y)f(x,y)x,y

∑

P

~

nf(x,y),i=i1,2,⋯,nn

    因此，最⼤熵模型的定义可以表⽰为：假设满⾜所有约束条件的模型集合为：

定义在条件概率分布上的条件熵为：

则模型集合中条件熵最⼤的模型称为最⼤熵模型。

2.2最⼤熵模型的求解

    最⼤熵模型其实可以转化为约束最优化问题，具体表⽰如下：

利⽤拉格朗⽇乘⼦法可以将该问题转化为⽆约束的对偶问题，具体如下：

其中，为拉格朗⽇乘⼦。

C≡P∈P∣Ef=Ef,i=1,2,⋯,n{P(i)P

~(i)}

P(Y∣X)

H(P)=−(x)P(y∣x)logP(y∣x)x,y

∑

P

~

CH(P)

min−H(P)=(x)P(y∣x)logP(y∣x)P∈C∑x,yP

~

−Ef=0,i=1,2,⋯,nP(i)P

~(i)

P(y∣x)=1∑y

L(P,w)w

max

P∈C

min

=

≡−H(P)+w1−P(y∣x)+wEf−Ef0(y

∑

)i=1

∑

i(p

~(i)P(i))

(x)P(y∣x)logP(y∣x)+w1−P(y∣x)x,y

∑

P

~

0(y

∑

)

+w(x,y)f(x,y)−(x)P(y∣x)f(x,y)i=1

∑n

i(x,y

∑

P

~

i

x,y

∑

P

~

i)

w,w,w,⋯,w012n

    接下来，先将拉格朗⽇乘⼦固定，然后求解内部的极⼩化问题，记为：

该函数也称为对偶函数，记其解为：

具体地，对计算的偏导数：

在的情况下，令其为0可得：

由于，因此有：

该函数表达式即为最⼤熵模型，其中，

    接着，计算外部的极⼤化问题，即：

对拉格朗⽇乘⼦计算偏导数，并令其为0，可得其解为，即：

最后，将该解代⼊公式即可得到最终的最⼤熵模型，因此，最⼤熵模型其实就是对对偶函数的极⼤化

问题。

2.3极⼤似然估计

minL(P,w)P∈C

Ψ(w)=L(P,w)=P∈C

min

LP,w(w)

P=wargL(P,w)=P∈C

min

P(y∣x)w

L(P,w)P(y∣x)

∂P(y∣x)

∂L(P,w)

=(x)(logP(y∣x)+1)−w−(x)wf(x,y)x,y

∑

P

~

y

∑

0

x,y

∑

(P~

i=1

∑

ii)

=(x)logP(y∣x)+1−w−wf(x,y)x,y

∑

P

~(0i=1

∑n

ii)

(x)>P

~

0

P(y∣x)=expwf(x,y)+w−1=(i=1

∑n

ii0)

exp1−w(0)

expwf(x,y)(∑i=1

n

ii)

P(y∣x)=∑y1

P(y∣x)=wexpwf(x,y)

Z(x)w

1(i=1

∑n

ii)

Z(x)=wexpwf(x,y)y

∑

(i=1

∑n

ii)

Ψ(w)w

max

w∗

w=∗argΨ(w)w

max

P(y∣x)wP=∗P=w∗P(y∣x)w∗Ψ(w)

    对于给定的训练集，条件概率分布的对数似然函数可以表⽰为：

当条件概率分布是最⼤熵模型时，有：

⽽通过上⼀节我们知道，在最后⼀步最⼤化对偶函数$Psi(w)$时，有：

因此，可以发现：

这就说明，最⼤熵模型中对偶函数的极⼤化问题其实等价于最⼤熵模型的极⼤似然估计。因此，最⼤熵模型可以写成更⼀般的形式如下：

其中，

其中，为权值向量，为特征函数，因此，对参数进⾏极⼤似然估计即可得到最终的最⼤熵模型。该模型的

表达形式其实有点类似于Logistic回归模型，因此也是对数线性函数中的⼀种。

2.4最⼤熵模型的最优化算法

P(Y∣X)

LP=P

~(w)logP(y∣x)=x,y

∏

(x,y)P

~

(x,y)logP(y∣x)x,y

∑

P

~

P(y∣x)

LPP

^(w)=(x,y)logP(y∣x)x,y

∑

P

~

=(x,y)wf(x,y)−(x,y)logZ(x)x,y

∑

P

~

i=1

∑n

ii

x,y

∑

P

~

w

=(x,y)wf(x,y)−(x)logZ(x)x,y

∑

P

~

i=1

∑n

ii

x

∑

P

~

w

Ψ(w)=

=

=

=

(x)P(y∣x)logP(y∣x)+w(x,y)f(x,y)−(x)P(y∣x)f(x,y)x,y

∑

P

~

ww

i=1

∑

i(x,y

∑

P

~

i

x,y

∑

P

~

wi)

(x,y)wf(x,y)+(x)P(y∣x)logP(y∣x)−wf(x,y)x,y

∑

P

~

i=1

∑n

ii

x,y

∑

P

~

w(w

i=1

∑n

ii)

(x,y)wf(x,y)−(x)P(y∣x)logZ(x)x,y

∑

P

~

i=1

∑n

ii

x,y

∑

P

~

ww

(x,y)wf(x,y)−(x)logZ(x)x,y

∑

P

~

i=1

∑n

ii

x

∑

P

~

w

Ψ(w)=LPP

~(w)

P(y∣x)=wexpwf(x,y)

Z(x)w

1(i=1

∑n

ii)

Z(x)=wexpwf(x,y)y

∑

(i=1

∑n

ii)

w∈Rnf(x,y),i=i1,2,⋯,n

    在计算机中，⼀般最⼤熵模型的求解会通过迭代算法来进⾏求解，因为⽬标函数是凸函数，因此，很多种最优化的⽅法都能找到全局最

优解，常⽤的有改进的迭代尺度法、拟⽜顿法等。

2.4.1改进的迭代尺度法

    改进的迭代尺度法（ImprovedIterativeScaling，IIS）是⼀种最⼤熵模型学习的最优化算法。由前⾯我们知道，最⼤熵模型的对数似

然函数为：

其⽬标是通过求似然函数的极⼤值来估计模型的参数，因此，IIS的想法是：假设最⼤熵模型当前的参数向量是，

我们希望找到⼀个新的参数向量，使得模型的对数似然函数值增⼤，如果能有这样⼀种参数

向量更新的⽅法，那么就可以重复使⽤这⼀⽅法，直⾄找到对数似然函数的最⼤值。

    对于给定的经验分布，模型参数从到，对数似然函数的改变量是：

利⽤不等式：

建⽴对数似然函数改变量的下界：

将右端记为：

因此有：

即为对数似然函数改变量的⼀个下界。如果能找到适当的使得下界提⾼，那么对数似然函数也会提⾼，然⽽，函数

中的是⼀个向量，含有多个变量，不易同时优化，因此，IIS试图⼀次只优化其中⼀个变量，⽽固定其他变量。但是直

接对求极⼤值得到的估计还是⽐较⿇烦，因此，IIS进⼀步降低下界，具体地，IIS引进了⼀个量：

表⽰所有特征在出现的次数，因此，可以进⼀步改写为：

L(w)=(x,y)wf(x,y)−x,y

∑

P

~

i=1

∑n

ii(x)logZ(x)x

∑

P

~

w

w^w=w,w,⋯,w(12n)

T

w+δ=w+δ,w+δ,⋯,w+δ(1122nn)

T

τ:w→w+δ

(x,y)P

~

ww+δ

L(w+δ)−L(w)=(x,y)logP(y∣x)−(x,y)logP(y∣x)x,y

∑

P

~

w+δ

x,y

∑

P

~

w

=(x,y)δf(x,y)−(x)logx,y

∑

P

~

i=1

∑n

ii

x

∑

P

~

Z(x)w

Z(x)w+δ

−logα⩾1−α,α>0

L(w+δ)−L(w)⩾(x,y)δf(x,y)+1−(x)x,y

∑

P

~

i=1

∑

ii

x

∑

P

~

Z(x)w

Z(x)w+δ

=(x,y)δf(x,y)+1−(x)P(y∣x)expδf(x,y)x,y

∑

P

~

i=1

∑n

ii

x

∑

P

~

y

∑

w

i=1

∑n

ii

A(δ∣w)=(x,y)δf(x,y)+x,y

∑

P

~

i=1

∑n

ii1−(x)P(y∣x)expδf(x,y)x

∑

Py

∑

w

i=1

∑n

ii

L(w+δ)−L(w)⩾A(δ∣w)

A(δ∣w)δA(δ∣w)

A(δ∣w)δδiδ,i=ij

A(δ∣w)δiA(δ∣w)f(x,y)

#f(x,y)=#f(x,y)i

∑

i

f(x,y)#(x,y)A(δ∣w)

利⽤指数函数的凸性以及Jenn不等式，可得：

因此有：

记不等式右端为：

因此有：

这样⼀来，对求的偏导数，有：

令其为0可得：

这样⼀来，依次对求解⽅程可以求出。

    因此，IIS算法可以总结如下：

1.输⼊：特征函数，经验分布，模型

2.输出：最优参数值，最优模型

3.对所有的，取初值

4.对每⼀：

（a）令是⽅程：

的解，其中，

（b）更新值：

5.如果不是所有都收敛，重复步骤4

A(δ∣w)=(x,y)δf(x,y)+x,y

∑

P

~

i=1

∑n

ii1−(x)P(y∣x)expf(x,y)x

∑

P

~

y

∑

w(

#i=1

∑n

f(x,y)

#δf(x,y)ii)

expδf(x,y)⩽(i=1

∑n

f(x,y)

#f(x,y)i

i

#)expδf(x,y)i=1

∑n

f(x,y)

#f(x,y)i

(i

#)

A(δ∣w)⩾(x,y)δf(x,y)+x,y

∑

P

~

i=1

∑n

ii1−(x)P(y∣x)expδf(x,y)x

∑

P

~

y

∑

w

i=1

∑n

(f(x,y)

#f(x,y)i)(i#)

B(δ∣w)=(x,y)δf(x,y)+x,y

∑

P

~

i=1

∑n

ii1−(x)P(y∣x)expδf(x,y)x

∑

P

~

y

∑

w

i=1

∑n

(f(x,y)

#f(x,y)i)(i#)

L(w+δ)−L(w)⩾B(δ∣w)

B(δ∣w)δi

=

∂δi

∂B(δ∣w)

(x,y)f(x,y)−x,y

∑

P

~

i(x)P(y∣x)f(x,y)expδf(x,y)x

∑

P

~

y

∑

wi(i

#)

(x)P(y∣x)f(x,y)expδf(x,y)=x,y

∑

P

~

wi(i

#)Efp

~(i)

δiδ

f,f,⋯,f12n(X,Y)P

~

P(y∣x)w

wi

∗

Pw∗

i∈{1,2,⋯,n}w=i0

i∈{1,2,⋯,n}

δi

(x)P(y∣x)f(x,y)expδf(x,y)=x,y

∑

P

~

i(i

#)EfP

~(t)

f(x,y)=∗f(x,y)∑i=1

n

i

wiw←iw+iδi

wi

    这⾥⽐较关键的⼀步是求解，如果是常数，即对任何，有，则可以显式表达为：

否则，就得通过⽜顿法进⾏求解，以表⽰步骤4中的⽅程，则⽜顿法通过迭代求得：

3.最⼤熵模型的python实现

  采⽤python对最⼤熵模型进⾏实现，模型的优化算法采⽤的是IIS算法，具体的代码如下：

importmath

importnumpyasnp

classMaxEntropy(object):

def__init__(lf,eps=0.005,maxiter=1000):

lf._Y=t()#标签集合，相当去去重后的y

lf._numXY={}#key为(x,y)，value为出现次数

lf._N=0#样本数

lf._Ep_=[]#样本分布的特征期望值

lf._xyID={}#key记录(x,y),value记录id号

lf._n=0#特征键值(x,y)的个数

lf._C=0#最⼤特征数

lf._IDxy={}#key为id号，value为对应的(x,y)

lf._w=[]

lf._eps=eps#收敛条件

lf._lastw=[]#上⼀次w参数值

r=maxiter

def_Zx(lf,X):

"""计算每个Z(x)值"""

zx=0

foryinlf._Y:

ss=0

forxinX:

if(x,y)inlf._numXY:

ss+=lf._w[lf._xyID[(x,y)]]

zx+=(ss)

returnzx

def_model_pyx(lf,y,X):

"""计算每个P(y|x)"""

zx=lf._Zx(X)

ss=0

forxinX:

if(x,y)inlf._numXY:

ss+=lf._w[lf._xyID[(x,y)]]

pyx=(ss)/zx

returnpyx

def_model_ep(lf,X,index):

"""计算特征函数fi关于模型的期望"""

x,y=lf._IDxy[index]

ep=0

forsampleinX:

ifxnotinsample:

continue

δif(x,y)#x,yf(x,y)=#Mδi

δ=ilog

M

1

Efp(i)

Efp

~(i)

gδ=(i)0δi

∗

δ=i

(k+1)

δ−i

(k)gδ′(i(k))

gδ(i

(k))

continue

pyx=lf._model_pyx(y,sample)

ep+=pyx/lf._N

returnep

def_convergence(lf):

"""判断是否全部收敛"""

forlast,nowinzip(lf._lastw,lf._w):

ifabs(last-now)>=lf._eps:

returnFal

returnTrue

defpredict(lf,X):

"""计算预测概率"""

result=[]

X=y(X).tolist()

forxinX:

Z=lf._Zx(x)

logit={}

foryinlf._Y:

ss=0

forxiinx:

if(xi,y)inlf._numXY:

ss+=lf._w[lf._xyID[(xi,y)]]

pyx=(ss)/Z

logit[y]=pyx

logit=sorted((),key=lambdax:x[1],rever=True)

(logit[0][0])

returnresult

deffit(lf,X,Y):

"""训练模型"""

X=y(X).tolist()

Y=y(Y).tolist()

forx,yinzip(X,Y):

#集合中y若已存在则会⾃动忽略

lf._(y)

forxiinx:

if(xi,y)inlf._numXY:

lf._numXY[(xi,y)]+=1

el:

lf._numXY[(xi,y)]=1

lf._N=len(X)

lf._n=len(lf._numXY)

lf._C=max([len(sample)-1forsampleinX])

lf._w=[0]*lf._n

lf._lastw=lf._w[:]

#计算特征函数fi关于经验分布的期望

lf._Ep_=[0]*lf._n

fori,xyinenumerate(lf._numXY):

lf._Ep_[i]=lf._numXY[xy]/lf._N

lf._xyID[xy]=i

lf._IDxy[i]=xy

#更新模型的参数

forloopinrange(r):

print("iter:%d"%loop)

lf._lastw=lf._w[:]

foriinrange(lf._n):

ep=lf._model_ep(X,i)#计算第i个特征的模型期望

lf._w[i]+=(lf._Ep_[i]/ep)/lf._C#更新参数

print("w:",lf._w)

iflf._convergence():#判断是否收敛

break

break

    有关整个项⽬的完整代码参考本⼈的github链接：

github链接：

4.总结

    最后总结⼀下：

最⼤熵模型因为涉及到联合概率的经验分布计算，因此，⽐较适⽤于特征变量和⽬标变量都是离散的情况。

当特征变量维度⽐较⼤，数据量⽐较多时，此时特征函数可能会⾮常多，因此，模型的训练速度可能会相对⽐较慢。