最大熵模型是由最大熵原理推导实现。
1 最大熵原理 最大熵原理认为，学习概率模型时，所有可能的概率模型中，熵最大的模型是最好的模型。所以，最大熵原理可以表述为在满足约束条件的模型集合中选取熵最大的模型。
假设离散随机变量
X
X
X的概率分布是
P
(
X
)
P(X)
P(X),其熵为：
H
(
P
)
=
−
∑
x
P
(
x
)
l
o
g
P
(
x
)
H(P)=-sum_xP(x)logP(x)
H(P)=−x∑P(x)logP(x)
熵满足下列不等式：
0
≤
H
(
P
)
≤
l
o
g
∣
X
∣
0 leq H(P) leq log|X|
0≤H(P)≤log∣X∣
其中，
∣
X
∣
|X|
∣X∣是
X
X
X的取值的个数，当且仅当
X
X
X的分布是均匀分布时右边的等号成立。这就是说，当
X
X
X服从均匀分布，熵最大。
最大熵原理认为要选择的概率模型首先必须满足已有的事实，即约束条件。在没有更多信息的情况下，那些不确定的部分都是“等可能的”。最大熵原理通过熵的最大化来表示等可能性。
假设分类模型是一个条件概率分布
P
(
Y
∣
X
)
P(Y|X)
P(Y∣X),
X
∈
x
⊆
R
n
X in x subseteq R^n
X∈x⊆Rn表示输入，
Y
∈
y
Y in y
Y∈y表示输出。这个模型表示的是对于给定的输入
X
X
X，以条件概率
P
(
Y
∣
X
)
P(Y|X)
P(Y∣X)输出Y。
给定一个训练集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
,
(
x
N
,
y
N
)
}
T=left{(x_1,y_1),(x_2,y_2),..,(x_N,y_N) right}
T={(x1,y1),(x2,y2),..,(xN,yN)}
可以确定联合分布
P
(
X
,
Y
)
P(X,Y)
P(X,Y)的经验分布和边缘分布P(X)的经验分布，分别以
P
~
(
X
,
Y
)
widetilde{P}(X,Y)
P
(X,Y)和
P
~
(
X
)
widetilde{P}(X)
P
(X) 表示。
P
~
(
X
=
x
,
Y
=
y
)
=
v
(
X
=
x
,
Y
=
y
)
N
widetilde{P}(X=x,Y=y)=frac{v(X=x,Y=y)}{N}
P
(X=x,Y=y)=Nv(X=x,Y=y)
P
~
(
X
=
x
)
=
v
(
X
=
x
)
N
widetilde{P}(X=x)=frac{v(X=x)}{N}
P
(X=x)=Nv(X=x)
其中
v
(
X
=
x
,
Y
=
y
)
v(X=x,Y=y)
v(X=x,Y=y)表示训练数据中样本
(
x
,
y
)
(x,y)
(x,y)出现的频数。
用特征函数
f
(
x
,
y
)
f(x,y)
f(x,y)描述输出
x
x
x和输出
y
y
y之间的某一个事实。其定义是：
f
(
x
,
y
)
=
{
1
,
x与y满足某一事实
0
,
否则
f(x,y)= begin{cases} 1, & text{x与y满足某一事实} \[5ex] 0, & text{否则} end{cases}
f(x,y)=⎩⎪⎪⎨⎪⎪⎧1,0,x与y满足某一事实否则
特征函数
f
(
x
,
y
)
f(x,y)
f(x,y)关于经验分布
P
~
(
X
,
Y
)
widetilde{P}(X,Y)
P
(X,Y)的期望值，用
E
p
~
(
f
)
E_{widetilde{p}(f)}
Ep
(f)表示：
E
p
~
(
f
)
=
∑
x
,
y
P
~
(
X
,
Y
)
f
(
x
,
y
)
E_{widetilde{p}(f)}=sum_{x,y} widetilde{P}(X,Y) f(x,y)
Ep
(f)=x,y∑P
(X,Y)f(x,y)
特征函数
f
(
x
,
y
)
f(x,y)
f(x,y)关于经验分布
P
~
(
X
,
Y
)
widetilde{P}(X,Y)
P
(X,Y)的期望值，用
E
p
(
f
)
E_{p(f)}
Ep(f)表示：
E
p
(
f
)
=
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
f
(
x
,
y
)
E_{p(f)}=sum_{x,y}widetilde{P}(x)P(y|x)f(x,y)
Ep(f)=x,y∑P
(x)P(y∣x)f(x,y)
如果模型能够获取训练数据中的信息，那么可以假设这两个期望值相等。
E
p
~
(
f
)
=
E
p
(
f
)
E_{widetilde{p}(f)}=E_{p(f)}
Ep
(f)=Ep(f)
或
∑
x
,
y
P
~
(
X
,
Y
)
f
(
x
,
y
)
=
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
f
(
x
,
y
)
sum_{x,y} widetilde{P}(X,Y) f(x,y)=sum_{x,y}widetilde{P}(x)P(y|x)f(x,y)
x,y∑P
(X,Y)f(x,y)=x,y∑P
(x)P(y∣x)f(x,y)
因此可以得到我们最大熵模型：
C
=
{
p
∈
P
∣
E
p
~
(
f
)
=
E
p
(
f
)
,
i
=
1
,
2
,
.
.
.
,
n
}
C=left{p in P|E_{widetilde{p}(f)}=E_{p(f)},i=1,2,...,nright}
C={p∈P∣Ep
(f)=Ep(f),i=1,2,...,n}
定义在条件概率分布
P
(
Y
∣
X
)
P(Y|X)
P(Y∣X)上的条件熵为：
H
(
P
)
=
−
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
l
o
g
P
(
y
∣
x
)
H(P)=-sum_{x,y}widetilde{P}(x)P(y|x)logP(y|x)
H(P)=−x,y∑P
(x)P(y∣x)logP(y∣x)
则集合
C
C
C中条件熵
H
(
P
)
H(P)
H(P)最大的模型称为最大熵模型。
最大熵模型的学习可以形式化为约束最优化问题。
m
a
x
p
∈
C
H
(
P
)
=
−
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
l
o
g
P
(
y
∣
x
)
max_{p in C}H(P)=-sum_{x,y}widetilde{P}(x)P(y|x)logP(y|x)
maxp∈CH(P)=−x,y∑P
(x)P(y∣x)logP(y∣x)
s
.
t
.
E
p
(
f
i
)
=
E
P
~
(
f
i
)
,
i
=
1
,
2
,
.
.
.
,
n
s.t. E_p(f_i)=E_{widetilde{P}}(f_i), i = 1,2,...,n
s.t.Ep(fi)=EP
(fi),i=1,2,...,n
∑
y
P
(
y
∣
x
)
=
1
sum_y P(y|x)=1
y∑P(y∣x)=1
将约束最优化的原始问题转换为无约束最优化的对偶问题。通过求解对偶问题求解原始问题。定义拉格朗日函数
L
(
P
,
w
)
L(P,w)
L(P,w)。
L
(
P
,
w
)
=
−
H
(
P
)
+
w
0
(
1
−
∑
y
P
(
y
∣
x
)
)
+
∑
i
=
1
n
w
i
(
E
p
(
f
i
)
−
E
P
~
(
f
i
)
)
L(P,w)=-H(P)+w_0(1-sum_yP(y|x))+sum_{i=1}^nw_i(E_p(f_i)-E_{widetilde{P}}(f_i))
L(P,w)=−H(P)+w0(1−y∑P(y∣x))+i=1∑nwi(Ep(fi)−EP
(fi))
最优化的原始问题是
m
a
x
P
∈
C
m
i
n
w
L
(
P
,
w
)
max_{P in C}min_wL(P,w)
maxP∈CminwL(P,w)
对偶问题是
m
i
n
w
m
a
x
p
∈
C
L
(
P
,
w
)
min_wmax_{p in C}L(P,w)
minwmaxp∈CL(P,w)
记作：
Ψ
(
w
)
=
m
i
n
P
∈
C
L
(
P
,
w
)
=
L
(
P
w
,
w
)
Psi(w)=min_{P in C}L(P,w)=L(P_w,w)
Ψ(w)=minP∈CL(P,w)=L(Pw,w)
求
L
(
P
,
w
)
L(P,w)
L(P,w)对
P
(
y
∣
x
)
P(y|x)
P(y∣x)的偏导数，且令其
∂
L
(
P
,
w
)
∂
P
(
y
∣
x
)
=
0
frac{partial L(P,w)}{partial P(y|x)}=0
∂P(y∣x)∂L(P,w)=0。由于
∑
y
P
(
y
∣
x
)
=
1
sum_yP(y|x)=1
∑yP(y∣x)=1 ，可以得到：
P
w
(
y
∣
x
)
=
1
Z
w
(
x
)
e
∑
i
=
1
n
w
i
f
i
(
x
,
y
)
P_w(y|x)=frac{1}{Z_w(x)}e^{sum_{i=1}^nw_if_i(x,y)}
Pw(y∣x)=Zw(x)1e∑i=1nwifi(x,y)
Z
w
(
x
)
=
∑
y
e
∑
i
=
1
n
w
i
f
i
(
x
,
y
)
Z_w(x)=sum_ye^{sum_{i=1}^nw_if_i(x,y)}
Zw(x)=y∑e∑i=1nwifi(x,y)
Z
w
(
x
)
Z_w(x)
Zw(x)称为规范化因子，$ f_i(x,y)$是特征函数。
w
i
w_i
wi是特征的权值。
之后，求解对偶问题外部的极大化问题
m
a
x
w
Ψ
(
w
)
max_wPsi(w)
maxwΨ(w)
将其解记为
w
∗
w^*
w∗，即：
w
∗
=
a
r
g
m
a
x
w
Ψ
(
w
)
w^*=argmax_wPsi(w)
w∗=argmaxwΨ(w)
对
w
w
w求偏导并令其为0，即可得到需要得到的参数值。
对偶函数的极大化等价于最大熵模型的极大似然估计。
经验概率分布
P
~
(
X
,
Y
)
widetilde{P}(X,Y)
P
(X,Y)，条件概率分布
P
(
Y
∣
X
)
P(Y|X)
P(Y∣X)的对数似然函数表示为：
L
P
~
(
P
w
)
=
l
o
g
∏
x
,
y
P
(
y
∣
x
)
P
~
(
x
,
y
)
=
∑
x
,
y
P
~
(
x
,
y
)
l
o
g
P
(
y
∣
x
)
L_{widetilde{P}}(P_w)=logprod_{x,y}P(y|x)^{widetilde{P}(x,y)}=sum_{x,y}widetilde{P}(x,y)logP(y|x)
LP
(Pw)=logx,y∏P(y∣x)P
(x,y)=x,y∑P
(x,y)logP(y∣x)
通过分开计算
L
P
~
(
P
w
)
L_{widetilde{P}}(P_w)
LP
(Pw)和
Ψ
(
w
)
Psi(w)
Ψ(w)可得：
Ψ
(
w
)
=
L
P
~
(
P
w
)
Psi(w)=L_{widetilde{P}}(P_w)
Ψ(w)=LP
(Pw)
这样，最大熵模型的学习问题转换为具体求解对书似然函数极大化或对偶函数极大化的问题。
改进的迭代尺度法（improved iterative scaling,IIS）是一种最大熵模型学习的最优化算法。IIS的想法是：假设最大熵模型当前的参数向量是
w
=
(
w
1
,
w
2
,
.
.
.
,
w
n
)
T
w=(w_1,w_2,...,w_n)^T
w=(w1,w2,...,wn)T，我们希望找到一个新的参数向量
w
+
δ
=
(
w
1
+
δ
1
,
w
2
+
δ
2
,
.
.
.
,
w
n
+
δ
n
)
T
w+delta=(w_1+delta_1,w_2+delta_2,...,w_n+delta_n)^T
w+δ=(w1+δ1,w2+δ2,...,wn+δn)T。使得模型的对数似然函数值增大。
对于给定的经验分布
P
~
∗
(
x
,
y
)
widetilde{P}*(x,y)
P
∗(x,y)，模型参数从
w
w
w到
w
+
δ
w+delta
w+δ,对数似然函数的改变量为：
L
(
w
+
δ
)
−
L
(
w
)
=
∑
x
,
y
P
~
(
x
,
y
)
∑
i
=
1
n
δ
i
f
i
(
x
,
y
)
−
∑
x
P
~
(
x
)
l
o
g
Z
w
+
δ
(
x
)
Z
w
(
x
)
L(w+delta)-L(w)=sum_{x,y}widetilde{P}(x,y) sum_{i=1}^ndelta_if_i(x,y)-sum_xwidetilde{P}(x)logfrac{Z_{w+delta}(x)}{Z_w(x)}
L(w+δ)−L(w)=x,y∑P
(x,y)i=1∑nδifi(x,y)−x∑P
(x)logZw(x)Zw+δ(x)
利用不等式：
−
l
o
g
α
≥
1
−
α
,
α
>
0
-logalpha geq 1-alpha,alpha > 0
−logα≥1−α,α>0
即:
−
l
o
g
Z
w
+
δ
(
x
)
Z
w
(
x
)
≥
1
−
Z
w
+
δ
(
x
)
Z
w
(
x
)
-logfrac{Z_{w+delta}(x)}{Z_w(x)} geq 1 - frac{Z_{w+delta}(x)}{Z_w(x)}
−logZw(x)Zw+δ(x)≥1−Zw(x)Zw+δ(x)
因此：
L
(
w
+
δ
)
−
L
(
w
)
≥
A
(
δ
∣
w
)
L(w+delta)-L(w) geq A(delta|w)
L(w+δ)−L(w)≥A(δ∣w)
A
(
δ
∣
w
)
A(delta|w)
A(δ∣w)是对数似然函数该变量的一个下界。下界提高，对数似然函数也会提高。IIS进一步降低下界，引进了一个量
f
#
(
x
,
y
)
f^{#}(x,y)
f#(x,y)
f
#
(
x
,
y
)
=
∑
i
f
i
(
x
,
y
)
f^{#}(x,y)=sum_if_i(x,y)
f#(x,y)=i∑fi(x,y)
未完继续。。。
