机器学习笔记之三： 熵

时间：2021-12-04 19:56:56

熵的推导

已知随机变量 X 的概率分布 P(X) ，我们对事件 X=xi(i=0,1,...,N) 进行编码，编码要求符合前缀编码规则，（即任何一个编码都不能是另一个有效编码的前缀，例如已有编码10，则编码100,101,1011，等都不是可用的编码）。

在这种编码规则下，记 X=xi 编码的长度为 L(xi) ，则它的代价（它所占用的编码空间的比例）记为 C(xi)=12L(xi) 。例如编码10，它的长度为2，任何以10开头的编码都被它占用，10开头的编码占整个编码空间的比例为 1/22=1/4 。

编码长度 Len(X) 也是一个随机变量，它的期望：

E[L(X)]=∑i=0NP(xi)L(xi)(1)

现在我们希望编码长度的期望最小，约束条件是代价总和为1：
∑i=0NC(xi)=∑i=0N12L(xi)=1(2)

这是一个有约束条件的最优化问题，可以用拉格朗日乘子法。构建拉格朗日函数
L(L(xi),λ)=∑i=0NP(xi)L(xi)−λ(∑i=0N12L(xi)−1)(3)

为简化我们用 C(xi) 表示 L(xi) ，即 L(xi)=−log2C(xi) ，则拉格朗日函数变为：

L(C(xi),λ)=∑i=0N−P(xi)log2C(xi)−λ(∑i=0NC(xi)−1)(4)

拉格朗日函数取极值条件：
∂L∂C(xi)=−1ln2P(xi)C(xi)+λ=0

⟹P(xi)C(xi)=λln2

又有：

∑i=0NC(xi)=1

∑i=0NP(xi)=1

最终有:
P(xi)C(xi)=1

所以，当事件 X=xi 的编码长度对应得代价与其发生的概率相等时，编码长度期望值最小。最小的编码长度为：
min(E[L])=∑i=0N−P(xi)log2P(xi)(5)

举个例子， Bob只能说4个单词”dog”, “cat”, “fish”, “bird”，概率分布为
机器学习笔记之三： 熵
现在我们需要跟Bob交流，必须先进行编码，如果采用固定长度的编码:
机器学习笔记之三： 熵
编码长度期望为 1/2∗2+1/4∗2+1/8∗2+1/8∗2=2bits

而采用最优编码，即概率为 P(xi) 的单词编码长度为 −log2P(xi) :
机器学习笔记之三： 熵
编码长度期望为 1/2∗1+1/4∗2+1/8∗3+1/8∗3=1.75bits

编码长度期望的最小值，被称为entropy(熵），它是由随机变量的分布决定的，我们称分布 p 的熵为 H(p) :

H(p)=∑xp(x)log21p(x)(6) 

import math

def H(p_seq):
    return sum(-p*math.log(p) for p in p_seq if p>0)/math.log(2)
H([0.25,0.25,0.25,0.25])
2.0

熵的理解

先看几个例子：

x1 x2 x3 x4 entropy
分布1 1 0 0 0
分布2 0.8 0.2 0 0
分布3 0.5 0.5 0 0
分布4 0 0 0.2 0.8
分布5 0.25 0.25 0.25 0.25

分布1只能取x1一个值，它的熵为0。分布2和分布3能取两个值，但分布3更平均，它的熵更大。分布2和分布4是两个不同的分布，但是分布的集中程度相同，他们的熵也相同。分布3和分布5都是均匀分布，但分布5取值范围更广，它的熵更大。

从以上例子可以看出，分布约集中，其熵越小。从这个意义上来说，熵代表着不确定性，不确定度越小，熵越小。熵的取值范围：

0≤H(p)≤log2N

（对于连续变量的微分熵，其值可以小于0。）

为了加深对熵这个概念的理解，着重看一下 熵的定义式（6）。它是一个和式，和式的每一项是两个部分的乘积，第一部分是概率函数 p(x) （在国外教科书中也称为概率质量函数），第二部分是一个随机变量的函数，也是一个随机变量，其含义是最优编码下的编码长度。所以熵是最优编码下消息编码长度的期望。对于连续变量，其定义是：

h(p)=∫+∞−∞p(x)1logp(x)dx(7)

h(p) 称为分布 p 的 微分熵(differential entropy)。其中 p(x) 为概率密度函数。(为简化，这里及后面的部分用 log 代表 log2 )

下面来看一个更一般的式子:

∫+∞−∞p(x)g(x)dx(8)

其中 p(x) 满足:

  • p(x)≥0

  • ∫+∞−∞p(x)dx=1

以及它的离散形式

∑xp(x)g(x)(9)

其中 p(x) 满足:

  • p(x)≥0

  • ∑xp(x)=1

这个式子很重要，将会在很多地方看到它的各种各样的形式，举例说明：

（1） 当 g(x)=1logp(x) 时， 它就是熵

（2） 当 g(x)=x 时， 它就是期望

（3） 当 g(x)=(x−E[X])2 时， 它就是方差

（4）物理学的例子，质心= ∫ρ(x)/Mxdx ， 这里 g(x)=x , p(x)=ρ(x)/M , ρ(x) 是密度

（5）另一个物理学的例子:

转动惯量总质量=JM=∫dmMr2=∭ρ(x,y,z)Mr(x,y,z)2dxdydz

这里 ρ 表示密度， r 表示到转轴的距离。

（6）机器学习的例子，在EM算法的E-step中要用到以下的变换：

p(x)=∑zp(x,z)=∑zQ(z)p(x,z)Q(z)=E[p(x,z)Q(z)]

这里， Q(z) 是隐含变量 z 的一个分布。

（7）当 g(x)=1logq(x) 时， 它就是下面要讲到的交叉熵(cross entropy)

交叉熵(cross entropy)

现在如果有另一个分布 q(x) :
机器学习笔记之三： 熵

在使用分布 p 的最优编码的情况下，分布 q 的编码长度期望为: 1/8∗1+1/2∗2+1/4∗3+1/8∗3=2.25

这个长度称为 q 相对于 p 的交叉熵(cross entropy)，记为:

Hp(q)=∑xq(x)log1p(x)(10)

这里强调q相对于p是因为交叉熵不是对称的，即 Hp(q)≠Hq(p) 

def cross_entropy(p_seq, q_seq):
    return sum(-q* math.log(p) for (p,q) in zip(p_seq,q_seq) if p>0)/math.log(2)

p_seq=[1/2,1/4,1/8,1/8]
q_seq=[1/8,1/2,1/4,1/8]
print('cross entropy of q with respect to p:',cross_entropy(p_seq,q_seq))
print('cross entropy of p with respect to q:',cross_entropy(q_seq,p_seq))

cross entropy of q with respect to p: 2.25
cross entropy of p with respect to q: 2.375

交叉熵本身并没有多大的意义，有意义的是交叉熵与熵的差，称为Kullback–Leibler距离（简称KL距离）：

Dp(q)=Hp(q)−H(q)(11)

它的意义是分布q采用另一个分布p的最优编码与采用自身的最优编码比较，消息编码长度的差。它表征的是两个分布的差异。当两个分布相同时，KL距离为0，当两个分布的差异越大，KL距离越大。KL距离在机器学习中经常被当做损失函数来使用。

多变量的熵

先看一个例子：
机器学习笔记之三： 熵

X与Y的联合熵：

H(X,Y)=∑x,yp(x,y)log1p(x,y)(12)

以上图为例把X，Y的组合看成一个随机变量，则它有四种值：raining & t-shirt, raning & coat, sunny & t-shirt, sunny & coat, 其概率分别为6%，19%， 56%， 19%，故 H(X,Y)=0.06∗log(1/0.06)+0.19∗log(1/0.19)+0.56∗log(1/0.56)+0.19∗log(1/0.19)=1.62bits 

H([0.06,0.19,0.19,0.56])
1.6224272282706345

Y给定时X的条件熵：

H(X|Y)≜∑x,yp(x,y)log1p(x|y)(13)

注意 (13)式与（12）式的区别：

H(X|Y)≠∑x,yp(x|y)log1p(x|y)

与 H(X,Y) 是直接从熵的定义得出的不同， H(X|Y) 是定义式，这是因为 X|Y 并不是随机变量，随机变量的值域必须是基本事件的集合， X|Y 不满足这个条件（在概率论的教科书中，也没有“条件事件”这一说法，只有“条件概率”，而且“条件概率”也是一个定义式）。

还可以从另一个角度看条件熵，X|Y=raining 和 X|Y=sunny 是随机变量，它们的熵可以算出来，然后对这两个熵求期望，得到：

H(X|Y)=p(x|y=raining)∗H(X|Y=raining)+p(x|y=sunny)∗H(X|Y=sunny)

推导过程如下：

H(X|Y)=∑x,yp(x,y)log1p(x|y)=∑x,yp(y)p(x|y)log1p(x|y)=∑yp(y)∑xp(x|y)log1p(x|y)

把（13）式条件熵与交叉熵对比，可以看出条件熵是联合概率 p(x,y) 相对于条件概率 p(x|y) 的交叉熵。

X_prob=[0.62,0.38] # t-shirt, coat
Y_prob=[0.25,0.75] # raning, sunny
joint_prob = [0.06,0.19,0.56,0.19] 
cond_prob_x_y = [0.25,0.75,0.75,0.25]
cond_prob_y_x = [0.08,0.5,0.92,0.5]
print('H(X) =',H(X_prob))
print('H(Y) =',H(Y_prob))
print('H(X,Y) =', H(joint_prob))
print('H(X|Y) =',cross_entropy(cond_prob_x_y, joint_prob))
print('H(Y|X) =',cross_entropy(cond_prob_y_x, joint_prob))
H(X) = 0.9580420222262997
H(Y) = 0.8112781244591328
H(X,Y) = 1.6224272282706347
H(X|Y) = 0.8112781244591328
H(Y|X) = 0.6659961422684021

条件熵和联合熵存在以下关系：

H(X,Y)=H(X|Y)+H(Y)

H(X,Y)=H(Y|X)+H(X)

推导过程如下：
H(X|Y)+H(Y)=∑x,yp(x,y)log1p(x|y)+∑yp(y)log1p(y)

=∑x,yp(x,y)log1p(x|y)+∑y∑xp(x,y)log1p(y)

=∑x,yp(x,y)(log1p(x|y)+log1p(y))

=∑x,yp(x,y)(log1p(x|y)p(y))

=∑x,yp(x,y)log1p(x,y)

=H(X,Y)

上面等式的意义是X,Y联合的信息等于Y中的信息加上X中除去Y的信息。

多变量熵的一个重要概念是交互信息（mutual information）,它被定义为：

I(X,Y)=H(X)+H(Y)−H(X,Y)

=∑x,yp(x,y)(log1p(x)+log1p(y)−log1p(x,y))

=∑x,yp(x,y)logp(x,y)p(x)p(y)(14)

交互信息表示两个随机变量X，Y之间共享的信息，当X,Y相互独立时，交互信息为0， 当X,Y一一对应时，交互信息最大。
交互信息还可以表示为：

I(X,Y)=H(X)−H(X|Y)=H(Y)−H(Y|X)

另一个概念是变动信息(variation information),它被定义为：

V(X,Y)=H(X,Y)−I(X,Y)

下面的图有助于理解这几个概念：
机器学习笔记之三： 熵

把式（13）KL距离定义式变换一下：

Dp(q)=Hp(q)−H(q)=∑xq(x)log1p(x)−∑xq(x)log1q(x)

=∑xq(x)logq(x)p(x)

上式的意义是p的最优编码和q的最优编码在编码同一分布q的消息时编码长度的差。与式（14）对比可以看出，交互信息表示与假设X,Y相互独立( p(x)p(y) )相比，了解X,Y之间的相互关系 (p(x,y)) 之后，编码长度可以缩短的量。

交互信息在神经网络中有很多应用，如交互信息最大化原则（Infomax），参看Simon Haykin 《神经网络与机器学习》。

参考文献

[1] colah’s blog Visual Information Theory.

[2] Simon Haykin 《神经网络与机器学习》

标签：

相关文章