信息论 The First Law of Complexodynamics

信息量和熵

信息量

一个事件到底包含多少信息量？

举个例子：

• 太阳从东方升起
• 出门被鸟屎砸了
• 太阳从西方升起

第一件事显然没什么信息量，大家都知道太阳会从东方升起；但第二件事信息量就比较大，因为被鸟屎砸是一件概率很小的事，也不知道该说你幸运还是倒霉；到了第三件事，这信息量直接爆炸了，从来没有人见过太阳从西方升起。

可以看出，概率越低的事件，信息量就越大。

Shannon 定义了信息量：$I(x) = -\log P(x)$

可以看出，祖师爷用了 log 来定义，而 log 有一个很好的性质，就是可加性，如果两个独立事件同时发生，那么信息量可以直接相加：

$$P(x,y)=P(x)P(y)$$ $$$$

熵

我们已经得到了单个事件的信息量，但是我们更常见的是概率分布，那么我们就想知道这个概率分布的平均信息量是多少：

$$H(P) = -\sum_x P(x)\log P(x)$$

恭喜你，发明了熵，熵就是平均的信息量，也就是平均的不确定性。

举个例子，一正一反的公平硬币的熵显然大于两个正面的硬币，因为后者是完全确定的，熵为 0.

Shannon 还证明了，熵就是最优编码的理论极限，你的编码再牛，平均编码长度也不可能低于熵。

交叉熵与 KL 散度

令$P$为真实分布，$Q$为我们近似的分布。

我们定义交叉熵为$H(P,Q)=-\sum P(x)\log Q(x)$，再定义 KL 散度为$D_{KL}(P || Q) = \sum_{x} P(x)\log \frac{P(x)}{Q(x)}$，KL 散度衡量了我们用 Q 去近似 P 时的差异。注意，KL 散度不是距离，不具有对称性，即$D_{KL}(P || Q) \neq D_{KL}(Q || P)$。

交叉熵和 KL 散度间存在关系$H(P,Q) = H(P) + D_{KL}(P||Q)$，可以看到$H(P)$实际上是常量，我们想要尽量用 Q 拟合 P，实际上就是要交叉熵尽量小，也就是让 KL 散度尽量小。

实际上，在 one-hot 分类任务中，交叉熵就是$-\log P_\theta(y|x)$，也就是 Negative Log Likelihood，因此，训练神经网络就是最小化 NLL，即最大似然估计（MLE）。

Kolmogorov Complexity

Kolmogorov complexity（柯尔莫哥洛夫复杂度）用来衡量一个对象的信息量或者复杂度。更直白的解释：设我们有一个字符串对象，那么 Kolmogorov complexity 就为最短的能生成这个字符串的程序的长度。

数学表示

数学表示为：$K(x) = \min \{|p| : U(p) = x\}$

其中：

• $U$为一个通用图灵机
• $p$为一个程序
• $x$为一个字符串对象
• $|p|$为程序的长度，也就是 Kolmogorov complexity
• $U(p)=x$为约束，要求运行程序$p$能生成字符串$x$

例子

举一个例子，假设我们有两个字符串：

1. 010101010101010101
2. 907451298711345978

对于第一个字符串，可以发现很明显的规律，我们的程序可以是「'01' * 9」；而对于第二个字符串，根本找不出规律，我们的程序只能是「'907451298711345978'」。显然，第一个字符串对应的程序更短，而第二个字符串对应的程序很长。

实际上，Kolmogorov complexity 衡量的就是可压缩程度，对于有规律的字符串，其能被很好的压缩，对应的 Kolmogorov complexity 就小；而没有规律的字符串，我们很难去压缩它，所以对应的 Kolmogorov complexity 就大。

一个字符串的$K(x)$，就是其极限压缩率，许多压缩算法都力求接近$K(x)$。如果一个字符串的$K(x) \approx |x|$，那么这个字符串就是算法随机的，无法压缩。

机器学习的本质

回想一下，机器学习的目标，就是找到一个模型，尽可能的生成/解释数据，并且让这个模型尽可能小。

如果我们用 Kolmogorov complexity 去描述机器学习的目标，就是要找到对 model 和 data encoding 的最短描述，即$\min (K(model) + K(data | model))$，这也就是 Minimum Description Length，这说明简单模型 + 小误差是最优的。

所以核心很简单，如果一个模型能用很简单的形式找到数据中的规律，那么这个模型就好。这下你应该可以理解我们为什么需要使用正则化来降低模型复杂度了。

计算 K(x)

我们通过 Kolmogorov complexity 的数学表示和相关例子已经可以理解到其核心思想，现在我们来尝试计算$K(x)$.

开个玩笑，很遗憾，计算$K(x)$是不可能的。理论上我们可以通过枚举找到这个最短程序，但我们不能确定这个枚举过程会一直运行还是会停下，这是个经典的停机问题，其已经被计算机祖师爷图灵证明过是不可能的。

所以，在机器学习中，我们不可能找到最优解，我们只能通过算法来近似。

熵与复杂性

在一个封闭系统中，我们可以发现一个很有趣的现象，熵在从小变大，而复杂性则从小变大再变小。这个现象似乎还没有被很好的解释。

扩展阅读： https://scottaaronson.blog/?p=762