从熵到费诺不等式-笔记

4 Oct 2021

从熵到费诺不等式

熵，联合熵，条件熵

用熵来描述分布的不确定性，熵定义为自信息的期望：

\[H(X)=-\sum_{x \in \mathcal{X}} p(x)log_2p(x)\]

此处以2为底，单位为比特(bit)。其中\(-log_2p(x)\)即为事件\(x\)发生的自信息。

熵有一些性质：

\[H(X) \geq 0\]
\(H_b(X) = (log_ba)H_a(X)\) 这个性质说明熵可以从一个基换到的另一个基，本文默认为以2为底。

对于多元分布，有联合熵和条件熵，其定义分别为：

\[\begin{aligned}H(X,Y)=-\sum_{x \in \mathcal{X}}\sum_{y \in \mathcal{Y}}p(x,y)log\ p(x,y) \end{aligned}\] \[\begin{aligned}H(Y|X)&=\sum_{x \in \mathcal{X}}p(x)H(Y|X=x) \\&=-\sum_{x \in \mathcal{X}}p(x)\sum_{y \in \mathcal{Y}}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{aligned}\]

由于条件概率的公式：

\[p(x,y)=p(x)p(y|x)\]

所以有链式法则：

\[\begin{aligned}H(X,Y)=H(X) + H(Y|X)\end{aligned}\tag{1.1}\]

相对熵，交叉熵，互信息

相对熵也叫KL散度，用于描述两个分布间的距离：

\[\begin{aligned}D(p||q)=\sum_{x \in \mathcal{X}}p(x)log\ \frac{p(x)}{q(x)}\end{aligned}\tag{2.1}\]

一般，相对熵测量假设分布\(q\)拟合真实分布\(p\)的无效性，相对熵越大，两个分布间距离越大，分布\(q\)拟合真实分布\(p\)越无效。

特殊情况规定\(0log\ \frac{0}{0}=0,\ 0log\ \frac{0}{q}=0,\ 0log\ \frac{p}{0}=\infty\)

将相对熵拆开：

\[\begin{aligned}D(p||q)=\sum_{x \in \mathcal{X}}p(x)log\ p(x) - \sum_{x \in \mathcal{X}}p(x)log\ q(x) \end{aligned}\]

第一项是真实分布\(p\)的熵，在机器学习中，一般假设这一部分不变。则第二项即为交叉熵:

\[\begin{aligned}CrossEntrophy(p, q)=-\sum_{x \in \mathcal{X}}p(x)log\ q(x)\end{aligned}\]

交叉熵即可用于设计分类问题的损失函数。

互信息定义为联合分布\(p(x,y)\)与乘积分布\(p(x)p(y)\)之间的相对熵

\[\begin{aligned}I(X;Y)&=\sum_{x \in \mathcal{X}}\sum_{y \in \mathcal{Y}}p(x,y)log\ \frac{p(x,y)}{p(x)p(y)}\\&=D(p(x,y)||p(x)p(y))\end{aligned}\tag{2.2}\]

推导可得：

\[I(X;Y)=H(Y)-H(Y|X)\]
\[I(X;Y)=H(X)-H(X|Y)\]
\[\begin{aligned}I(X;Y)=H(X)+H(Y)-H(X,Y)=I(Y;X)\end{aligned}\tag{2.3}\]
\(I(X,X)=H(X)-H(X\vert X)=H(X)\) 据此，熵也叫分布的自信息。

熵，互信息，联合熵，条件熵之间的关系如下。

信息表示不确定性。互信息\(I(X;Y)\)表示\(Y\)对\(X\)的不确定性的减少量，\(H(X\|Y)\)表示引入\(Y\)后，\(X\)剩余的不确定性。\(H(X)=H(X\|Y)+I(X;Y)\)。互信息\(I(Y;X)\)表示\(X\)对\(Y\)的不确定性的减少量，\(H(Y\|X)\)表示引入\(X\)后，\(Y\)剩余的不确定性。\(H(Y)=H(Y\|X)+I(Y;X)\)。

熵的上界

Jensen’s Inequality
\[Ef(X)\geq f(EX)\]
Information inequality
\[D(p||q)\geq0\]
Proof:
\[\begin{aligned} \because -D(p||q)&=\sum_{x \in \mathcal{X}}p(x)log\ \frac{q(x)}{p(x)}\\&\leq log\sum_{x \in \mathcal{X}}p(x)\frac{q(x)}{p(x)}, by\ Jensen's Inequality\\&=0 \\ \therefore D(p||q)&\geq 0,D(p||q)=0\ iff\ p=q\end{aligned}\]
由此可推知，\(I(X;Y)\geq 0\)
\[\begin{aligned}H(X)\leq log|\mathcal{X}|\end{aligned}\tag{3.1}\]
Proof:

设\(u(x)=\frac{1}{\|\mathcal{X}\|}\)是在\(\mathcal{X}\)的均匀分布，则：
\[\begin{aligned}\because D(p||u)=\sum p(x)log\ \frac{p(x)}{u(x)}=log|\mathcal{X}|-H(X)\geq 0 \\ \therefore H(X)\leq log|\mathcal{X}|,H(X)=log|\mathcal{X}|\ iff\ X是\mathcal{X}上的均匀分布\end{aligned}\]

由此，可知熵的上界是\(log\|\mathcal{X}\|\)，达成这个上界的条件是在\(\mathcal{X}\)上的均匀分布。此时分布最无序，类比于热力学中的熵，体系最混乱的时候熵最大。

链式法则

条件概率的链式法则：

\[\begin{aligned}p(x_1, x_2, ..., x_n)&=\prod_{i=1}^np(x_i|x_{i-1}, ..., x_1)\\&=p(x_1)p(x_2|x_1)p(x_3|x_2, x_1)...p(x_n|x_{n-1}, ...,x_2, x_1)\end{aligned}\]

联合熵的链式法则：

\[\begin{aligned}H(X_1, X_2, ..., X_n)&=\sum_{i=1}^nH(X_i|X_{i-1}, ..., X_1)\\&=H(X_1)+H(X_2|X_1)+H(X_3|X_2,X_1)+...+H(X_n|X_{n-1}, ...,X_2,X_1)\end{aligned}\tag{4.1}\]

定义 by Conditional mutual information - Wikipedia：条件互信息\(I(X;Y\|Z)\)被定义为\(P_{(X,Y)\|Z}\)与\(P_{X\|Z}\)和\(P_{Y\|Z}\)的乘积的KL散度(相对熵)的期望(相对于\(Z\))，即

\[I(X;Y|Z)=\int_\mathcal{Z}D_{KL}(P_{(X,Y)|Z}||P_{X|Z}P_{Y|Z})dP_Z\]

由定义可以看出\(I(X;Y\|Z)\)可以读作在\(Z\)的条件下，\(X\)和\(Y\)的互信息，所以自然的有\(I(X;Y\|Z)=I(Y;X\|Z)\)。离散条件下，条件互信息定义的公式及简化公式为：

\[\begin{aligned}I(X;Y|Z)&=\sum_{z \in \mathcal{Z}}p_Z(z)\sum_{y \in \mathcal{Y}}\sum_{x \in \mathcal{X}}p_{X,Y|Z}(x, y|z)log\frac{p_{X,Y|Z}(x, y|z)}{p_{X|Z}(x|z)p_{Y|Z}(y|z)}\\&=\sum_{z \in \mathcal{Z}}\sum_{y \in \mathcal{Y}}\sum_{x \in \mathcal{X}}p_{X,Y,Z}(x, y, z)log\frac{p_Z(z)p_{X,Y,Z}(x, y, z)}{p_{X,Z}(x, z)p_{Y,Z}(y,z)}\end{aligned}\]

条件互信息与熵的关系：

\[I(X;Y|Z)=H(X|Z)+H(Y|Z)-H(X,Y|Z)\tag{4.2}\]
\[I(X;Y|Z)=H(X|Z)-H(X|Y,Z)\tag{4.3}\]
\[I(X;Y|Z)=H(Y|Z)-H(Y|X,Z)\tag{4.4}\]

与互信息的公式相比只是在每一项加了条件\(Z\)。

\[\begin{aligned}I(X;Y,Z)=I(X;Y|Z)+I(X;Z)\end{aligned}\tag{4.5}\]

需要结合下图理解。

互信息的链式法则:

\[\begin{aligned}I(X_1,X_2,...,X_n; Y)&=\sum_{i=1}^nI(X_i;Y|X_{i-1}, X_{i-2},...,X_{1})\\&=I(X_1;Y)+I(X_2;Y|X_1)+I(X_3;Y|X_2,X_1)+...+I(X_n;Y|X_{n-1},...,X_1)\end{aligned}\tag{4.4}\]

这个链式法则结合上图以及上一个公式更好理解。如果求一堆X和Y的互信息，那先求第一个\(X_1\)与\(Y\)的互信息，即\(I(X_1;Y)\)，然后求排除掉\(X_1\)后（也即在\(X_1\)的条件下），\(X_2\)与\(Y\)的互信息，即\(I(X_2;Y\|X_1)\)。以此类推得到上述链式法则。关于此法则的证明如下：

Proof:

\[\begin{aligned}I(X_1,X_2,...,X_n;Y)&=H(X_1,X_2,...,X_n)-H(X_1,X_2,...,X_n|Y)\\&=\sum_{i=1}^nH(X_i|X_{i-1},...,X_1)-\sum_{i=1}^nH(X_i|X_{i-1},...,X_1,Y)、根据公式(4.1)\\&=I(X_i;Y|X_{i-1},...,X_1),\ 根据公式(4.3)\end{aligned}\]

马尔科夫链与数据处理不等式

马尔可夫链的下一状态的概率分布只由当前分布决定。用\(X\rightarrow Y \rightarrow Z\)表示随机变量\(X,Y,Z\)构成一条马尔科夫链，\(p(z\|x)=p(z)\)。

数据处理不等式给出：

\[\begin{aligned}I(X;Y)\geq I(X;Z)\end{aligned}\tag{5.1}\]

Proof:

\[\begin{aligned}I(X;Y,Z)&=I(X;Z)+I(X;Y|Z)\\&=I(X;Y)+I(X;Z|Y)\end{aligned}\]

因为\(Z\)与\(X\)相互独立，所以\(I(X;Z\|Y)=0\)。

因为\(I(X;Y\vert Z)\geq 0\)

所以\(I(X;Y)\geq I(X;Z)\)

“话越传越离谱”。

Fano’s Inequality

假设我们想估计随机变量\(X\)，我们观察到和\(X\)相关的随机变量\(Y\)。根据\(Y\)，我们计算得到\(X\)的估计量\(\widehat{X}=g(Y)\)，\(g(Y)\)可以是含有随机性的函数。\(X \rightarrow Y \rightarrow \widehat{X}\)构成马尔科夫链，我们希望估计\(X \neq \widehat{X}\)的概率下限（也就可以估计准确率的上限）。

定义错误率为\(P_e=Pr({X \neq \widehat{X}})\)。则费诺不等式为：

\[H(P_e)+P_elog|\mathcal{X}|\geq H(X|\widehat{X})\geq H(X|Y)\tag{6.1}\]

\(H(P_e)\)是一个0-1分布的熵，由熵的上界公式(3.1)，\(H(P_e)\leq log2=1\)。所以该公式也可以弱化为：

\[\begin{aligned}1+P_elog|\mathcal{X}|&\geq H(X|Y)\\P_e &\geq \frac{H(X|Y)-1}{log|\mathcal{X}|}\end{aligned}\tag{6.2}\]

Proof:

首先证明公式6.1左边的不等号。定义一个估计错误的事件的随机变量：

\[\begin{aligned}E=\left\{\begin{matrix} 1& if\ \widehat{X}\neq X\\ 0& if\ \widehat{X} = X \end{matrix}\right.\end{aligned}\]

根据熵的链式法则：

\[\begin{aligned}H(E,X|\widehat{X})&=H(X|\widehat{X})+H(E|X,\widehat{X})\\&=H(E|\widehat{X})+H(X|E,\widehat{X})\end{aligned}\tag{6.3}\]

其中

\[H(E\vert X,\widehat{X})=0\]
\[H(E\vert \widehat{X}) \leq H(E)=H(P_e)\]
\[\begin{aligned}H(X|E,\widehat{X})&=Pr(E=0)H(X|\widehat{X},E=0)+Pr(E=1)H(X|\widehat{X},E=1)\\&=(1-P_e)0+P_eH(X|\widehat{X},E=1)\\&\leq P_eH(X)\\&\leq P_elog|\mathcal{X}|\end{aligned}\]

将上述三个公式代入6.3，有：

\[H(X|\widehat{X})\leq H(P_e)+P_elog|\mathcal{X}|\tag{6.4}\]

又因为\(X \rightarrow Y \rightarrow \widehat{X}\)构成了一个马尔科夫链，根据数据处理不等式：

\[\begin{aligned}\because I(X;Y) &\geq I(X,\widehat{X})\\\therefore H(X)-H(X|Y) &\geq H(X)-H(X|\widehat{X})\\\therefore H(X|Y)&\leq H(X|\widehat{X})\end{aligned}\]

带入公式6.4：

\[H(P_e)+P_elog|\mathcal{X}|\geq H(X|\widehat{X})\geq H(X|Y)\]

即为费诺不等式。

algorithm