概率论熵

概率论中的熵

我们直接给出定义：

信息量（Information Content）

​ 信息量是指一个随机事件提供的信息量大小。一个事件发生的概率越小，它提供的信息量就越大。信息量的定义是概率对数的相反数，即：

$$I(X) = -log_b(p)$$

其中 $p$ 是该事件发生的概率

熵（Entropy）

​ 熵是衡量随机变量不确定性的一个量度。在信息论中，熵用于量化信息的不确定性或信息的混乱程度（信息量的期望）。一个系统的熵越高，表示系统的不确定性越大：

对于离散随机变量 $X$ 取值为 $x_i$ 且对应的概率为 $ P(X=x_i)=p_i$，其熵 $H(X)$ 定义为：

$$H(X)=−\sum_i p_i log_b (p_i)$$

对于连续随机变量 $X$ 服从于概率分布 $f(x)$，其熵 $H(X)$ 定义为：

$$H(X)=−\int_{-\infin}^{\infin} f(x) log_b (f(x))dx$$

其中，$b$ 是对数的底数，通常取2（此时单位是比特），也可以取自然对数的底数 $e$（此时单位是纳特）

​ 同理概率论的知识可以定义条件熵和联合熵：

$$H(Y \mid X) = \sum_x p(x)H(Y \mid X=x) \\ H(X, Y) -= \sum_{x, y} p(x, y)log\ p(x,y)$$

为什么这样定义熵？

​ Motivation：

1. 度量不确定性：熵提供了一种度量信息源不确定性的方法。在信息论中，熵越高，表示信息源产生的信息越不确定，即我们从信息源获得的信息越具有价值，因为它减少了我们对结果的不确定性
2. 符合逻辑预期：即不太可能发生的事件应该具有更高的信息量。如果一个事件几乎肯定会发生（概率接近1），那么当它实际发生时，它提供的信息量很少或没有。相反，如果一个事件的发生概率很低，那么当它发生时，它提供的信息量很大（且要求概率为0时，熵不应该无限大）
3. 概率的乘积规则：熵的定义需要与概率论的基本原则相一致，特别是与联合概率和条件概率的规则相容。熵的定义形式确保了当我们考虑多个随机变量的联合熵或条件熵时，这些概率规则仍然适用
4. 可加性：我们要求从多个独立来源获得的信息量应该是它们各自信息量的总和，因此熵应该具有可加性的性质

​ 根据以上规则，再去理解这个式子可能会更加容易（但实际上香农自己都说不知道熵到底是什么，我的理解就是用这个数学表达式去大概建模量化信息，这个建模不一定是最好的，但是这个形式相对简单所以用得最多）

​ 熵（Entropy）在信息论中的含义直接关联到了数据编码的效率。当我们要编码一个具有不同符号概率分布的信息源时，熵提供了一个理论上的最优编码长度的下限。也就是说，对于一个给定的概率分布，我们可以设计出一种编码方式，使得平均而言，每个符号编码的长度趋近于这个分布的熵值。这种编码方式被称为熵编码

交叉熵（Cross-Entropy）

​ 交叉熵是衡量两个概率分布相似度的一个指标。在机器学习中，交叉熵常用于损失函数，衡量模型预测的概率分布与真实数据的概率分布之间的差异。交叉熵的数学定义如下：

对于两个概率分布 $P$ 和 $Q$

• 若 $P,Q$ 的概率分布均为离散的，交叉熵 $H(P,Q)$ 定义为：

$$H(P, Q) = -\sum_i P(i)log_b(Q(i))$$

• 若 $P,Q$ 的概率分布均为连续的，且服从于分布 $f,g$，交叉熵 $H(P,Q)$ 定义为：

$$H(P,Q) = -\int_{-\infin}^{\infin} f(x)log_b(g(x))dx$$

​ 交叉熵可以视为在真实分布 $P$ 下，使用概率分布 $Q$ 来编码事件的平均编码长度：

​ 如果我们有一个事件的概率分布 $P(x)$，它是真实的或理想的情况，那么根据熵（Entropy）的概念，我们知道使用最优的编码方式（即按照每个事件发生的概率为其分配码长），能够达到最小的平均编码长度。而对于任意另一个概率分布 $Q(x)$，如果我们尝试用它来编码同样的事件，那么由于 $Q(x)$ 可能并不精确匹配真实的概率分布 $P(x)$，因此会使得编码效率下降，导致平均编码长度增加（同样的，我的理解还是）

Kullback-Leibler (KL) 散度

​ KL散度是衡量两个概率分布差异的另一种方式，它是交叉熵和熵的差值：

• 对于离散的情况：

$$KL(P\mid \mid Q)=\sum_iP(x_i)log_b\left(\frac{Q(x_i)}{P(x_i)}\right) = E_{p(x)}\ log\left( \frac{p(x)}{q(x)} \right)$$

• 对于连续的情况：

$$KL(P \mid \mid Q) = \int_{-\infin}^{\infin}f(x)log_b\left( \frac{f(x)}{g(x)} \right) dx = E_{p(x)}\ log\left( \frac{p(x)}{q(x)} \right)$$

• KL散度总是非负的，当且仅当 $P$ 和 $Q$ 完全相同时，KL散度为0

• KL散度不具有对称性

一些重要等式和证明

联合熵和熵，条件熵（理解下面式子，独立的时候两个变量的熵之和为它们联合分布的熵）：

$$H(X, Y) = -\sum_{x,y} p(x, y) log\ p(x, y) \\ =-\sum_{x,y } p(x, y) log\left(p(y \mid x)p(x) \right)\\ = -\sum_{x,y } p(x, y) log\left(p(y \mid x) \right) -\sum_{x,y}p(x,y)log\ p(x) \\ = H(Y\mid X) - \sum_x \sum_yp(x, y)log\ p(x) \\ = H(Y\mid X) - \sum_x log\ p(x)\sum_yp(x, y) \\ = H(Y \mid X) - \sum_x log\ p(x) \times p(x) \\ = H(Y \mid X) + H(X)$$

KL散度大于0：

$$KL(X \mid \mid Y) = \int f(x)log\left( \frac{f(x)}{g(x)} \right)dx \\ = - \int f(x)log\left( \frac{g(x)}{f(x)} \right)dx \\ \geq -\int f(x)\left( \frac{g(x)}{f(x)} -1\right)dx \\ = \int \left( g(x) - f(x)\right)dx = 0$$

KL散度和交叉熵，熵的关系（用编码理解KL散度衡量两个概率分布的差异的含义）：

$$KL(X \mid \mid Y) = H(X, Y) - H(X) \\ = -\sum_i p_ilog\left( q_i \right) + \sum_i p_ilog\left( p_i \right) \\ = \sum_i p_i log \left( \frac{p_i}{q_i} \right)$$

常用优化策略（优化KL散度相当于优化交叉熵 ）：

$$\nabla_{\theta}D(p\mid \mid q_{\theta}) = \nabla_{\theta}H(p, q_{\theta}) - \nabla_{\theta}H(P) \\ = \nabla_{\theta} H(p. q_{\theta})$$

另外一个理解KL散度的方式：

• 有两个概率分布 $p,q$（均为伯努利分布，视为投硬币），用 $p$ 投出的结果和 $q$ 投出的结果的差异进行衡量，也就可以认为是对概率分布的差异进行衡量：

注意下面知识拿一个简单的伯努利分布举一个例子，$seq$ 代表一个投出来的一个硬币序列，用他们投出来同一个序列的概率值衡量他们之间的概率分布差异：

$$log\left( \frac{P(seq\mid q)}{p(seq \mid q)}^{\frac{1}{N}} \right) =\frac{1}{N}log \left( \frac{p(h)^{N_h}p(t)^{N_t}}{q(h)^{N_h} q(t)^{N_t}} \right) \\ =\frac{N_h}{N} log\ p(h) + \frac{N_h}{N} log\ p(t) -\frac{N_t}{N}log\ q(h) -\frac{N_t}{N}log\ q(t) \\ \sim p(h) log\ p(h) +p(t)log\ p(t) -p(h)log\ q(h) -p(t)log\ q(t) \\ = p(h)log\left(\frac{p(h)}{q(h)}\right) + p(t)log\left( \frac{p(t)}{q(t)} \right) \\ \sim KL(p\mid\mid q)$$

编码定理：

​ 通信中的编码问题（最小期望码长）：假设一个离散型随机变量X取值于$\{x_1 , ⋅ ⋅ ⋅ ,x_N\}$ ，其相应概率为 $\{p(x_1 ), ⋅ ⋅ ⋅ ,p(x_N )\}$，设计一个编码系统，将 $x_i$ 编成 $n_i$ 位的二进制序列，通过一个通信网络将从A处传送到B处，为避免混乱，要求编码后的序列不能出现一个序列是另一个序列的延伸。如何设计编码系统使得最终的期望码长最小

引理1:

​ 为了将 $X$ 的可能取值编码成0-1序列，且任何一个序列都不能是另一序列的延伸，其充要条件为：

$$\sum_{i=1}^N \left( \frac{1}{2}\right)^{n_i} \leq 1$$

证明:

记 $w_{j}$ 为 $x_{i}$ 中编码长度为 $j$ 的个数， $j = 1,2,3{\ldots}$ ，显然有:

$$w_{1}2^{n {-} 1} + w_{2}2^{n {-} 2} + {\cdots} + w_{n {-} 1}2 + w_{n} {\leq} 2^{n}$$

两边同除以 $2^{n}$ 得:

{\sum}\limits_{j = 1}^nw_{j}{\left( \frac{1}{2} \right)}^{j} = {\sum}\limits_{i = 1}^N{\left( \frac{1}{2} \right)}^{n_{i}} \leq 1

无噪声编码定理:

​ 假设每个信号单位从位置A到位置B的过程没有发生错误，则编码的期望码长不小于随机变量的信息熵:

{\sum}\limits_{i = 1}^N n_{i}p\left( x_{i} \right) {\geq} H(X) = - \sum_{i = 1}^N p\left( x_{i} \right)\log p\left( x_{i} \right)

证明： 记 $p_{i} = p\left( x_{i} \right),q_{i} = 2^{-n_i}/\sum_{j = 1}^N 2^{-n_j}$ ，则有

{\sum}\limits_{i = 1}^Np_{i} = {\sum}\limits_{i = 1}^Nq_{i} = 1 \\ {-} {\sum}\limits_{i = 1}^Np_{i}\log\left( \frac{p_{i}}{q_{i}} \right) = {-} \log e{\sum}\limits_{i = 1}^Np_{i}\ln\left( \frac{p_{i}}{q_{i}} \right) \\ = \log e{\sum}\limits_{i = 1}^Np_{i}\ln\left( \frac{q_{i}}{p_{i}} \right) \\ {\leq} \log e{\sum}\limits_{i = 1}^Np_{i}\left( \frac{q_{i}}{p_{i}} {-} 1 \right) \\ = \log e\left( {\sum}\limits_{i = 1}^Np_{i} {-} {\sum}\limits_{i = 1}^Nq_{i} \right) = 0

由此可得:

{-} {\sum}\limits_{i = 1}^Np\left( x_{i} \right)\log p\left( x_{i} \right) {\leq} {-} {\sum}\limits_{i = 1}^Np_{i}\log q_{i} \\ = \sum_{i = 1}^N n_i p_i + \log\left( \sum_{j = 1}^N 2^{-n_j} \right) \leq \sum_{i = 1}^N n_i p_i