本章介绍信息论的一些基本概念，如熵、联合熵、条件熵、互信息、相对熵、交叉熵、困惑度，以及噪声信道模型。
熵
如果X是一个离散型随机变量，取值空间为R，其概率分布为$ p(x) = P(X = x),x \in R$，那么X的熵（entropy） $ H(X)$定义为：
$$
H(X) = - \sum_{x \in R} {p(x) \log _2p(x)}
$$
其中，约定$ 0 \log 0 = 0$。$ H(X)$可以写为$ H(p)$。之后将$ \log _2p(x)$简写成$ \log p(x)$。
熵又称为自信息（self-information），可以视为描述一个随机变量所需的信息量
$ \log (x)$代表编码x需要的长度
为什么熵最大的模型是最符合事件真实分布的模型
最大熵：整个系统是用无信息先验模型来进行拟合，现有数据是一些evidence，根据这些evidence不断更新先验知识，组成新的先验知识对新的数据进行模拟，除了已有的evidence之外，所有情况出现的概率应该是一致的，这种情况下熵最大，我们没有办法假设有些情况出现的概率更高，所以使得熵最大的模型能最真实的反应事件的分布情况
联合熵和条件熵
如果X，Y是一对离散型随机变量 $X,Y \sim p(x,y)$，X，Y的联合熵（joint entropy）$ H(X,Y)$定义为： $$ H(X,Y) = - \sum_{x \in X}\sum_{y \in Y} {p(x,y) \log p(x,y)} $$ 给定随机变量X的情况下，随机变量Y的条件熵（conditional entropy） 定义为：
$$ H(Y|X) = \sum_{x \in X}{p(x)H(Y|X=x)} = \sum_{x \in X}{p(x)} \left[\sum_{y \in Y}p(y|x) \log (y|x) \right] = -\sum_{x \in X}\sum_{y \in Y} {p(x,y) \log p(y|x)} $$
熵的连锁规则：
$$
H(X_1,X_2,\cdots,X_n) = H(X_1) + H(X_2|X_1) + \cdots + H(X_n|X_1,\cdots,X_{n - 1})
$$
一般地，对于一条长度为n的信息，每一个字符或字的熵为：
$$
H_{rate} = \frac{1}{n} H(X_{1n}) = - \frac{1}{n} \sum_{x_{1n}}{p(x_{1n}) \log p(x_{1n})}
$$
这个数值称为熵率（entropy rate）。其中，变量 $ X_{1n}$ 表示随机变量序列$ (X_1,X_2,\cdots,X_n)$，$ x_{1n} = (x_1,x_2,\cdots,x_n)$。
假定一种语言是由一系列符号组成的随机过程，$ L(X_i)$，例如，某报纸的一批语料，那么，我们可以定义这种语言L的熵作为其随机过程的熵率，即
$$
H_{rate}(L) = \lim_{n \to \infty} \frac{1}{n} H(X_1,X_2,\cdots,X_n)
$$
互信息
根据熵的连锁规则，有
$$
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的互信息（mutual information），记作$ I(X;Y)$。或者定义为：如果 $X,Y \sim p(x,y)$，则X，Y之间的互信息$ I(X;Y) = H(X) - H(X|Y)$。
$I(X;Y)$反映的是在知道了Y的值之后X的不确定性的减少量。可以理解为Y的值透露了多少关于X的信息量。
由于$ H(X|X) = 0$，因此
$$
H(X) = H(X) - H(X|X) = I(X;X)
$$
这一方面说明了为什么熵又叫自信息，另一方面说明了两个互相依赖的变量之间的互信息不是一个常量，而是取决于它们的熵。
相对熵
相对熵（relative entropy） 又称Kullback-Leibler差异（Kullback-Leibler divergence），或简称KL距离，是衡量相同事件空间里两个概率分布相对差距的测度。两个概率分布$ p(x)$和$ q(x)$的相对熵定义为：
$$
D(p||q) = \sum_{x \in X}{p(x) \log {\frac{p(x)}{q(x)}}}
$$
该定义中约定$ 0 \log (0/q) = 0$，$ q \log (q/0) = \infty$，表示成期望值为：
$$
D(p||q) = E_p \left( \log {\frac{p(X)}{q(X)}} \right)
$$
$ \log (p(x) / q(x))$ 表示用分布p来编码需要的长度 - 用q来编码所需长度
显然，当两个随机分布完全相同时，即$p = q$，其相对熵为0。
互信息实际上就是衡量一个联合分布与独立性差距多大的测度：
$$
I(X;Y) = D(p(x,y)||p(x)p(y))
$$
交叉熵
如果一个随机变量X ~ $ p(x)$，$ q(x)$为用于近似$ p(x)$的概率分布，那么，随机变量X和模型$ q$之间的 交叉熵（cross entropy） 定义为：
$$
H(X,q) = H(X) + D(p||q) = H(X,p) + D(p||q)
= - \sum_{x} {p(x) \log q(x)}
= E_p \left( \log {\frac{1}{q(x)}} \right)
$$
由此，可以定义语言 $L= (X) \sim p(x)$与其模型$ q$的交叉熵为：
$$
H(L,q) \approx -\frac{1}{N} \log {q(x_1^N)}
$$
马尔可夫链：第n个词出现的概率只与 1 ... n-1 个词有关
稳态过程：第n个词出现的概率只与前n-1个词有关，与时间状态无关，比如句子："我 有 ... ,，我 有 ..."，第一个“有”出现的概率为1/100，第二个“有”出现的概率也是1/100，与这个词出现在句首、句中还是句尾无关。
困惑度
给定语言L的样本$ l_1^n = l_1,l_2,\cdots,l_n$，L的困惑度（perplexity） $PP_q$定义为： $$ PP_q = 2^{H(L,q)} \approx 2^{-\frac{1}{n} \log q(l_1^n)} = \left [ q(l_1^n) \right ]^{-\frac{1}{n}} $$ 语言模型的任务就是寻找困惑度最小的模型，使其最接近真实语言的情况。
噪声信道模型
香农（Claude Elwood Shannon）提出了噪声信道模型（noisy channel model），其目标就是优化噪声信道中信号传输的吞吐量和准确率，其基本假设是一个信道的输出以一定的概率依赖于输入。
信道容量（capacity） 的定义如下，其基本思想是用降低传输速率来换取高保真通信的可能性。
$$
C = \max_{p(X)}I(X;Y)
$$
根据这个定义，如果能够设计一个输入编码X，其概率分布为$ p(X)$，使其输入与输出之间的互信息达到最大值，那么，我们的设计就达到了信道的最大传输容量。从数学上讲，信道容量C就是平均互信息量的最大值。
参考
宗成庆《统计自然语言处理》第二章
