信息论

创建时间 2021-09-22

更新时间 2021-09-29

分类

读书笔记

标签

编码信息论

一些定义

信息：可以降低不确定性的东西
信源：信息的发送方
信宿：信息的接收方
信道：信息从发送方到接收方的传输途径

基础问题和概念

信息论解答了通信理论中的两个基本问题：

临界数据压缩的值 / 熵 $H$
临界通信传输速率 / 信道容量 $C$

奥卡姆剃刀原则：

如非必要，勿增实体
最简约的解释最佳

科尔莫戈罗夫复杂度：一组数据串的复杂度可以定义为计算该数据串所需最短二进制程序的长度。

自信息 - 随机事件的概率

定义：考虑可能输出为 $x_i, i=1, 2, \cdots, n$ 的离散随机变量 $X$ 。则事件 $X=x_i$ 的 自信息 定义为

$I(x_i) = \log\left[{1 \over P(x_i)}\right] = -\log P(x_i)$

注意到大概率事件没有小概率事件携带的信息多，对于 $P(x_i) = 1$ 的事件，有 $I(x_i) = 0$ ，因为小概率事件意味着高度的不确定性，反之亦然；具有高度不确定性的随机变量带有更多的信息。我们在本章中将一直用不确定性的信息量的这种相关性作自然解释。

$I(x_i)$ 的单位取决于取对数的底数，通常取 $2$ 或者 $e$ 。当以 $2$ 为底数时，单位为 比特(bit)，当以 $e$ 为底数时，单位为 奈特(nat)；由于 $0 \leqslant P(x_i) \leqslant 1$ ，故 $I(x_i) \geqslant 0$ ，即自信息是非负的；

自信息描述了某个随机事件发生带来的信息量，或者说准确回答该不确定的问题需要的信息量；与该随机事件的概率一一对应，对于可以一一对应的两个对象，也就是两个对象形成双射，我觉得 可以认为是同一个东西，这样就可以节约信息量。

确定的问题无需回答，故不需要信息，信息量为 $0$

例：假如有一个掷硬币的二元信源：若正面 $H$ 出现则输出 $1$ ，若反面 $T$ 出现则输出 $0$ ，对于该信源，有 $\displaystyle P(1) = P(0) = {1 \over 2}$ 。来自该信源的每一个输出所含的信息量为：

$\begin{aligned} I(x_i) =& -\log_2 P(x_i) \\ =& -\log_2 P(0.5) = 1 (bit)\\ \end{aligned}$

假定二元信源连续输出是统计独立的，即信源是 无记忆的

例：假如一个 $m$ 比特的数组，则共有 $2^m$ 个可能的 $m$ 比特组，每一个都等可能地具有概率 $2^{-m}$ ，一个 $m$ 比特组的自信息为

$\begin{aligned} I(x_i) =& -\log_2 P(x_i) \\ =& -\log_2 2^{-m} = m (bit)\\ \end{aligned}$

当信源的一些输出被看做一个组的时候，这种信息的对数度量具有所期望的 可加性

联合自信息 - 联合概率的推广

定义：随机变量 $X, Y$ ，它们的联合概率密度函数为 $p(x, y)$ ，则关于 $X, Y$ 的联合自信息为：

$I(X,Y) = -\log p(x, y)$

当 $X$ 与 $Y$ 相互独立时， $p(X, Y) = p(X)p(Y)$ ，有 $I(X, Y) = I(X) + I(Y)$

条件自信息 - 条件概率的推广

定义：随机变量 $X, Y$ ，它们的联合概率密度函数为 $p(x, y)$ ，其边际概率密度函数分别是 $p(x)$ 和 $p(y)$ ，在给定 $Y$ 的条件下，事件 $X$ 的条件自信息为：

$I(X|Y) = - \log p(X|Y)$

互信息 - 两事件的关联信息

定义：随机事件 $x, y$ 之间的 互信息 $I(x; y)$ 为

$I(x;y) = \log \left[{P(x | y) \over P(x)}\right]$

$\begin{aligned} & {P(x|y) \over P(x)}\\ \xlongequal{分子分母同乘以 P(y)}& {P(x|y)P(y) \over P(x)P(y)}\\ \xlongequal{概率乘法公式}& {P(x, y) \over P(x)P(y)}\\ \xlongequal{条件概率公式}& {P(y | x) \over P(y)}\\ \end{aligned}$

因此

$\begin{aligned} I(x;y) =& \log \left[{P(x | y) \over P(x)}\right] \\ =& \log \left[ P(y | x) \over P(y) \right] \\ =& I(y;x) \end{aligned}$

对 $I(x;y) = I(y;x)$ 的自然解释如下：事件 $Y = y$ 的出现所提供的关于 $X = x$ 的信息完全等同于事件 $X = x$ 出现提供关于 $Y = y$ 的信息。考虑文氏图，换句话说，两件事交叉的部分是唯一的，

熵 - 概率分布带来的信息

熵是某个分布不确定性的度量

定义：随机变量 $X$ 的 平均自信息 为：

$\begin{aligned} H(X) =& \sum_{x \in X} P(x)I(x) \\ =& - \sum_{x \in X} P(x) \log P(x) \end{aligned}$

其中， $X$ 代表信源可能输出的字母符号， $H(X)$ 代表每个信源字母的平均信息；在此情况下，我们称 $H(X)$ 为 熵(entropy)；

$X$ 的熵可以表示为 $\displaystyle\log\left[{1 \over P(X)}\right]$ 的数学期望值。

术语熵取则统计力学，在该学科中它用来表示一个系统的无序程度，某种意义上二者是等价的；

熵实际上是随机变量 $X$ 的分布的泛函数，并不依赖于 $X$ 的实际取值，而仅仅依赖于分布的概率；

引理： $H(X) \geqslant 0$

证明：

由 $0 \leqslant p(x) \leqslant 1$ ，知 $- \log P(x) \geqslant 0$

故 $\displaystyle H(x) = - \sum_{x \in X} P(x) \log P(x) \geqslant 0$

联合熵 - 二维概率分布带来的信息

定义：一对联合概率分布是 $P(x, y)$ 的离散随机变量 $(X, Y)$ 的 联合熵 定义为：

$H(X;Y) = - \sum_{x \in X} \sum_{y \in Y} P(x, y) \log P(x, y)$

条件熵 - 给定条件后剩余的不确定性

定义：若 $(X, Y) \sim P(x, y)$ ，则 平均条件自信息 又称作 条件熵，定义为：

$\begin{aligned} H(X|Y) =& \sum_{x \in X} P(X) H(Y|X=x) \\ =& - \sum_{x \in X} P(X) \sum_{y \in Y} P(y | x) \log P(y | x)\\ =& - \sum_{x \in X}\sum_{y \in Y} P(x, y) \log P(y | x) \end{aligned}$

对该定义的自然解释如下： $H(X|Y)$ 是在观察到 $Y$ 的情况下， $X$ 中的 信息（或不确定性）

一对随机变量的熵等于其中一个随机变量的熵加上另一个随机变量的条件熵

链式法则定理：

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

证明：

$\begin{aligned} H(X, Y) =& -\sum_{x \in X} \sum_{y \in Y} P(x, y) \log p(x, y) \\ \xlongequal{概率乘法公式}& -\sum_{x \in X} \sum_{y \in Y} P(x, y) \log p(x)p(y|x) \\ =& -\sum_{x \in X} \sum_{y \in Y} P(x, y) \log p(x) -\sum_{x \in X} \sum_{y \in Y} P(x, y) \log p(y|x) \\ =& -\sum_{x \in X} P(x) \log p(x) -\sum_{x \in X} \sum_{y \in Y} P(x, y) \log p(y|x) \\ =& H(X) + H(Y|X) \\ \end{aligned}$

本质上是乘法公式： $P(X,Y) = P(X)P(Y|X)$

相对熵 - 两个分布之间的距离

定义：两个概率密度函数 $p(x)$ 和 $q(x)$ 之间的相对熵定义为：

$D(p \| q) = \sum_{x\in X} p(x) \log {p(x) \over q(x)}$

由于相对熵并不对称，也不满足三角不等式，因此它实际上并非两个分布之间的真实距离。但，将相对熵视为分布之间的距离往往会很有用。

平均互信息

定义：随机变量 $X, Y$ ，它们的联合概率密度函数为 $p(x, y)$ ，其边际概率密度函数分别是 $p(x)$ 和 $p(y)$ ，互信息 $I(X; Y)$ 为联合分布 $p(x, y)$ 和乘积分布 $p(x)p(y)$ 之间的 相对熵

$\begin{aligned} I(X;Y) =& \sum_{x \in X} \sum_{y \in Y} p(x, y) \log {p(x|y) \over p(x)} \\ =& \sum_{x \in X} \sum_{y \in Y} p(x, y) \log {p(x, y) \over p(x)p(y) } \\ =& H(X) + H(Y) - H(X, Y) \end{aligned}$

我们有以下规则：

$\begin{aligned} H(X,Y) =& H(X) + H(Y|X) = H(Y) + H(X|Y) \\ I(X;Y) =& H(X) + H(Y) - H(X,Y) \\ I(X;X) =& H(X) - H(X | Y) = H(X) \\ \end{aligned}$

信源编码

信源存在 模拟信源 和 离散信源 两种

信息论