信息论基础 1~8
信息论基础 1~8
1 绪论与概览
2 熵 相对熵与互信息
2.1 熵
\[H(X) = - \sum_{x \in X}{p(x)\log{p(x)}}\]2.2 联合熵
\[H(X, Y) = - \sum_{x \in X} \sum_{y \in Y} p(x,y)\log{p(x,y)}\] \[H(Y|X)= \sum_{x \in X}p(x)H(Y|X=x)\]定理2.2.1(链式法则): \(H(X, Y) = H(X) + H(Y|X)\)
2.3 相对熵与互信息
相对熵(relative entropy): \(D(p || q) = \sum_{x \in X} p(x) \log{\frac{p(x)}{q(x)}}=E_p \log{\frac{p(x)}{q(x)}}\)
互信息(mutual information): \(I(X;Y) = \sum_{x \in X} \sum_{y \in Y} p(x,y) \log{\frac{p(x,y)}{p(x)p(y)}} = D(p(x,y)||p(x)p(y))\)
2.4 熵与互信息的关系
\[I(X;Y) = H(X) - H(X | Y) = H(Y) - H(Y | X)\]互信息I(X;Y)是在给定Y知识的条件下X的不确定度的缩减量
\[I(X;Y) = H(X) + H(Y) - H(X, Y)\]2.5 熵,相对熵与互信息的链式法则
定理2.5.1(熵的链式法则): \(H(X_1, X_2, \dots, X_n) = \sum_{i = 1}^n H(X_i|X_{i-1}, \dots, X_1)\)
定理2.5.2(互信息的链式法则): \(I(X_1, X_2, \dots, X_n;Y) = \sum_{i = 1}^n I(X_i;Y|X_{i-1}, \dots, X_1)\)
条件相对熵: \(D(p(y|x)||q(y|x)) = \sum_x p(x) \sum_y p(y|x) \log{\frac{p(y|x)}{q(y|x)}} = E_{p(x,y)}\log{\frac{p(Y|X)}{q(Y|X)}}\)
定理2.5.3(相对熵的链式法则): \(D(p(x,y) || q(x,y)) = D(p(x)||q(x)) + D(p(y|x)||q(y|x))\)
2.6 Jensen不等式及其结果
定理2.6.2(Jensen不等式): 若给定凸函数f和一个随机变量X,则 \(Ef(X) \ge f(EX)\)
定理2.6.3(信息不等式): \(D(p||q) \ge 0\)
推论(互信息的非负性): \(I(X;Y) \ge 0\)
定理2.6.4: \(H(X) \le \log{|X|}\)
定理2.6.5(条件作用使熵减小): \(H(X|Y) \le H(X)\)
从直观上讲,此定理说明知道另一随机变量Y的信息只会降低X的不确定度. 注意这仅对平均意义成立. 具体来说, \(H(X|Y=y)\) 可能比\(H(X)\)大或者小,或者两者相等.
定理2.6.6(熵的独立界): \(H(X_1, X_2, \dots, X_n) \le \sum_{i=1}^n H(X_i)\)
2.7 对数和不等式及其应用
定理2.7.1(对数和不等式): \(\sum_{i = 1}^n a_i \log{\frac{a_i}{b_i}} \ge (\sum_{i=1}^n a_i)\log{\frac{\sum_{i = 1}^n a_i}{\sum_{i = 1}^n b_i}}\)
定理2.7.2(相对熵的凸性): \(D(p || q)\) 关于对(p,q)是凸的
定理2.7.3(熵的凹性): H(p)是关于p的凹函数
2.8 数据处理不等式
2.9 充分统计量
这节很有意思,利用统计量代替原有抽样,并且不损失信息.
2.10 费诺不等式
定理2.10.1(费诺不等式): 对任何满足 \(X \to Y \to\hat{X},\) 设 \(P_e = Pr\{X \neq \hat{X}\},\) 有
\[H(P_e) + P_e \log{|\mathcal{X}|} \ge H(X | \hat{X}) \ge H(X | Y)\]上述不等式可以减弱为
\[1 + P_e \log{|\mathcal{X}|} \ge H(X | Y)\]或
\[P_e \ge \frac{H(X|Y) - 1}{\log{|\mathcal{X}|}}\]引理 2.10.1: 如果X和X’独立同分布,具有熵H(X),则
\[Pr(X = X') \ge 2^{-H(X)}\]3 渐进均分性
4 随机过程的熵率
4.1 马尔科夫链
4.2 熵率
4.3 例子:加权图上随机游动的熵率
4.4 热力学第二定律
4.5 马尔科夫链的函数
\[H(Y_n | Y_{n-1}, \dots, Y_1, X_1) \le H(\mathcal{Y}) \le H(Y_n | Y_{n-1}, \dots, Y_1)\]5 数据压缩
5.1 有关编码的几个例子
5.2 Kraft不等式
定理5.2.1(Kraft不等式): 对于D元字母表上的即时码,码字长度 \(l_1, l_2, \dots, l_m\)必定满足不等式
\[\sum_i D^{-l_i} \le 1\]5.3 最优码
\[l_i^* = - \log_D p_i\]5.4 最优码长的界
5.5 唯一可译码的Kraft不等式
5.6 赫夫曼码
5.7 有关赫夫曼码的评论
5.8 赫夫曼码的最优性
5.9 Shannon-Fano-Elias编码
5.10 香农码的竞争最优性
5.11由均匀硬币投掷生成离散分布
6 博弈与数据压缩
6.1 赛马
6.2 博弈与边信息
6.3 相依的赛马及其熵率
6.4 英文的熵
6.5 数据压缩与博弈
6.6 英语的熵的博弈估计
7 信道容量
离散信道: \(C = \max_{p(x)} I(X;Y)\)
7.1 信道容量的几个例子
7.2 对称信道
如果信道转移矩阵 \(p(y|x)\) 的任何两行相互置换,任何两列也相互置换,那么称该信道是对称的.
7.3 信道容量的性质
7.4 信道编码定理预览
7.5 定义
7.6 联合典型序列
7.7 信道编码定理
7.8 零误差码
7.9 费诺不等式与编码定理的逆定理
7.10 信道编码定理的逆定理中的等式
7.11 汉明码
7.12 反馈容量
7.13 信源信道分离定理
8 微分熵
8.1 定义
\[h(X) = -\int_S f(x)\log{f(x)}dx\]均匀分布 \(h(X) = \log{a}\)
正态分布 \(h(X) = 1/2\log{2 \pi e \delta^2}\)