[Information Theory] 复习时的一些心得理解
[Information Theory] 复习时的一些心得
注：此篇笔记对应的教材是《信息论基础》，对应英文版是《Elements of Information Theory》。此篇笔记并不详细阐述内容，而是跳跃性地讲述一些我可能不怎么正确的感受。
Chapter 2
一些定义
信息熵、联合熵、条件熵
对信息熵的定义的理解：
为什么要用log？
对于某个概率为p的东西，我们想找一个东西描述它的信息，要满足以下条件：
非负
如果概率是1，信息量为0
函数连续(这样比较好)
如果两件事独立，一起发生的信息是单独发生的信息之和
这样就可以得出\(I(p) \propto log\frac{1}{p}\)
知道这个之后，\(H\)的定义是怎么出来的？
- 刚才讨论的是对于\(p\)的，对于\(H\)，就是看一个随机变量，它具有一定的概率分布，我们要求它的信息。那么显然就可以理解为它对于刚在给定概率下信息的期望(相当于求个和或者说积个分，把每个\(p\)下贡献的信息累加起来)
- 因此我们有了
\[ H(X) = \mathbb{E}_plog\frac{1}{p(x)} \]
理解了上面所说，联合熵、条件熵也就不难理解了，不过是看联合概率、条件概率罢了
信息熵的链式法则
\[ H(X_1, X_2, \cdots ,X_n) = \sum_{i=1}^nH(X_i|X_{i-1}, \cdots, X_1) \]
顺便，互信息的链式法则：\(I(X_1, \cdots , X_n;Y) = \sum_{i=1}^n I(X_i;Y|X_{i-1}, \cdots, X_1)\)
对于Chain rule的理解：
- 理解一下\(H(X,Y) = H(X) + H(Y|X)\)即可
- 想看看\(X, Y\)的信息。我们先知道了\(X\)的信息，此时由于\(X\)、\(Y\)之间可能存在一定的相关性，我们对\(X\)已经有了一点点的了解，剩下的关于\(X, Y\)的信息即为\(H(X|Y)\)
- 跟同学交流时，他说有点像是线性代数中的Cramer法则？就好像分解成一些正交空间一样。有点感觉。
根据上面的第二条，似乎互信息用\(I(X,Y) = H(X) - H(X|Y)\)来表示是很显然的一件事了
KL散度（相对熵）
首先我们看看公式 \[ D(p||q) = \sum_{x\in \mathcal{X}}p(x)log\frac{p(x)}{q(x)} =\mathbb{E}_plog\frac{p(X)}{q(X)} \] 为了延续上面的理解方式，可以写成 \[ D(p||q) = \mathbb{E}_p(log\frac{1}{q(X)}-log\frac{1}{p(X)}) \] E中的第一项似乎是在一个给定值下q的信息，第二项是p的信息，好像就是信息差。而这件事是对p的期望，似乎是从p的角度看待这件事的一般，从p的角度看两者的差距。
在网上找到了一种我觉得很妙的解释：
假设P(X=0)=0.8，P(X=1)=0.2，那么我们可以用0来编码消息0，用10来编码消息1，这样平均每个消息的编码长度为： L(P) = 0.8 * 1 + 0.2 * 2 = 1.2 bits 这也等于X的熵H(P)。 但是如果我们不知道X的真实概率分布P(X)，而只知道一个近似的概率分布Q(X)，那么我们可能会用不同的编码方案来传输消息。例如，假设Q(X=0)=0.5，Q(X=1)=0.5，那么我们可能会用01来编码消息0，用11来编码消息1，这样平均每个消息的编码长度为： L(Q) = 0.8 * 2 + 0.2 * 2 = 2 bits 这也等于X的交叉熵H(P,Q)。 可以看出，由于我们使用了一个不准确的概率分布Q(X)来编码消息，导致了平均每个消息的编码长度增加了0.8 bits，这就是用Q(X)来近似P(X)所造成的信息损失。这个信息损失就是KL散度D(P||Q)： D(P||Q) = L(Q) - L(P) = H(P,Q) - H(P) = 0.8 bits 也就是说，KL散度衡量了如果我们使用Q(X)来代替P(X)，那么每个消息需要额外传输多少比特数。
后来我们知道，KL散度是肯定大于0的，但是显然每个点两者信息的大小关系有可能有大有小，而最后大于0，反映了一种最优性和必然性，回头再看看。
学完了后面，回头看这个，感觉好显然了……
互信息和DL-散度的关系
\[ I(X,Y) = D[p(X,Y)||p(X)p(Y)] \]
条件互信息
\[ I(X;Y|Z) = H(X| Z) - H(X|Y, Z) \]
这可以从信息增益的角度理解，也可以写成\(\mathbb{E}\)的形式从KL-D的角度理解
互信息的链式法则
\[ I(X_1,X_2\cdots X_n;Y) = \sum_{i=1}^{n}I(X_i;Y|X_{i-1},\cdots,X_1) \]
理解上，跟信息熵的链式法则一样，只不过之前的信息现在变成了和Y之间的互信息
条件相对熵
\[ D[p(y|x) || q(y|x)] = \mathbb{E}_{x,y}log\frac{p(Y|X)}{q(Y|X)} \]
相对熵的链式法则
\[ D[p(x, y)||q(x,y)] = D[p(x)||q(x)] + D[p(y|x)||q(y|x)] \]
这个要怎么很直观地理解？
相对熵可以看作是两个分布之间的差异或不相似度的度量，而链式法则可以看作是一种将这种差异分解为局部差异和条件差异的方法。
一些推论
首先，教材引入了Jensen不等式，这在几何上非常容易理解，不赘述
结论： \[ f(x): convex\;\Rightarrow\;\mathbb{E}f(X) \ge f(\mathbb{E}X) \] 以此证明 \[ D[p||q]\ge 0 \]
数学上很好证，讲讲理解 \[ H(X) = \sum_xp(x)log\frac{1}{p(x)} \]
\[ D[p(x)||q(x)] = \sum_x p(x)[log\frac{1}{q(x)}-log\frac{1}{p(x)}] \]
我们盯着这两个式子，\(log\frac{1}{p(x)}\)随着\(p(x)\)的增大而减小，是否就是说，在概率大的时候我们要挑选一个小一点的东西对它进行表示，概率小的时候用大一点的东西对它进行表示，那么最后我们总共的消耗比较小（编码的角度）
而对于KL散度，我们已经知道了\(p(x)\)，那么对于每个概率点，用\(log\frac{1}{p(x)}\)来表示应该是最优的，但是如果我们偏偏要用\(log\frac{1}{q(x)}\)来对每个概率点表示，比如我们在P中有很大概率的时候，用了Q中有很小概率的东西进行了表示，那就造成了很大的损失，导致KL散度增加。每个点的改变的程度就是[]中的式子相减。因为函数的性质，总体加起来肯定会变大，这更说明了原来的表示的最优性。
相对熵的凸性
\[ D(\lambda p_1+(1-\lambda)p_2||\lambda q_1+(1-\lambda)q_2)\le \lambda D(p_1||q_1)+(1-\lambda)D(p_2||q_2) \]
怎么理解？？？
Q：单个映射是不是也可以看成一个MC？
Chapter 3 渐进均分性
关于渐进均分性
这一章提出了典型集的概念。我们用抛硬币举例，抛100000次均匀硬币，全部正面朝上概率几乎为0，而50000次左右正面朝上的概率似乎大一些。渐进均分就是说，某些特定的情况（比如刚才提到的大约一半次数朝上）的概率之和将会无限趋近于1，同时，这些特定的情况本身的概率是几乎相等的。
一些标记：
一系列随机变量\(X_1, X_2, \cdots, X_n \;\;i.i.d \sim p(x)\)
典型集\(A_{\varepsilon}^{(n)}\)
则对于典型集以及处于典型集里的\((X_1, X_2, \cdots, X_n)\)：
- \(Pr\{A_{\varepsilon}^{(n)}\}>1-\varepsilon\)
- \(|A_{\varepsilon}^{(n)}|\rightarrow 2^{nH(X)}\)
- \(p(x_1, x_2, \cdots, x_n)\rightarrow 2^{-nH(X)}\)
Chapter 4 平稳过程的熵率
关于平稳过程的熵率
熵率的定义： \[ H(\mathcal{X}) = \lim_{n\rightarrow \infty}{\frac{1}{n}H(X_1, X_2, \cdots, X_n)} \] 再定义 \[ H'(\mathcal{X}) = \lim_{n\rightarrow \infty}{H(X_n|X_{n-1}, \cdots , X_1)} \] 对于一个平稳随机过程，有 \[ H(\mathcal{X}) = H'(\mathcal{X}) \] 对于马尔科夫过程，有 \[ H(\mathcal{X}) = H'(\mathcal{X}) = H(X_2|X_1) = -\sum_{ij}{\mu_iP_{ij}}\log{P_{ij}} \]
Chapter 5 数据压缩
关于数据压缩
给信息编码。主要关注前缀码(即时码)。
Kraft不等式： \[ \sum_iD^{-l_i}\le 1 \] 可以推广到无穷。这个的证明非常妙！想象成一个D进制数，然后把所有编码投影到区间[0, 1]，同时由于是即时码，取一个点会导致某个区间不可用。
对于满足某一组离散分布的点，最优码长\(L \rightarrow H_D(X)\)
Chapter 6 信息论与统计学
现在我们有一个字母表\(\mathcal{X}\). 里面的元素为\(\{a_1, a_2, \cdots, a_{|\mathcal{X} |}\}\)
我们有\(n\)个随机变量，它们都取自这个字母表。我们现在不关注每个随机变量具体取了字母表中的哪个元素，而关注统计上的情况，也就是说几个元素取了哪个字母表中元素。我们把这种分布一样的情况称为一个型，称为\(P\)，型一样的元素组成的集合称为型类\(T(P)\).所有型组成的集合是\(\mathcal{P}\)
型总数的粗略估计： \[ |\mathcal{P_n}| \le (n+1)^{|\mathcal{X}|} \] 型类大小估计： \[ \frac{1}{(n+1)^{|\mathcal{X}|}}2^{nH(P)}\le|T(P)|\le2^{nH(P)} \] 在任意概率\(Q\)下，属于型类\(T(P)\)的概率： \[ Q^n(T(P)) = 2^{-nD(P||Q)} \] 在任意概率\(Q\)下，型类\(P\)中某一元素\(x\)的概率： \[ Q^n(x) = 2^{-n(D(P_x||Q)+H(P_x))} \] 可以感受到均分的存在。