【计算机科学与技术】信息论笔记：合集_计算机科学与技术读书笔记

200804本篇是《信息论》的读书笔记，欢迎各位路过指正！今天十章全部更新完毕啦。

0.分章节目录

• 【计算机科学与技术】信息论笔记（1）：熵、相对熵与互信息
• 【计算机科学与技术】信息论笔记（2）： 渐近均分性
• 【计算机科学与技术】信息论笔记（3）：随机过程的熵率
• 【计算机科学与技术】信息论笔记（4）：数据压缩
• 【计算机科学与技术】 信息论笔记（5）：信道容量
• 【计算机科学与技术】信息论笔记（6）：微分熵
• 【计算机科学与技术】信息论笔记（7）：高斯信道
• 【计算机科学与技术】信息论笔记（8）：率失真理论
• 【计算机科学与技术】信息论笔记（9）：最大熵
• 【计算机科学与技术】信息论笔记（10）：通用信源编码

1. 熵、相对熵与互信息

1.1 绪论与概述

• 香农（C.E.Shannon） 于1948年发表论文 “通信的数学理论” 奠定了信息论的基础。

• 香农第一定理（无失真信源编码定理）：给出编码极限。

• 香农第二定理（有噪信道编码定理）：传输速率小于信道容量，则误码率可以任意小。

• 香农第三定理（保失真度准则下的有失真信源编码定理）：给定失真度，只要码字足够长，就可以使编码的失真度小于给定失真度。

1.2 熵

• 熵的定义：

$$H(X)=H\left(p_1,p_2,\cdots ,p_K\right)=-\sum _{n=1}^K{p}_n\log p_n$$

• 一元信源模型：

[ X p ( x ) ] = [ a 1 a 2 ⋯ a K p ( a 1 ) p ( a 2 ) ⋯ p ( a K ) ] \left[

$$\begin{array}{c}X \\ p(x)\end{array}$$ \right]=\left[ $$\begin{array}{cccc}a_{1} & a_{2} & \cdots & a_{K} \\ p\left(a_{1}\right) & p\left(a_{2}\right) & \cdots & p\left(a_{K}\right)\end{array}$$ \right] [Xp(x)​]=[a1​p(a1​)​a2​p(a2​)​⋯⋯​aK​p(aK​)​]

有$0\le p_n\le 1$，${\sum }_{n=1}^K{p}_n=1$。若$X\sim p(x)$，则随机变量$g(X)$的期望为$E[g(x)]=\sum g(x)p(x)$。随机变量$X$的熵可看为随机变量$log(1/p(X))$的数学期望，其中$p(x)$为$X$的概率密度函数。

• 熵函数应符合下面三条公理：（1）对称性：交换下标不影响熵值。（2）最大值：等概分布熵值最大。（3）若$p_K=p_{11}+...+p_{1i}$则两个分布有如下关系：

$$H\left(p_1,p_2,\cdots ,p_{K-1},p_{11},p_{12},\cdots ,p_{1l}\right)=H\left(p_1,p_2,\cdots ,p_k\right)+p_{k}H\left(\frac{p_{11}}{p_K},\frac{p_{12}}{p_K},\cdots ,\frac{p_{1i}}{p_K}\right)$$

• 熵的含义：（1）平均意义：熵是整个集合的统计特性。（2）信息熵：$H(X)$表示每个消息提供的平均信息量。（3）随机性：信息熵$H(X)$表征了变量X的随机性。

• 熵的链式法则：
  $$H\left(X_1,X_2,\cdots ,X_n\right)=\sum _{i=1}^{n}H\left(X_i\mid X_{i-1},\cdots ,X_1\right)$$

1.3 联合熵

• 二元信源模型：
  $$\left[\begin{array}{c}XY\\ p(XY)\end{array}\right]=\left[\begin{array}{ccccc}{a}_1{b}_1& a_1{b}_2& a_1{b}_3& \dots & a_k{b}_J\\ p\left(a_1,b_1\right)& p\left(a_1,b_2\right)& p\left(a_1,b_3\right)& \dots & p\left(a_K,b_J\right)\end{array}\right]$$

其中${\sum }_{k=1}^K{\sum }_{j=1}^{J}p(a_k,b_j)=1$。

• 联合熵的定义：
  $$H(X,Y)=-\sum _{k=1}^K\sum _{j=1}^{J}p\left(a_k,b_j\right)\log p\left(a_k,b_j\right)=-E[\log p(X,Y)]$$

若独立，则联合熵等于单个随机变量熵之和；条件熵等于无条件熵（绝对熵）。

• 有等式

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

1.4 条件熵

• 条件熵的定义：

$$H(Y|X)=-\sum _{k=1}^K\sum _{j=1}^{J}p(a_k,b_j)\log p(b_j|a_k)$$

• 条件熵链式法则：

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

• 确定关系：若$X$与$Y$有确定的函数关系，且$X$可以完全确定$Y$（或$Y$完全确定$X$），则$H(Y|X)=H(X|Y)=0$。

• 条件熵不大于绝对熵是平均意义下的结论。

1.5 相对熵

• 相对熵（Kullback熵） ：两个随机分布之间距离的度量。
  $$D(p||q)=\sum _{k=1}^{K}p(a_k)\log \frac{p(a_k)}{q(a_k)}$$

• 条件相对熵：一对随机变量的两个联合分布之间的相对熵可以展开为相对熵和条件相对熵之和。

$$D(p(y\mid x)\Vert q(y\mid x))=\sum _{x}p(x)\sum _{y}p(y\mid x)\log \frac{p(y\mid x)}{q(y\mid x)}=E_{p(x,y)}\log \frac{p(Y\mid X)}{q(Y\mid X)}$$

• 相对熵的链式法则：
  $$D(p(x,y)\Vert q(x,y))=D(p(x)\Vert q(x))+D(p(y\mid x)\Vert q(y\mid x))$$

1.6 互信息

• 互信息的定义：
  $$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=I(Y;X)$$
  也可以采用直接定义$X$与$Y$之间的互信息为
  $$I(X;Y)=\sum _{k=1}^K\sum _{j=1}^{J}p\left(a_k,b_j\right)\log \frac{p\left(a_k,b_j\right)}{p\left(a_k\right)p\left(b_j\right)}$$

• 熵与互信息的关系：互信息是随机变量之间相互依存度的度量信息。

• 单个互信息物理意义：$Y=b_j$下获得的$X=a_k$的信息量，互信息$I(X;Y)$为单个互信息的均值。

• 熵可由互信息导出。自信息的数学期望就是信息熵，$H(X)=E[I(a_k,a_k)]=E[H(a_k)]$。

• 条件互信息：给定随机变量$Z$时，由$Y$的信息而获得的关于$X$的信息
  $$I(X;Y\mid Z)=H(X\mid Z)-H(X\mid Y,Z)=\sum _{k=1}^K\sum _{j=1}^J\sum _{l=1}^{L}p\left(a_k,b_j,c_i\right)\log \frac{p\left(a_k,b_j\mid c_i\right)}{p\left(a_k\mid c_i\right)p\left(b_j\mid c_i\right)}$$

• 互信息的链式法则：
  $$I\left(X_1,X_2,\cdots ,X_n;Y\right)=\sum _{i=1}^{n}I\left(X_i;Y\mid X_{i-1},\cdots ,X_1\right)$$

1.7 Jensen不等式

• Jensen不等式：设函数$f(x)$是凸域$D$上的下凸函数，则对任意$a_m\in D$，$0\le {\lambda }_m\le 1,{\lambda }_1+...+{\lambda }_M=1$有
  $$f\left(\sum _{m=1}^M{\lambda }_m{\alpha }_m\right)\le \sum _{m=1}^M{\lambda }_{m}f\left({\alpha }_n\right)$$

• 信息不等式：两个概率密度函数为$p(x)$和$q(x)$之间的鉴别信息为$D(p||q)$，则：$D(p||q)\ge 0$，当且仅当对任意的$x$，$p(x)=q(x)$，等号成立。

• 推论：
  $$\begin{gathered} I(X;Y)\ge 0 \\ I(X;Y|Z)\ge 0 \\ D(p(y|x)||q(y|x))\ge 0 \end{gathered}$$
  $H(X)\le log|X|$，其中$|X|$表示$X$的字母表$X$中元素的个数，当且仅当$X$服从$X$上的均匀分布时，等号成立。

• 意义：在平均意义下，信源的不确定性减少。
  $$H(X)\ge H(X|Y)$$

• 熵的独立界：当且仅当$X_i$相互独立，等号成立。熵函数为上凸函数。
  $$H\left(X_1,X_2,\cdots ,X_n\right)\le \sum _{i=1}^{n}H\left(X_i\right)$$

• 定理：互信息为信源概率分布的上凸函数；互信息为信道矩阵的下凸函数。

1.8 对数和不等式

• 上面的等式中假设信源概率分布为$p:p(a_k)$。互信息由概率分布和条件概率矩阵确定。记为$Q:p(b_j|a_k)$。$Q$有时也称为信道转移概率矩阵。互信息可记为$I(p,Q)$。
• 对数和不等式：对于非负数$a_1,a_2,\dots ,a_n$和$b_1,b_2,\dots ,b_n$，当且仅当$\frac{a_i}{b_i}$为常数时，等号成立 。
  $$\sum _{i=1}^n{a}_i\log \frac{a_i}{b_i}\ge \left(\sum _{i=1}^n{a}_i\right)\log \left(\sum _{i=1}^n{a}_i/\sum _{i=1}^n{b}_i\right)$$
• 相对熵的下凸性：$D(p||q)$关于对$(p,q)$是下凸的。

1.9 数据处理不等式

• 数据处理不等式：数据处理都会损失信息。 若$X\to Y\to Z$构成Markov链，则
  $$I(X;Y)\ge I(X;Z)$$

• 费诺不等式：定义误差概率为 P e = P r { X ^ ≠ X } P_e = Pr\{\hat{X} \neq X\} Pe​=Pr{ X^​=X}。则对任何满足$X\to Y\to \hat{X}$的估计量$\hat{X}$,有
  $$\begin{gathered} H\left(P_{\mathrm{e}}\right)+P_{\mathrm{e}}\log |\mathbf{X}|\ge H(X\mid \hat{X})\ge H(X\mid Y) \\ 1+P_{\mathrm{e}}\log |\mathbf{X}|\ge H(X\mid Y) \end{gathered}$$

• 意义：假定没有任何关于$Y$的知识，只能在毫无信息的情况下对$X$进行推测。 设 X ∈ { 1 , 2 , … , K } X\in \{1,2,…,K\} X∈{ 1,2,…,K}且$p_1\ge p_2\ge \dots \ge p_K$，则对$X$的最佳估计是 $\hat{X}=1$，而此时产生的误差概率为$P_e=1-p_1$。

• 误差概率与熵之间的不等式：设$X$和$X’$为两个独立同分布的随机变量，有相同的熵$H(X)$，那么$X=X^{\prime }$的概率为

$$\mathrm{Pr}\left(X=X^{\prime }\right)=\sum p^2(x)$$

2. 渐进均分性

2.1 渐进均分性定理

• 信息符号冗余度：冗余度高，符号携带的信息率低，易于压缩；

• 信源的冗余编码：提高单个信息符号所携带的信息量。

• 渐进等同分割性（Asymptotic Equipartition Property）结论：信源分布等概，信息熵最大。

• 定理2.1.1（渐进均分性）：设$X_1,X_2,...,X_n$ 是概率密度函数为p(x)的独立同分布(i.i.d)的随机变量，则
  $$-\frac{1}{n}\log p\left(X_1,X_2,\cdots ,X_n\right)\to H(X)$$

• 直观解释：当序列足够长时，一部分序列就显现出这样的性质：**序列中各个符号的出现频数非常接近于各自的出现概率，而这些序列的概率则趋近于相等，且它们的和非常接近于1，这些序列就称为典型序列。**其余的非典型序列的出现概率之和接近于零。

香农在1948年的《通信的数学理论》中注意到它并表述为一个定理。后来麦克米伦在1953年发表的《信息论的基本定理》一文中严格地证明了这一结果。

• 定义2.1.1（典型集）：设$X_1,X_2,...,X_n$ 是概率密度函数为$p(x)$的i.i.d随机序列，如果联合分布$p(x_1$