最⼤大熵模型
熵的相关概念，第⼀一次在决策树那章做了简单介绍，但是要想正确理解熵的确实需要下⼀一番功夫。这次，我们在最⼤大熵模型这章继续来学习熵，理解熵在该模型中所扮演的⾓角⾊色。
以⼀一个问题开始我们的学习：机器学习的⺫⽬目的或者意义是什么？
对于监督学习来说，我们希望通过现有获得的观测数据训练⼀一个数据模型，然后来对未知类别样本和数据进⾏行回归和分类预测。那么问题来了，什么样的模型才是⽐比较好的模型呢？也许熵可以给我们提供了另⼀一种特别的视⾓角。好，让我们重新看⼀一下熵的定义：
H(x)=−
∑
x=1
N
P(x)log(P(x))
0
⽐比如，⼀一个抛硬币的实验，得到正反两⾯面的概率分别都是0.5，相应系统的熵为1。也就是说，如果⼀一个随机变量的分布确定之后，熵也就唯⼀一确定了。假设这⾥里的P(x)是我们随机变量的真实分布，因此这个熵是我们的下界，任何估计得到的数据分布的熵都应当⼤大于等于它。
那么，最⼤大熵模型以及同样为指数模型的逻辑斯特回归模型究竟是怎么和熵联系起来的呢？为什么利⽤用熵的约束可以使得我们训练的模型可以很好地表征观测数据。
⾸首先，让我们来看⼀一下逻辑斯特回归所使⽤用的交叉熵损失函数：
CE(x)=−
∑
x=1
N
P(x)log(Q(x))
H(x)
因此，通过优化最⼩小CE(x)会使得Q(x)尽量逼近真实数据分布P(x)。噢，原来通过最⼩小化交叉熵可以使得模型朝着我们想要的⽅方向进⾏行优化，表达训练样本啊！
然后，我们再来看⼀一下最⼤大熵模型这边⼜又是什么情况。
经验告诉我们，对于已知事件可以通过极⼤大似然估计来统计各个事件发⽣生的概率，⽽而对于未知事件⼀一般做法是把剩余概率平均分给这些事件。⽐比如，下⾯面这个简单的例⼦子：概率/颜⾊色P(x)
红球3/5
绿球蓝球为什么这样做？因为我们⽆无法获得额外的信息来使得熵进⼀一步减⼩小，也可以说我们⽆无法再做进⼀一步的判断。平均这个词⽣生来就和熵有特殊的关系，我们知道当P(x)服从均匀分布时，系统的熵最⼤大。
我们的⺫⽬目标刚好就是使得未知事件的概率分布为均匀分布，也就是使这些未知事件的熵最⼤大。通过这个约束得到的模型就不会对未知事件做任何假设，公平的对待它们，这就是最⼤大熵的核⼼心思想。
先简单窥探⼀一下最⼤大熵模型中熵的引⼊入定义：
H(x)=−
∑
x,y
P−(x)P(y|x)log(P(y|x))
注意，这⾥里定义的是条件熵，P(y|x)是我们需要估计的⺫⽬目标分布。所以，优化上⾯面的条件熵并使其最⼤大，得到的最优模型就能实现我们公平的理想。当然，这种约束只应该尽量施加在未知样本上，⽽而对于已知样本还需要做点什么，后⾯面我们会继续探讨。可能这⾥里有⼈人会有⼀一些疑问，⽐比如：
1. 为什么都是熵， 怎么⼀一下求最⼤大值好，⼀一下⼜又求最⼩小值好？
我们的最终⺫⽬目的都是希望模型最优，熵⼤大熵⼩小只是准则和途径。最终都是希望估计分布和真实分布趋于⼀一致。2. 抛硬币是服从均匀分布，如果我们针对该问题学习到的模型也⼤大致服从均匀分布是不是说明该模型不好，因为熵⼤大？我们只是希望估计分布的熵尽可能和真实分布的熵⼀一致，⽽而不是希望对真实分布做什么改变以求熵⼩小。 举个栗⼦子，我只是希望我画苹果像真实的苹果，⽽而不是要求苹果像其它什么⽔水果，⽐比如⾹香蕉（假设苹果的熵⽐比⾹香蕉的熵⼤大）。
最⼤大熵模型
上⼀一节提到最⼤大熵模型是怎么利⽤用熵来约束未知事件的概率分布服从均匀分布。那已知事件或者说已知样本怎么处理呢？我们还必须让我们的模型能够很好的表⽰示已知样本啊！好像缺了什么，对吧？是时候我们来看下最⼤大熵代价损失函数：
H(x)=−∑
x,y
∑
x,y
P−(x)P(y|x)log(P(y|x))
∑
x,y
P−(x)P(y|x)f(x,y)=
∑
y
P−(x,y)f(x,y)
P(y|x)=1
第⼆二个等式就是⽤用来约束模型训练尽量表⽰示我们的已知样本信息。最⼤大熵模型这⾥里引⼊入了⼀一个特征函数的概念：
f(x,y) = 1, x与y满⾜足某⼀一事实f(x,y) = 0, 否则
12
为什么需要特征函数？⽐比较容易理解的是，特征函数其实是⼀一个⽤用户接⼝口，我们可以通过定制特征函数来控制模型的训练。⽐比如，我们可以这样设计特征函数：
f(x,y) = 1, 客户拥有⼀一套房产，允许贷款f(x,y) = 0, 否则
12
好像还是不太清楚为什么需要特征函数啊！我们换个⾓角度来思考，即怎样度量两个分布之间的距离或者相似度呢？
∑
x,y
||p(x,y)−q(x,y)||
q(x,y)f(x,y)
(x,y)f(x,y)=
∑
x,y
p(x,y)f(x,y)=∑
x,y
∑
x,y
q(x,y)f(x,y)
p(x,y)log(p(x,y)/q(x,y))
第⼀一个就是常⽤用的欧式距离；第⼆二个是f(x,y)关于两个分布的期望差值；第三个是KL距离。我们重点关注第⼆二个度量⽅方法，因为最⼤大熵模型⽤用的就是这种。
注意，f(x,y)必须是实数函数，⽽而最⼤大熵模型⼀一般要求这个函数是⼀一个⼆二值函数。也就是说通过这个特征函数把x和y之间千丝万缕的关系转化成了⼀一个实数值，这时我们就可以度量P−(x)P(y|x)和P−(x,y)两个分布之间的相似度了。我们再来看个图，理解⼀一下特征函数f(x,y)的实质意义是什么。
从这⾥里看出，特征函数其实就是从分布上采样，特征函数越多、越好就可以使得采样越充分，但同时模型也就越复杂，容易过拟合。
所以在这些特征函数的约束下，使得两个分布在这些采样点上都能取得⼀一致，进⽽而使得两个分布尽量相似。
说到这⾥里，特征函数的意义应该明⽩白了。没错，最⼤大熵模型就是通过约束上⾯面说的两个期望相等来使得模型尽量去学习表征我们的观测数据。
最⼤大熵模型学习
对于最⼤大熵这种有约束的优化问题，⼀一般情况下会通过拉格朗⽇日乘⼦子法把它转化为⽆无约束优化问题。
minpmaxwL(p,w)=
∑
x,y
P(x)P(y|x)log(P(y|x))+w0(1−
−
∑
y
P(y|x))+
∑
i=1
n
wi(
∑
x,y
P−(x,y)fi(x,y)−
∑
x,y
P−(x)P(y|x)fi(x,y))
整个优化⺫⽬目标表达式包含两个未知项，⼀一个是待求的类后验分布P(y|x)，另⼀一个是权重w。
⼀一⽅方⾯面，我们希望w越⼤大越好，这等价于要求模型要尽可能拟合或者说表⽰示我们的数据；另⼀一⽅方⾯面，希望最后选择的P(y|x)使得
L(p,w)越⼩小越好，这⼜又等价于要求选择的模型使得条件熵H(x)越⼤大越好。
到此，只要优化上⾯面的函数，就可以满⾜足我们两⽅方⾯面的需求了。
对于简单的栗⼦子，我们可以直接求上⾯面代价函数的解析解，其实就是⼆二元函数的极值求解问题。⽐比如，先对P(y|x)求偏导并令求导公式等于0，然后再对w求导并令求导公式等于0，解出w∗。最终，我们求得的P(y|x)形式为：
exp(∑nwifi(x,y))Pw(y|x)=
wZw(x)=
∑
y
exp(wifi(x,y))
∑
i=1
n
⽽而实际上，我们遇到的问题⼤大多是样本多、特征函数也多的情况，这个时候只能采⽤用迭代求解的⽅方法。
最⼤大熵模型⺫⽬目前最采⽤用的迭代优化算法主要是IIS（迭代尺度法），也出现了该算法的很多变体算法。⼤大家有兴趣可以关注⼀一下。
基本IIS算法思想：
假设最⼤大熵模型当前的参数是：
wt=(w1,w2,...,wn)T
找到新的参数：
wt+1=(w1+δ1,w2+δ2,...,wn+δn)T
使得模型的对数似然值
L(w)=
∑
x,y
P−(x,y)
∑
i=1
n
wifi(x,y)−
∑
x
P−(x)log(Zw(x))
增⼤大。不断地使⽤用该⽅方法对w进⾏行更新，就可以使得w最终收敛到w∗。那现在的问题就变成了怎么去迭代寻找
δ=(δ1,δ2,...,δn)T了。
题。
⽐比如，现在的优化问题是：
在机器学习领域，有⼀一个⾮非常好的优化策略，就是当原问题难以求解的时候，可以通过优化原问题的下界函数，来间接优化原问
L(wt+1)−L(wt)=
∑
x,y
P(x,y)
−
∑
i=1
n
δifi(x,y)−
∑
x
P−(x)log
w
统计学习⽅方法 李航著
最⼤大熵模型
熵的相关概念，第⼀一次在决策树那章做了简单介绍，但是要想正确理解熵的确实需要下⼀一番功夫。这次，我们在最⼤大熵模型这章继续来学习熵，理解熵在该模型中所扮演的⾓角⾊色。
以⼀一个问题开始我们的学习：机器学习的⺫⽬目的或者意义是什么？
对于监督学习来说，我们希望通过现有获得的观测数据训练⼀一个数据模型，然后来对未知类别样本和数据进⾏行回归和分类预测。那么问题来了，什么样的模型才是⽐比较好的模型呢？也许熵可以给我们提供了另⼀一种特别的视⾓角。好，让我们重新看⼀一下熵的定义：
H(x)=−
∑
x=1
N
P(x)log(P(x))
0
⽐比如，⼀一个抛硬币的实验，得到正反两⾯面的概率分别都是0.5，相应系统的熵为1。也就是说，如果⼀一个随机变量的分布确定之后，熵也就唯⼀一确定了。假设这⾥里的P(x)是我们随机变量的真实分布，因此这个熵是我们的下界，任何估计得到的数据分布的熵都应当⼤大于等于它。
那么，最⼤大熵模型以及同样为指数模型的逻辑斯特回归模型究竟是怎么和熵联系起来的呢？为什么利⽤用熵的约束可以使得我们训练的模型可以很好地表征观测数据。
⾸首先，让我们来看⼀一下逻辑斯特回归所使⽤用的交叉熵损失函数：
CE(x)=−
∑
x=1
N
P(x)log(Q(x))
H(x)
因此，通过优化最⼩小CE(x)会使得Q(x)尽量逼近真实数据分布P(x)。噢，原来通过最⼩小化交叉熵可以使得模型朝着我们想要的⽅方向进⾏行优化，表达训练样本啊！
然后，我们再来看⼀一下最⼤大熵模型这边⼜又是什么情况。
经验告诉我们，对于已知事件可以通过极⼤大似然估计来统计各个事件发⽣生的概率，⽽而对于未知事件⼀一般做法是把剩余概率平均分给这些事件。⽐比如，下⾯面这个简单的例⼦子：概率/颜⾊色P(x)
红球3/5
绿球蓝球为什么这样做？因为我们⽆无法获得额外的信息来使得熵进⼀一步减⼩小，也可以说我们⽆无法再做进⼀一步的判断。平均这个词⽣生来就和熵有特殊的关系，我们知道当P(x)服从均匀分布时，系统的熵最⼤大。
我们的⺫⽬目标刚好就是使得未知事件的概率分布为均匀分布，也就是使这些未知事件的熵最⼤大。通过这个约束得到的模型就不会对未知事件做任何假设，公平的对待它们，这就是最⼤大熵的核⼼心思想。
先简单窥探⼀一下最⼤大熵模型中熵的引⼊入定义：
H(x)=−
∑
x,y
P−(x)P(y|x)log(P(y|x))
注意，这⾥里定义的是条件熵，P(y|x)是我们需要估计的⺫⽬目标分布。所以，优化上⾯面的条件熵并使其最⼤大，得到的最优模型就能实现我们公平的理想。当然，这种约束只应该尽量施加在未知样本上，⽽而对于已知样本还需要做点什么，后⾯面我们会继续探讨。可能这⾥里有⼈人会有⼀一些疑问，⽐比如：
1. 为什么都是熵， 怎么⼀一下求最⼤大值好，⼀一下⼜又求最⼩小值好？
我们的最终⺫⽬目的都是希望模型最优，熵⼤大熵⼩小只是准则和途径。最终都是希望估计分布和真实分布趋于⼀一致。2. 抛硬币是服从均匀分布，如果我们针对该问题学习到的模型也⼤大致服从均匀分布是不是说明该模型不好，因为熵⼤大？我们只是希望估计分布的熵尽可能和真实分布的熵⼀一致，⽽而不是希望对真实分布做什么改变以求熵⼩小。 举个栗⼦子，我只是希望我画苹果像真实的苹果，⽽而不是要求苹果像其它什么⽔水果，⽐比如⾹香蕉（假设苹果的熵⽐比⾹香蕉的熵⼤大）。
最⼤大熵模型
上⼀一节提到最⼤大熵模型是怎么利⽤用熵来约束未知事件的概率分布服从均匀分布。那已知事件或者说已知样本怎么处理呢？我们还必须让我们的模型能够很好的表⽰示已知样本啊！好像缺了什么，对吧？是时候我们来看下最⼤大熵代价损失函数：
H(x)=−∑
x,y
∑
x,y
P−(x)P(y|x)log(P(y|x))
∑
x,y
P−(x)P(y|x)f(x,y)=
∑
y
P−(x,y)f(x,y)
P(y|x)=1
第⼆二个等式就是⽤用来约束模型训练尽量表⽰示我们的已知样本信息。最⼤大熵模型这⾥里引⼊入了⼀一个特征函数的概念：
f(x,y) = 1, x与y满⾜足某⼀一事实f(x,y) = 0, 否则
12
为什么需要特征函数？⽐比较容易理解的是，特征函数其实是⼀一个⽤用户接⼝口，我们可以通过定制特征函数来控制模型的训练。⽐比如，我们可以这样设计特征函数：
f(x,y) = 1, 客户拥有⼀一套房产，允许贷款f(x,y) = 0, 否则
12
好像还是不太清楚为什么需要特征函数啊！我们换个⾓角度来思考，即怎样度量两个分布之间的距离或者相似度呢？
∑
x,y
||p(x,y)−q(x,y)||
q(x,y)f(x,y)
(x,y)f(x,y)=
∑
x,y
p(x,y)f(x,y)=∑
x,y
∑
x,y
q(x,y)f(x,y)
p(x,y)log(p(x,y)/q(x,y))
第⼀一个就是常⽤用的欧式距离；第⼆二个是f(x,y)关于两个分布的期望差值；第三个是KL距离。我们重点关注第⼆二个度量⽅方法，因为最⼤大熵模型⽤用的就是这种。
注意，f(x,y)必须是实数函数，⽽而最⼤大熵模型⼀一般要求这个函数是⼀一个⼆二值函数。也就是说通过这个特征函数把x和y之间千丝万缕的关系转化成了⼀一个实数值，这时我们就可以度量P−(x)P(y|x)和P−(x,y)两个分布之间的相似度了。我们再来看个图，理解⼀一下特征函数f(x,y)的实质意义是什么。
从这⾥里看出，特征函数其实就是从分布上采样，特征函数越多、越好就可以使得采样越充分，但同时模型也就越复杂，容易过拟合。
所以在这些特征函数的约束下，使得两个分布在这些采样点上都能取得⼀一致，进⽽而使得两个分布尽量相似。
说到这⾥里，特征函数的意义应该明⽩白了。没错，最⼤大熵模型就是通过约束上⾯面说的两个期望相等来使得模型尽量去学习表征我们的观测数据。
最⼤大熵模型学习
对于最⼤大熵这种有约束的优化问题，⼀一般情况下会通过拉格朗⽇日乘⼦子法把它转化为⽆无约束优化问题。
minpmaxwL(p,w)=
∑
x,y
P(x)P(y|x)log(P(y|x))+w0(1−
−
∑
y
P(y|x))+
∑
i=1
n
wi(
∑
x,y
P−(x,y)fi(x,y)−
∑
x,y
P−(x)P(y|x)fi(x,y))
整个优化⺫⽬目标表达式包含两个未知项，⼀一个是待求的类后验分布P(y|x)，另⼀一个是权重w。
⼀一⽅方⾯面，我们希望w越⼤大越好，这等价于要求模型要尽可能拟合或者说表⽰示我们的数据；另⼀一⽅方⾯面，希望最后选择的P(y|x)使得
L(p,w)越⼩小越好，这⼜又等价于要求选择的模型使得条件熵H(x)越⼤大越好。
到此，只要优化上⾯面的函数，就可以满⾜足我们两⽅方⾯面的需求了。
对于简单的栗⼦子，我们可以直接求上⾯面代价函数的解析解，其实就是⼆二元函数的极值求解问题。⽐比如，先对P(y|x)求偏导并令求导公式等于0，然后再对w求导并令求导公式等于0，解出w∗。最终，我们求得的P(y|x)形式为：
exp(∑nwifi(x,y))Pw(y|x)=
wZw(x)=
∑
y
exp(wifi(x,y))
∑
i=1
n
⽽而实际上，我们遇到的问题⼤大多是样本多、特征函数也多的情况，这个时候只能采⽤用迭代求解的⽅方法。
最⼤大熵模型⺫⽬目前最采⽤用的迭代优化算法主要是IIS（迭代尺度法），也出现了该算法的很多变体算法。⼤大家有兴趣可以关注⼀一下。
基本IIS算法思想：
假设最⼤大熵模型当前的参数是：
wt=(w1,w2,...,wn)T
找到新的参数：
wt+1=(w1+δ1,w2+δ2,...,wn+δn)T
使得模型的对数似然值
L(w)=
∑
x,y
P−(x,y)
∑
i=1
n
wifi(x,y)−
∑
x
P−(x)log(Zw(x))
增⼤大。不断地使⽤用该⽅方法对w进⾏行更新，就可以使得w最终收敛到w∗。那现在的问题就变成了怎么去迭代寻找
δ=(δ1,δ2,...,δn)T了。
题。
⽐比如，现在的优化问题是：
在机器学习领域，有⼀一个⾮非常好的优化策略，就是当原问题难以求解的时候，可以通过优化原问题的下界函数，来间接优化原问
L(wt+1)−L(wt)=
∑
x,y
P(x,y)
−
∑
i=1
n
δifi(x,y)−
∑
x
P−(x)log
w
统计学习⽅方法 李航著