数学之美 笔记2
<br>
如上篇笔记所言，我非常喜欢吴军老师的这本《数学之美》。这篇阅读笔记包含信息论中的一些重要概念，它们对于通信、数据压缩以及自然语言处理都有很重要的指导意义。
信息熵与冗余度
信息熵是衡量信息大小的一个度量概念，由香农博士（Claude Shannon）提出。书中首先用了一个简单的例子来介绍信息量的概念，假设有32支球队参加世界杯，那么所有球队需要5位的二进制编码来完整表示，所以”谁是世界冠军“的信息量就是5比特。信息量的大小一般与所有可能情况的对数函数 $log$ 相关。
但是众所周知，这32只球队每支球队夺冠的可能性，或者说概率是不可能完全相等的，因此假设让一个懂球的人来猜，或许只需要3-4次就能猜出冠军球队（将少数几个强队分成一组，其他分成另一组，然后猜测冠军是否在热门球队组中，重复此过程）。所以，严格来说”谁是世界杯冠军“的信息量要比5比特少。香农博士指出，其准确的信息量是
$$ H = - \sum p_i ; log(p_i) $$ 其中，$p_i$ 表示第 $i$ 支球队的夺冠概率。香农将它称作信息熵（Entropy），用 $H$ 表示，单位是比特。信息熵的通用公式为 $$ H = -\sum\limits_{x\in X} P(x);logP(x) $$
信息论中另一个有用的概念是冗余度。举个简单的例子，一本书有50万字，用一个较好的算法对其进行压缩，信息量大约是250万比特，也就是320KB；但是如果不进行压缩，仅用国际的两字节编码储存这本书，需要大约1MB，这两个数量的差距就是这本书的冗余度。在所有语言中，汉语是一个冗余度相对较小的语言。
信息的作用
自古以来，信息与消除不确定性就是相互关联的。抽象来说，一个事物内部总是会存在随机性，也就是不确定性，假定为 $U$ ，而消除它的唯一办法就是引入信息 $I$ ，引入信息的量取决于 $U$ 的大小，要 $I > U$ 才行。若引入的信息量 $I$ 小于 $U$，则引入信息后的不确定性可以用式子
$$ U' = U - I $$
来表示。
网页搜索本质上来说就是利用信息消除不确定性的过程。给定用户提供的关键词，怎么才能从成千上万亿的网页中找到用户需要的呢？这时正确的做法应当是去挖掘正确有用的信息，比如网站的质量信息；如果还是不够，不妨问问用户。不正确的做法是去玩弄数字以及公式，这样做往往没有什么效果；而最糟糕的做法是去人为地“蒙”，虽然“蒙”增加了信息，并满足了一部分用户的口味，但是同时却牺牲了其他大部分用户，本质上看搜索结果更糟。合理运用信息，而非玩弄什么公式和机器学习算法是做好搜索的关键。
互信息
互信息是香农在信息论中提出的概念，用以量化度量两个随机事件的相关性。假设有两个随机事件 $X$ 和 $Y$ ，它们的互信息定义是： $$ I(X;Y) = \sum\limits_{x\in X,,y\in Y}P(x,y),log\frac{P(x,y)}{P(x)P(y)} $$ 别看这个公式复杂，其实它与之前我们提到的信息熵密切相关。通过数学证明，互信息就是随机事件的信息熵 $H(X)$ 与在知道随机事件 $Y$ 后的条件熵 $H(X|Y)$ 的差，即 $$ I(X;Y) = H(X) - H(X|Y) $$ 值得指出的是，互信息是一个取值在 0 到 $min(H(X), H(Y))$ 之间的函数。当 $X$ 和 $Y$ 完全相关时，它的取值是 $H(X)$，同时 $H(X)=H(Y)$; 当两者完全无关时，它的取值是 0。
那么互信息有什么用呢？机器翻译中，最难的两个问题之一是词义的多元性，（又称歧义性）。比如Bush既是总统布什的名字，又是灌木丛的英文，所以在翻译时机器很难简单的判断选择哪个意思。一种简单而有效的解决办法就是使用互信息：首先从大量文本中找出和总统布什一起出现的互信息最大的词，比如总统、国会等；再用同样方法找出和灌木丛一起出现的互信息打的词，比如土壤、植物等。有了这些，在翻译时看看上下文哪组词多就行了。
交叉熵
交叉熵 或者 相对熵 （Kullback-Leibler Divergence）是库尔贝克和莱伯勒提出的用以衡量两个取值为正的函数的相似性的概念。其定义如下： $$ KL(f(x)||g(x)) = \sum\limits_{x\in X}f(x)\cdot log\frac{f(x)}{g(x)} $$ 如书中所说，公式本身并不重要，只要记住下面三条结论：
-
对于两个完全相同的函数，其交叉熵为 0。
-
交叉熵越大，两个函数差异越大；反之，交叉熵越小，函数差异越小。
-
对于概率分布或者概率密度函数，若取值均大于零，交叉熵可以用来度量两个随机分布的相似性。
值得注意的是，交叉熵是不对称的，这样用起来有时候不是很方便。因此，詹森和香农提出了一种新的交叉熵： $$ JS(f(x)||g(x)) = \frac{1}{2}[KL(f(x)||g(x)+KL(g(x)||f(x))] $$
小结
信息熵，条件熵和交叉熵这三个概念与语言模型的关系非常密切。信息熵不仅是对信息的量化度量，而且是整个信息论的基础。它可以直接用于衡量统计模型的好坏。如果有了上下文条件，应该用条件熵。如果再考虑到从训练语料和真实应用的文本中得到的概率函数有偏差，就需要再引入交叉熵的概念。
参考
-《数学之美》第二版第六章 -- 吴军