人对事物的认知体现为对可能发生的诸事概率的估计, 信息改变这种估计. 例如最近北京天气多变, 对于明天是否要下雨, 我完全不确定, 所以我会认为明天下雨的概率和不下雨相等, 都是 1/2. 此时我看到天上云越来越多, 我获得了信息, 觉得下雨的可能性更大了. 接着我看了天气预报, 预报说明天有 80% 的概率下雨, 我获得了更多信息. 到了明天, 我发现真的下雨了, 我获得该信息后, 在我眼里下雨的概率变成了 1.
因此可以通过概率分布来定量刻画信息: 我们希望从概率分布中计算出一个表征信息多少的量, 对于一个服从该概率分布的随机变量, 如果我们得知了一个确定的结果, 此时我们就获得了信息, 信息量正是上述从概率分布中计算出的量. 如果这样理解, 这个量刻画的是知道一个随机变量的结果时获得的信息; 反过来, 它也可以理解为当我们只能做出一定的估计时, 相比知道确定的结果我们缺失了多少信息.
从上述直觉可以给出这个量应该满足的一些性质: 可能的结果数量一定, 当我们只能估计所有结果等概率出现时, 我们缺失的信息越多; 作出等概率估计的前提下, 可能的结果数量越多, 我们缺失的信息越多; 对于两个独立事件, 我们总的缺失的信息等于对两个事件各自缺失的信息之和……
可以从直觉的要求出发, 加上一些数学上方便的条件来构造出我们需要的信息量, 也可以考虑如下问题.
考虑一个长度为 $N$ 的字符串, 每个字符都服从概率分布 $\left\lbrace p_i\right\rbrace$, 当 $N$ 很大时, 各个字符出现频率不等于概率分布的那些字符串是几乎不可能出现的. 因此, 我们有很大的把握只考虑
\[\frac{N!}{\prod_i \left(p_i N\right)!}\]个 “标准” 字符串. 再考虑以 0 和 1 构成, 且每个字符 0, 1 出现概率相等的字符串, 此时标准字符串的数量仍由上式表达. 为了方便, 取对数得
\[\log \frac{N!}{\prod_i \left(p_i N\right)!}\approx -N\sum_i p_i \log p_i.\]对数底取 2, 则上述 $(0, 1)$ 字符串长度为 $M$ 时, 其标准字符串数量的对数为 $M$. 当
\[M = -N\sum_i p_i \log p_i\]时, 我们可以在两个字符串间构造一个几乎一对一的映射, 此时可以认为两个字符串所含信息量相等. 我们称一个等概率分布的 0, 1 字符为一个比特, 设 1 比特所含的信息量为 1, 则长度为 $M$ 的 $(0,1)$ 字符串所含信息量为 $M$, 则按 $\left\lbrace p_i\right\rbrace$ 分布的单个字符信息量为
\[H\left(\left\lbrace p_i\right\rbrace\right)=\frac{M}{N}=-\sum_i p_i \log p_i.\]不难验证函数 $H$ 符合前文所述直觉. 我们称 $H$ 为信息熵, 因为其表达式和玻尔兹曼熵一致.
简而言之, 一个长度为 $N$, 每个字符都服从概率分布 $\left\lbrace p_i\right\rbrace$ 的字符串, 其标准字符串个数为 $2^{NH({p_i})}$, 每个标准字符串的概率为 $2^{-NH({p_i})}$.
由上述论证不难得出, $H({p_i})$ 还刻画了将信息用比特表达时所需的最小比特数, 即 $N$ 个服从 ${p_i}$ 分布的字符可以用 $NH({p_i})$ 个比特表达. 此即香农的信源编码定理.
对两个随机变量 $X, Y$, 还可考虑条件熵. 设其满足分布 $P_{X,Y}$, 则条件熵定义为已知 $Y$ 时按 $X$ 的条件概率算出的熵对 $Y$ 作加权平均,
\[H(X\mid Y)=-\sum_y P_Y(y)\sum_x \frac{P_{XY}(x,y)}{P_Y(y)}\log \frac{P_{XY}(x,y)}{P_Y(y)}=H(X,Y)-H(Y).\]直觉上, 条件熵描述了已知 $Y$ 时我们对 $X$ 的不确定程度, 因此一定有
\[H(X,Y)-H(Y)\geq 0,\]当 $X$ 和 $Y$ “完全绑定”, 即对每个 $y$, $P_{XY}(x,y)$ 只对唯一一个 $x$ 非零时, 上式为 0; 当 $X, Y$ 完全无关, 即 $P_{XY}(x,y)=P_X(x)P_Y(y)$ 时, 上式等于 $H(X)$.
不难想象, 当我们知道 $Y$ 时, 我们对 $X$ 的理解总不差于什么都不知道时对 $X$ 的理解, 换句话说, 知道 $Y$ 会降低我们对 $X$ 的不确定程度, 因此
\[I(X;Y)\equiv H(X)+H(Y)-H(X,Y) = H(X) - H(X\mid Y) \geq 0.\]这里 $I(X;Y)$ 称为互信息, 它刻画了 $X$ 和 $Y$ 的关联, 具体来说, 它刻画了 $Y$ 能为我们提供多少有关 $X$ 的信息. 如果 $X, Y$ 完全独立, 则 $Y$ 不能提供有关 $X$ 的任何信息, 前文已论述此时 $H(X\mid Y)=H(X)$, 故互信息为 0. 注意, 互信息对于 $X$ 和 $Y$ 是对称的.
从确定一个随机变量可以提供关于另一个随机变量的多少知识出发, 互信息的对称性并不非常显然. 我们不妨从另一个角度考虑互信息: $P_{XY}$ 和 $P_{X}P_{Y}$ 两个分布的差异. 当然, 刻画两个分布的差异本身就是一个有价值的问题.
考虑一个按 $Q(x)$ 分布的随机变量 $X$, 做 $N$ 次实验, 观察到它按 $P(x)$ 分布的概率为
\[N!\prod_x \frac{Q(x)^{NP(x)}}{\left(NP(x)\right)!}.\]取对数, 得
\[\log N!\prod_x \frac{Q(x)^{NP(x)}}{\left(NP(x)\right)!}\approx -N\sum_xP(x)\left(\log P(x)-\log Q(x)\right)\equiv -NH(P_X\parallel Q_X).\]其中 $H(P_X\parallel Q_X)$ 称为相对熵. 当 $P, Q$ 相等时, 相对熵为 0. 基于这一构造, 我们认为相对熵刻画了两个分布的距离, 尽管它并不对称. 由于 $2^{-NH(P_X\mid Q_X)}$ 表征一个概率, 所以相对熵一定不小于 0.
回到两个随机变量的情况. 当两个随机变量实际上独立分布时, 观察到两个随机变量服从联合概率分布 $P_{XY}$ 的概率由相对熵给出,
\[\begin{aligned} H(P_{XY}\parallel P_XP_Y)&=\sum_{x,y}P_{XY}\left(x,y\right)\log \frac{P_{XY}\left(x,y\right)}{P_X(x)P_Y(y)}\\ &=H(X)+H(Y)-H(X,Y)\\ & = I(X;Y). \end{aligned}\]因此, 互信息刻画了联合分布与独立分布的距离, 即两个变量的关联.
相对熵的这一构造可以用于理解有噪声信道编码定理. 考虑离散无记忆信道, 输入 $X$ 服从概率分布 $P_X$, 信道获得输入后依概率 $P_{Y\mid X}$ 输出 $Y$, 这一条件概率刻画了现实通信中可能发生的错误. 接受者需要通过输出确定输入, 但因为错误的存在, 我们应该以某种方式 “编码” 需要传输的信息. 例如我们需要传输 $k$ 个比特的信息, 这样的 “标准” 信息共有 $K=2^{k}$ 个, 如果直接传输这 $k$ 个字符, 发生错误后我们将无法重构输入信息, 因为一个错误会把一个标准信息变成另一个标准信息. 我们用另外一些长度为 $n>k$ 的字符串来表示这些信息, 则我们要传输的信息位于 $N=2^{nH(X)}$ 个标准信息里一个大小为 $K$ 的子集, 只要这个子集分布得足够 “稀疏”, 错误就只会把要传递的信息拉到子集外面, 此时我们就能发现错误, 如果拉得不够远, 我们就能通过寻找最近的子集中的元素来恢复要传输的信息.
对应于将 $k$ 比特的信息用长度为 $n$ 的字符串表示这一 “编码” 的过程, 通过输出信息推断输入信息称为 “解码”. 对于给定的 $k$, 我们应该取多大的 $n$ 以保证成功解码呢? 假设我们在 $N$ 个标准信息中随机取了 $K$ 个要传递的信息, 称为编码集, 我们构造元素为 $(x^n,y^n)$ 的标准集如下: $x^n$ 属于编码集, $y^n$ 是 $x^n$ 按照 $P_{Y\mid X}$ 的频率处理各字符得到的字符串. 信道输出了一个 $y^n_*$, 我们就去标准集中找对应的 $x^n$: 如果标准集中存在唯一的 $(x^n,y^n_\ast)$, 则解码成功, 如果标准集中不存在或存在多个 $(x^n,y^n_\ast)$, 则失败. 由标准集的构造可知, 当 $n$ 很大时, 几乎不可能不存在 $(x^n,y^n_\ast)$, 因此只需考虑存在多个 $(x^n,y^n_\ast)$ 导致解码失败的概率.
假设真实的输入信息是 $x_\ast$, 它是随机的, 因此编码集中一个任意的 $x^n$ 与 $y^n_\ast$ 没有关联. 但是, 当且仅当 $x^n$ 和 $y^n_\ast$ 中字符的频率服从 $P_XP_{Y\mid X}$ 这一联合分布时, $(x^n,y^n_\ast)$ 在标准集中. 于是, 解码失败的概率等于事实上独立分布的两个变量展示出联合分布行为的概率, 这恰好可以用我们之前讨论过的互信息写出,
\[P(\text{fail})=\sum_{x^n}P\left(x^n,y_*^n\right)=2^{k}2^{-nI(X;Y)},\]注意, 因为 $x^n$ 的随机性, 求和内每一项都相等. 定义码率
\[R = \frac{k}{n},\]则失败的概率为 $2^{-n(I(X;Y)-R)}$. 当 $n$ 很大时, 若 $I(X;Y)-R>0$, 则失败的概率可以任意小. 因此, 信道允许成功解码的码率上限由 $I(X;Y)$ 的上限给出. 注意, $I(X;Y)$ 由 $P_X$ 和 $P_{Y\mid X}$ 决定, 后者已经随信道确定, 而前者是输入信息的性质, 编码时可以优化 $P_X$ 使得容许的码率尽可能高. 出于这些考虑, 我们定义信道的容量为
\[C=\sup_{P_X}I\left(X;Y\right),\]它给出了信道能无错误传输的编码其码率的上限.