文章目录
前言
最大熵模型是由最大熵原理推导实现。最大熵原理是概率模型学习的一个准则,该原理认为在已知约束条件下,且没有其他的先验知识来限制模型时,选择具有最大熵的模型,可以保证不会引入偏见。
一、最大熵模型是什么?
最大熵原理应用到分类得到最大熵模型。
给定训练集
T
=
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
,
(
x
N
,
y
N
)
T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}
T=(x1,y1),(x2,y2),...,(xN,yN),联合分布P(X,Y)以及边缘分布P(X)的经验分布都可以由训练数据得到:
P
~
(
X
=
x
,
Y
=
y
)
=
c
o
u
n
t
(
X
=
x
,
Y
=
y
)
N
P
~
(
X
=
x
)
=
c
o
u
n
t
(
X
=
x
)
N
\widetilde{P}(X=x,Y=y)=\frac{count(X=x,Y=y)}{N} \\ \widetilde{P}(X=x)=\frac{count(X=x)}{N}
P
(X=x,Y=y)=Ncount(X=x,Y=y)P
(X=x)=Ncount(X=x)
用特征函数f(x,y)描述输入x和输出y之间的某一个事实,特征函数是一个二值函数,当x与y满足某一事实时取1,否则取0。例如,可以令特征x与标签y在训练集出现过时取1,否则取0。
特征函数f(x,y)关于经验分布
P
~
(
X
=
x
,
Y
=
y
)
\widetilde{P}(X=x,Y=y)
P
(X=x,Y=y)的期望值为:
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)关于模型P(Y|X)与经验分布
P
~
(
x
)
\widetilde{P}(x)
P
(x)的期望值为:
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)
如果模型能够获取训练数据中的信息,那么就可以假设这两个期望值相等,即:
∑
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
∣
∑
x
,
y
P
~
(
x
,
y
)
f
i
(
x
,
y
)
=
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
f
i
(
x
,
y
)
,
i
=
1
,
2
,
.
.
.
,
n
}
C=\{P|\sum_{x,y}\widetilde{P}(x,y)f_i(x,y)=\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y),\quad i=1,2,...,n\}
C={P∣x,y∑P
(x,y)fi(x,y)=x,y∑P
(x)P(y∣x)fi(x,y),i=1,2,...,n}
其中n为特征函数个数。
定义在条件概率分布P(Y|X)上的条件概率熵为:
H
(
P
)
=
−
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
ln
P
(
y
∣
x
)
H(P)=-\sum_{x,y}\widetilde{P}(x)P(y|x)\ln{P(y|x)}
H(P)=−x,y∑P
(x)P(y∣x)lnP(y∣x)
模型集合C中条件熵H§最大的模型称为最大熵模型。
二、极大似然估计
最大熵模型的学习过程就是求解最大熵模型的过程,等价于求解以下最优化问题:
max
H
(
P
)
=
−
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
ln
P
(
y
∣
x
)
s
.
t
.
∑
x
,
y
P
~
(
x
,
y
)
f
i
(
x
,
y
)
=
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
f
i
(
x
,
y
)
,
i
=
1
,
2
,
.
.
.
,
n
∑
x
,
y
P
(
y
∣
x
)
P
~
(
x
)
=
1
\max H(P)=-\sum_{x,y}\widetilde{P}(x)P(y|x)\ln{P(y|x)} \\ s.t. \qquad \sum_{x,y}\widetilde{P}(x,y)f_i(x,y)=\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y),\quad i=1,2,...,n \\ \sum_{x,y}P(y|x)\widetilde{P}(x)=1
maxH(P)=−x,y∑P
(x)P(y∣x)lnP(y∣x)s.t.x,y∑P
(x,y)fi(x,y)=x,y∑P
(x)P(y∣x)fi(x,y),i=1,2,...,nx,y∑P(y∣x)P
(x)=1
按照最优化问题的习惯,求解与上述问题等价的
min
−
H
(
p
)
\min -H(p)
min−H(p)。
引入拉格朗日乘子
w
0
,
w
1
,
.
.
.
,
w
n
w_0,w_1,...,w_n
w0,w1,...,wn将上述带约束条件的最优化问题转化为无约束的最优化问题,定义拉格朗日函数:
L
(
P
,
W
)
=
−
H
(
P
)
+
w
0
(
1
−
∑
x
,
y
P
(
y
∣
x
)
P
~
(
x
)
)
+
∑
i
=
1
n
w
i
(
∑
x
,
y
P
~
(
x
,
y
)
f
i
(
x
,
y
)
−
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
f
i
(
x
,
y
)
)
=
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
ln
P
(
y
∣
x
)
+
w
0
(
1
−
∑
x
,
y
P
(
y
∣
x
)
P
~
(
x
)
)
+
∑
i
=
1
n
w
i
(
∑
x
,
y
P
~
(
x
,
y
)
f
i
(
x
,
y
)
−
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
f
i
(
x
,
y
)
)
L(P,W)=-H(P)+w_0(1-\sum_{x,y}P(y|x)\widetilde{P}(x))+\sum_{i=1}^nw_i(\sum_{x,y}\widetilde{P}(x,y)f_i(x,y)-\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y)) \\ = \sum_{x,y}\widetilde{P}(x)P(y|x)\ln{P(y|x)} +w_0(1-\sum_{x,y}P(y|x)\widetilde{P}(x))+\sum_{i=1}^nw_i(\sum_{x,y}\widetilde{P}(x,y)f_i(x,y)-\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y))
L(P,W)=−H(P)+w0(1−x,y∑P(y∣x)P
(x))+i=1∑nwi(x,y∑P
(x,y)fi(x,y)−x,y∑P
(x)P(y∣x)fi(x,y))=x,y∑P
(x)P(y∣x)lnP(y∣x)+w0(1−x,y∑P(y∣x)P
(x))+i=1∑nwi(x,y∑P
(x,y)fi(x,y)−x,y∑P
(x)P(y∣x)fi(x,y))
这里最优化的原始问题是:
min
P
∈
C
max
w
L
(
P
,
w
)
\min_{P\in{C}}\max_wL(P,w)
P∈CminwmaxL(P,w)
对偶问题是:
max
w
min
P
∈
C
L
(
P
,
w
)
\max_w\min_{P\in{C}}L(P,w)
wmaxP∈CminL(P,w)
在上式内部的最小化部分固定w,此时L(P,w)是关于P的函数,用
θ
(
P
)
\theta(P)
θ(P)表示,对P(y|x)求偏导数得:
∂
θ
(
P
)
∂
P
(
y
∣
x
)
=
P
~
(
x
)
(
1
+
ln
P
(
y
∣
x
)
)
−
P
~
(
x
)
w
0
−
P
~
(
x
)
∑
i
=
1
n
w
i
f
i
(
x
,
y
)
=
P
~
(
x
)
(
1
+
ln
P
(
y
∣
x
)
−
w
0
−
∑
i
=
1
n
w
i
f
i
(
x
,
y
)
)
\frac{\partial{\theta(P)}}{\partial{P(y|x)}}=\widetilde{P}(x)(1+\ln{P(y|x)})-\widetilde{P}(x)w_0-\widetilde{P}(x)\sum_{i=1}^nw_if_i(x,y) \\ = \widetilde{P}(x)(1+\ln{P(y|x)}-w_0-\sum_{i=1}^nw_if_i(x,y))
∂P(y∣x)∂θ(P)=P
(x)(1+lnP(y∣x))−P
(x)w0−P
(x)i=1∑nwifi(x,y)=P
(x)(1+lnP(y∣x)−w0−i=1∑nwifi(x,y))
令偏导数等于0,因为
P
~
(
x
)
>
0
\widetilde{P}(x)>0
P
(x)>0,所以
1
+
ln
P
(
y
∣
x
)
−
w
0
−
∑
i
=
1
n
w
i
f
i
(
x
,
y
)
=
0
1+\ln{P(y|x)}-w_0-\sum_{i=1}^nw_if_i(x,y)=0
1+lnP(y∣x)−w0−∑i=1nwifi(x,y)=0,解得:
P
(
y
∣
x
)
=
e
∑
i
=
1
n
w
i
f
i
(
x
,
y
)
e
1
−
w
0
P(y|x)=\frac{e^{\sum_{i=1}^nw_if_i(x,y)}}{e^{1-w_0}}
P(y∣x)=e1−w0e∑i=1nwifi(x,y)
由于
∑
y
P
(
y
∣
x
)
=
1
\sum_yP(y|x)=1
∑yP(y∣x)=1,得到P(y|x)关于w的表达式为:
P
w
(
y
∣
x
)
=
1
Z
w
(
x
)
e
∑
i
=
1
n
w
i
f
i
(
x
,
y
)
Z
w
(
x
)
=
∑
y
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)} \\ Z_w(x)=\sum_ye^{\sum_{i=1}^nw_if_i(x,y)}
Pw(y∣x)=Zw(x)1e∑i=1nwifi(x,y)Zw(x)=y∑e∑i=1nwifi(x,y)
由上式表示的模型
P
w
=
P
w
(
y
∣
x
)
P_w=P_w(y|x)
Pw=Pw(y∣x)就是最大熵模型,w是最大熵模型的参数向量,每一维度为对应特征函数的权重。
令
w
=
[
w
1
,
w
2
,
.
.
.
,
w
n
]
T
,
f
(
x
,
y
)
=
[
f
1
(
x
,
y
)
,
f
2
(
x
,
y
)
,
.
.
.
,
f
n
(
x
,
y
)
]
\boldsymbol{w}=[w_1,w_2,...,w_n]^T, \boldsymbol{f(x,y)}=[f_1(x,y),f_2(x,y),...,f_n(x,y)]
w=[w1,w2,...,wn]T,f(x,y)=[f1(x,y),f2(x,y),...,fn(x,y)],则:
∑
i
=
1
n
w
i
f
i
(
x
,
y
)
=
w
T
f
(
x
,
y
)
\sum_{i=1}^nw_if_i(x,y)=\boldsymbol{w}^T\boldsymbol{f(x,y)}
i=1∑nwifi(x,y)=wTf(x,y)
将
P
w
(
y
∣
x
)
P_w(y|x)
Pw(y∣x)用w表示代入
L
(
P
,
W
)
L(P,W)
L(P,W)的表达式并结合
∑
x
,
y
P
(
y
∣
x
)
P
~
(
x
)
=
1
\sum_{x,y}P(y|x)\widetilde{P}(x)=1
∑x,yP(y∣x)P
(x)=1得:
L
(
P
,
W
)
=
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
(
w
T
f
(
x
,
y
)
−
ln
Z
w
(
x
)
)
+
∑
x
,
y
P
~
(
x
,
y
)
w
T
f
(
x
,
y
)
−
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
w
T
f
(
x
,
y
)
=
∑
x
,
y
P
~
(
x
,
y
)
w
T
f
(
x
,
y
)
−
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
ln
Z
w
(
x
)
L(P,W)=\sum_{x,y}\widetilde{P}(x)P(y|x)(\boldsymbol{w}^T\boldsymbol{f(x,y)}-\ln{Z_w(x)})+\\ \sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_{x,y}\widetilde{P}(x)P(y|x)\boldsymbol{w}^T\boldsymbol{f(x,y)} \\ = \sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_{x,y}\widetilde{P}(x)P(y|x)\ln{Z_w(x)}
L(P,W)=x,y∑P
(x)P(y∣x)(wTf(x,y)−lnZw(x))+x,y∑P
(x,y)wTf(x,y)−x,y∑P
(x)P(y∣x)wTf(x,y)=x,y∑P
(x,y)wTf(x,y)−x,y∑P
(x)P(y∣x)lnZw(x)
因为:
∑
y
P
~
(
x
)
P
(
y
∣
x
)
ln
Z
w
(
x
)
=
P
~
(
x
)
ln
Z
w
(
x
)
\sum_{y}\widetilde{P}(x)P(y|x)\ln{Z_w(x)}=\widetilde{P}(x)\ln{Z_w(x)}
y∑P
(x)P(y∣x)lnZw(x)=P
(x)lnZw(x)
所以:
L
(
P
,
W
)
=
∑
x
,
y
P
~
(
x
,
y
)
w
T
f
(
x
,
y
)
−
∑
x
P
~
(
x
)
ln
Z
w
(
x
)
L(P,W)=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_x\widetilde{P}(x)\ln{Z_w(x)}
L(P,W)=x,y∑P
(x,y)wTf(x,y)−x∑P
(x)lnZw(x)
所以最大熵模型可以转化为极大化上述函数。接下来考虑
P
w
(
x
,
y
)
P_w(x,y)
Pw(x,y)的对数似然函数,即
L
P
~
(
P
w
)
=
ln
∏
x
,
y
P
(
y
∣
x
)
P
~
(
x
,
y
)
=
∑
x
,
y
P
~
(
x
,
y
)
ln
P
(
y
∣
x
)
=
∑
x
,
y
P
~
(
x
,
y
)
w
T
f
(
x
,
y
)
−
∑
x
,
y
P
~
(
x
,
y
)
ln
Z
w
(
x
)
L_{\widetilde{P}}(P_w)=\ln \prod_{x,y}P(y|x)^{\widetilde{P}(x,y)}=\sum_{x,y}\widetilde{P}(x,y)\ln P(y|x) \\ = \sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_{x,y}\widetilde{P}(x,y)\ln Z_w(x)
LP
(Pw)=lnx,y∏P(y∣x)P
(x,y)=x,y∑P
(x,y)lnP(y∣x)=x,y∑P
(x,y)wTf(x,y)−x,y∑P
(x,y)lnZw(x)
因为:
∑
y
P
~
(
x
,
y
)
ln
Z
w
(
x
)
=
ln
Z
w
(
x
)
∑
y
P
~
(
x
,
y
)
=
ln
Z
w
(
x
)
P
~
(
x
)
\sum_{y}\widetilde{P}(x,y)\ln Z_w(x)=\ln Z_w(x)\sum_{y}\widetilde{P}(x,y)=\ln Z_w(x)\widetilde{P}(x)
y∑P
(x,y)lnZw(x)=lnZw(x)y∑P
(x,y)=lnZw(x)P
(x)
所以:
L
P
~
(
P
w
)
=
∑
x
,
y
P
~
(
x
,
y
)
w
T
f
(
x
,
y
)
−
∑
x
P
~
(
x
)
ln
Z
w
(
x
)
L_{\widetilde{P}}(P_w)=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_x\widetilde{P}(x)\ln{Z_w(x)}
LP
(Pw)=x,y∑P
(x,y)wTf(x,y)−x∑P
(x)lnZw(x)
综上,极大化
L
(
P
,
w
)
L(P,w)
L(P,w)等价于最大熵模型的极大似然估计。
三、模型学习的最优化算法
IIS的想法是:假设最大熵模型当前的参数向量是
w
\boldsymbol w
w,我们希望找到一个新的参数向量:
w
+
δ
\boldsymbol w+\boldsymbol \delta
w+δ,使得模型的对数似然函数增大。不断重复这一过程直到找到对数似然函数的最大值。
更新前后的对数似然函数改变量为:
L
P
~
(
P
w
+
δ
)
−
L
P
~
(
P
w
)
=
(
∑
x
,
y
P
~
(
x
,
y
)
(
w
+
δ
)
T
f
(
x
,
y
)
−
∑
x
P
~
(
x
)
ln
Z
w
+
δ
(
x
)
)
−
(
∑
x
,
y
P
~
(
x
,
y
)
w
T
f
(
x
,
y
)
−
∑
x
P
~
(
x
)
ln
Z
w
(
x
)
)
=
∑
x
,
y
P
~
(
x
,
y
)
δ
T
f
(
x
,
y
)
−
∑
x
P
~
(
x
)
ln
Z
w
+
δ
(
x
)
Z
w
(
x
)
L_{\widetilde{P}}(P_{w+\delta})-L_{\widetilde{P}}(P_w)=(\sum_{x,y}\widetilde{P}(x,y)(\boldsymbol{w+\delta})^T\boldsymbol{f(x,y)}-\sum_x\widetilde{P}(x)\ln{Z_{w+\delta}(x)})-\\ (\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{w}^T\boldsymbol{f(x,y)}-\sum_x\widetilde{P}(x)\ln{Z_w(x)}) \\=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}-\sum_x\widetilde{P}(x)\ln \frac{Z_{w+\delta}(x)}{Z_w(x)}
LP
(Pw+δ)−LP
(Pw)=(x,y∑P
(x,y)(w+δ)Tf(x,y)−x∑P
(x)lnZw+δ(x))−(x,y∑P
(x,y)wTf(x,y)−x∑P
(x)lnZw(x))=x,y∑P
(x,y)δTf(x,y)−x∑P
(x)lnZw(x)Zw+δ(x)
利用不等式
−
ln
α
≥
1
−
α
-\ln \alpha \ge 1-\alpha
−lnα≥1−α,得:
L
P
~
(
P
w
+
δ
)
−
L
P
~
(
P
w
)
≥
∑
x
,
y
P
~
(
x
,
y
)
δ
T
f
(
x
,
y
)
+
1
−
∑
x
P
~
(
x
)
Z
w
+
δ
(
x
)
Z
w
(
x
)
=
∑
x
,
y
P
~
(
x
,
y
)
δ
T
f
(
x
,
y
)
+
1
−
∑
x
P
~
(
x
)
∑
y
P
w
(
y
∣
x
)
e
δ
T
f
(
x
,
y
)
L_{\widetilde{P}}(P_{w+\delta})-L_{\widetilde{P}}(P_w) \ge \sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1 - \sum_{x}\widetilde{P}(x)\frac{Z_{w+\delta}(x)}{Z_w(x)} \\=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)e^{\boldsymbol \delta ^T\boldsymbol {f(x,y)}}
LP
(Pw+δ)−LP
(Pw)≥x,y∑P
(x,y)δTf(x,y)+1−x∑P
(x)Zw(x)Zw+δ(x)=x,y∑P
(x,y)δTf(x,y)+1−x∑P
(x)y∑Pw(y∣x)eδTf(x,y)
令
A
(
δ
∣
w
)
=
∑
x
,
y
P
~
(
x
,
y
)
δ
T
f
(
x
,
y
)
+
1
−
∑
x
P
~
(
x
)
∑
y
P
w
(
y
∣
x
)
e
δ
T
f
(
x
,
y
)
A(\boldsymbol \delta|\boldsymbol w)=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)e^{\boldsymbol \delta ^T\boldsymbol {f(x,y)}}
A(δ∣w)=∑x,yP
(x,y)δTf(x,y)+1−∑xP
(x)∑yPw(y∣x)eδTf(x,y)为对数似然函数的改变量的一个下界,因为
δ
\boldsymbol \delta
δ是一个n维向量,而
A
(
δ
∣
w
)
A(\boldsymbol \delta|\boldsymbol w)
A(δ∣w)在e的指数部分有
δ
\boldsymbol \delta
δ,所以若此时求偏导会导致导数的每一个分量都有
δ
\boldsymbol \delta
δ。因此,尝试寻找一个新的下界,使得指数部分只存在
δ
\boldsymbol \delta
δ的单个分量。
令
f
#
(
x
,
y
)
=
1
T
f
(
x
,
y
)
f^\#(x,y)=\boldsymbol 1^T\boldsymbol {f(x,y)}
f#(x,y)=1Tf(x,y)即(x,y)处特征出现的次数,则:
A
(
δ
∣
w
)
=
∑
x
,
y
P
~
(
x
,
y
)
δ
T
f
(
x
,
y
)
+
1
−
∑
x
P
~
(
x
)
∑
y
P
w
(
y
∣
x
)
e
f
#
(
x
,
y
)
δ
T
f
(
x
,
y
)
f
#
(
x
,
y
)
=
∑
x
,
y
P
~
(
x
,
y
)
δ
T
f
(
x
,
y
)
+
1
−
∑
x
P
~
(
x
)
∑
y
P
w
(
y
∣
x
)
e
f
#
(
x
,
y
)
∑
i
=
1
n
δ
i
f
i
(
x
,
y
)
f
#
(
x
,
y
)
A(\boldsymbol \delta|\boldsymbol w)=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)e^{f^\#(x,y) \frac{\boldsymbol \delta ^T\boldsymbol {f(x,y)}}{f^\#(x,y)}}\\=\sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)e^{f^\#(x,y) \sum_{i=1}^n\delta_i\frac{f_i(x,y)}{f^\#(x,y)}}
A(δ∣w)=x,y∑P
(x,y)δTf(x,y)+1−x∑P
(x)y∑Pw(y∣x)ef#(x,y)f#(x,y)δTf(x,y)=x,y∑P
(x,y)δTf(x,y)+1−x∑P
(x)y∑Pw(y∣x)ef#(x,y)∑i=1nδif#(x,y)fi(x,y)
由于
f
i
(
x
,
y
)
f
#
(
x
,
y
)
≥
0
,
∑
i
=
1
n
f
i
(
x
,
y
)
f
#
(
x
,
y
)
=
1
\frac{f_i(x,y)}{f^\#(x,y)}\ge0, \sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}=1
f#(x,y)fi(x,y)≥0,∑i=1nf#(x,y)fi(x,y)=1且e的指数函数为下凸函数,则由琴生不等式得:
e
f
#
(
x
,
y
)
∑
i
=
1
n
δ
i
f
i
(
x
,
y
)
f
#
(
x
,
y
)
≤
∑
i
=
1
n
f
i
(
x
,
y
)
f
#
(
x
,
y
)
e
f
#
(
x
,
y
)
δ
i
e^{f^\#(x,y) \sum_{i=1}^n\delta_i\frac{f_i(x,y)}{f^\#(x,y)}} \le \sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}e^{f^\#(x,y)\delta_i}
ef#(x,y)∑i=1nδif#(x,y)fi(x,y)≤i=1∑nf#(x,y)fi(x,y)ef#(x,y)δi
所以:
A
(
δ
∣
w
)
≥
s
u
m
x
,
y
P
~
(
x
,
y
)
δ
T
f
(
x
,
y
)
+
1
−
∑
x
P
~
(
x
)
∑
y
P
w
(
y
∣
x
)
∑
i
=
1
n
f
i
(
x
,
y
)
f
#
(
x
,
y
)
e
f
#
(
x
,
y
)
δ
i
A(\boldsymbol \delta|\boldsymbol w) \ge sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)\sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}e^{f^\#(x,y)\delta^i}
A(δ∣w)≥sumx,yP
(x,y)δTf(x,y)+1−x∑P
(x)y∑Pw(y∣x)i=1∑nf#(x,y)fi(x,y)ef#(x,y)δi
令
B
(
δ
∣
w
)
=
∑
x
,
y
P
~
(
x
,
y
)
δ
T
f
(
x
,
y
)
+
1
−
∑
x
P
~
(
x
)
∑
y
P
w
(
y
∣
x
)
∑
i
=
1
n
f
i
(
x
,
y
)
f
#
(
x
,
y
)
e
f
#
(
x
,
y
)
δ
i
B(\boldsymbol \delta|\boldsymbol w) = \sum_{x,y}\widetilde{P}(x,y)\boldsymbol{\delta}^T\boldsymbol{f(x,y)}+1- \sum_{x}\widetilde{P}(x)\sum_yP_w(y|x)\sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}e^{f^\#(x,y)\delta^i}
B(δ∣w)=∑x,yP
(x,y)δTf(x,y)+1−∑xP
(x)∑yPw(y∣x)∑i=1nf#(x,y)fi(x,y)ef#(x,y)δi为对数似然函数改变量的一个新下界,将其对
δ
\boldsymbol \delta
δ的任一分量求导得:
∂
B
(
δ
∣
w
)
∂
δ
i
=
∑
x
,
y
P
~
(
x
,
y
)
f
i
(
x
,
y
)
−
∑
x
,
y
P
~
(
x
)
P
w
(
y
∣
x
)
f
i
(
x
,
y
)
e
f
#
(
x
,
y
)
δ
i
\frac{\partial B(\boldsymbol \delta|\boldsymbol w)}{\partial \delta_i}=\sum_{x,y}\widetilde{P}(x,y)f_i(x,y)-\sum_{x,y}\widetilde{P}(x)P_w(y|x)f_i(x,y)e^{f^\#(x,y)\delta_i}
∂δi∂B(δ∣w)=x,y∑P
(x,y)fi(x,y)−x,y∑P
(x)Pw(y∣x)fi(x,y)ef#(x,y)δi
令偏导数等于0得到:
∑
x
,
y
P
~
(
x
)
P
w
(
y
∣
x
)
f
i
(
x
,
y
)
e
f
#
(
x
,
y
)
δ
i
=
E
P
~
(
f
i
)
\sum_{x,y}\widetilde{P}(x)P_w(y|x)f_i(x,y)e^{f^\#(x,y)\delta_i}=E_{\widetilde P}(f_i)
x,y∑P
(x)Pw(y∣x)fi(x,y)ef#(x,y)δi=EP
(fi)
依次对
δ
\boldsymbol \delta
δ的分量求上式的解即可解出
δ
\boldsymbol \delta
δ。
为简化求解过程,一般假设
f
#
(
x
,
y
)
δ
i
=
M
f^\#(x,y)\delta_i=M
f#(x,y)δi=M为一常数,即假设对任意的(x,y),特征出现的次数相同。那么
δ
i
\delta_i
δi可显式得出:
δ
i
=
1
M
ln
E
P
~
(
f
i
)
E
P
(
f
i
)
\delta_i=\frac{1}{M}\ln \frac{E_{\widetilde P}(f_i)}{E_P(f_i)}
δi=M1lnEP(fi)EP
(fi)
若
f
#
(
x
,
y
)
δ
i
f^\#(x,y)\delta_i
f#(x,y)δi不为常数,则需要通过数值计算求解,如使用牛顿法迭代求解。
四、代码实现
代码如下:
import numpy as np
from collections import defaultdict
from sklearn.datasets import load_digits
from time import sleep
from tqdm import tqdm
def load_data():
'''
加载sklearn自带的手写数字识别数据集
返回 输入、输出
'''
digits = load_digits()
xs = digits.data
ys = digits.target
return xs, ys
class MaxEntropy(object):
def __init__(self, train_xs, train_ys, test_xs, test_ys, iterations=200):
self.train_xs = train_xs
self.train_ys = train_ys
self.test_xs = test_xs
self.test_ys = test_ys
self.iterations = iterations
self.example_cnt, self.feature_cnt = train_xs.shape
self.feature_label_pairs_dict, self.pair_cnt = self.get_feature_label() # pair_cnt相当于特征函数个数
self.weights = np.zeros((self.pair_cnt,))
self.xy2id_dicts, self.id2xy_dict = self.get_search_dict()
self.e_hat_f = self.get_e_hat_f()
self.e_f = self.get_e_f()
self.f_weight = self.get_f_weight()
def get_feature_label(self):
"""
获取
每个特征的特征标签对字典
总的特征标签对的个数
:return:
"""
feature_label_pairs = [defaultdict(int) for feature_id in range(self.feature_cnt)]
pair_cnt = 0
for example_id in range(self.example_cnt):
for feature_id in range(self.feature_cnt):
feature_label_pairs[feature_id][(self.train_xs[example_id][feature_id], self.train_ys[example_id])] += 1
for pair_dict in feature_label_pairs:
pair_cnt += len(pair_dict)
return feature_label_pairs, pair_cnt
def get_search_dict(self):
"""
保存特征标签对xy对应id的字典数组
保存特征标签对id对应xy的的字典
:return:
"""
idx = 0
xy2id_dicts = [dict() for feature_id in range(self.feature_cnt)]
id2xy_dict = dict()
for feature_id in range(self.feature_cnt):
for (x, y) in self.feature_label_pairs_dict[feature_id].keys():
xy2id_dicts[feature_id][(x, y)] = idx
id2xy_dict[idx] = (x, y)
idx += 1
return xy2id_dicts, id2xy_dict
def get_e_hat_f(self):
"""
特征函数f(x,y)关于经验分布P_hat(X,Y)的期望值
:return:
"""
e_hat_f = np.zeros((self.pair_cnt,))
for feature_id in range(self.feature_cnt):
for (x, y) in self.feature_label_pairs_dict[feature_id]:
idx = self.xy2id_dicts[feature_id][(x, y)]
e_hat_f[idx] = self.feature_label_pairs_dict[feature_id][(x, y)] / self.example_cnt
return e_hat_f
def get_pw_xy(self, x):
"""
求解条件概率分布P_w(y|x)
:param x:
:return:
"""
uniques = np.unique(self.train_ys)
numerators = np.zeros((max(uniques)+1, ))
for feature_id in range(self.feature_cnt):
for label in uniques:
if (x[feature_id], label) in self.feature_label_pairs_dict[feature_id]:
idx = self.xy2id_dicts[feature_id][(x[feature_id], label)]
numerators[label] += self.weights[idx]
numerators = np.exp(numerators)
z_w = np.sum(numerators)
return numerators / z_w
def predict(self, x):
'''
预测标签
:param X:要预测的样本
:return: 预测值
'''
return np.argmax(self.get_pw_xy(x))
def test(self):
'''
对测试集进行测试
:return:
'''
# 错误值计数
error_cnt = 0
# 对测试集中所有样本进行遍历
for i in range(len(self.test_xs)):
# 预测该样本对应的标签
result = self.predict(self.test_xs[i])
# 如果错误,计数值加1
if result != self.test_ys[i]:
error_cnt += 1
# 返回准确率
return 1 - error_cnt / len(self.test_xs)
def get_e_f(self):
"""
计算特征函数f(x,y)关于模型P(X|Y)与经验分布P_hat(X)的期望
:return:
"""
e_f = np.zeros((self.pair_cnt,))
for example_id in range(self.example_cnt):
pw_xy = self.get_pw_xy(self.train_xs[example_id])
for feature_id in range(self.feature_cnt):
if (self.train_xs[example_id][feature_id], self.train_ys[example_id]) \
in self.feature_label_pairs_dict[feature_id]:
idx = self.xy2id_dicts[feature_id][self.train_xs[example_id][feature_id], self.train_ys[example_id]]
e_f[idx] += (1 / self.example_cnt) * pw_xy[self.train_ys[example_id]]
return e_f
def get_f_weight(self):
"""
计算iis引进的一个量1 / f_#(x,y)
:return:
"""
f_weight = np.zeros((self.pair_cnt,))
for feature_id_1 in range(self.feature_cnt):
for x_y_pair_1 in self.feature_label_pairs_dict[feature_id_1]:
idx = self.xy2id_dicts[feature_id_1][x_y_pair_1]
similar_x_y_cnt = 0
x_y_count = self.feature_label_pairs_dict[feature_id_1][x_y_pair_1]
for feature_id_2 in range(self.feature_cnt):
for x_y_pair_2 in self.feature_label_pairs_dict[feature_id_2]:
if x_y_pair_2 == x_y_pair_1:
similar_x_y_cnt += self.feature_label_pairs_dict[feature_id_2][x_y_pair_2]
f_weight[idx] = x_y_count / similar_x_y_cnt
return f_weight
def iis_train(self):
"""
采用改进尺度迭代法进行训练
:return:
"""
for i in tqdm(range(self.iterations)):
# sigma_array = self.f_weight * np.log(self.e_hat_f / self.e_f)
sigma_array = (1 / self.feature_cnt) * np.log(self.e_hat_f / self.e_f)
self.weights = self.weights + sigma_array
if (i+1) % 5 == 0:
accuracy = self.test()
print('the accuracy is:%.4f' % accuracy)
sleep(0.03)
if __name__ == '__main__':
features, targets = load_data()
train_count = int(len(features) * 0.8)
train_xs, train_ys = features[:train_count], targets[:train_count]
test_xs, test_ys = features[train_count:], targets[train_count:]
# 初始化最大熵类
maxEnt = MaxEntropy(train_xs, train_ys, test_xs, test_ys)
# 开始训练
print('start to train')
maxEnt.iis_train()
# 开始测试
print('start to test')
accuracy = maxEnt.test()
print('the accuracy is:%.4f' % accuracy)
标签:最大,ln,sum,boldsymbol,feature,self,widetilde,模型 From: https://blog.csdn.net/qq_47190374/article/details/136971135