熵-互信息-熵率

本节定义熵|相对熵|互信息等度量以及常用不等式，这些度量作为后续通信、统计、复杂性和赌博中许多问题的自然答案而出现，也是这些定义的价值所在。

主要内容

熵的定义

\begin{array}{r} H (X) = - \sum_{x \in X} p (x) \log p (x) \end{array}

Properties of $H$
1. $H (X) \geq 0$
2. $H_{b} (X) = (\log_{b} a) H_{a} (X)$
3. Conditioning reduces entropy（条件熵性质），当 $X ⊥ ⊥ Y$ 时等号成立
$H (X | Y) \leq H (X)$
1. $H (X_{1}, X_{2}, \dots, X_{n}) \leq \sum_{i = 1}^{n} H (X_{i})$ , 当且仅当 $X_{i}$ 相互独立时取等
2. $H (X) \leq \log | X |$ , 当且仅当 $X$ 服从 $X$ 上的均匀分布等号成立。
3. $H (p)$ is concave in $p$ .
Relative Enrtopy

D (p ∥ q) = \sum_{x} p (x) \log \frac{p (x)}{q (x)}

Mutual Information

I (X; Y) = \sum_{x \in X} \sum_{y \in Y} p (x, y) \log \frac{p (x, y)}{p (x) p (y)}

等价表达式

\begin{matrix} H (X) = E_{p} \log \frac{1}{p (X)} \\ H (X, Y) = E_{p} \log \frac{1}{p (X, Y)} \\ H (X | Y) = E_{p} \log \frac{1}{p (X | Y)} \\ I (X; Y) = E_{p} \log \frac{p (X, Y)}{p (X) p (Y)} \\ D (p | | q) = E_{p} \log \frac{p (X)}{q (X)} \end{matrix}

相对熵 $D$ 与互信息 $I$ 性质
- $I (X; Y) = H (X) - H (X | Y) = H (Y) - H (Y | X) = H (X) + H (Y) - H (X, Y)$
- $D (p ∥ q) \geq 0$
- $I (X; Y) = D (p (x, y) | | p (x) p (y)) \geq 0$ 当且仅当 $X ⊥ ⊥ Y$ 时等号成立
- 若 $| X | = m$ 且 $u$ 是 $X$ 上的均匀分布，则 $D (p ∥ u) = \log m - H (p)$
- $D (p ∥ q)$ 关于 $(p, q)$ 时凸的
链式法则
- Entropy:
$H (X_{1}, X_{2}, \dots, X_{n}) = \sum_{i = 1}^{n} H (X_{i} | X_{i - 1}, \dots, X_{1})$
- Mutual information:
$I (X_{1}, X_{2}, \dots, X_{n}; Y) = \sum_{i = 1}^{n} I (X_{i}; Y | X_{1}, X_{2}, \dots, X_{i - 1})$
- Relative entropy:
$D (p (x, y) | | q (x, y)) = D (p (x) | | q (x)) + D (p (y | x) | | q (y | x))$
Jensen 不等式
对数和不等式
充分统计量： $T (X)$ is sufficient relative to ${f_{θ} (x)}$ if and only if $I (θ; X) = I (θ; T (X))$ for all distributions on $θ$ .
Fano 不等式： $H (P_{e}) + P_{e} \log | X | \geq H (X | Y)$
若 $X, X^{'}$ 独立同分布，则 $Pr (X = X^{'}) \geq 2^{- H (X)}$

熵 (Entropy)

Entropy

The entropy $H (X)$ of a discrete random variable $X$ is

\begin{matrix} (2.1) & \begin{array}{r} H (X) = - \sum_{x \in X} p (x) \log p (x) \end{array} \end{matrix}

$H (X)$ 是 $\log (1 / p (X))$ 的期望
熵度量了随机变量的“随机性”
$H (X) \geq 0$
$H_{b} (X) = (\log_{b} a) H_{a} (X)$
熵的对数 log 所用底为 2，单位为 bit。若使用底为 $e$ 时单位为 nat（奈特）。
$X$ 上的均匀分布是其最大熵分布

H (X) \leq \log | X |

Proof

证明利用定义的相对熵

0 \leq D (p ∥ u) = \sum p (x) \log \frac{p (x)}{u (x)} = \log | X | - H (X)

其中 $u (x) = \frac{1}{| X |}$ 是均匀分布概率质量函数

$X = {\begin{cases} 1 & with probability p, \\ 0 & with probability 1 - p . \end{cases}$
对一个服从二项分布的随机变量 $X$ 有
$H (X) = - p \log p - (1 - p) \log (1 - p) \overset{def}{=} H (p)$

可以看出 $H (p)$ 是凹函数。

Joint Entropy & Conditional Entropy

联合熵|条件熵

The joint entropy $H (X, Y)$ of a pair of discrete random variables $(X, Y)$ with a joint distribution $p (x, y)$ is defined as

\begin{matrix} (2.8) & H (X, Y) = - \sum_{x \in X} \sum_{y \in Y} p (x, y) \log p (x, y) \end{matrix}

the conditional entropy $H (Y | X)$ is defined as

\begin{aligned} H (Y | X) & = \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}

联合熵可表示为 $- E \log p (X, Y)$ ; 条件熵可表示为 $- E \log p (Y | X)$

相对熵 (Relative Enrtopy)

相对熵是两个随机分布之间距离的度量。统计学中对应似然比的对数期望。

\begin{matrix} (2.26-2.27) & D (p | | q) = \sum_{x \in X} p (x) \log \frac{p (x)}{q (x)} = E_{p} \log \frac{p (X)}{q (X)} \end{matrix}

约定 $0 \log \frac{0}{0} = 0, p \log \frac{p}{0} = \infty$

若已知随机变量真实分布为

p

, 但却使用针对分布

q

的编码，那么平均需要

H (p) + D (p ∥ q)

比特描述该随机变量。

$D (p ∥ q) \geq 0$

Proof

利用 Jensen's inequality (2.85) 进行证明。设 $A = {x : p (x) > 0}$ 为 $p (x)$ 支撑集，则

\begin{aligned} - D (p | | q) & = - \sum_{x \in A} p (x) \log \frac{p (x)}{q (x)} = \sum_{x \in A} p (x) \log \frac{q (x)}{p (x)} \\ \leq \log \sum_{x \in A} p (x) \frac{q (x)}{p (x)} = \log \sum_{x \in A} q (x) \\ \leq \log \sum_{x \in X} q (x) = 0 \end{aligned}

利用 Log sum inequality 证明：

\begin{aligned} D (p | | q) & = \sum p (x) \log \frac{p (x)}{q (x)} \\ \geq (\sum p (x)) \log \frac{\sum p (x)}{\sum q (x)} = 1 \log \frac{1}{1} = 0 \end{aligned}

相对熵不对称，也不满足三角不等式，因此实际上并非两个分布之间的真实距离
相对熵的凸性： $D (p ∥ q)$ 关于 $(p, q)$ 是凸的

\begin{matrix} (2.105) & D (λ p_{1} + (1 - λ) p_{2} | | λ q_{1} + (1 - λ) q_{2}) \leq λ D (p_{1} | | q_{1}) + (1 - λ) D (p_{2} | | q_{2}), \forall 0 \leq λ \leq 1 \end{matrix}

同理利用对数和不等式易证。

互信息 (Mutual Information)

互信息是一个随机变量包含另一个随机变量信息量的度量。也即给定另一随机变量“知识”的条件下，原信息量不确定性的缩减量。

\begin{matrix} I (X; Y) = \sum_{x \in X} \sum_{y \in Y} p (x, y) \log \frac{p (x, y)}{p (x) p (y)} \\ = D (p (x, y) ∥ p (x) p (y)) \\ = E_{p (x, y)} \log \frac{p (X, Y)}{p (X) p (Y)} . \end{matrix}

上式为离散型随机变量情形，微分熵中奖探讨含有连续随机变量的情形。

$I (X; Y) \geq 0$ 当且仅当 $X, Y$ 独立时取等

证明利用 $I (X; Y) = D (p (x, y) ∥ p (x) p (y)) \geq 0$

【条件互信息（conditional mutual information）】

\begin{aligned} I (X; Y | Z) & = H (X | Z) - H (X | Y, Z) = E_{p (x, y, z)} \log \frac{p (X, Y | Z)}{p (X | Z) p (Y | Z)} \end{aligned}

Chain Rules

joint entropy & entropy

\begin{matrix} (2.14) & H (X, Y) = H (X) + H (Y | X) \end{matrix}

证明主要利用定义以及 $p (x, y) = p (x) p (y | x)$ 直接推导 (2.15~2.19)

【推论】 $H (X, Y | Z) = H (X | Z) + H (Y | X, Z)$

注意 $H (Y | X) \neq H (X | Y)$

Mutual information & entropy

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

Chain rule for entropy

H (X_{1}, X_{2}, \dots, X_{n}) = \sum_{i = 1}^{n} H (X_{i} | X_{i - 1}, \dots, X_{1}) X_{1}, X_{2} \dots, X_{n} \sim p (x_{1}, x_{2} \dots, x_{n})

证明利用 $p (x_{1}, \dots, x_{n}) = \prod_{i = 1}^{n} p (x_{i} | x_{i - 1}, \dots, x_{1})$ 与定义递推

Chain rule for information

\begin{matrix} (2.62) & I (X_{1}, X_{2}, \dots, X_{i}; Y) = \sum_{i = 1}^{n} I (X_{i}; Y | X_{i - 1}, X_{i - 2}, \dots, X_{1}) \end{matrix}

利用 $L H S = H (X_{1}, X_{2}, \dots, X_{n}) - H (X_{1}, X_{2}, \dots, X_{n} | Y)$ 以及上述熵的链式法则易证

Chain rule for relative entropy

\begin{matrix} (2.67) & D (p (x, y) ∥ q (x, y)) = D (p (x) ∥ q (x)) + D (p (y | x) ∥ q (y | x)) \end{matrix}

其中条件相对熵 $D (p (y | x) ∥ q (y | x))$ 是在 $p (x)$ 上对 $p (y | x), q (y | x)$ 之间相对熵的平均值。

D (p (y | x) | | q (y | x)) = \sum_{x} p (x) \sum_{y} p (y | x) \log \frac{p (y | x)}{q (y | x)} = E_{p (x, y)} \log \frac{p (Y | X)}{q (Y | X)}

证明思路利用 $\frac{p (x, y)}{q (x, y)} = \frac{p (x)}{q (x)} \frac{p (y | x)}{q (y | x)}$ 进行 log 的拆分易证（2.68~2.71）

Independence bound on entropy

\begin{matrix} (2.96) & H (X_{1}, X_{2}, \dots, X_{n}) \leq \sum_{i = 1}^{n} H (X_{i}) X_{1}, X_{2} \dots, X_{n} \sim p (x_{1}, x_{2} \dots, x_{n}) \end{matrix}

根据上述图例以及定义易证，且当 $X_{i}$ 相互独立时取等。

常用不等式

Jensen's inequality

If $f$ is a convex function and $X$ is a random variable,

\begin{matrix} (2.76) & E f (X) \geq f (E X) \end{matrix}

Moreover, if $f$ is strictly convex, the equality implies that $P {X = E X} = 1$ i.e., $X$ is a constant.

如果是 concave 则变为 $\leq$ 。

离散情形下可利用数学归纳法（两点分布利用凸函数定义直接得到）

Log sum inequality

（对数和不等式）对于非负数 $a_{1}, a_{2} \dots, a_{n}, b_{1}, b_{2} \dots, b_{n}$

\begin{matrix} (2.99) & \sum_{i = 1}^{n} a_{i} \log \frac{a_{i}}{b_{i}} \geq (\sum_{i = 1}^{n} a_{i}) \log \frac{\sum_{i = 1}^{n} a_{i}}{\sum_{i = 1}^{n} b_{i}} \end{matrix}

当且仅当 $a_{i} / b_{i} = c o n s t$ 时等号成立。
【证明思路】
不等式等价于

\sum_{i} \frac{b_{i}}{\sum_{j} b_{j}} \frac{a_{i}}{b_{i}} \log \frac{a_{i}}{b_{i}} \geq \sum_{i} \frac{a_{i}}{\sum_{j} b_{j}} \cdot \log \sum_{i} \frac{a_{i}}{\sum_{j} b_{j}}

利用 Jensen's inequality，因为 $f (t) = t \log t$ 严格凸； LHS 即 $E f (X)$ ，RHS 即 $f (E X)$ 得证。

Data-processing inequality

If X → Y → Z forms a Markov chain, $I (X; Y) \geq I (X; Z)$

Fano's inequality

其他

If $X$ and $X^{'}$ are i.i.d. with entropy $H (X)$ ,

\begin{matrix} (2.146) & Pr (X = X^{'}) \geq 2^{- H (X)} \end{matrix}

with equality if and only if $X$ has a uniform distribution.