信息论

临时补一下...

Information theory

Entropy

对于离散型随机变量\(X\)，出于方便，我们用\(|X|\)来表示其样本空间的大小，那么，我们定义随机变量\(X\)的熵（entropy）

\[\begin{align}H(X) = \sum_{x \in X} -p(x) \log p(x) = \sum_{x \in X} p(x) \log \frac{1}{p(x)} \end{align}\]

（特别的，如果\(p(x) = 0\)，认为\(p(x) \log \frac{1}{p(x)} = 0\)）

熵有下列的性质

• 如果\(X\)均匀随机，那么\(H(X) = |X| * \frac{1}{|X|} * \log |X| = \log |X|\)

• \(0 \leq H(X) \leq \log |X|\)

  • 不等式左边成立当且仅当\(X\)只在一个地方取得概率\(1\)，其余地方取得概率\(0\)

  • 不等式右边成立当且仅当\(X\)​均匀分布

  • 不等式的左边是显然的，右边则考虑函数\(x \log x\)的凸性

对于服从二项分布的\(X\)，有特殊的一种熵（Binary entropy function）

\[\begin{align}H(p) = H(X) = p \log \frac{1}{p} + (1-p) \log \frac{1}{1-p} \end{align}\]

熵的定义只依赖于概率分布，只要确定了概率分布，我们就可以定义出熵，因此，在二元情况下，我们可以定义

\[\begin{align}H(X, Y) = \sum_{x \in X, y \in Y} p(x, y) \log \frac{1}{p(x, y)} \end{align}\]

为联合熵（joint entropy）

• \(H(X, X) = H(X)\)​
• \(H(X, Y) = H(Y, X)\)​

定义

\[\begin{align} H(X | Y = y) = \sum_x p(x | Y = y) \log \frac{1}{p(x|Y=y)} \end{align}\]

\[\begin{align}H(X|Y) &= \sum_{y \in Y} p(y) H(X | Y = y) \\ &= \sum_{y \in Y} p(y) \sum_{x \in X} p(x | y) \log \frac{1}{p(x | y)} \\ &= \sum_{x \in X, y \in Y} p(x, y) \log \frac{1}{p(x|y)}\end{align}\]​

其中第二项称为条件熵（conditional entropy）

注意到

\[\begin{align} \log p(x|y) = \log \frac{p(x, y)}{p(y)} = \log p(x, y) - \log p(y)\end{align}\]​

（式中的\(p(y)\)为对应的边缘分布函数）

我们有

\[\begin{align} H(X|Y) = H(X, Y) - H(Y)\end{align}\]

由对称性，得到

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

我们可以得到链式法则

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

• 当\(X, Y\)独立时，\(H(X, Y) = H(X) + H(Y)\)
• 贝叶斯公式：\(H(X, Y | Z) = H(X|Z) + H(Y | X, Z)\)
  • 注意到\(p(x, y | z) = \frac{p(x, y, z)}{p(z)} = \frac{p(x, y, z)}{p(x, z)} * \frac{p(x, z)}{p(z)} = p(y|x, z) * p(x|z)\)
• 当且仅当\(Y\)是\(X\)的一个函数时，\(H(Y|X) = 0\)，也即\(H(X, Y) = H(X)\)

Relative entropy

对于概率函数\(p(x), q(x)\)，定义

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

为相对熵（relative entropy），也称KL距离，用于衡量两个概率函数之间的“距离”

但是KL距离并不是一种度量（metric）

• 当\(p(x) = 0\)时，\(0 \log \frac{0}{q(x)} = 0\)，反之若\(p(x) \neq 0, q(x) = 0\)时，\(p(x) \log \frac{p(x)}{0} = \infty\)

• \(D(p || q) \geq 0\)​，当且仅当\(p = q\)时取等​

  • \(-D(p || q) = \sum_{x\in X} - p(x) \log \frac{q(x)}{p(x)} \leq \log \sum q(x) \leq \log 1 = 0\)

    其中第一步为琴生不等式

    当且仅当\(q(x)/p(x) \equiv C\)，并且\(\sum q(x) = 1\)时取等，从而\(1 = \sum p(x) = \frac{1}{C} \sum q(x) = \frac {1}{C}\)，于是\(C = 1\)，进而\(p(x) = q(x)\)，对于\(0\)的讨论这里略去

定义差分距离（也即向量的1-范数）

\[\begin{align} V(p, q) = \sum_{x \in X} |p(x) - q(x)|\end{align}\]

Pinsker 不等式：\(D(p || q) \geq \frac{1}{2 \ln 2} V^2(p, q)\)​​（不懂，先记着）

对于\(p(x, y), q(x, y)\)，定义条件相对熵为

\[\begin{align} D( p(y|x) || q(y|x)) &= \sum_{x} p(x) D(p(Y|x)||q(Y|x)) \\ &= \sum_x \sum_y p(x)p(y|x) \log \frac{p(y|x)}{q(y|x)} \\ &= \sum_{x, y} p(x, y) \log \frac{ p(y|x)}{q(y|x)}\end{align}\]​

有了条件相对熵之后，就可以类比的写出链式法则

\[\begin{align} D(p(x, y) || q(x, y)) = D(p(x) || q(x)) + D(p(y|x) || q(y|x))\end{align}\]

只需注意到\(\log \frac{p(x, y)}{q(x, y)} = \log \frac{p(x) p(y|x)}{q(x) q(y|x)} = \log \frac{p(x)}{q(x)} + \log \frac{p(y|x)}{q(y|x)}\)

Mutual information

定义

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

为\(X, Y\)的互信息（mutual information）

• \(I(X;Y) = I(Y;X)\)
• \(I(X;X) = H(X)\)​
• 既然\(I(X;Y)\)是一个KL距离，那么\(I(X;Y) \geq 0\)​，等号成立当且仅当\(p(x, y) = p(x)p(y)\)，即\(X, Y\)独立

由于\(\log \frac{p(x, y)}{p(x)p(y)} = \log p(x, y) - \log p(x) - \log p(y)\)

因此

\[\begin{align} I(X;Y) &= H(X) + H(Y) - H(X, Y) \\ &= H(X) - H(X | Y)\\ &= H(Y) - H(Y|X)\end{align}\]​

• 由\(I(X;Y) = H(X) - H(X|Y) \geq 0\)​，那么\(H(X|Y) \leq H(X)\)​​，当\(X, Y\)​独立时取等
• \(I(X;Y) \leq H(X)\)

定义

\[\begin{align} I(X;Y | Z) &= \sum_{x, y, z} p(x ,y, z) \log \frac{p(x, y | z)}{p(x|z) p(y|z) } \\ &= H(X|Z) - H(X|Y,Z)\end{align}\]​

当且仅当在给定\(Z\)的情况下，\(X, Y\)独立时取等

计算条件互信息时，有链式法则

\[\begin{align} I(X_1, X_2, ..., X_n ; Y) = \sum_{i=1}^n I(X_i ; Y|X_1, X_2, ..., X_{i-1})\end{align}\]

Entropy Bound

\[H(X_1, X_2, ..., X_n) \leq \sum_{i=1}^n H(X_i)\]

取等当且仅当\(X_1, ..., X_n\)独立（用链式法则证明）

接下来要引入马尔科夫链，称\(X, Y, Z\)形成马尔科夫链，当且仅当

\[\begin{align} p(x, y, z) = p(x)p(y|x)p(z|y)\end{align}\]

（也就是\(p(z|y) = p(z|x, y)\)），写作\(X \to Y \to Z\)

• 如果\(X\to Y \to Z\)，那么\(I(X;Z|Y) = 0\)

• 如果\(X \to Y \to Z\)，那么\(I(X;Y) \geq I(X;Z)\)

  • \(I(X;Y) - I(X;Z) = I(X;Y,Z) - I(X;Z|Y) - (I(X;Y,Z) - I(X;Y|Z)) = I(X;Y|Z) \geq 0\)
  • 由上述等式，还能观察到\(I(X;Y) \geq I(X;Y|Z)\)
  • 但是，一般情况下，\(I(X;Y) \geq I(X;Y|Z)\)不一定成立

• 如果\(X \to Y \to Z\)，那么\(H(X|Z) \geq H(X|Y)\)

• $ H(X|Z) - H(X|Y,Z) = I(X;Y|Z)I(X;Z|Y) = H(X|Y) - H(X|Y,Z)$

Entropy rate

稳态过程，一个随机过程称为稳态，如果其任意子集的联合分布具有时间不变性，

\[\begin{align} \forall n, l, x_1, x_2,..., x_n \in X, P(X_1 = x_1, X_2 = x_2, ..., X_n = x_n) = P(X_{1+l} = x_1, ..., X_{n+l} = x_n)\end{align}\]

稳态过程具有时间可逆性，即

\[\begin{align} H(X_0 | X_{-1},X_{-2},..X_{-n}) = H(X_0 | X_1, X_2, ..., X_n)\end{align}\]

而对于马尔科夫链，其为稳态充要条件为\(p(X_{n+1}) = p(X_n)\)

或者说\(P(x_1,x_2,...,x_n)^T = (x_1, ..., x_n)^T\)，其中\(P\)为转移矩阵

---

对于随机过程，定义熵率

\[\begin{align} H(X) = \lim_{n \to \infty} \frac{1}{n} H(X_1, X_2, ..., X_n)\end{align}\]

熵率不一定存在，但对于稳态而言，熵率是存在的

我们先考虑\(A_n = H(X_n | X_{n-1}, ..., X_1)\)

注意到\(0 \leq A_{n+1} = H(X_{n+1} | X_{n},...,X_1) \leq H(X_{n+1} | X_n,...,X_2) = H(X_n | X_{n-1},...,X_1) = A_n\)，\(A_n\)单调递减有下限，因此\(A_n\)有极限

那么

\[\begin{align} H'(X) = \lim_{n \to \infty} H(X_n | X_{n-1},...,X_1)\end{align}\]

存在，根据数学分析中的结论，我们有

\[\begin{align} H(X) = H'(X)\end{align}\]

存在

特别的，对于稳态马尔科夫链，将有\(H(X) = H'(X) = H(X_2 | X_1)\)

如果设出马尔科夫链的极限分布\(\pi\)和转移矩阵\(P\)，那么我们将得到

\[\begin{align} H(X) = \sum_{ij} \pi_i P_{ij} \log \frac{1}{P_{ij}}\end{align}\]

---

设\(Y = f(X)\)，如果\(\{X\}\)构成稳态的马尔科夫链，那么\(\{Y\}\)也构成稳态的马尔科夫链

• \(p(X_{n+1}) = p(X_n) \Rightarrow p(Y_{n+1}) = p(Y_n)\)

那么，\(H(Y) = \lim_{n \to \infty} H(Y_n | Y_{n-1}, ..., Y_1)\)

通过一些（奇怪的）技巧，我们可以对\(H(Y)\)进行更好的估值，这依赖于以下定理

\[\begin{align} H(Y_n | Y_{n-1},...,Y_1, X_1) \leq H(y) \leq H(Y_n | Y_{n-1},...,Y_1)\end{align}\]

\[\begin{align} \lim_{n \to \infty} H(Y_n | Y_{n-1},...,Y_1,X_1) = \lim_{n \to \infty} H(Y_n|Y_{n-2},...,Y_1) = H(y)\end{align}\]​

• 注意到\(Y\)是\(X\)的函数，尝试在熵的已知中添加\(Y\)

Data Compression

大概到了新的阶段

对于一个随机变量\(X\)的信源编码（source code），是一个从随机变量\(X\)的样本空间到一个有限长度的字符串的映射（不妨设字母表为\(D\)，记所有的有限长度的字符串的集合为\(D^*\)），让\(C(x)\)表示对应于\(x\)的编码，而\(l(x)\)表示\(C(x)\)的长度

记\(L(C) = E_{p(x)}[l(x)] = \sum_{x} p(x) l(x)\)，一般的，我们希望一个编码方式能够最小化\(L(C)\)

对于一种编码，称其扩展\(C^*\)为以\(X\)的样本空间为字符集构成的有限字符串映射到有限长度的字符串的映射，满足\(C(x_1 + x_2 + ... + x_n) = C(x_1) + C(x_2) + ... + C(x_n)\)，这里的"+"表示字符串的拼接

• 当一种编码的扩展是一个单射时，称这种编码是唯一可解码的
• 一种编码称为前缀码，或者即时码，如果任意两个码都没有互为前缀，类似的定义后缀码

Kraft inequality

Kraft 不等式：对于一种前缀码，设其字母表大小为\(D\)​​，那么编码长度\(l_1, ..., l_m (m = |X|)\)​​将满足

\[\begin{align} \sum_{i=1}^m D^{-l_i} \leq 1\end{align}\]

并且，给定一组满足该不等式的编码长度，那么一定存在一种前缀码以这些长度编码

• 考虑用Trie树表示前缀码，反过来则用归纳法证明
• 这个结论在编码长度有可数无穷的情况下也是对的，可以考虑用\([0,1)\)中的\(D\)进制小数来证明

利用拉格朗日乘数法，得到最优情况下，我们应该控制编码长度为\(l_i = -\log_D p_i(p_i = D^{-l_i})\)，此时\(L(C) = H_D(X)\)

但是一般的，这个长度不是整数，因此一般的有\(L(C) \geq H_D(X)\)​，但是我们有\(H_D(X) \leq L(C) < H_D(X) + 1\)​

Shannon codes

我们直接取\(l_i = \lceil -\log_D p_i \rceil\)，就有\(-\log_D p_i \leq l_i < -\log_D p_i + 1\)，于是\(H_D(X) \leq L(C) < H_D(X) + 1\)，这种编码称为Shannon codes

进一步，如果我们对\(X_1, X_2,...,X_n\)​（样本空间相同）一起编码，运用刚刚的结论，得到

\[H(X_1, ..., X_n) \leq E [l(X_1, ..., X_n)] < H(X_1,...,X_n) + 1\]

将\(L(C)\)记为编码一个随机变量所用的期望长度，那么\(L(C) = \frac{1}{n} E [l(X_1, ..., X_n)]\)，代入上式，得到 \[\frac{H(X_1, ..., X_n)}{n} \leq L(C)< \frac{H(X_1,...,X_n) + 1}{n}\]

如果\(X_1,...,X_n,...\)构成一个稳态的话，根据前文的结论，我们有\(L(C) \to H(X)\)（这里为熵率）

这种编码方式称为区块编码，而上述结论称为香农第一定理

---

如果我们运用\(\{q(x)\}\)来给一个概率为\(\{p(x)\}\)的随机变量编码，那么我们将有

\[\begin{align} H(p) + D(p||q) \leq E_p \; \lceil\log \frac{1}{q(x)} \rceil < H(p) + D(p || q) + 1\end{align}\]​

当然，这里的\(\lceil\log \frac{1}{q(x)} \rceil\)表示编码长度

这个式子只需要对取整号进行简单放缩后，运用定义就可以得到

---

Kraft不等式的约束范围非常非常广，事实上，我们只考虑前缀码就足够了

对于一种唯一可解码，设其字母表大小为\(D\)​，那么编码长度\(l_1, ..., l_m (m = |X|)\)​将满足

\[\begin{align} \sum_{i=1}^m D^{-l_i} \leq 1\end{align}\]

并且，给定一组满足该不等式的编码长度，那么一定存在一种唯一可解码以这些长度编码

Huffman codes

哈夫曼编码可以使得\(L(C)\)最小，并且哈夫曼编码是一种前缀码

这玩意初中生都会了....就不写了

有个扩展叫canonical codes，就先不学了..。

Shannon-Fano-Elias coding

考虑\(X\)的分布函数\(F(x)\)，定义其MCDF为\(F^*(x) = F(x) - \frac{1}{2} p(x)\)

不难发现，\(F^*(x)\)和\(p(x) > 0\)的\(x\)​之间存在着对应关系，从而可以用于编码

考虑截取\(F^*(x)\)的前\(l(x) = \lceil \log \frac{1}{p(x)}\rceil + 1\)位（二进制），那么有\(F^*(x) - C(x) \leq \frac{1}{2^{l(x)}} \leq \frac{p(x)}{2} = F^*(x) - F^*(x-1)\)

因此这种编码方式也构成一种前缀码，由于多用了1个bit来避免重复，因此此时\(L < H(x) + 2\)​

Channel

一个信道的模型，大概就是对信息进行编码，通过信道（可能有噪声，以一个概率来描述），之后解码

我们假设发送了\(w = x_1x_2...x_k\)，经过信道后得到\(y_1y_2...y_k\)

这些数字的生成是有先后顺序的，\(w \to x_1 \to y_1 \to x_2 \to y_2 ... \to x_k \to y_k\)

为了表示方便，记\(x^i = x_1,x_2...,x_i, y^i = y_1, y_2, ..., y_i\)

对于一个好的信道，我们希望它能发送更多的信息，也即熵尽可能大

Discrete memoryless channel

离散无记忆信道（DMC），满足

\[\begin{align} p(y_k | x^k, y^{k-1}) = p(y_k | x_k) \end{align}\]

其中\(x_k\)是第\(k\)个发送的信息，而\(x^k\)为前\(k\)次发送的信息，\(y^{k-1}\)为前\(k-1\)​个发送后的信息

而一个无反馈（feedback）的信道，满足

\[\begin{align} p(x_k | x^{k-1}, y^{k-1}) = p(x_k | x^{k-1})\end{align}\]

也就是前\(k-1\)次经过信道后的信息对于第\(k\)次发送的信息没有影响

结合这两个概率，一般默认DMC是没有反馈的

对于DMC而言，有

\[\begin{align} p(y^n |x^n) = \prod_{i=1}^n p(y_i | x_i)\end{align}\]​

用熵来表示，就是

\[\begin{align} H(Y^n | X^n) = \sum_{i=1}^n H(Y_i | X_i) \end{align}\]​

运用上式，有

\[H(Y^n) - H(Y^n|X^n)= H(Y^n) - \sum_{i=1}^n H(Y_i | X_i) \leq \sum_{i=1}^n (H(Y_i) - H(Y_i | X_i))\]

\[\begin{align} I(X^n ; Y^n) \leq \sum_{i=1}^n I(X_i ; Y_i) \end{align}\]

在DMC中，\(w \to X^n \to Y^n \to w'\)构成一个马尔科夫链，其中\(w'\)​为解码后的信息

Channel coding

编码器（encoder），是一个将信息映射到\(X^n\)的映射，并且要求是单射，类似的有解码器

码本（codebook），记录了编码器的映射规则，码本为发送者和接收者共有

码字（codewords），用\(x^n(i)\)表示编码\(i\)的字符串

对于一个信道\((X, p(y|x), Y)\)​​​而言，其一个编码\((M, n)\)包括发送信息的集合（\(M\)​），编码器（引申出码本和码字），解码器

为了衡量信道发送的信息是否有误，定义

\[\begin{align}\lambda_i = p( g(Y^n) \neq i | X^n = x^n(i)) = \sum_{y^n} p(y^n | x^n(i))* [g(y^n) \neq i] \end{align}\]

定义最大错误概率为

\[\begin{align} \lambda^{(n)} = \max_{i \in [M]} \lambda_i\end{align}\]

定义平均错误概率为

\[\begin{align} P_e^{(n)} = \frac{1}{M} \sum_{i=1}^M \lambda_i\end{align}\]

对于一个信道编码\((M, n)\)​，定义码率为

\[\begin{align} R = \frac{\log M}{n} \end{align}\]​

如果存在一系列的编码\((2^{nR}, n)\)，使得当\(n \to \infty\)时，\(\lambda^{(n)} \to 0\)，就称码率\(R\)​是可取的

定义信道容量\(C\)为所有可取码率的上确界

• 信道编码定理

  对于DMC而言，一切小于信道容量\(C\)​的码率是可取的

• 特别的，对于默认的DMC，\(C = \max_{p(x)} I(X;Y)\)

  而对于有反馈的DMC而言，信道容量并不能得到提高

Typical set

接下来是一点关于典型集的内容...

如果\(X_1,...,X_n,...\)是i.i.d.的，那么

\[\begin{align} -\frac{1}{n} \log p(X_1,...,X_n) \to H(X) (n \to \infty)\end{align}\]​

这个性质称为AEP（渐进均分性），根据大数定理，我们知道满足上述条件的\(X\)序列的概率和几乎是\(1\)​

我们把满足上述条件的序列弄成一个集合\(A_{\epsilon}^{(n)}\)​，称为典型集（typical set），形式化的讲就是，如果\((x_1,...,x_n) \in X^n\)在集合\(A_{\epsilon}^{(n)}\)中，那么

\[\begin{align}2^{-n(H(X) + \epsilon)} \leq p(x_1,...,x_n) \leq 2^{-n(H(X) - \epsilon)}\end{align}\]

• 上述式子等价于：\(|\frac{1}{n} \log p(x_1,...,x_n) + H(X)| \leq \epsilon\)
• 根据之前的讨论，当\(n\)足够大时，典型集中的序列的概率之和趋近于\(1\)
• \((1 - \epsilon) 2^{n(H(X) - \epsilon)} \leq |A_{\epsilon}^{(n)}| \leq 2^{n(H(X) - \epsilon)}\)，也就是其大小趋近于\(2^{nH(X)}\)​
  • 注意到\(A_{\epsilon}^{(n)}\)的概率和有上界\(1\)，有下界\(1- \epsilon\)​

对于两个随机过程，我们可以定义联合典型集

如果\((x^n , y^n) \in X^n \times Y^n\)在集合\(A_{\epsilon}^{(n)}\)中，那么

\(2^{-n(H(X) + \epsilon)} \leq p(x^n) \leq 2^{-n(H(X) - \epsilon)}\)​

\(2^{-n(H(X) + \epsilon)} \leq p(y^n) \leq 2^{-n(H(X) - \epsilon)}\)​

\(2^{-n(H(X,Y) + \epsilon)} \leq p(x^n, y^n) \leq 2^{-n(H(X, Y) - \epsilon)}\)​

• \(|A_{\epsilon}^{(n)}| \to 2^{nH(X,Y)}\)

• 如果\((X', Y') \sim p(x^n)p(y^n)\)，那么\(p((X', Y') \in A_{\epsilon}^{(n)}) \to 2^{-nI(X;Y)}\)​

  • \(p((X', Y') \in A_{\epsilon}^{(n)}) = \sum_{(x^n, y^n)} p(x^n) p(y^n) \to 2^{nH(X, Y)} * 2^{-nH(X)} * 2^{-nH(Y)} = 2^{-nI(X;Y)}\)

    式中为集合的大小乘上相应的概率，具体的写法就分两个方向放缩

Source-channel coding theorem

• 信源信道联合编码定理

  如果\(X_1, ..., X_n\)是一个满足渐进均分性，并且\(H(X) < C\)，那么存在一种信源信道的联合编码方案，使得\(p(X^n \neq (X^n)') \to 0\)

  反之，对于任何稳态随机过程，如果\(H(X) > C\)，那么不存在使得\(p(X^n \neq (X^n)') \to 0\)的一种联合编码方案

感觉该知道的都差不多了....先记到这里...