【课程笔记】中科大信息论（三）

熵的链式法则

\[\begin{aligned} H(X, Y) &=\mathrm{E}\left[\log \frac{1}{p(X, Y)}\right] \\ &=\mathrm{E}\left[\log \frac{1}{p(X) p(Y \mid X)}\right] \\ &=\mathrm{E}\left[\log \frac{1}{p(X)}+\log \frac{1}{p(Y \mid X)}\right] \\ &=\mathrm{E}\left[\log \frac{1}{p(X)}\right]+\mathrm{E}\left[\log \frac{1}{p(Y \mid X)}\right] \\ &=H(X)+H(Y \mid X) \end{aligned} \]

如果把求熵的负号写在外面，容易出错
理解三个变量的链式法则$p(x,y\mid z)=p(x\mid z)p(y\mid x,z)$

两边同乘$p(z)$，将$x,z$看成一个整体，就变成了二元的链式法则

\[p(y,x,z)=p(x,z)p(y|x,z) \]
取期望的时候一定要小心
- $\mathrm{E}_{X,Y}\left[\log \frac{1}{p(X)}\right]=H(X)$的计算方法
  1. 跳步骤的做法：因为内部只有$X$，所以期望下标不用写$Y$
    
    \[\mathrm{E}_{X,Y}\left[\log \frac{1}{p(X)}\right]=\mathrm{E}_{X}\left[\log \frac{1}{p(X)}\right]=H(X) \]
  2. 不跳步骤的做法：将连加符号拆开，$\sum_{x,y,z} = \sum_{x} \sum_{y}\sum_{z}$
    
    \[\begin{aligned} \mathrm{E}_{X,Y}\left[\log \frac{1}{p(X)}\right] &= \sum_{x,y}p(x,y)\log \frac{1}{p(X)} \\ &=\sum_{x}\left[\sum_{y}p(x,y)\right]\log \frac{1}{p(X)}\\ &=\sum_{x}p(x)\log \frac{1}{p(X)}\\ &= H(X) \end{aligned} \]
- $\mathrm{E}\left[\log \frac{1}{p(Y \mid X)}\right]$的计算注意，期望是同时对$X,Y$取的，不是$P(Y|X=x)$。不忘初心！

链式法则的一般形式

\[H\left(X_{1}, X_{2}, \ldots, X_{n}\right)=\sum_{i=1}^{n} H\left(X_{i} \mid X_{i-1}, \ldots, X_{1}\right) \]

藕断丝连

并不是单纯的链，除非是Markov否则有影响

感觉来自于条件概率的分步形式
当计算条件概率（条件熵）更简单时，相较于遍历不同取值的概率，可以降低工作量

条件熵的界$H(Y \mid X) \leq H(Y)$

依然使用做差+IT不等式证明
- 做差的方向：由于IT不等式是$\ln r\le r-1$，为了处理熵中的$\log$项，需要将对数放在左边，因此要做差找到$A-B\le 0$的形式
- IT不等式可以去除对数运算，便于计算期望
- 条件分布经常算不动，所以要乘回联合分布
  
  \[\frac{p(Y)}{p(Y\mid X)}=\frac{p(Y)p(X)}{p(Y\mid X)p(X)}=\frac{p(X)p(Y)}{p(X,Y)} \]
从不确定度的角度理解条件熵：增加条件后，不确定度只可能减少，因此条件熵≤无条件熵
变量间的关系（条件概率）比单独某个事件更值得研究

条件熵的推论

$H(Y \mid X, Z) \leq H(Y \mid Z)$
- 依然是做差+IT不等式，不过需要条件概率的拆分
  
  \[\begin{aligned} \mathrm{E}_{X,Y,Z}\left[\frac{p(Y\mid Z)p(X\mid Z)}{p(X,Y\mid Z)}\right] &= \sum_{x,y,z}p(x,y,z)\frac{p(y\mid z)p(x\mid z)}{p(x,y\mid z)} \\ &=\sum_{x,y,z}p(z)p(x,y\mid z)\frac{p(y\mid z)p(x\mid z)}{p(x,y\mid z)}\\ &=\sum_{x,y,z}p(z)p(x,y\mid z)\frac{p(y\mid z)p(x\mid z)}{p(x,y\mid z)}\\ &= \sum_{z}p(z)\sum_{y}\sum_{x}p(x\mid z)p(y\mid z)\\ &= 1 \end{aligned} \]
  条件概率求和时
  - $\sum_{y}p(y\mid z)=1$
  - $\sum_{z,y}p(y\mid z)=\mid\mathcal{Z}\mid$
- 条件独立和独立一般不能互推，而独立的条件一般比较强
$H\left(X_{1}, X_{2}, \ldots, X_{n}\right) \leq H\left(X_{1}\right)+H\left(X_{2}\right)+\ldots+H\left(X_{n}\right)$

在相互独立时取等：$X_1$与$X_2$独立，$X_3$与$X_1,X_2$独立，则$p(X_1X_2X_3)=p(X_1X_2)p(X_3)=p(X_1)p(X_2)p(X_3)$
当变量间的关系是函数关系
- $H(Y\mid X) = 0$ holds if there is a mapping $f$ such that $Y = f (X)$
  
  $p(y\mid x)=0~ \text{or}~1$，所以有$H(f (X)\mid X) = 0$
  
  充分非必要条件
- $H(f (X)) \le H(X)$ holds in general, and equality holds iff $ f$ is a bijection.
  
  两种证明方法
  - 用定义，核心在于离散的映射关系，值域不会比定义域大
    
    当是双射的时候，一一对应，因此熵等；
    
    当不是双射的时候，存在概率的合并，以二元输入$p_i,p_j$合并成$(p_i+p_j)$为例，有
    
    \[\begin{aligned} h(p_i,p_j) &= -p_i\log(p_i)-pj\log(p_j) \\ &> -p_i\log(p_i+p_j)-p_j\log(p_i+p_j) \\ &= -(p_i+p_j)\log(p_i+p_j) \\ &= h(p_i+p_j) \end{aligned} \]
    由于概率合并过后，对数更大，取负后熵更小
  - 从两个方向用链式法则展开
    
    \[\begin{aligned} H(X,f(X)) &= H(X)+H(f(X)\mid X) \\ &=H(f(X))+H(X\mid f(X)) \end{aligned} \]
    因此第二个等号两边可以看作天平。
    
    其中$H(f(X)\mid X)=0,H(X\mid f(X))\ge 0$，所以$H(X)$更大；同时当且仅当$H(X\mid f(X))= 0$时取等，也就是双射

理论资料

【课程笔记】中科大信息论（三）

熵的链式法则

链式法则的一般形式

条件熵的界\(H(Y \mid X) \leq H(Y)\)

条件熵的推论

相关

标签