1. 引言
在本教程中，我们将探讨熵（Entropy）这一概念，以及它在计算机科学不同分支中的应用。熵的概念最早来源于香农（Shannon）的信息论，而信息论的诞生与通信问题密切相关。
✅ 熵本质上是对不确定性或信息量的度量。它越小，表示系统越有序、可预测；它越大，表示系统越混乱、不确定。
2. 通信的基本概念
我们可以将通信定义为：一个机制主动与其他机制建立联系的过程。
一个通信系统通常包含三个基本元素：
- 信源（Source）
- 信道（Channel）
- 接收端（Receiver）
信息论的核心问题是：如何度量信息？如何在有噪声或无噪声的条件下传输信息？
3. 组合熵（Combinatorial Entropy）
我们可以通过排列组合来理解熵的本质。
假设我们有符号 A、B、C，分别出现 2 次、5 次、3 次。例如以下两个排列：
B C B B C C A B A B
B A C B A C B B C B
这两个排列属于多组合排列（Multinomial Permutation）。其总数为：
$$ P = \left(\begin{array}{c}10\2,5,3\end{array}\right) = \frac{10!}{2!5!3!} = 2520 $$
如果我们想用二进制字符串唯一编码这些排列，需要满足：
$$ 2^b = P \Rightarrow b = \log_2 P $$
平均每个符号需要的比特数为：
$$ H_c = \frac{1}{N} \log_2 P $$
这个量称为组合熵（Combinatorial Entropy），单位是 bit/symbol。
4. 信息论中的熵（Shannon Entropy）
香农熵（Shannon Entropy）可以从组合熵推导而来：
$$ H_c = \frac{1}{N} \left( \log_2 N! - \sum_{i=1}^{L} \log_2 n_i! \right) $$
使用斯特林公式（Stirling’s Approximation）近似后，可得：
$$ H = -\sum_{i=1}^{L} p_i \log_2 p_i $$
这就是我们熟知的香农熵。它表示每个符号平均所需比特数的上限，即：
$$ H > H_c $$
如果使用自然对数，香农熵变为：
$$ H = -\sum_{i=1}^{L} p_i \ln p_i $$
此时单位为 nats/symbol。无论是 bit 还是 nat，它们都是无量纲单位。
5. 连续情况下的熵：微分熵（Differential Entropy）
当从离散情况推广到连续情况时，香农简单地将求和替换为积分：
$$ h = -\int p(x) \log p(x) dx $$
这个量称为微分熵（Differential Entropy）。注意，与离散熵不同的是：
✅ 微分熵可以是负数
✅ 微分熵不是在变量变换下不变的
例如，若 $ p(x) $ 是正态分布：
$$ p(x) = \frac{1}{\sqrt{2\pi\sigma^2}} e^{-\frac{(x-\mu)^2}{2\sigma^2}} $$
则其微分熵为：
$$ h = \frac{1}{2} \log(2\pi e \sigma^2) $$
当 $ \sigma < \sqrt{\frac{1}{2\pi e}} $ 时，微分熵为负值。
⚠️ 因此，微分熵不能简单地视为离散熵的推广。Jaynes 提出了一个修正版本，称为相对熵（Relative Entropy）：
$$ D(p||m) = \int p(x) \log \frac{p(x)}{m(x)} dx $$
其中 $ m(x) $ 是一个先验概率密度，例如均匀分布。
6. 熵与信息的关系
香农指出：信息与语义无关。信息只是选择消息的自由度。
例如，从两个消息中选择一个，需要 1 bit（$\log_2 2$）的信息。
Shannon 曾说：“通信的语义方面与技术方面无关。”
6.1 遍历过程（Ergodic Processes）
在实际通信中，符号的选择往往不是独立的。例如英文中，字母 j 后面出现元音的概率远高于 x。
这种过程称为马尔可夫过程（Markov Process）。如果一个马尔可夫过程在样本足够多时统计特性稳定，则称为遍历过程（Ergodic Process）。
熵在此类过程中，是对不确定性、意外性或信息量的度量。
7. 最大熵原理
香农熵在所有可能性等概率时达到最大值。例如两个选项时：
$$ H = -p \ln p - (1-p) \ln (1-p) $$
当 $ p = 0.5 $ 时熵最大。
我们可以推广到更多选项：
- 正态分布在固定方差下具有最大熵。
- 均匀分布在有限区间上具有最大熵。
例如，在区间 $[a, b]$ 上的均匀分布：
$$ p = \frac{1}{b-a}, \quad h_{\max} = \ln(b-a) $$
而在离散情况下，最大熵为：
$$ H_{\max} = \ln N $$
8. 物理类比：热力学熵
香农熵与热力学熵非常相似。
8.1 热力学熵（Thermodynamic Entropy）
根据玻尔兹曼公式：
$$ S = k_B \ln W $$
其中：
- $ S $ 是系统的熵
- $ k_B $ 是玻尔兹曼常数
- $ W $ 是系统微观状态数
这个公式表明，熵是系统微观状态数的度量，与组合熵的思想非常相似。
8.2 无序与熵
在一个孤立系统中，熵会随着不可逆过程而增加，直到达到最大值。例如：
- 气体扩散
- 热量传递
这些过程最终达到热平衡，即熵最大。
8.3 量子力学与不确定性原理
不确定性原理可以表示为：
$$ \Delta x \Delta p \geq \frac{\hbar}{2} $$
用信息熵的形式表示为：
$$ h(x) + h(p_x) \geq \ln(\pi e \hbar) $$
这表明熵不仅是信息的度量，也是物理系统不确定性的度量。
9. 熵的基本性质
以下是熵的一些基本性质：
- 连续性：概率的微小变化只引起熵的微小变化。
- 对称性：熵对结果顺序不敏感。
- 可加性：熵应独立于我们如何划分过程。
10. 其他形式的熵
给定两个随机变量 $ (x, y) $，可以定义：
联合熵（Joint Entropy）： $$ H(x, y) = -\sum_{x,y} p(x,y) \ln p(x,y) $$
条件熵（Conditional Entropy）： $$ H(x|y) = H(x,y) - H(y) $$
互信息（Mutual Information）： $$ I(x,y) = H(x) - H(x|y) = H(y) - H(y|x) $$
互信息衡量两个变量之间的相互依赖性。
11. 通信与信息传输
通信系统中，熵与最大熵的比值称为相对熵，1 减去相对熵就是冗余度（Redundancy）。
若信道容量为 $ C $，信源熵为 $ H $，则平均传输速率上限为 $ \frac{C}{H} $。
有趣的是，在有噪声的信道中，接收到的信息熵反而比发送的大，因为噪声带来了额外的不确定性。
12. 数据压缩
数据压缩是熵和信息论的重要应用之一。
12.1 熵与编码
每个符号用长度为 $ l_i $ 的码字表示，平均码长为：
$$ L = \sum p_i l_i $$
香农第一定理（Source Coding Theorem）指出：
$$ H(S) \leq L < H(S) + 1 $$
即：熵是平均码长的下限。熵越小，压缩潜力越大。
12.2 压缩效率
编码效率定义为：
$$ \eta = \frac{H(S)}{L} $$
若每个码字都不是其他码字的前缀（前缀码），则保证唯一可解码。
Kraft-McMillan 不等式：
$$ \sum 2^{-l_i} \leq 1 $$
若满足此不等式，就可以构造前缀码。
12.3 压缩方案示例
考虑一个符号向量 $ \Sigma $，每个符号的概率为 $ p_i $，目标是用二进制字符集 $ \Gamma = {0,1} $ 编码。
定义编码函数 $ f $ 和解码函数 $ g $：
$$ f: \Sigma^n \rightarrow \Gamma^m, \quad g: \Gamma^m \rightarrow \Sigma^n $$
若满足：
$$ m = \alpha n, \quad \text{Pr}[g(f(x)) = x] > 1 - \delta $$
则称该方案为 $ (n, \alpha, \delta) $ 压缩方案。
13. 熵与机器学习
13.1 交叉熵损失函数（Cross-Entropy Loss）
在神经网络中，我们常使用交叉熵作为损失函数：
$$ E = -\sum_n \sum_k \left[ t_k \ln y_k + (1-t_k) \ln(1-y_k) \right] $$
这个函数在分类任务中非常常见，尤其是在二分类问题中。
13.2 最大熵原理（Maximum Entropy Principle）
Jaynes 提出的最大熵原理（MaxEnt）认为：在给定约束下，最合理的概率分布是熵最大的那个。
在机器学习中，这个原理可用于优化模型输出的条件概率分布。
相关概念：
- 最大互信息（MaxMI）：最大化输出与目标之间的互信息。
- 最小互信息（MinMI）：最小化输出与输入之间的互信息。
在已知输入和目标边缘分布时，MinMI 等价于 MaxEnt。
13.3 估计器的误差下界
设目标为 $ t $，估计器输出为 $ y(x) $，则其均方误差满足：
$$ \left\langle (t - y(x))^2 \right\rangle \geq \frac{1}{2\pi e} \exp\left{ 2h(y|x) \right} $$
这个不等式在量子力学中也有重要意义。
14. 总结
在本教程中，我们回顾了熵的概念及其在计算机科学多个领域的应用。从信息论到热力学，再到机器学习和数据压缩，熵始终是一个核心度量。
虽然本教程无法涵盖所有细节，但它为深入理解熵提供了坚实的基础。熵不仅是信息的度量，也是系统不确定性的体现，在多个学科中都扮演着重要角色。