Entropy, relative entropy and mutual information

文章目录

EntropyJoint EntropyConditional EntropyChain ruleMutual InformationRelative Entropy Chain RulesChain Rule for EntropyChain Rule for Mutual InformationConditional Mutual Information Chain Rule for Relative Entropy Jensen's InequalityProperties Log Sum InequalityData-Processing InequalitySufficient StatisticsStatistics and Mutual InformationSufficient Statistics and Compression

Entropy, relative entropy and mutual information.

Entropy

$$H(X)=-\sum _{x}p(x)\log p(x),$$ 熵非负, 且当且仅当$X$确定性的时候为有最小值0, 即$P(X=x_0)=1$.

Proof:

由$\log$的凹性可得 $$\begin{array}{ll}H(X)& =-{\sum }_{x}p(x)\log p(x)\\ & ={\sum }_{x}p(x)\log \frac{1}{p(x)}\\ & \ge \log 1=0.\end{array}$$

Joint Entropy

$$H(X,Y):=-{\mathbb{E}}_{p(x,y)}[\log p(x,y)]=\sum _{x\in \mathcal{X}}\sum _{y\in \mathcal{Y}}p(x,y)\log p(x,y).$$

Conditional Entropy

$$\begin{array}{ll}H(Y|X)& =-{\mathbb{E}}_{p(x)}[H(Y|X=x)]\\ & =-{\sum }_{x\in \mathcal{X}}p(x)H(Y|X=x)\\ & =-{\sum }_{x\in \mathcal{X}}{\sum }_{y\in \mathcal{Y}}p(x)p(y|x)\log p(y|x)\\ & =-{\sum }_{x\in \mathcal{X}}{\sum }_{y\in \mathcal{Y}}p(x,y)\log p(y|x).\end{array}$$

注意 $H(Y|X)$ 和 $H(Y|X=x)$ 的区别.

Chain rule

$$H(X,Y)=H(X)+H(Y|X).$$

proof:

根据$p(y|x)=\frac{p(x,y)}{p(x)}$以及上面的推导可知: $$\begin{array}{ll}H(Y|X)& =H(X,Y)+{\sum }_{x\in \mathcal{X}}{\sum }_{y\in \mathcal{Y}}p(x,y)\log p(x)\\ & =H(X,Y)-H(X).\end{array}$$

推论: $$H(X,Y|Z)=H(X|Z)+H(Y|X,Z).$$

$$\begin{array}{ll}H(Y|X,Z)& ={\mathbb{E}}_{x,z}[H(Y|x,z)]\\ & =-{\sum }_{x,z}p(x,z)p(y|x,z)\log p(y|x,z)\\ & =-{\sum }_{x,z}p(x,y,z)[\log p(x,y|z)-\log p(x|z)]\\ & ={\mathbb{E}}_{z}H(X,Y|z)-{\mathbb{E}}_{z}H(X|z)=H(X,Y|Z)-H(X|Z).\end{array}$$

Mutual Information

$$I(X;Y)=H(X)-H(X|Y)=\sum _{x\in \mathcal{X}}\sum _{y\in \mathcal{Y}}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}$$

$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=I(Y;X)=H(X)+H(Y)-H(X,Y)\ge 0$

$I(X,X)=H(X)$

Relative Entropy

$$D(p\Vert q):={\mathbb{E}}_p(\log \frac{p(x)}{q(x)})=\sum _{x\in \mathcal{X}}p(x)\log \frac{p(x)}{q(x)}.$$

Chain Rules

Chain Rule for Entropy

设$(X_1,X_2,\dots ,X_n)\sim p(x_1,x_2,\dots ,x_n)$: $$H(X_1,X_2,\dots ,X_n)=\sum _{i-1}^{n}H(X_i|X_{i-1},\dots ,X_1).$$

proof:

归纳法 + $H(X,Y)=H(X)+H(Y|X)$.

Chain Rule for Mutual Information

Conditional Mutual Information

定义: $$I(X;Y|Z):=H(X|Z)-H(X|Y,Z)={\mathbb{E}}_{p(x,y,z)}\log \frac{p(X,Y|Z)}{p(X|Z)p(Y|Z)}.$$

性质:

$$I(X_1,X_2,\dots ,X_n;Y)=\sum _{i=1}^{n}I(X_i;Y|X_{i-1},\dots ,X_1).$$ proof:

$$\begin{array}{ll}I(X_1,X_2,\dots ,X_n;Y)& =H(X_1,\dots ,X_n)+H(Y)-H(X_1,\dots ,X_n;Y)\\ & =H(X_1,\dots ,X_{n-1})+H(X_n|X_1,\dots ,X_{n-1})+H(Y)-H(X_1,\dots ,X_n;Y)\\ & =I(X_1,X_2,\dots ,X_{n-1};Y)+H(X_n|X_1,\dots ,X_{n-1})-H(X_n|X_1,\dots ,X_{n-1};Y)\\ & =I(X_1,X_2,\dots ,X_{n-1};Y)+I(X_n;Y|X_1,\dots ,X_{n-1}).\end{array}$$

Chain Rule for Relative Entropy

定义: $$\begin{array}{ll}D(p(y|x)\Vert q(y|x))& :={\mathbb{E}}_{p(x,y)}[\log \frac{p(Y|X)}{q(Y|X)}]\\ & ={\sum }_{x}p(x){\sum }_{y}p(y|x)\log \frac{p(y|x)}{q(y|x)}.\end{array}$$

性质: $$D(p(x,y)\Vert q(x,y))=D(p(x)\Vert q(x))+D(p(y|x)\Vert q(y|x)).$$ proof: $$\begin{array}{ll}D(p(x,y)\Vert q(x,y))& ={\sum }_{x,y}p(x,y)\log \frac{p(x,y)}{q(x,y)}\\ & ={\sum }_{x,y}p(x,y)\log \frac{p(y|x)p(x)}{q(y|x)q(x)}\\ & ={\sum }_{x,y}[p(x,y)(\log \frac{p(y|x)}{q(y|x)}+\log \frac{p(x)}{q(x)})]\\ & =D(p(x)\Vert q(x))+D(p(y|x)\Vert q(y|x)).\end{array}$$

补充: $$D(p(x,y)\Vert q(x,y))=D(p(y)\Vert q(y))+D(p(x|y)\Vert q(x|y)).$$ 故, 当$p(x)=q(x)$的时候, 我们可以得到 $$D(p(x,y)\Vert q(x,y))=D(p(y|x)\Vert q(y|x))\ge D(p(y)\Vert q(y))$$

$D(p(y|x)\Vert q(y|x))=D(p(x,y)\Vert p(x)q(y|x))$

$D(p(x_1,x_2,\dots ,x_n)\Vert q(x_1,x_2,\dots ,x_m))={\sum }_{i=1}^{n}D(p(x_i|x_{i-1},\dots ,x_1)\Vert q(x_i|x_{i-1},\dots ,x_1))$

$D(p(y)\Vert q(y))\le D(p(y|x)\Vert q(y|x))$, $q(x)=p(x)$.

1, 2, 3的证明都可以通过上面的稍作变换得到.

Jensen’s Inequality

如果$f$是凸函数, 则 $$\mathbb{E}[f(X)]\ge f(\mathbb{E}[X]).$$

Properties

$D(p\Vert q)\ge 0$ 当且仅当$p=q$取等号.$I(X;Y)\ge 0$当且仅当$X,Y$独立取等号.$D(p(y|x)\Vert q(y|x))\ge 0$ (根据上面的性质)， 当且仅当$p(y|x)=q(y|x)$取等号, $p(x)>0$.$I(X;Y|Z)\ge 0$, 当且仅当$X,Y$条件独立.$H(X|Y)\le H(X)$, 当且仅当$X,Y$独立等号成立.$H(X_1,X_2,\dots ,X_n)\le {\sum }_{i=1}^{n}H(X_i)$, 当且仅当所有变量独立等号成立.

Log Sum Inequality

$D(p\Vert q)$ 关于$(p,q)$为凸函数, 即$\forall 0\le \lambda \le 1$: $$D(\lambda p_1+(1-\lambda )p_2\Vert \lambda q_1+(1-\lambda )q_2)\le \lambda D(p_1\Vert q_1)+(1-\lambda )D(p_2\Vert q_2).$$

此部分的证明, 一方面可以通过$p\log \frac{p}{q}$的凸性得到, 更有趣的证明是, 构造一个新的联合分布 $$p(x,c)=p_1\cdot \lambda +p_2\cdot (1-\lambda ),q(x,c)=q_1\cdot \lambda +q_2\cdot (1-\lambda ).$$ 即 $$\begin{gathered} p(x|c=0)=p_1,p(x|c=1)=p_2,q(x|c=0)=q_1,q(x|c=2)=q_2, \\ p(c=0)=q(c=0)=\lambda ,p(c=1)=q(c=1)=1-\lambda . \end{gathered}$$ 并注意到$D(p(y)\Vert q(y))\le D(p(y|x)\Vert q(y|x))$.

$H(X)=-{\sum }_{x\in \mathcal{X}}p(x)\log p(x)$是关于$p$的凹函数.$I(X,Y)={\sum }_{x,y}p(y|x)p(x)\log \frac{p(y|x)}{p(y)}$, 当固定$p(y|x)$的时候是关于$p(x)$的凹函数, 当固定$p(x)$的时候, 是关于$p(y|x)$的凸函数.

仅仅证明后半部分, 任给$p_1(y|x),p_2(y|x)$, 由于$p(x)$固定, 故$\forall 0\le \lambda \le 1$: $$\begin{gathered} p(x,y):=\lambda p_1(x,y)+(1-\lambda )p_2(x,y)=[\lambda p_1(y|x)+(1-\lambda )p_2(y|x)]p(x) \\ p(y):=\sum _{x}p(x,y)=\lambda \sum _x{p}_1(x,y)+(1-\lambda )\sum _x{p}_2(x,y) \\ q(x,y):=p(x)p(y)=\sum _{x}p(x,y)=\lambda p(x)\sum _x{p}_1(x,y)+(1-\lambda )p(x)\sum _x{p}_2(x,y)=:\lambda q_1(x,y)+(1-\lambda )q_2(x,y). \end{gathered}$$ 又 $$I(X,Y)=D(p(x,y)\Vert p(x)p(y))=D(p(x,y)\Vert q(x,y)),$$

因为KL散度关于$(p,q)$是凸函数, 所以$I$关于$p(y|x)$如此.

Data-Processing Inequality

数据$X\to Y\to Z$, 即$P(X,Y,Z)=P(X)P(Y|X)P(Z|Y)$ 比如$Y=f(X),Z=g(Y)$.

$$I(Y,Z;X)=I(X;Y)+I(X;Z|Y)=I(X;Z)+I(X;Y|Z),$$

又 $$\begin{gathered} I(X;Z|Y)=\sum _{x,y,z}p(x,y,z)\log \frac{p(x,z|y)}{p(x|y)p(z|y)}=\sum _{x,y,z}p(x,y,z)\log 1=0. \\ I(X;Y|Z)=\sum _{x,y,z}p(x,y,z)\log \frac{p(x|y)}{p(x|z)}\ge 0. \end{gathered}$$

故 $$\begin{gathered} I(X;Z)\le I(X;Y) \\ I(X;Y|Z)\le I(X;Y). \end{gathered}$$

Sufficient Statistics

Statistics and Mutual Information

一族概率分布$\{f_{\theta (x)}\}$

$X\sim f_{\theta }(x)$, $T(X)$为其统计量, 则 $$\theta \to X\to T(X)$$

故 $$I(\theta ;X)\ge I(\theta ;T(X))$$

Sufficient Statistics and Compression

充分统计量定义: 一个函数$T(X)$被称之为一族概率分布$\{f_{\theta }(x)\}$的充分统计量, 如果给定$T(X)=t$时$X$的条件分布与$\theta$无关, 即 $$f_{\theta }(x)=f(x|t)f_{\theta }(t)\Rightarrow \theta \to T(X)\to X\Rightarrow I(\theta ;T(X))\ge I(\theta ;X).$$ 此时, $I(\theta ;T(X))=I(\theta ;X)$.

最小充分统计量定义: 如果一个充分统计量$T(X)$与其余的一切关于$\{f_{\theta }(x)\}$的充分统计量$U(X)$满足 $$\theta \to T(X)\to U(X)\to X.$$