00 What is Information · DennyQi's Log

什么是信息

The real measure of information is not in the symbols we send -- it's in the symbols we could have sent, but did not.

“信息(information)”的含义是什么呢？提到信息，我们会联想到填表时的个人信息表格，联想到计算机中数字的二进制表示。在日常语言中，我们会这样使用“信息”这一词汇：这一句话是信息量很大的；这是一句废话（信息量几乎为0）；……

在自然语言中，并没有对“什么是信息”这一问题的精确回答。“信息”一词和“文字”、“符号”、“句子”、“语言”、“特征”等词语相关联。然而，仔细思考我们会发现，所有关于“信息”的现象都和人与人（主体与主体）之间的通信(communication)有关。信息产生于人与人的交流——一方将自己知道的告知(inform)另一方。一方要将“已知信息”告知另一方时，必须将这种“已知信息”通过某种物理过程作用在接收方身上。这种物理作用可以是呼喊（声波，也就是介质的振动），电磁波等等。更奇妙的是，物理过程本身并不重要，而是那些能够从物理过程中抽象出来的模式(pattern)构成了信息。只要发送方和接收方达成了某一统一意见（称为“协议(protocol)”），发送方就可以把想要发送的内容“编码(encode)”为某一物理模式，接收方可以通过“解码(decode)”把信息从物理模式中提取出来。这样一来，关于“信息”的讨论就可以完全独立于物理过程，而在一个抽象的数学语言中得到描述。

“计算机”恰好就是处理信息的最好工具，它本质上是对一系列存储在内部的0和1的物理信号的处理。这就是为什么，现代的“信息科学”几乎等同于“计算机科学”。对信息科学的研究很多时候可以独立于物理学的研究，这是不同层级学科之间的独立性的一个最显著案例。当然，物理学的发展会促进计算机的存储空间、计算效率、体系结构（单线程还是多线程，传统图灵机还是量子计算机）等，但任何不以物理作为直接出发点的学科基本都可以用信息科学的方法来研究，因为一旦利用信息的数学定义建立起数学模型，余下的就转化为对数学模型本身的研究了。

一个可能出人意料的事实是，“信息”这一概念的精确定义和“概率”紧密联系在一起。信息的“获得”会把我们认知中的不确定性转化为确定的东西，我们会发现这种“把不确定转化为确定”“把未知转化为已知”的过程是信息的本质。信息的本质是这一转化的过程，而不是完成这个转化的符号。我们生活中也会有这样的体验，当预感到即将“获知信息”时我们会感到紧张：当我们等待高考成绩发送到手机短信时，我们会紧张，因为此时我们不知道我们会收到令人满意的高考成绩还是令人沮丧的高考成绩，当手机接收到短信的一瞬间，未知转化为了已知。比如说，我们收到了高考总分是650分。我们可以说，我们收到的信息就是数字“650”吗？事实上重要的不仅是“数字是650”，“数字不是651”、“数字不是700”、“数字不是600”都很重要。在我们收到成绩前，我们脑中可能会有一个关于分数预计的概率分布，但是在收到成绩以后我们得到了样本空间中一个具体的值，不再是一个概率分布了。由此可见，关于“信息”的数学概念应当通过“概率”来定义的。

信息与随机事件

有了以上认知以后，我们可以用数学语言构建“信息”这一概念。

考虑一个最简单的“通信”的场景：A和B分别位于不同的房间内。A会在它的房间进行一次抛均匀硬币的实验。由于B在另一个房间，除非A把实验结果“告知”B，B始终处在“硬币朝上、硬币朝下”这二者的不确定性之间。在实验前，A和B达成协议，用一张只能写0或1的字符串的纸条传递实验结果。如果正面朝上，纸条上写0；如果反面朝上，纸条上写1。通过传递纸条这一过程，A和B就硬币的抛掷结果完成了通信。在此通信期间，纸条上的数字0或1传递了实验结果的信息。在这个实验中，无论如何，我们只需要一个二进制位(bit)就能传递“抛均匀硬币的实验结果”这一信息。

如果场景稍微复杂一些，光靠一个二进制位就不足以完成信息传递了。假设A在房间内抛一个八面体的均匀骰子，那么就有八种可能结果，因此要把信息传递给B，至少需要 $3$ 个二进制位（ $2^3=8$ ）。如果少于3个二进制位，B永远都不可能推断出A的实验结果究竟是什么。

抛硬币只需要 $1$ 个二进制位就足够传递信息，而抛骰子却需要 $3$ 个二进制位。所以我们说，“抛骰子的结果”的信息量要比“抛硬币的结果”的信息量更大。为什么后者必须要用更多的位数呢？因为抛骰子这一随机事件比抛硬币这一随机事件的“不确定性(uncertainty)”更大。抛硬币时，B事先知道结果只有两种，A在通知它结果以后只帮B排除了一种情况；抛骰子时，B事先知道结果可能有8种，A通知它以后立即帮B排除了其余的7种情况。抛骰子这一随机事件的结果的不确定性比抛硬币更大。得知一个不确定性更大的事件的结果意味着得知更多的信息。由此可见，信息量的大小来源于所消除的不确定性的大小。

按照这样的思路，我们很容易把信息量的定义推广到一般情形。对于任何一个随机事件，其结果的可能情况越多，得知其结果时所获得的信息量就越大。假如一个随机事件有 $n$ 种可能的结果，那么描述其结果至少需要 $\log_2 n$ 个二进制位。

熵(Entropy)

然而我们认识到，以上的对信息的描述方式并不精确。按照以上说法，信息似乎只与随机变量的“取值个数”有关，而并不与具体的“分布”有关。比如，如果我们抛的是一个带有倾向性的硬币——正面概率为60%，反面概率为40%。按照以上说法，在得知抛这枚带有倾向性的硬币的结果时，我们所获得的信息量是和抛均匀硬币时相同的。当我们把这种“倾向性”推广到极端，就会立刻意识到不对劲：假如某一硬币正面向上的概率为99.99%，反面向上的概率为0.01%，那么我们在得知其结果的时候会如何反应呢？如果我们得知结果为“正面向上”，我们会觉得这几乎是一句废话，信息量几乎为0；但是如果我们得知结果为“反面向上”，我们会非常惊讶，好像发生了一件非常神奇的事情，换言之这一结果包含很大的信息量。就好像，对于一个常年干旱的地区，如果你告诉那里的居民“明天不会下雨”，居民会觉得你这句话没任何价值；但是如果你说“明天会下雨”，居民就会认为这句话有很大的信息量。

我们应当定义一个关于分布的函数，作为对信息量的数学描述。我们对这一描述会有一些基本的要求：

首先，对于均匀分布，信息量应当等于可能情况的对数。
其次，从上面的例子不难想到，这应当是一个连续的函数——这正是我们用“极端法”论证的基础，既然100%正面向上的硬币的结果毫无信息可言，那么99%正面向上的硬币的结果信息量也不会太大。
最后，信息量还应当满足链式法则：设分布 $\{p_1,\cdots,p_n\}$ 对应的信息量为 $H(p_1,\cdots,p_n)$ ，考虑一个不均匀分布的随机变量 $X$ ， $X=a$ 的概率为 $1/2$ ， $X=b$ 的概率为 $1/3$ ， $X=c$ 的概率为 $1/6$ 。那么， $X$ 的分布为 $\{1/2,1/3,1/6\}$ ，这个分布对应的信息量为 $H(1/2,1/3,1/6)$ ，我们可以这样理解信息量：当我们想要获取 $X$ 的取值时，首先询问是否成立 $X=a$ ，这个问题的答案的信息量为 $H(1/2,1/2)$ ；如果答案为否（这一事件发生的概率为 $1/2$ ），那么我们再次询问是否成立 $X=b$ ，这个问题的答案的信息量为 $H(2/3,1/3)$ 。所以， $H$ 应当满足以下分解性质： $H(1/2,1/3,1/6)=H(1/2,1/2)+1/2H(2/3,1/3)$ 。

综上所述，我们想找的函数 $H(p_1,\cdots,p_n)$ 要满足以下三条基本性质：

$H(1/n,\cdots,1/n)=\log_2 n$ ；
$H$ 是连续函数；
$H(p_1,\cdots,p_{n-1},\alpha p_n,(1-\alpha)p_n)=H(p_1,\cdots,p_{n-1},p_n)+p_nH(\alpha,1-\alpha)$

我们来推导这三条性质的必要条件：对于任何一个离散的分布 $\{p_1,\cdots,p_N\}$ ，如果 $p_i$ 都是有理数，我们总可以设存在整数 $n_1,\cdots,n_N$ 使得 $p_i=\dfrac{n_i}{n_1+\cdots+n_N}$ 。设 $S=n_1+\cdots+n_N$ ，所以分布 $\{p_1,\cdots,p_N\}$ 可以分解为 $S$ 个样本的均匀分布，并且该分解满足性质3。这意味着， $\log_2(S)=H(p_1,\cdots,p_n)+\sum p_i\log_2(n_i)$ 。这就导出了 $H(p_1,\cdots,p_n)=-\sum p_i\log_2(n_i)+\log_2(S)$ $=-\sum p_i\log_2(n_i)+\sum p_i\log_2(S)$ $=-\sum p_i\log_2(\dfrac{n_i}{S})$ $=-\sum p_i\log_2 p_i$ 。

于是，我们找到了这个著名的表达式

H(p_1,\cdots,p_n)=-\sum p_i\log_2 p_i

经检验，它满足我们提出的三个要求。这一结果最早出现在香农(Shannon)在1948年发表的名为A Mathematical Theory of Communication的论文中。文中把这一函数和统计力学中的Boltzmann定理联系起来，把这个函数命名为entropy(熵)。由于这是用于刻画信息量的熵，所以称为信息熵。

因为熵是关于离散概率分布的函数，所以对于任何离散随机变量 $X$ ，我们可以定义随机变量的信息熵。假设 $X$ 概率质量函数为 $p(x)$ ，其中 $p(x)=\Pr[X=x]$ ，则定义 $X$ 的熵为 $H(X)=-\sum\limits_{x\in\mathcal{X}}p(x)\log p(x)$ 。其中 $\mathcal{X}$ 是所有 $p(x)>0$ 的 $x$ 构成的集合。

现在我们来看我们导出的这一表达式的含义。我们可以把熵写成这样的形式： $H(p_1,\cdots,p_n)=\sum p_i \log \dfrac{1}{p_i}$ 。这很容易写作期望的形式： $H(p_1,\cdots,p_n)=\mathbb{E}[\log \dfrac{1}{p_i}]$ 。 $\log \dfrac{1}{p_i}$ 这一项的含义是什么呢？根据之前举的例子，这就可以看作是随机事件的每种结果带给我们的“惊讶程度”：当我们抛一枚99%正面朝上的硬币时，正面朝上带给我们的惊讶程度为 $\log \dfrac{100}{99}$ ，这是一个很接近0的小量，我们对这个结果丝毫不感到惊讶；反面朝上带给我们的惊讶程度为 $\log \dfrac{100}{1}\approx 6.64$ 。最终，整个事件的信息量是各个情况的惊讶程度的期望，也就是我们的平均惊讶程度。尽管 $6.64$ 的惊讶值很高，但只有 $1%$ 的概率会发生。最终，我们的平均惊讶程度为 $0.01\times 6.64+0.99\times 0.01\approx 0.0763$ 。

对于一个随机变量 $X$ ，当其均匀分布时，它就具有最大的熵。只要分布稍不均匀，熵就会降低。我们可以证明这一点：均匀分布时， $H(X)=\log |\mathcal{X}|$ 。而对于 $H(X)=\sum\limits_{x\in \mathcal{X}} p(x)\log \dfrac{1}{p(x)}$ ，我们把它看作在上凸函数 $\log x$ 上分别以 $p(x)$ 的权重选取 $x_i=\dfrac{1}{p(x)}$ ，由Jensen不等式可得 $H(X) \leq \log\left(\sum\limits_{x\in \mathcal{X}}p(x) \cdot \dfrac{1}{p(x)}\right)=\log |\mathcal{X}|$ 。当且仅当 $p(x)=\dfrac{1}{| \mathcal{X}|}$ 时取到等号。由此可见，离散的随机变量的熵始终满足 $0\leq H(X)\leq \log |\mathcal{X}|$ ，均匀分布时取到最大值。

熵是什么

由此可见，如果采用“熵”作为信息量的定义，那么抛掷一个非均匀硬币的结果的信息量是小于 $1$ 的。这个量究竟具有什么含义？答案是，信息熵在渐进意义下恰好对应一个概率分布的结果的最优期望前缀码编码长度。简而言之，当分布个数趋向无穷时，平均意义下用“熵”那么多个二进制位就可以传递该分布对应的信息。

最优编码这一事实其实某种程度上已经体现在表达式 $H(p_1,\cdots,p_n)=\sum p_i\log_2 \dfrac{1}{p_i}$ 中了。任何有生活经验的人都可以接收这样一种编码方式，对常用字用短的符号串编码，对生僻字用长的符号串编码，这样在平均意义上会得到更短的编码。例如，在摩尔斯编码中，最常用的英文字母 $e$ 只用一个点表示，而最少用的字母 $q$ 要用横横点横四个字符表示。可见，在熵的概念被提出之前人们已经从经验中获得了一些关于最优编码的知识了。

熵的提出给出了一个最优编码的一个下界：在平均长度的意义下编码长度最优也不可能低于熵的大小。编码方法是，出现概率为 $p_i$ 的消息用长度为 $\log_2\dfrac{1}{p_i}$ 的二进制串表示。可以证明，一定存在这样一种编码方式，严格的数学证明过程在附录中。