信息论基本概念

文章导读：

1. 熵
2. 联合熵和条件熵
3. 互信息
4. 相对熵
5. 交叉熵
6. 困惑度
7. 模拟信道模型
   

最近在看《统计自然语言处理》，觉得第二章预备知识里的关于信息论的一些基本概念总结得很不错。虽然对于熵这个词，我接触过很多次，在机器学习里的很多地方也都有涉及到，比如说最大熵模型，决策树训练时的互信息等等。但是有的时候我还是会经常搞混淆，这里简单介绍一下常用的概念。

一. 熵

对于离散变量(X), 假设其取值空间为(R)，其概率分布为(p(x) = P(X = x), x in R)，那么定义随机变量(X)的熵为：

[H(X) = - sum_{x in R} p(x)log_x (p(x)) ]

约定(0log(0) = 0)。由于这里使用了2为底，所以该公式定义的熵的单位为二进制单位(比特)，实际情况也有使用其它底数的版本的熵。
熵又被成为自信息(self-information)，可以将其描述为一个随机变量不稳定的程度。通过简单的数学计算可以证明当随机变量(X)在其取值空间上对所有值等概率的情况下，熵达到最大值，也就是说随机变量随机性越强，它的熵越大。如果在某一个值上取值概率为1，也就是说这个随机变量其实并不随机，是一个定值，这个时候的熵达到最小值0，它毫无随机性。
熵还可以表示信源(X)每发出一个符号所提供的平均信息量。熵越大，越难猜测变量正确的值，因此给予的信息就越多。

二. 联合熵和条件熵

有了单变量的情况，很自然就想到多变量下联合概率和条件概率的情况。
对于一堆随机变量(X, Y)，其联合概率为(p(x, y))，则其联合熵为：

[H(X, Y) = - sum_{xin X} sum_{y in Y} log_2(p(x, y)) ]

联合熵实际熵就是描述一对随机变量平均所需要的信息量。
条件熵就是给定条件概率(p(Y|X))的情况下：

[H(Y|X) = sum_{xin X} p(x)H(Y|X = x) = sum_{x in X}sum_{yin Y}p(x)p(y|x)log(p(y|x) = sum_{xin X}sum_{y in Y}p(x)frac{p(x,y)}{p(x)}log(frac{p(x,y)}{p(x)}) = sum_{xin X}sum_{y in Y}p(x,y)log(p(x,y) - p(x,y)logp(x) = sum_{xin X}sum_{y in Y}p(x, y)log(p(x,y) - sum_{xin X}p(x)log(p(x)) = H(X, Y) - H(X) ]

这个式子也被称为熵的连锁规则，推广到一般情况有：

[H(X_1, X_2, ..., X_n) = H(X_1) + H(X_2|X_1) + H(X_3|X_2, X_2) + ... + H(X_n|X_{n-1}, X_{n-2},...,X_1) ]

条件熵可以看作是在受变量(X)影响的情况下，变量(Y)的不稳定程度。
对于来自于同一个分布(X)的一个随机变量序列((X_1, X_2, ..., X_n))，用(X_{1n})表示。当我们求这个序列的熵的时候，我们可以将其表示为(n)个同样的随机分布(X)的联合熵，为(-sum_{x_{1n}} p(x_{1n})log(p(x_{1n})))。
于是，对于一条长度为n的信息，每一个字符或字的熵为：

[H_{rate} = frac{1}{n}H(X_{1n}) = -frac{1}{n}sum_{x_{1n}} p(x_{1n})log(p(x_{1n})) ]

这个数值被称为熵率。
对于语言模型来说，如果假定一种语言是由一系列符号组成的随机过程(L=(X_i))，例如，某报纸的一批预料，那么，可以定义这种语言L的熵率作为其随机过程的熵率：

[H_{rate} = lim_{n ightarrow infty}frac{1}{n}H(X_{1n}) ]

三. 互信息

根据上面的链式法则得到：

[H(X, Y) = H(X) + H(Y|X) = H(Y) + H(X|Y) ]

于是有: $$H(X) - H(X|Y) = H(Y) - H(Y|X)$$
这个差值被称为变量(X)和(Y)之间的互信息，计作(I(X; Y))。它反映了在知道了(Y)的值以后，(X)的不确定性的减少量，同时也是在知道了(X)的值以后，(Y)的不确定性的减少量。可以理解为(Y)的值透露了多少关于(X)的信息量。
将其展开:

[I(X;Y) = H(X)-H(X|Y) = H(X) + H(Y) - H(X, Y) = -sum_x p(x)log(p(x)) - sum_y p(y)log(p(y)) + sum_{x, y} p(x, y)log(p(x, y)) = sum_{x, y}p(x,y)logfrac{p(x, y)}{p(x)p(y)} ]

从这个式子可以看出(I(X;X) = H(X) - H(X|X) = H(X))，这也就是把熵称为自信息的原因。另一方面可以看出，如果(I(X;Y)>>0)，则表明(X)和(Y)是高度相关的。如果(I(X;Y) = 0)，即(p(x,y)=p(x)p(y))则说明两者完全独立。如果(I(X;Y)<<0)，则表明(Y)的出现不但未使(X)的不确定性降低，反而加大了其不确定性，这通常是不利的。
同样可以推导条件互信息。
条件互信息：

[I(X;Y|Z) = I((X;Y | Z)) = H(X|Z) - H(X|Y,Z) = H(X) - I(X;Z) - (H(X) - I(X;Y,Z)) = I(X;Y,Z) - I(X;Z) ]

四. 相对熵

相对熵又被称为KL距离，是衡量相同事件空间里两个概率分布相对差距的测度。两个概率分布(p(x))和(q(x))的相对熵定义为：

[D(p||q) = sum_{xin X}p(x)logfrac{p(x)}{q(x)} = E_p(logfrac{p(x)}{q(x)}) ]

显然，当两个随机分布完全相同，即(p=q)时，相对熵为0，当其差别增加时，其相对熵的期望值也增大。
之前证明了$$I(X;Y) = sum_{x, y}p(x,y)logfrac{p(x, y)}{p(x)p(y)} = D(p(x,y)||p(x)p(y))$$
于是知道互信息就是衡量一个联合分布与独立性差距多大的测度。

五. 交叉熵

根据前面的定义，知道熵就是一个不确定性的测度。对于某件事情，我们知道的越多，熵就越小，因而我们对于试验的结果就越不感到意外。交叉熵的概念就是用来衡量估计模型与真是概率分布之间差异情况的。
如果一个随机变量(Xsim p(x))，(q)是我们计算得到的模型，(q(x))是模型(q)对于真实分布(p(x))的近似表示。那么随机变量(X)和模型(q)之间的交叉熵定义为：

[H(X, q) = H(X) + D(p || q) = -sum_{xin X} p(x)log(p(x)) + sum_{xin X} p(x)logfrac{p(x)}{q(x)} = -sum_{xin X}p(x)log(q(x)) = E_p(logfrac{1}{q(x)}) ]

这里联想到之前在介绍神经元交叉熵损失的时候给出了这样一个定义(yln(a) + (1-y)ln(a))，可以知道这里的(y)并不是对应说真实的标签，而是对于该神经元的两种状态0或1，当其真实值为1时，即(p(x = 1) = 1),损失为(log(q(x=1))，当其真实值为0时，即(p(x=0) = 1),损失就是(log(1-q(x=1) = log(q(x=0)))，和我们这里交叉熵的定义完全符合。
注意到这里交叉熵写作(H(X, q))，这似乎就是联合熵的形式，这样表示不会引起误会吗？事实上，交叉熵可以看作是一种特殊场景下的联合熵，它是衡量一个变量(X)，和我们对其的近似表示(q(x))的联合熵。如何这个近似非常完美，即(q(x))就是(X)的真实分布(p(x))，那么(D(p||q) = 0, H(X, q) = H(X, X))，就是自身的联合熵了。
接着我们定义一个语言(L = (X) sim p(x))与我们构建的语言模型(q)的交叉熵为：

[H(L, q) = -lim_{n ightarrow infty}frac{1}{n} sum_{x^n_1} p(x^n_1)log(q(x^n_1)) ]

其中，(x^n_1 = x_1, x_2, .. ,x_n)为语言(L)的词序列样本，这里的词包括样本中出现的任意词汇、数字、标点等。我们假设这种语言是“理想”的，于是有n趋于无穷大时，有全部“词汇”的概率和为1，根据信息论的定理，假定语言L是稳态遍历的随机过程，就可以得到：

[H(L, q) = -lim_{n ightarrow infty}frac{1}{n} log(q(x^n_1)) ]

就是说可以用样本的熵表示整个语言的熵。
在实际情况下，当我们选择的样本量n足够大的时候，可以将上式子近似表示为(-frac{1}{N}log(q(x^N_1))，交叉熵越小，表示我们的模型越接近真实的语言模型，效果越好。

六. 困惑度

在设计语言模型的时候，我们通常并不使用交叉熵而是使用困惑度(perplexity)来表示。给定语言L的样本(l^n_1 = l_1...l_n),L的困惑度PP_q为：

[pp_q = 2^{H(L,q)} approx 2^{-frac{1}{n}log(q(l^n_1)} = [q(l^n_1)]^{-frac{1}{n}} ]

于是语言模型设计的任务就是寻找困惑度最小的模型，使其最接近真实语言的情况。
从perplexity的计算式可以看出来，它是对于样本句子出现的概率，在句子长度上Normalize一下的结果。它越小，说明出现概率越大，所得模型就越好。

七. 模拟信道模型

在学通信原理的时候学习过信道的概念，一个信号经过一个信道，会由于压缩编码，噪声引入，然后在解码的时候就会多少有一点失真。
在自然语言处理中，很多问题也都可以归结为这样的模型。给定输出(O)(可能含有误传信息)的情况下，如何从所有可能的输入(I)中选出最可能的那个：

[hat{I} = argmax_I (p(I|O)) = argmax_I (frac{P(I)p(O|I)}{p(O)}) = argmax_I (p(I)p(O|I)) ]

其中(p(I))成为语言模型，是指在输入语言中“词”序列的概率分布；另一个(p(O|I))成为信道概率。
对应到实际的NLP问题，比如说机器翻译在进行汉译英的时候，汉语句子看作是信道输出O，求出最可能的信道输入英语句子I。
噪声信道模型在NLP中有非常多的用途，除了机器翻译以外，还用于词性标注、语音识别、文字识别等很多问题的研究。