波粒二象性公式总结最大熵模型中的数学推导

2020年11月4日发(作者：班廷)
最大熵模型中的数学推导


http:iclev_JULY_0
引言 写完SVM之后，一直想继续写机器学习的系列，
无奈一直时间不稳定且对各个模 型算法的理解尚不够，所以
导致迟迟未动笔。无独有偶，重写KMP得益于今年4月个
人组织的 算法班，而动笔继续写这个机器学习系列，正得益
于今年10月组织的机器学习班。 10月26 日机器学习
班第6次课，身为讲师之一的邹博讲最大熵模型，他从熵的
概念，讲到为何要最大熵 、最大熵的推导，以及求解参数的
IIS方法，整个过程讲得非常流畅，特别是其中的数学推导。
晚上我把他的PPT 在微博上公开分享了出来，但对于没有
上过课的朋友直接看PPT 会感到非常 跳跃，因此我打算针
对机器学习班的某些次课写一系列博客，刚好也算继续博客
中未完的机器学 习系列。 综上，本文结合邹博最大熵模
型的PPT和其它相关资料写就，可以看成是课程笔记或学 习
心得，着重推导。有何建议或意见，欢迎随时于本文评论下
指出，thanks。
1 何谓熵？ 从名字上来看，熵给人一种很玄乎，不知道
是啥的感觉。其实，熵的定义 很简单，即用来表示随机变量
的不确定性。之所以给人玄乎的感觉，大概是因为为何要取
这样的 名字，以及怎么用。 熵的概念最早起源于物理学，
用于度量一个热力学系统的无序程度。在信息 论里面，熵是
对不确定性的测量。1.1 熵的引入 事实上，熵的英文原
文为entr opy，最初由德国物理学家鲁道夫·克劳修斯提出，
其表达式为： 它表示一个系系统在不受外 部干扰时，其
内部最稳定的状态。后来一中国学者翻译entropy时，考虑
到entrop y是能量Q跟温度T的商，且跟火有关，便把entropy
形象的翻译成“熵”。 我们知道， 任何粒子的常态都是随
机运动，也就是无序运动，如果让粒子呈现有序化，必须
耗费能量。所以 ，温度（热能）可以被看作有序化的一种
度量，而熵可以看作是无序化的度量。 如果没有外部< br>能量输入，封闭系统趋向越来越混乱（熵越来越大）。比如，
如果房间无人打扫，不可能越来越干 净（有序化），只可能
越来越乱（无序化）。而要让一个系统变得更有序，必须有
外部能量的输 入。 1948年，香农Claude E. Shannon
引入信息（熵），将其定义为离散 随机事件的出现概率。一
个系统越是有序，信息熵就越低；反之，一个系统越是混乱，
信息熵就 越高。所以说，信息熵可以被认为是系统有序化程
度的一个度量。
若无特别指出，下文中所有提到的熵均为信息熵。
1.2 熵的定义 下面分别给出熵、联合熵、条件熵、相对
熵、互信息的定义。 熵：如果一个随机变量X的可能取
值为X = {x1, x2,…, xk}，其概率分布为P(X = xi) = pi（i =
1,2, ..., n），则随机变量X的熵定义为： 把最前面
的负号放到最后，便成了： 上面两个熵的公式，无论用
哪个都行，而且两者等 价，一个意思（这两个公式在下文中
都会用到）。
联合熵：两个随机变量X，Y的联合分布，可以形成联
合熵Joint Entropy，用H(X,Y)表示。
条件熵：在随机变量X发生的前提下，随机变量Y发 生
所新带来的熵定义为Y的条件熵，用H(Y|X)表示，用来衡量
在已知随机变量X的条件下 随机变量Y的不确定性。 且
有此式子成立：H(Y|X) = H(X,Y) – H(X)， 整个式子表示(X,Y)
发生所包含的熵减去X单独发生包含的熵。至于怎么得来的
请看推导： 简单解释下上面的推导过程。整个式子共6
行，其中第二行推到第三行的依据是边缘分布p(x)等于联 合
分布p(x,y)的和；第三行推到第四行的依据是把公因子
logp(x)乘进去，然后把 x,y写在一起；第四行推到第五行的
依据是：因为两个sigma都有p(x,y)，故提取公因子p (x,y)
放到外边，然后把里边的-（log p(x,y) - log p(x)）写成- log
(p(x,y)p(x) ) ；第五行推到第六行的依据是：条件概率的定
义p(x,y) = p(x) * p(y|x)，故p(x,y) p(x) = p(y|x)。 相
对熵：又称互熵，交叉熵，鉴别信息，Kullback熵，
Kullback- Leible散度等。设p(x)、q(x)是X中取值的两个概
率分布，则p对q的相对熵是：
在一定程度上，相对熵可以度量两个随机变量的“距离”，
且有D(p||q) ≠D(q||p)。另外，值得一提的是，D(p||q)是必然
大于等于0的。
互 信息：两个随机变量X，Y的互信息定义为X，Y的
联合分布和各自独立分布乘积的相对熵，用I(X, Y)表示：
且有I(X,Y)=D(P(X,Y) || P(X)P(Y))。下面，咱们来计算下
H(Y)-I(X,Y)的结果，如下： 通过上面的计算过程，我们
发现竟然有H(Y)-I(X,Y) = H(Y|X)。故通过条件熵的定义，有：
H(Y|X) = H(X,Y) - H(X)，而根据互信息定义展开得到H(Y|X)
= H(Y) - I(X,Y)，把前者跟后者结合起来，便有I(X,Y)= H(X)
+ H(Y) - H(X,Y)，此结论被多数文献作为互信息的定义。
2 最大熵 熵是随机变量不确定性的度 量，不确定性越大，
熵值越大；若随机变量退化成定值，熵为0。如果没有外界
干扰，随机变量 总是趋向于无序，在经过足够时间的稳定演
化，它应该能够达到的最大程度的熵。 为了准确 的估
计随机变量的状态，我们一般习惯性最大化熵，其原则是承
认已知事物（知识），且对未知 事物不做任何假设，没有任
何偏见。2.1 无偏原则 下面举个大多数有关最大熵模型
的文章中都喜欢举的一个例子。 一篇文章中出现了“学习”这个词，那这个词是主语、谓语、还是宾语呢？换言之，已
知“学习”可能是动词，也可能是名词， 故“学习”可以被标为主
语、谓语、宾语、定语等等。令x1表示“学习”被标为名词，
x2表示“学习”被标为动词。令y1表示“学习”被标为主语， y2
表示被标为谓语， y3表示宾语， y4表示定语。 且这
些概率值加起来的和必为1，即 ，， 则根据无偏原则，认为
这个分布中取各个值的概率是相等的，故得到： 因为没
有任何的先验知识，所以这种判断是合理的。如果有了一定
的先验知识呢？
即进一步，若已知：“学习”被标为定语的可能性很小，
只有0.05，即，剩下的依然根据无偏原则， 可得： 再进
一步，当“学习”被标作名词x1的时候，它被标作谓语y2的
概率为0. 95，即，此时仍然需要坚持无偏见原则，使得概率
分布尽量平均。但怎么样才能得到尽量无偏见的分布 ？
实践经验和理论计算都告诉我们，在完全无约束状态下，均
匀分布等价于熵最大（有 约束的情况下，不一定是概率相等
的均匀分布。 比如，给定均值和方差，熵最大的分布就变
成了正态分布 ）。 于是，问题便转化为了：计算X和Y
的分布，使得H(Y|X)达到最大值，并且满足下述条件： 因
此，也就引出了最大熵模型的本质，它要解决的问题就是已
知X，计算Y的概率，且尽可能让 Y的概率最大（实践中，
X可能是某单词的上下文信息，Y是该单词翻译成me，I，
us、w e的各自概率），从而根据已有信息，尽可能最准确的
推测未知信息，这就是最大熵模型所要解决的问题 。 转
换成公式，便是要最大化下述式子H(Y|X)： 已知X，计
算Y的最大可能的概率，且满足以下4个约束条件：2.2 最
大熵模型的表示 至此，我们可以写出最大熵模型的一般
表达式了，如下： 其中，P={p | p是X上满足条件的概
率分布} 继续阐述之前，先定义下特征、样本和特征函数。
特征：(x,y)
y：这个特征中需要确定的信息x：这个特征中的上下文信息 样本：关于某个特征(x,y)的样本，特征所描述的语法现象在
标准集合里的分布：(xi,yi )对，其中，yi是y的一个实例，xi
是yi的上下文。
对于一个特征(x0,y0)，定义特征函数： 特征函数关
于经验分布在样本中的期望值是： 其中，。 特征函
数关于模型P(Y|X)与经验分布P-(X)的期望值为： 换言
之，如果能够获取训练数据中的信息，那么上述这两个期望
值相等，即：
现回到最大熵模型的表达式上来。注意到p(x,y) = p(x) *
p(y|x)，但因为p( x)不好求，所以一般用样本中x出现的概率
代替x在总体中的分布概率“p(x)”，从而得到最大熵 模
型的完整表述如下： 其约束条件为： 该问题已
知若干条件，要求若 干变量的值使到目标函数（熵）最大，
其数学本质是最优化问题（Optimization Prob lem），其约束
条件是线性的等式，而目标函数是非线性的，所以该问题属
于非线性规划（线 性约束）(non-linear programming with
linear constr aints)问题，故可通过引入Lagrange函数将原
约束最优化问题转换为无约束的最优化的对 偶问题。2.3 凸
优化中的对偶问题 考虑到机器学习里，不少问题都在围
绕着一个“ 最优化”打转，而最优化中凸优化最为常见，所以
为了过渡自然，这里简单阐述下凸优化中的对偶问题。
一般优化问题可以表示为下述式子： 其中，subject to
导出的是约束条件，f(x)表示不等式约束，h(x)表示等式约束。
然后可通过引入拉格朗日乘子λ和v，建立拉格朗日函数，
如下： 对固定的x，Lagrange函数L(x,λ,v)为关于λ和
v的仿射函数。2.4 对偶问题的极大化 针对原问题，首
先引入拉格朗日乘子λ0,λ1,λ2, ..., λi，定义拉格朗日函数，
转换为对偶问题求其极大化： 然后求偏导,： 注：上
面这里是对P(y|x)求偏导，即只把P(y|x)当做未知数，其他
都是常数。因此，求偏导时， 只有跟P(y0|x0)相等的那个
才会起作用，其他的(x,y)都不是关于P(y0|x0)的系< br>数，是常数项，而常数项一律被“偏导掉”了。 令上述的
偏导结果等于0，解得： 进一步转换： 其中，Z(x)
称为规范化因子。 由于 = 1，所以有 从而有 现
将求得的最优解P*(y|x)带回之前建立的拉格朗日函数L
得到关于λ的式子： 再回过头来看这个式子： 可
知，最大熵模型模型属于对数线性模型，因为其包含指数函
数，所以几乎不可能有解析解。换言之，即便有了解析解，
仍然需要数值解。那么，能不能找到 另一种逼近？构造函数
f(λ)，求其最大最小值？ 相当于问题转换成了寻找与样
本的 分布最接近的概率分布模型，如何寻找呢？你可能想到
了极大似然估计。2.5 最大熵模型的极大似然估计 极大
似然估计MLE的一般形式表示为： 其中，是对模型进
行估计的概率分布，是实验结果得到的概率分布。 进一
步转换，可得： 对上式两边取对数可得： 因上
述式子最后结果的 第二项是常数项（因为第二项是关于样本
的联合概率和样本自变量的式子，都是定值），所以最终结果为： 至此，我们发现极大似然估计和条件熵的定义式
具有极大的相似性，故可以大胆猜测 它们极有可能殊途同归，
使得它们建立的目标函数也是相同的。 我们来推导下，验
证下这个猜测。 将之前得到的最大熵的解带入MLE，计
算得到： 注：上述式子的最后一步推导中，根据P(x,y) =
P(x) * P(y|x)，和之前得到的结论 = 1 推出。 然后拿这
个通过极大似然估计得到的结果跟 之前得到的对偶问题的
极大化解对比下，发现二者的右端果然具有完全相同的目标
函数。换言之 ，之前最大熵模型的对偶问题的极大化等价于
最大熵模型的极大似然估计。 且根据MLE的正确 性，
可以断定：最大熵的解（无偏的对待不确定性）同时是最符
合样本数据分布的解，进一步证 明了最大熵模型的合理性。
两相对比，熵是表示不确定性的度量，似然表示的是与知识
的吻合程 度，进一步，最大熵模型是对不确定度的无偏分配，
最大似然估计则是对知识的无偏理解。
3 参数求解法：IIS 回顾下之前最大熵模型的解： 其
中 对数似然函数为： 相当于现在的问题转换成：通
过极大似然函数求解最大熵模型的参数，即求上述对数似然
函数参 数λ 的极大值。此时，通常通过迭代算法求解，比如
改进的迭代尺度法IIS、梯度下降法、牛顿法或 拟牛顿法。
这里主要介绍下其中的改进的迭代尺度法IIS。 改进的
迭代尺度法IIS 的核心思想是：假设最大熵模型当前的参数
向量是λ，希望找到一个新的参数向量λ+δ，使得当前模型
的对数似然函数值L增加。重复这一过程，直至找到对数似
然函数的最大值。 下面，咱们来计算下参数λ 变到λ+δ
的过程中，对数似然函数的增加量，用L(λ+δ)-L(λ) 表示，同
时利用不等式：-lnx ≥1-x , x>0，可得到对数似然函数增
加量的下界，如下： 将上述求得的下界结果记为A(δ | λ)，
为了进一步降低这个下界，即缩小A(δ | λ)的值，引入一个变
量： 其中，f 是一个二值函数，故f#(x, y)表示的是所有
特征(x, y)出现的次数，同时然后利用Jason不等式，可得：
我们把上述式子求得的A(δ | λ)的下界记为B(δ | λ)： 相
当于B(δ | λ)是对数似然函数增加量的一个新的下界，可记作：
L(λ+δ)-L(λ) >= B(δ | λ)。 接下来，对B(δ | λ)求偏导，
得： 此时得到的偏导结果只含δ，除δ之外不再含其它
变量，令其为0，可得： 从而求得δ，问题得解。 值
得一提的是，在求解δ的过程中，如果若f#(x,y)=M为常数，
则 否则，用牛顿法解决： 求得了δ，便相当于求得
权值λ，最终将λ 回代到下式中： 即得到最大熵模型的
最优估计。
4 参考文献热力学熵
http:-mo%E7%8 6%B5，信息熵：
http:i%E7%86%B5_(%E4%BF%A1
%E6%81% AF%E8%AE%BA)，百度百科：
http:；熵的社会学意义：
http:；北
京10月机器学习班之邹博的最大熵模型PPT：
http:1qWLSehI；北京10月机器学习 班之
邹博的凸优化PPT：http:1sjHMj2d；《统
计学习方法 李航著》；


2014-10-27 16:28 星期一
阅读(2998)


上一篇：机房收费系统 之 登录BUG （二）
下一篇：c++中string类的源代码