最大熵模型

7.1 最大熵模型

最大熵模型(maximum entropy model)由最大熵原理推导实现。

7.1.1 最大熵原理

最大熵原理:学习概率模型时,在所有可能的概率模型(分布)中,熵最大的模型是最好的模型。

通常用约束条件来确定概率模型的集合,所以,最大熵原理也可表述为在满足约束条件的模型集合中选取熵最大的模型

假设离散随机变量X的概率分布是P(X),则其熵是:

熵满足下列不等式:

式中,|X|是X的取值个数,当且仅当X的分布是均匀分布时右边的等号成立。这就是说,当X服从均匀分布时,熵最大

直观地,最大熵原理认为要选择的概率模型首先必须满足已有的事实,即约束条件。在没有更多信息的情况下,那些不确定的部分都是”等可能的”最大熵原理通过熵的最大化来表示等可能性

7.1.2 最大熵模型的定义

假设分类模型是一个条件概率分布P(Y|X), 表示输入,表示输出,分别是输入和输出的集合。

给定一个训练数据集 学习的目标是用最大熵原理选择最好的分类模型

注意:此处的(x1,y1)中,x1为样本的某个特征,标量。所以中的X表示某个特征的随机变量(标量),Y表示标签随机变量(标量)。

定义约束条件

给定训练数据集,可以确定联合分布P(X,Y)的经验分布和边缘分布P(X)的经验分布,分别以表示。这里,

其中,v(X=x,Y=y)表示训练数据中样本(x,y)出现的频数,v(X=x)表示训练数据中输入x出现的频数,N表示训练样本容量。

定义特征函数:

它是一个二值函数,当x和y满足这个事实时取值为1,否则取值为0。

特征函数f(x,y)关于经验分布的期望值,用表示:

特征函数f(x,y)关于模型P(Y|X)与经验分布的期望值,用表示:

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

将式(6.10)作为模型学习的约束条件。假如有n个特征函数,那么就有n个约束条件。

定义6.3(最大熵模型)假设满足所有约束条件的模型集合为:

定义在条件概率分布P(Y|X)上的条件熵为:

则模型集合中条件熵H(P)最大的模型称为最大熵模型。式中的对数为自然对数。

注意:式(6.13)对应于第五章中式(5.5)。

7.1.3 最大熵模型的学习

最大熵模型的学习可以形式化为约束最优化问题。

对于给定的训练数据集以及特征函数,i=1,2,…,n,最大熵模型的学习等价于约束最优化问题:

按照最优化问题的习惯,将求最大值问题改写为等价的求最小值问题:

求解过程:

  1. 定义最优化的原始问题

    首先,引进拉格朗日乘子,定义拉格朗日函数L(P,w):

最优化的原始问题是:

  1. 对偶问题

    在满足KKT条件的情况下,原始问题的解与对偶问题的解等价

  2. 求解对偶问题的极小化问题

    具体地,求L(P,w)对P(y|x)的偏导数。

    令偏导数为0,在的情况下,解得:

    由于,得:

    其中,

    为归一化因子;是特征函数;是特征权重。由式(6.22)、式(6.23)表示的模型就是最大熵模型。w是最大熵模型中的参数向量。

  3. 求解对偶问题的极大化问题

    将其解记为,即:

    从而使得是学习到的最优模型(最大熵模型)。也就是说,最大熵模型的学习归结为对偶函数的极大化。

7.1.4 极大似然估计

证明对偶函数的极大化等价于最大熵模型的极大似然估计。

已知训练数据的经验概率分布,条件概率分布的对数似然函数表示为:

当条件概率分布P(y|x)是最大熵模型(6.22)和(6.23)时,对数似然函数为:

再看对偶函数。由式(6.17)和式(6.20)可得(注意:这里没有,可以参考(6.22),(6.23)发现该参数对求解对偶函数没有影响,只起到简化函数的作用,如下式的最后一步演化。):

最后一步用到

结论:比较式(6.26)和式(6.27),可得:

也就是说,最大熵模型的学习问题就可以转化为具体求解对数似然函数极大化或对偶函数极大化的问题。

最大熵模型的一般形式如式(6.22)及式(6.23)所示。

7.2 最大熵模型学习算法

逻辑斯蒂回归模型、最大熵模型学习归结为以似然函数为目标函数的最优化问题,通常通过迭代算法求解。

常用的求解方法有改进的迭代尺度法、梯度下降法、牛顿法或拟牛顿法。牛顿法或拟牛顿法一般收敛速度更快。

7.2.1 改进的迭代尺度法

改进的迭代尺度法是一种最大熵模型学习的最优化算法。

已知最大熵模型为:

其中,

对数似然函数为:

目标是通过极大似然估计学习模型参数,即求对数似然函数的极大值

改进的迭代尺度法的思路是:假设最大熵模型当前的参数向量是,我们希望找到一个新的参数向量,使得模型的对数似然函数值增大,如果能有这样一种参数向量更新的方法,那么就可以重复使用这一方法,直到找到对数似然函数的最大值。

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

利用不等式

建立对数似然函数改变量的下界:

上式,第一步应用了不等式,第二步应用了,第三步应用了

以及式(6.22)。

将右端记为:

于是有:

是对数似然函数改变量的一个下界。

如果能找到适当的使下界提高,那么对数似然函数也会提高

引入一个量

因为特征函数是一个二值函数,故表示所有特征在(x,y)出现的次数。这样,,改写为:

利用指数函数的凸性以及对任意i,有这一事实。

根据Jensen不等式,得到:

于是式(6.30)可改写为:

记不等式(6.31)右端为:

于是得到了:

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

的偏导数:

在式(6.32)中,除外,不含任何其他变量。令偏导数为0可得:

于是,依次对求解方程(6.33)可以求出

算法6.1(改进的迭代尺度算法IIS)

输入:特征函数;经验分布,模型

输出:最优参数值;最优模型

  1. 对所有,取初值

  2. 对每一

    (a) 令是方程的解,这里,

    (b) 更新的值:

  3. 如果不是所有都收敛,重复步(2)。

此算法的关键步骤为(a),即求解式(6.33)中的

  • 如果是常数,即对任何x,y,有,那么可以显式表示为(注意:此处的M相当于学习率,为超参数):
  • 如果不是常数,那么必须通过数值计算求。简单有效的方法为牛顿法。把式(6.33)表示成牛顿法通过迭代求得,使得。迭代公式:只要适当选取初始值,由于方程(6.33)有单根,因此牛顿法恒收敛,而且收敛速度更快。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
class MaxEnt(object):

def __init__(self, X, Y, n_iter=500, M=10000.0):

self.n_iter = n_iter
self.M = M#P91中的M,相当于学习速率

self.X_ = np.array(X)
self.Y_ = np.unique(Y)
self.Y = np.array(Y)
self.N,self.n_feature = self.X_.shape #训练数据集大小

self.cal_Vxy()
self.n = len(self.Vxy) #数据集中所有特征的取值情况与标签之间的组合对数,如P59例子中的6+3+3+5=17对

self.build_dict()
self.cal_Pxy()

def cal_Vxy(self):
'''
计算v(X=x,Y=y),P82
'''
self.Vxy = defaultdict(int)

for i in range(self.N):
x_, y = self.X_[i,:], self.Y[i]

for x in x_:
self.Vxy[(x,y)] += 1

def build_dict(self):
self.id2xy = {}
self.xy2id = {}

for i, (x,y) in enumerate(self.Vxy):
self.id2xy[i] = (x,y)
self.xy2id[(x,y)] = i

def cal_Pxy(self):
'''
计算P(X=x,Y=y),P82
'''
self.Pxy = defaultdict(float)
for n_id in range(self.n):
(x,y) = self.id2xy[n_id]
self.Pxy[n_id] = float(self.Vxy[(x,y)])/float(self.N)

def cal_Zxy(self, X,y):
'''
计算给定y的Zw(x|yi),P85 式6.23
X:一个样本
y:该样本对应的标签
'''
result = 0.0
for x in X:
if (x,y) in self.xy2id:
id = self.xy2id[(x,y)]
result += self.w[id]
return (math.exp(result),y)

def cal_Pyx(self, X):
'''
X:指具体一个样本

计算P(y|x),P85的式(6.22)
返回所有y对应的条件概率
'''
Pyxs = [(self.cal_Zxy(X,y)) for y in self.Y_]
Zwx = sum([prob for prob,y in Pyxs])

return [(prob/Zwx, y) for prob,y in Pyxs]

def cal_Epfi(self):
'''
计算特征函数关于模型P(Y|X)与经验分布P(X)的期望值
'''
self.Epfi = [0.0 for i in range(self.n)]
for i, X in enumerate(self.X_):
Pyxs = self.cal_Pyx(X)

for x in X: #遍历指定样本X的每一个特征
for Pyx,y in Pyxs:
if (x,y) in self.xy2id:
n_id = self.xy2id[(x,y)]
self.Epfi[n_id] += Pyx*(1.0/self.N) #(1.0/self.N)表示经验分布P(X),服从均匀分布

def train(self, X, Y):
'''
IIS学习算法
'''

#第一步:初始化参数值wi为0
self.w = [0.0]*self.n

max_iteration = self.n_iter #最大迭代次数
for i in range(self.n_iter):
#求delta_i
deltas = []
self.cal_Epfi()
for i in range(self.n):
delta = 1/self.M*math.log(self.Pxy[i]/self.Epfi[i])
deltas.append(delta)
#更新Wi
self.w = [self.w[i]+deltas[i] for i in range(self.n)]

def predict(self, testset):
results = []
for test in testset:
result = self.cal_Pyx(test)
results.append(max(result, key=lambda x: x[0])[1])
return results

7.2.2拟牛顿法

对于最大熵模型而言,

目标函数:

梯度:

其中,

相应的拟牛顿法BFGS算法如下 。

算法6.2(最大熵模型学习的BFGS算法)

输入:特征函数;经验分布,目标函数 f(w),梯度,精度要求

输出:最优参数值;最优模型

  1. 选定初始点,取为正定对称矩阵,置k=0

  2. 计算。若,则停止计算,得;否则转(3)

  3. ,求出

  4. 一维搜索:求使得

  5. 计算,若,则停止计算,得;否则,按下式求出:

    其中,

  6. 置k=k+1,转(3)