机器学习中的熵、条件熵、相对熵(KL散度)和交叉熵

2019-04-26 本文已影响0人 MaosongRan

1、信息熵 (information entropy)

熵 (entropy) 这一词最初来源于热力学。1948年，克劳德·爱尔伍德·香农将热力学中的熵引入信息论，所以也被称为香农熵 (Shannon entropy)，信息熵 (information entropy)。本文只讨论信息熵。首先，我们先来理解一下信息这个概念。信息是一个很抽象的概念，百度百科将它定义为：指音讯、消息、通讯系统传输和处理的对象，泛指人类社会传播的一切内容。那信息可以被量化么？可以的！香农提出的“信息熵”概念解决了这一问题。

一条信息的信息量大小和它的不确定性有直接的关系。我们需要搞清楚一件非常非常不确定的事，或者是我们一无所知的事，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，我们就不需要太多的信息就能把它搞清楚。所以，从这个角度，我们可以认为，信息量的度量就等于不确定性的多少。比如，有人说广东下雪了。对于这句话，我们是十分不确定的。因为广东几十年来下雪的次数寥寥无几。为了搞清楚，我们就要去看天气预报，新闻，询问在广东的朋友，而这就需要大量的信息，信息熵很高。再比如，中国男足进军2022年卡塔尔世界杯决赛圈。对于这句话，因为确定性很高，几乎不需要引入信息，信息熵很低。

考虑一个离散的随机变量 $x$ ，由上面两个例子可知，信息的量度应该依赖于概率分布 $p(x)$ ，因此我们想要寻找一个函数 $I(x)$ ，它是概率 $p(x)$ 的单调函数，表达了信息的内容。怎么寻找呢？如果我们有两个不相关的事件 $x$ 和 $y$ ，那么观察两个事件同时发生时获得的信息量应该等于观察到事件各自发生时获得的信息之和，即：
$I(x,y)=I(x)+I(y)$

因为两个事件是独立不相关的，因此 $p(x,y)=p(x)p(y)$ 。根据这两个关系，很容易看出 $I(x)$ 一定与 $p(x)$ 的对数有关 (因为对数的运算法则是 $log_a(mn)=log_am+log_an$ )。因此，我们有

$I(x)=−\log_p(x)$

其中负号是用来保证信息量是正数或者零。而 $log$ 函数基的选择是任意的（信息论中基常常选择为2，因此信息的单位为比特bits；而机器学习中基常常选择为自然常数，因此单位常常被称为奈特nats）。 $I(x)$ 也被称为随机变量 x 的自信息 (self-information)，描述的是随机变量的某个事件发生所带来的信息量。图像如图：

entropy_01.png

最后，我们正式引出信息熵。现在假设一个发送者想传送一个随机变量的值给接收者。那么在这个过程中，他们传输的平均信息量可以通过求 $I(x)=−logp(x)$ 关于概率分布 $p(x)$ 的期望得到，即：

$H(X)=−∑xp(x)logp(x)=−∑i=1np(xi)logp(xi)$

$H(X)$ 就被称为随机变量 $x$ 的熵,它是表示随机变量不确定的度量，是对所有可能发生的事件产生的信息量的期望。

从公式可得，随机变量的取值个数越多，状态数也就越多，信息熵就越大，混乱程度就越大。当随机分布为均匀分布时，熵最大，且 $0≤H(X)≤logn$ 。稍后证明。将一维随机变量分布推广到多维随机变量分布，则其联合熵 (Joint entropy) 为：

$H(X,Y)=−∑x,yp(x,y)logp(x,y)=−∑i=1n∑j=1mp(xi,yi)logp(xi,yi)$

注意点：1、熵只依赖于随机变量的分布,与随机变量取值无关，所以也可以将 $X$ 的熵记作 $H(p)$ 。2、令 $0log0=0$ (因为某个取值概率可能为0)。

那么这些定义有着什么样的性质呢？考虑一个随机变量 $x$ 。这个随机变量有4种可能的状态，每个状态都是等可能的。为了把 x 的值传给接收者，我们需要传输2比特的消息。 $H(X)=−4×14log214=2 bits$

现在考虑一个具有4种可能的状态 {a,b,c,d} 的随机变量，每个状态各自的概率为 (12,14,18,18)

这种情形下的熵为：

$H(X)=−12log212−14log214−18log218−18log218=1.75 bits$

我们可以看到，非均匀分布比均匀分布的熵要小。现在让我们考虑如何把变量状态的类别传递给接收者。与之前一样，我们可以使用一个2比特的数字来完成这件事情。然而，我们可以利用非均匀分布这个特点，使用更短的编码来描述更可能的事件，使用更长的编码来描述不太可能的事件(这点和Huffman编码的原理一样，不知道Huffman树是不是根据熵的原理发明出来的）。我们希望这样做能够得到一个更短的平均编码长度。我们可以使用下面的编码串（哈夫曼编码）：0、10、110、111来表示状态 {a,b,c,d}。传输的编码的平均长度就是：

$average code length = 12×1+14×2+2×18×3=1.75 bits$

这个值与上方的随机变量的熵相等。熵和最短编码长度的这种关系是一种普遍的情形。

Shannon 编码定理表明熵是传输一个随机变量状态值所需的比特位下界（最短平均编码长度）。因此，信息熵可以应用在数据压缩方面。这里这篇文章讲的很详细了，我就不赘述了。

证明 $0≤H(X)≤logn$

利用拉格朗日乘子法证明：

因为 $p(1)+p(2)+⋯+p(n)=1$

所以有

目标函数： $f(p(1),p(2),…,p(n))=−(p(1)logp(1)+p(2)logp(2)+⋯+p(n)logp(n))$

约束条件： $g(p(1),p(2),…,p(n),λ)=p(1)+p(2)+⋯+p(n)−1=0$

1、定义拉格朗日函数：

$L(p(1),p(2),…,p(n),λ)=−(p(1)logp(1)+p(2)logp(2)+⋯+p(n)logp(n))+λ(p(1)+p(2)+⋯+p(n)−1)$

2、 $L(p(1),p(2),…,p(n),λ)$ 分别对 $p(1),p(2),p(n),λ$ 求偏导数，令偏导数为 0：

$λ−log(e⋅p(1))=0$

$λ−log(e⋅p(2))=0$

$……$

$λ−log(e⋅p(n))=0$

$p(1)+p(2)+⋯+p(n)−1=0$

3、求出 $p(1),p(2),…,p(n)$ 的值：

解方程得， $p(1)=p(2)=⋯=p(n)=1n$

代入 $f(p(1),p(2),…,p(n))$ 中得到目标函数的极值为 $f(1n,1n,…,1n)=−(1nlog1n+1nlog1n+⋯+1nlog1n)=−log(1n)=logn$

由此可证 logn 为最大值。

个人感觉上述证明不是很严谨的拉格朗日推导，见另一篇文章

2、条件熵 (Conditional entropy)

条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性。条件熵 $H(Y|X)$ 定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望：

entropy_03.png

条件熵 $H(Y|X)$ 相当于联合熵 $H(X,Y)$ 减去单独的熵 $H(X)$ ，即

$H(Y|X)=H(X,Y)−H(X)$ ，证明如下：

entropy_04.png

举个例子，比如环境温度是低还是高，和我穿短袖还是外套这两个事件可以组成联合概率分布 $H(X,Y)$ ，因为两个事件加起来的信息量肯定是大于单一事件的信息量的。假设 $H(X)$ 对应着今天环境温度的信息量，由于今天环境温度和今天我穿什么衣服这两个事件并不是独立分布的，所以在已知今天环境温度的情况下，我穿什么衣服的信息量或者说不确定性是被减少了。当已知 $H(X)$ 这个信息量的时候， $H(X,Y)$ 剩下的信息量就是条件熵：

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

因此，可以这样理解，描述 $X$ 和 $Y$ 所需的信息是描述 $X$ 自己所需的信息,加上给定 $X$ 的条件下具体化 $Y$ 所需的额外信息。关于条件熵的例子可以看这篇文章，讲得很详细。https://zhuanlan.zhihu.com/p/26551798

3、相对熵 (Relative entropy)，也称KL散度 (Kullback–Leibler divergence)

设 $p(x)、q(x)$ 是离散随机变量 $X$ 中取值的两个概率分布，则 $p$ 对 $q$ 的相对熵是：

$DKL(p||q)=\sum_xp(x)log\frac{p(x)}{q(x)}=E_{p(x)}log\frac{p(x)}{q(x)}$

性质：

1、如果 $p(x)$ 和 $q(x)$ 两个分布相同，那么相对熵等于0

2、 $DKL(p||q)≠DKL(q||p)$ ，相对熵具有不对称性。大家可以举个简单例子算一下。

3、 $DKL(p||q)≥0$ 证明如下（利用Jensen不等式https://en.wikipedia.org/wiki/Jensen%27s_inequality):

entropy_05.png

因为：

$\sum_xp(x)=1$

所以：

$DKL(p||q)≥0$

总结：相对熵可以用来衡量两个概率分布之间的差异，上面公式的意义就是求 $p$ 与 $q$ 之间的对数差在 $p$ 上的期望值。

4、交叉熵 (Cross entropy)

现在有关于样本集的两个概率分布 $p(x)$ 和 $q(x)$ ，其中 $p(x)$ 为真实分布， $q(x)$ 非真实分布。如果用真实分布 $p(x)$ 来衡量识别别一个样本所需要编码长度的期望（平均编码长度）为:

$H(p)=\sum_xp(x)log\frac{1}{p(x)}=-\sum_xp(x)log{p(x)}$

如果使用非真实分布 $q(x)$ 来表示来自真实分布 $p(x)$ 的平均编码长度，则是：

$H(p)=\sum_xp(x)log\frac{1}{q(x)}=-\sum_xp(x)log{q(x)}$ 。（因为用 $q(x)$ 来编码的样本来自于分布 $q(x)$ ，所以 $H(p,q)$ 中的概率是 $p(x)$ ）。此时就将 $H(p,q)$ 称之为交叉熵。举个例子。考虑一个随机变量 $x$ ，真实分布 $p(x)=(12,14,18,18)$ ，非真实分布 $q(x)=(14,14,14,14)$ ，则 $H(p)=1.75 bits$ （最短平均码长），交叉熵 $H(p,q)=12log24+14log24+18log24+18log24=2 bits$ 。由此可以看出根据非真实分布 $q(x)$ 得到的平均码长大于根据真实分布 $p(x)$ 得到的平均码长。

我们再化简一下相对熵的公式。
$DKL(p||q)=\sum_xp(x)log \frac{p(x)}{q(x)}=\sum_xp(x)logp(x)−\sum_x p(x)logq(x)$

有没有发现什么？

熵的公式 $H(p)=−\sum_xp(x)logp(x)$

交叉熵的公式 $H(p,q)=\sum_xp(x)log\frac{1}{q(x)}=−\sum_xp(x)logq(x)$

所以有：

$DKL(p||q)=H(p,q)−H(p)$ （当用非真实分布 $q(x)$ 得到的平均码长比真实分布 p(x) 得到的平均码长多出的比特数就是相对熵）

又因为 $DKL(p||q)≥0$

所以 $H(p,q)≥H(p)$ （当 $p(x)=q(x)$ 时取等号，此时交叉熵等于信息熵）

并且当 $H(p)$ 为常量时（注：在机器学习中，训练数据分布是固定的），最小化相对熵 $DKL(p||q)$ 等价于最小化交叉熵 $H(p,q)$ 也等价于最大化似然估计（具体参考Deep Learning 5.5）。

在机器学习中，我们希望在训练数据上模型学到的分布 $P(model)$ 和真实数据的分布 $P(real)$ 越接近越好，所以我们可以使其相对熵最小。但是我们没有真实数据的分布，所以只能希望模型学到的分布 $P(model)$ 和训练数据的分布 $P(train)$ 尽量相同。假设训练数据是从总体中独立同分布采样的，那么我们可以通过最小化训练数据的经验误差来降低模型的泛化误差。即：

希望学到的模型的分布和真实分布一致， $P(model)≃P(real)$
但是真实分布不可知，假设训练数据是从真实数据中独立同分布采样的， $P(train)≃P(real)$
因此，我们希望学到的模型分布至少和训练数据的分布一致， $P(train)≃P(model)$
根据之前的描述，最小化训练数据上的分布 $P(train)$ 与最小化模型分布 $P(model)$ 的差异等价于最小化相对熵，即 $DKL(P(train)||P(model))$ 。此时， $P(train)$ 就是 $DKL(p||q)$ 中的 $p$ ，即真实分布， $P(model)$ 就是 $q$ 。又因为训练数据的分布 $p$ 是给定的，所以求 $DKL(p||q)$ 等价于求 $H(p,q)$ 。得证，交叉熵可以用来计算学习模型分布与训练分布之间的差异。交叉熵广泛用于逻辑回归的Sigmoid和Softmax函数中作为损失函数使用。这篇文章先不说了。

5、总结

信息熵是衡量随机变量分布的混乱程度，是随机分布各事件发生的信息量的期望值，随机变量的取值个数越多，状态数也就越多，信息熵就越大，混乱程度就越大。当随机分布为均匀分布时，熵最大；信息熵推广到多维领域，则可得到联合信息熵；条件熵表示的是在 X 给定条件下，Y 的条件概率分布的熵对 X的期望。
相对熵可以用来衡量两个概率分布之间的差异。
交叉熵可以来衡量在给定的真实分布下，使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小。

或者：

信息熵是传输一个随机变量状态值所需的比特位下界（最短平均编码长度）。
相对熵是指用 q 来表示分布 p 额外需要的编码长度。
交叉熵是指用分布 q 来表示本来表示分布 p 的平均编码长度。

6、参考

1、吴军《数学之美》

2、李航《统计学习方法》

3、马春鹏《模式识别与机器学习》

3、如何通俗的解释交叉熵与相对熵

4、为什么交叉熵（cross-entropy）可以用于计算代价？

5、交叉熵的百度百科解释

6、信息熵到底是什么