信息论基本概念

2020-03-20 本文已影响0人 echo_ye4

单符号离散模型

信源每次输出一个单一符号，信宿每次接收一个单一符号
信源（事件X）
$\begin{pmatrix} X\\ P(X) \\ \end{pmatrix} = \begin{Bmatrix} a_1 && a_2 && ... && a_n\\ p(a_1) && p(a_2) && ... && p(a_n) \\ \end{Bmatrix}$
信宿（事件Y）
$\begin{pmatrix} Y\\ P(Y) \\ \end{pmatrix} = \begin{Bmatrix} b_1 && b_2 && ... && b_m\\ p(b_1) && p(b_2) && ... && p(b_m) \\ \end{Bmatrix}$

自信息

$I(a_i) = -log_2p(a_i)$ -- 自信息量
$I(a_ib_j) = -log_2p(a_ib_j)$ -- 联合自信息量
$I(a_i|b_j) = -log_2p(a_i|b_j)$ -- 条件自信息量

其中 $I(a_i)$ 表示 $a_i$ 的不确定度， $I(a_i|b_j)$ 表示已知 $b_j$ 的情况下， $a_i$ 仍存在的不确定度

熵（平均信息量）

信源熵
$H(X) = E(I(a_i)) = \sum p(a_i)I(a_i) = - \sum p(a_i)log_2p(a_i)$
联合熵
$H(XY) = E(I(a_ib_j)) = \sum \sum p(a_ib_j)I(a_ib_j) = - \sum p(a_ib_j)log_2p(a_ib_j)$
条件熵
$H(X|Y) = E(I(a_i|b_j)) = \sum \sum p(a_ib_j)I(a_i|b_j) = - \sum p(a_ib_j)log_2p(a_i|b_j)$

互信息

信源发出 $a_i$ 的概率为 $p(a_i)$
信宿收到 $b_j$ 时推测信源发出 $a_i$ 的概率为 $p(a_i|b_j)$
互信息量定义为：
$I(a_i;b_j) = log_2 \frac{p(a_i|b_j)}{p(a_i)} = I(a_i) - I(a_i|b_j)$
$b_j$ 对 $a_i$ 的互信息量可以理解为， $a_i$ 的不确定度减去 $b_j$ 确定后 $a_i$ 的不确定度，即 $b_j$ 确定后消除的对 $a_i$ 的不确定度

平均互信息量

$I(X;Y) = \sum \sum p(a_ib_j) I(a_i;b_j)$
其物理意义：
1）信源的先验不确定度- 信道疑义度
$I(X;Y) = H(X) - H(X|Y)$
2）信宿熵 - 信道噪声
$I(X;Y) = H(Y) - H(Y|X)$
3）通信前的熵 - 通信后产生统计性联系的熵
$I(X;Y) = H(X) + H(Y) - H(XY)$

image.png

信道容量

信道转移矩阵
$\begin{Bmatrix} p(b_1|a_1) & p(b_2|a_1) & ... & p(b_m|a_1) \\ ... &&&\\ p(b_1|a_n) & p(b_2|a_n) & ... & p(b_m|a_n) \\ \end{Bmatrix}$

如果信源熵为 $H(X)$ ，由于信道存在干扰，一般情况下输出端只能接收到 $I(X;Y)$

定义信道的信息传输率 $R = I(X;Y)$

平均互信息是信源无条件分布概率
${p(a_i)}$ 和信道转移概率 ${p(b_j|a_i)}$ 的函数，当信道特性（信道转移概率）固定后，互信息随着信源分布概率变化，且为上凸函数

找到一种信源概率分布，使信息传输率最大，定义这个最大的信息传输率为传输容量 $C = max R = max I(X;Y)$

相对熵与交叉熵

相对熵也称KL散度，在信息理论中，相对熵是用来度量使用基于Q的编码来编码来自P的样本平均所需的额外的比特个数。典型情况下，P表示数据的真实分布，Q表示数据的理论分布，模型分布，或P的近似分布。
$D_{KL(p||q)} = \sum p(x)log(\frac {p(x)}{q(x)})$
相对熵也可以衡量两个随机分布之间的距离

$D_{KL(p||q)} = \sum p(x)log(p(x)) - \sum p(x)log(q(x))$

定义交叉熵 $H(p,q) = \sum p(x)log(q(x))$

$D_{KL(p||q)} = H(X) - H(p,q)$

多符号离散平稳模型

信源每次输出一个符号序列，序列的每一位都是随机的，而前后符号是有统计关系的，若信源发出的符号序列的概率分布与时间无关，我们称之为多符号离散平稳信源。

二维平稳信源

信源发出的符号序列中，每两个符号看作一组，每组 $X = X_1X_2$ 代表一个消息，为了便于分析，我们假设组与组之间是统计独立的，但是要注意这与实际情况并不相符，由此得出的信源熵仅仅是近似值。
假设 $X_1,X_2 \in \left\{ a_1, a_2, ..., a_n \right\}$
则 $X \in \left\{ a_1a_1, ..., a_1a_n, a_2a_1, ..., a_na_n \right\}$
$\alpha_i = (a_{i1}a_{i2})$ ， $i = 1,2,...,n^2$
$\sum p(\alpha_i) = 1$
$\begin{pmatrix} X \\ P(X) \\ \end{pmatrix} = \begin{Bmatrix} \alpha_1 & \alpha_2 & ... & \alpha_i \\ p(\alpha_1) & p(\alpha_2) & ... & p(\alpha_i) \\ \end{Bmatrix}$

信源熵为 $H(X) = H(X_1X_2) = H(X_1) + H(X_2|X_1)$

N维平稳信源

信源熵为 $H(X) = H(X_1X_2) = H(X_1) + H(X_2|X_1) + H(X_3|X_1X_2) + ... + H(X_N|X_1X_2...X_{N-1})$

极限熵

信源平均每发一个符号所提供的信息量为
$H_N(X) = \frac 1N H(X_1X_2...X_N)$
当 $N -> \infty$ 时， $H_{\infty} = \lim_{N->\infty} \frac1NH(X_1X_2...X_N) = \lim_{N->\infty} H(X_N|X_1X_2...X_{N-1})$ ，称为极限熵
在研究实际信源时，必须求出极限熵才能确切地表达每发一个符号提供的信息量，而这是比较困难的

马尔可夫信源

在许多信源的输出序列中，符号之间的依赖是有限的，任何时刻信源发生的概率只与前面若干个符号有关。
在随机变量序列中，时刻m+1的随机变量 $X_{m+1}$ 只与前面发生的m个随机变量有关，与更前面的随机变量无关，这种信源称为马尔可夫信源
因此，极限熵 $H_{\infty} = H(X_{m+1}|X_1X_2...X_m)$

在机器学习上的应用

使用交叉熵作为loss function

在分类学习时，真实label的概率分布为Y，预测label的概率分布为A，要使A尽量接近Y，可以最小化 $D_{KL(p||q)}$ ，由于H(Y)是常数，因此可以简化为最小化 $-H(p,q)$
$min -\sum y log(a)$

最大熵模型

基本思想：在满足约束的情况下，最大化 $P(Y|X)$ 的条件熵，使用 $P(Y|X)$ 来进行预测

从训练数据中，根据极大似然估计，可以求出经验分布 $P'(X)$ 和 $P'(XY)$
特征函数 $f(x, y) = \left\{ \begin{array} {} 1 & x,y满足某一事实\\ 0 & 其他\\ \end{array} \right.$
用特征函数的期望建立约束，有n个特征函数，就有n个约束
$\sum p'(xy)f(x,y) = \sum p'(x)p(y|x)f(x,y)$

建立最优化模型
$max -\sum p'(x)p(y|x)log(p(y|x))$
$s.t. \sum p'(xy)f_i = \sum p'(x)p(y|x)f_i, i = 1,2,...,n$
$\sum_y p(y|x) = 1$

决策树模型

建立树模型，每个节点代表一个特征的划分，使用0-1 loss function
节点划分是一个NP-hard问题，考虑采用启发式算法，根据规则每次选择最好的节点
其中一个规则是该节点可以提供最多的信息，即熵减小最多，熵越小，loss function越小，所以实际上是选择使loss function减小最多的节点
设数据集为D，特征为A，分割前的熵为H(D)，分割后有多个数据集 $D_1, D_2,...$ ，分割后的熵为 $H(D,A) = \frac {D_1}{D}H(D_1) + \frac {D_2}{D}H(D_2) + ...$ ，因此信息增益为 $g(D,A) = H(D) - H(D,A)$ ，选择信息增益最大的特征