概率论熵

概率论中的熵

我们直接给出定义：

信息量（Information Content）

​ 信息量是指一个随机事件提供的信息量大小。越是出乎意料或发生概率越低的事件，一旦发生，则提供的信息量越大。信息量的定义是概率对数的相反数，即：

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

其中 $p$ 是事件发生的概率，$b$ 代表信息量的单位（用什么衡量信息量）通常取 $2$（此时单位是比特），也可以取自然对数的底数 $e$（此时单位是纳特）

熵（Entropy）

​ 熵是衡量随机变量不确定性的一个量度。在信息论中，熵用于量化信息的不确定性或信息的混乱程度（信息量的期望）。它反映了信息源产生信息的平均混乱程度或不可预测性。换句话说，熵代表了在接收到来自信源的消息之前，我们对于该消息内容所持有的平均信息量预期

​ 对于离散随机变量 $X$ 取值为 $x_i$ 且对应的概率为 $ P(X=x_i)=p_i$，其熵 $H(X)$ 定义为定义为所有可能状态的信息量加权和：

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

对于连续随机变量 $X$ 服从于概率分布 $p(x)$，其熵 $H(X)$ 通过积分形式给出：

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

​ 同理类似概率论的定义，我们可以可以定义条件熵（条件概率就是边缘化另外一个随机变量，同理调价熵也是边缘化另外一个随机变量）和联合熵（以离散状态为例）：

$$H(Y | X) = \sum_x p(x, y)H(Y | X=x) \\ H_{\text{joint}}(X, Y) -= \sum_{x, y} p(x, y)\log p(x,y)$$

为什么这样定义熵？

​ Motivation：

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

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

​ 熵（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} p(x)\log_b q(x)dx$$

​ 交叉熵可以被理解为在接收到来自信源的消息之前（$P$），如果我们使用一个不完全正确的概率分布（即估计的或预测的概率分布 $Q$）来编码这些消息，那么我们对于该消息内容所持有的平均信息量预期。即在真实分布 $P$ 下，使用概率分布 $Q$ 来编码事件的平均编码长度：

​ 如果我们有一个真实的概率分布 $P$ 描述了信源生成符号的概率，而我们使用另一个概率分布 $Q$ 来对这些符号进行编码。在这种情况下，交叉熵 $H(P,Q)$ 表示的是，当我们使用基于 $Q$ 的编码方案时，实际从 $P$ 产生的每个符号所需的平均比特数（或者说是平均信息量）。如果 $Q$ 不等于 $P$，那么这种编码方式不是最优的，可能会导致更高的平均比特数，也就是更大的信息量预期

Kullback-Leibler (KL) 散度

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

• 对于离散的情况：

$$KL(P|| Q)=\sum_i P(x_i)\log_b\left(\frac{Q(x_i)}{P(x_i)}\right) = \mathbb{E}_{x \sim 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 = \mathbb{E}_{x \sim p(x)} \log\left( \frac{p(x)}{q(x)} \right)$$

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

• KL散度不具有对称性

一些重要等式和证明

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

\begin{align} H_\text{joint}(X, Y) &= -\sum_{x,y} p(x, y) \log p(x, y) \\ &=-\sum_{x,y } p(x, y) \log\left[p(y | x)p(x) \right]\\ &= -\sum_{x,y } p(x, y) \log p(y | x) -\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) \end{align}

KL散度大于0：

\begin{align} KL(P || Q) &= \int p(x)\log\left( \frac{p(x)}{q(x)} \right)dx \\ &= - \int p(x)\log\left( \frac{q(x)}{p(x)} \right)dx \\ &\geq -\int p(x)\left( \frac{q(x)}{p(x)} -1\right)dx \\ &= \int \left( q(x) - p(x)\right)dx = 0 \end{align}

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

\begin{align} KL(P || Q) &= H(P, Q) - H(P) \\ &= -\sum_i p_i\log\left( q_i \right) + \sum_i p_i\log\left( p_i \right) \\ &= \sum_i p_i \log \left( \frac{p_i}{q_i} \right) \end{align}

• 从这个角度看，KL 散度可以理解为我们对 $X,Y$ 整体的信息量预期和对 $X$ 的信息量预期之差，假如 $P=Q$ 的话也就代表着信息量相同

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

$$\nabla_{\theta}D(p || 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