Information Theory

Posted on Edited on

信息论

信息熵（Entropy）

定义

对于一个分布XX，我们想要衡量它的信息量H(X)H(X)，作以下要求：

  • H(X)H(X)仅与XX的概率分布有关，和具体的xx无关；
  • H(X)H(X)关于概率连续（概率微小变化，信息量也发生微小变化）；
  • 对于独立分布XX和YY，总共的信息量应该为两者之和；
  • 概率越小，信息量越大。

可以得出H(X)H(X)的唯一形式为：

H(X)=−∑p(x)log⁡p(x)H(X) = -\sum p(x)\log p(x)

也就是各个事件的信息量−log⁡p-\log p按照pp加权求和。

按照底数不同，单位也不同。比如说以22为底，单位是bit\mathrm{bit}；以ee为底，单位是nat\mathrm{nat}。

香农熵的公理化推导（Claude）

Show More

目标

寻找一个函数 H(p1,p2,…,pn)H(p_1, p_2, \ldots, p_n)，用来度量概率分布 (p1,…,pn)(p_1, \ldots, p_n) 的"不确定性"，要求它满足三条自然公理。

三条公理

公理 1（连续性）

H(p1,p2,…,pn)H(p_1, p_2, \ldots, p_n) 是各 pip_i 的连续函数。

概率的微小扰动不应导致不确定性的突变。

公理 2（对称性 + 均匀分布单调性）

对于均匀分布 H(1n,…,1n)≜f(n)H\left(\frac{1}{n}, \ldots, \frac{1}{n}\right) \triangleq f(n)，要求 f(n)f(n) 关于 nn 严格单调递增。

等可能的结果越多，不确定性越大。

公理 3（递归分解性 / 链式法则）

若将某个结果进一步细分，总不确定性应满足：

H(1n,…,1n)=H(kn,n−kn)+kn H(1k,…,1k)⏟k 个+n−kn H(1n−k,…,1n−k)⏟n−k 个H\left(\frac{1}{n}, \ldots, \frac{1}{n}\right) = H\left(\frac{k}{n}, \frac{n-k}{n}\right) + \frac{k}{n}\,H\underbrace{\left(\frac{1}{k}, \ldots, \frac{1}{k}\right)}_{k\text{ 个}} + \frac{n-k}{n}\,H\underbrace{\left(\frac{1}{n-k}, \ldots, \frac{1}{n-k}\right)}_{n-k\text{ 个}}

更一般地，对任意分布，粗粒化后再细化的不确定性之和等于直接计算的不确定性：

H(p1,…,pn)=H(p1+p2, p3,…,pn)+(p1+p2) H ⁣(p1p1+p2,p2p1+p2)H(p_1,\ldots,p_n) = H(p_1+p_2,\, p_3,\ldots,p_n) + (p_1+p_2)\,H\!\left(\frac{p_1}{p_1+p_2},\frac{p_2}{p_1+p_2}\right)

分两步获得的信息量，等于一步获得的信息量。

推导过程

第一步：确定 f(n) 的形式

由公理 3，对均匀分布 n=kmn = km（k,mk, m 为正整数），将 kmkm 个等概率事件先分成 kk 组，每组 mm 个：

f(km)=f(k)+f(m)f(km) = f(k) + f(m)

这是经典的柯西函数方程：f(km)=f(k)+f(m)f(km) = f(k) + f(m)。

结合公理 1（连续性）和公理 2（严格单调递增），其唯一解为：

f(n)=Clog⁡n,C>0\boxed{f(n) = C \log n, \quad C > 0}

证明要点：令 g(x)=f(ex)g(x) = f(e^x)，则 g(x+y)=g(x)+g(y)g(x+y)=g(x)+g(y)，连续解唯一为 g(x)=Cxg(x)=Cx，故 f(n)=Clog⁡nf(n)=C\log n。

第二步：从均匀分布推广到有理数概率

设 pi=niNp_i = \frac{n_i}{N}，其中 nin_i 为正整数，N=∑iniN = \sum_i n_i。

考虑将 NN 个等概率事件分组：第 ii 组有 nin_i 个。由公理 3：

f(N)=H(p1,…,pk)+∑i=1kpi⋅f(ni)f(N) = H(p_1, \ldots, p_k) + \sum_{i=1}^k p_i \cdot f(n_i)

即：

Clog⁡N=H(p1,…,pk)+∑i=1kpi⋅Clog⁡niC\log N = H(p_1,\ldots,p_k) + \sum_{i=1}^k p_i \cdot C\log n_i

解出 HH：

H(p1,…,pk)=Clog⁡N−C∑i=1kpilog⁡niH(p_1,\ldots,p_k) = C\log N - C\sum_{i=1}^k p_i \log n_i

=C∑i=1kpilog⁡N−C∑i=1kpilog⁡ni= C\sum_{i=1}^k p_i \log N - C\sum_{i=1}^k p_i \log n_i

=−C∑i=1kpilog⁡niN= -C\sum_{i=1}^k p_i \log \frac{n_i}{N}

H(p1,…,pk)=−C∑i=1kpilog⁡pi\boxed{H(p_1,\ldots,p_k) = -C\sum_{i=1}^k p_i \log p_i}

第三步：推广到实数概率

对任意实数概率 pi∈[0,1]p_i \in [0,1]，取有理数序列 pi(m)→pip_i^{(m)} \to p_i，由公理 1（连续性）：

H(p1(m),…,pk(m))→H(p1,…,pk)H(p_1^{(m)}, \ldots, p_k^{(m)}) \to H(p_1, \ldots, p_k)

而左边对所有有理点均等于 −C∑pi(m)log⁡pi(m)-C\sum p_i^{(m)} \log p_i^{(m)}，取极限得结论对全体实数概率成立。

最终结论

满足三条公理的函数唯一（至多相差正常数 CC）：

H(p1,…,pn)=−C∑i=1npilog⁡pi\boxed{H(p_1, \ldots, p_n) = -C \sum_{i=1}^n p_i \log p_i}

  • 取 C=1C=1，对数底为 2 → 单位 bit
  • 取 C=1C=1，对数底为 ee → 单位 nat
  • 常数 CC 的选取仅影响单位，不影响结构

性质

  • concave

∂H(X)∂pi=−log⁡bpi−1log⁡b∂2H(X)∂pi2=−1pilog⁡b\begin{aligned} \frac{\partial H(X)}{\partial p_i} &= -\log_b p_i - \frac{1}{\log b}\\ \frac{\partial^2 H(X)}{\partial p_i^2} &= -\frac{1}{p_i\log b} \end{aligned}

b>1b > 1，所以是concave的。

  • 0≤H(X)≤log⁡∣X∣0\leq H(X)\leq \log\left| X\right|

f(x)=−xlog⁡xf(x) = -x\log x是concave的，所以说

H(X)=−∑pilog⁡pi=∑f(pi)≤∣X∣f(∑pi∣X∣)=−∣X∣1∣X∣log⁡1∣X∣=log⁡∣X∣\begin{aligned} H(X) &= -\sum p_i\log p_i\\ &= \sum f(p_i) \\ &\leq \left|X\right|f(\frac{\sum p_i}{\left|X\right|})\\ &= -\left|X\right|\frac{1}{\left|X\right|}\log \frac{1}{\left|X\right|}\\ &= \log \left|X\right| \end{aligned}

当且仅当均匀分布取等。

Joint Entropy

H(X,Y)=−∑p(x,y)log⁡p(x,y)H(X, Y) = -\sum p(x, y)\log p(x, y)

可以得到：

  • H(X,X)=H(X)H(X, X) = H(X)；
  • 如果X,YX, Y独立，H(X,Y)=H(X)+H(Y)H(X, Y) = H(X) + H(Y)。

可以定义一般的Joint Entropy：

H(X1,X2,⋯ ,Xn)=−E[log⁡p(X1,X2,⋯ ,Xn)]H(X_1, X_2, \cdots, X_n) = -\mathbf E[\log p(X_1, X_2, \cdots, X_n)]

Conditional Entropy

H(X∣Y)=−E[log⁡p(X∣Y)]H(X\mid Y) = -\mathbf E[\log p(X\mid Y)]

可以得到

H(X∣Y)+H(Y)=−E[log⁡p(X∣Y)]−E[log⁡p(Y)]=−E[log⁡p(X,Y)]=H(X,Y)\begin{aligned} H(X\mid Y) + H(Y) &= -\mathbf E[\log p(X\mid Y)] - \mathbf E[\log p(Y)] \\ &= -\mathbf E[\log p(X, Y)] \\ &= H(X, Y) \end{aligned}

Zero Entropy

如果H(Y∣X)=0H(Y\mid X) = 0，则YY是关于XX的函数。

Kullback-Leibler (KL) distance (Relative Entropy)

对于总体XX的两个概率密度分布p(x)p(x)和q(x)q(x)，定义KL散度为

D(p∥q)=∑p(x)log⁡p(x)q(x)D(p\parallel q) = \sum p(x)\log \frac{p(x)}{q(x)}

KL散度具有非对称性。

意义：如果用分布qq来近似分布pp，额外还需要的平均比特数，xx的信息量是log⁡p(x)\log p(x), 所以是∑p(x)[log⁡p(x)−log⁡q(x)]\sum p(x)[\log p(x) - \log q(x)]。

Mutual Information

I(X;Y)=∑x∑yp(x,y)log⁡p(x,y)p(x)p(y)=D(p(x,y)∥p(x)p(y))\begin{aligned}I(X; Y) &= \sum_x\sum_y p(x, y)\log \frac{p(x, y)}{p(x)p(y)}\\ &= D(p(x, y) \parallel p(x)p(y)) \end{aligned}

意义：测量完YY，XX的信息减少了多少。

又意义：用p(x)p(y)p(x)p(y)来拟合p(x,y)p(x, y)（假设独立），会损失多少信息。

所以说：

H(X)−H(X∣Y)=−∑p(x,y)log⁡p(x)p(x,y)p(y)=I(X;Y)H(X) - H(X\mid Y) = -\sum p(x,y)\log{\frac{p(x)}{\frac{p(x,y)}{p(y)}}} = I(X;Y)

也有

H(X)+H(Y)−H(X,Y)=−∑p(x)log⁡p(x)−∑p(y)log⁡p(y)+∑p(x,y)log⁡p(x,y)=−∑p(x,y)log⁡p(x)p(y)p(x,y)=I(X,Y)\begin{aligned} H(X) + H(Y) - H(X, Y) &= -\sum p(x)\log p(x) - \sum p(y)\log p(y) + \sum p(x, y)\log p(x, y)\\ &= -\sum p(x, y)\log \frac{p(x)p(y)}{p(x, y)}\\ &= I(X, Y) \end{aligned}

Conditional Mutual Information

定义为

I(X;Y∣Z)=H(X∣Z)−H(X∣Y,Z)I(X; Y \mid Z) = H(X \mid Z) - H(X \mid Y, Z)

Conditional Relative Entropy

定义为

D(p(y∣x)∥q(y∣x))=∑p(x)∑p(y∣x)log⁡p(y∣x)q(y∣x)D(p(y \mid x) \parallel q(y \mid x)) = \sum p(x) \sum p(y\mid x)\log \frac{p(y\mid x)}{q(y\mid x)}

优先级

",">";">"∣""," > ";" > "\mid"

Chain Rule

H(X,Y)=H(X∣Y)+H(Y)H(X, Y) = H(X \mid Y) + H(Y)

H(X1,X2,⋯ ,Xn)=H(Xn)+H(Xn∣X1,X2,⋯ ,Xn−1)=H(X1)+∑i=2nH(Xi∣X1,X2,⋯ ,Xi−1)≤∑i=1nH(Xi)\begin{aligned} H(X_1, X_2, \cdots, X_n) &= H(X_n) + H(X_n\mid X_1, X_2, \cdots, X_{n - 1})\\ &= H(X_1) + \sum_{i=2}^n H(X_i\mid X_1, X_2, \cdots, X_{i-1})\\ &\leq \sum_{i=1}^n H(X_i) \end{aligned}

I(X1,X2;Y)=H(X1,X2)−H(X1,X2∣Y)=H(X1)+H(X2∣X1)−H(X1∣Y)−H(X2∣X1,Y)=I(X1;Y)+I(X2;Y∣X1)\begin{aligned} I(X_1, X_2; Y) &= H(X_1, X_2) - H(X_1, X_2 \mid Y)\\ &= H(X_1) + H(X_2 \mid X_1) - H(X_1\mid Y) - H(X_2\mid X_1, Y)\\ &= I(X_1; Y) + I(X_2; Y\mid X_1) \end{aligned}

I(X1,X2,⋯ ,Xn;Y)=I(X1;Y)+∑i=2nI(Xi∣Y,X1,X2,⋯ ,Xi−1)\begin{aligned} I(X_1, X_2, \cdots, X_n; Y) = I(X_1; Y) + \sum_{i=2}^n I(X_i\mid Y, X_1, X_2, \cdots, X_{i-1}) \end{aligned}

Markov Chain

如果p(x,y,z)=p(z∣y)p(y∣x)p(x)p(x, y, z) = p(z\mid y)p(y\mid x)p(x)，那么称X→Y→ZX\rightarrow Y\rightarrow Z是一个马尔可夫链。

性质：

  • p(x∣y)p(z∣y)=p(x∣y)p(x,y,z)/p(x,y)=p(x,y,z)/p(y)=p(x,z∣y)p(x\mid y)p(z\mid y)=p(x\mid y)p(x, y, z)/p(x, y)=p(x,y,z)/p(y)=p(x,z\mid y)，XX和ZZ在YY的条件下独立  ⟺  X→Y→Z\iff X\rightarrow Y\rightarrow Z；
  • 由前一个性质可知，X→Y→Z  ⟺  Z→Y→XX\rightarrow Y\rightarrow Z\iff Z\rightarrow Y\rightarrow X；
  • 如果X→Y→ZX\rightarrow Y\rightarrow Z，那么I(X;Y)≥I(X;Z)I(X;Y)\geq I(X; Z);

证明：I(X;Y,Z)=I(X;Y)+I(X;Z∣Y)=I(X;Z)+I(X;Y∣Z)I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y)=I(X;Z)+I(X;Y\mid Z),其中I(X;Z∣Y)=0I(X;Z\mid Y)=0，所以不等式成立。

多元互信息

I(X;Y;Z)=I(X;Y)−I(X;Y∣Z)=I(X;Y)−I(X,Z;Y)+I(Z;Y)=I(Y;Z)−I(Y;Z∣X)=I(X;Z)−I(X;Z∣Y)\begin{aligned} I(X;Y;Z) &= I(X;Y) - I(X;Y\mid Z)\\ &= I(X;Y) - I(X, Z;Y) + I(Z; Y)\\ &= I(Y; Z) - I(Y; Z\mid X)\\ &= I(X; Z) - I(X; Z\mid Y) \end{aligned}

可以为正或者负。

如果X→Y→ZX\rightarrow Y\rightarrow Z，则

I(X;Y;Z)=I(X;Z)−I(X;Z∣Y)=I(X;Z)≥0\begin{aligned} I(X;Y;Z) &= I(X;Z) - I(X;Z\mid Y)\\ &= I(X;Z) \geq 0 \end{aligned}