信息论

• 为什么我们需要理论
• 信息论的开始
• 数据压缩
• 信息熵
• 熵的定义
• 举例
• 熵的性质
• 概览

为什么我们需要理论

信息论是成体系的理论，指引了后续大量研究发现，应用于通信、计算机、机器学习等众多学科。

一个好的理论应该：

• 表明什么是不可能的
• 预测未来

获得一个基础性理论是困难的：

• 我们没有很多正确的理论
• 基础理论通常是很难被替代的

Nothing is more practical than a good theory. —— Vladimar Vapnik

信息论的开始

1948，通信的数学理论，香农。

可以关注香农的纪录片：香农传. The Bit Player, 2018。

香农，信息论和其他众多学科和区域都有着密切联系：通信系统的极限、概率论、统计、不等式、经济学、算法理论、物理学、密码学、机器学习，ISIT 会议。

下面介绍一些和信息论有关的具体应用：

数据压缩

无损存档：

• .zip、.rar、.7z

视频压缩（有损、无损）：

• .rmvb、.mp4、.mkv

存储恢复技术（图片中的冗余的信息可以帮助我们恢复丢掉的信息）。

大的数据规模意味着我们需要分布式计算和存储数据，信息论帮助我们如何更好地在大的系统中传递信息，保证数据的可靠性。

人工智能发展异常迅猛，有很多理论或工具受到信息论的指引：

• 交叉熵损失函数
• 有偏置的决策树最大信息增益
• 维特比算法广泛用于 NLP
• RNNs 模型很多取自于编解码器

信息系统的安全问题，大数据和机器学习，信息论指导我们构建安全的信息系统。

本课程介绍信息论的基础内容：

• 基础概念
• 经典的问题
• 哪些工具是有用的
• 对工程问题的建模
• 跨学科交叉问题

前置要求：

• 基础概率论
  • 平均分布、高斯分布
  • 期望和方差
• 基础优化理论
  • 凸优化，凹凸性函数理论
• 数学分析
  • 微积分
  • 基础矩阵理论

基本内容：

1. 信息和信息的度量
2. AEP
3. 随机过程的熵率
4. 信息压缩
5. 信道容量
6. 微分熵
7. 高斯信道

信息熵

热力学第二定律告诉我们，系统的混乱程度是沿着一个方向进行的。

第一次证明热力学第二定律是玻尔兹曼，即玻尔兹曼熵公式。

熵的定义

$X$ 为离散型随机变量，使用字母表 $\mathcal{X}$ 表示样本空间。

概率质量函数（PMF）：

$$p(x) = \mathrm{Pr}(X = x),\, x \in \mathcal{X}$$

$X$ 的熵被定义为

$$H(X) = -\sum_{x \in \mathcal{X} } p(x)\log p(x)$$

• $x\log x \to 0,\, x \to 0$
• $H(X)$ 只依赖于 $p(x)$，有时 $H(X)$ 也写作 $H(p)$
• $H(X) \geqslant 0$
• 如果 $X$ 是均匀分布，那么 $H(X) = \log|\mathcal{X}|$

对数的底数并没有定义：

• 如果是 $\mathrm{e}$ 则被称为 nats
• 如果是 $2$ 则是 bits
• 如果是 $10$ 则是 bans

通过换底公式可得：

• $H_b(X) = \log_b aH_a(X)$

举例

二进制的熵函数 $H(p)$，

$$X = \begin{cases} 1, & \text{probability } p \\ 0, & \text{probability } 1-p \end{cases}$$

此系统的熵为

$$H(X) = -p\log p - (1-p)\log(1-p)$$

$$X = \begin{cases} a, & \text{probability } 1 / 2 \\ b, & \text{probability } 1 / 4 \\ c, & \text{probability } 1 / 8 \\ d, & \text{probability } 1 / 8 \end{cases}$$

计算得到 $H(X) = \dfrac{7}{4}$。

若 $g(X)$ 是 $X$ 的期望，那么

$$E_p g(X) = \sum_{x \in \mathcal{X} }g(x)p(x)$$

$$H(X) = E_p \log \frac{1}{p(X)}$$

熵的性质

对于随机变量 $X$ 定义在 $\mathcal{X}$ 上，有

$$0 \leqslant H(X) \leqslant \log|\mathcal{X}|$$

只需证明

$$\sum_{x \in \mathcal{X} } -p(x)\log p(x) \leqslant \log|\mathcal{X}|$$

可通过以下事实证明：

• 当 $0 \leqslant x \leqslant 1,\, -x\log x \geqslant 0$
• $x\log x = 0 \iff x = 0 \lor x = 1$
• $H(X) \geqslant 0$
• $f(x) = -x\log x$ 是凸函数

  国内外的凹凸性和国内正好相反

• $\sum_x p(x) = 1$

使用凸函数的性质，有：

$$\frac{1}{|\mathcal{X}|}\sum_{x \in \mathcal{X} } -p(x)\log p(x) \leqslant -\frac{1}{|\mathcal{X}|}\log\frac{\sum_{x}p(x)}{|\mathcal{X}|} = \frac{1}{|\mathcal{X}|}\log|\mathcal{X}|$$

当且仅当 $p(x) = 1/|\mathcal{X}|$ 时取等。

凸函数性质

$$\sum_{i}p_i f(x_i) \leqslant f\left(\sum_{i}p_i x_i\right)$$

概览

由于熵只依赖于概率分布，不依赖于字母表，所以概率分布与熵对应。

对于一系列随机变量 $X_1,\,X_2,\,\cdots,\,X_n$，其联合概率分布为

$$p(x_1,\,x_2,\,\cdots,\,x_n)$$

其中的一个联合概率是 $p(x_i,\,x_j)$，其中的条件概率可以写作 $p(x_i|\cdots)$。

通过概率论，可以使用贝叶斯规则和链式展开。