[读书笔记] [PRML] 1.6 Information Theory
本节的主要知识点涵盖了信息论中的一些核心指标熵 、相对熵（KL散度） 以及条件熵 等相关概念，并延伸至这些关键指标在机器学习领域的重要作用。具体而言，在特征选择等任务中具有重要应用的决策树方法，在当前研究热点中取得显著成效的互信息理论同样发挥着不可替代的作用。
在熵之前存在一个被称为信息量的概念，请问什么是信息量呢？当得知‘有效抗癌药物研发成功’时，请问你会感到非常惊讶；而当得知‘今天下午将停电’时，则不会觉得那么令人震惊；同样地，请问当得知‘明天太阳会升起’时，则不会予以关注。由此可见，在这三条消息中体现出的不同让你感到意外的程度（degree of surprise）是截然不同的。对于第一条消息而言，请问你会感到非常意外；这意味着这条消息所包含的信息含量较大；而对于第三条消息来说，请问你不会对此感到意外一言半语也无法形容这种差异；因此可以得出结论：**信息量实际上就是在一条消息中所传达出的意外程度或令人震惊的程度。
此外，在这三条消息中涉及的各个事件发生的可能性也不尽相同。具体而言，在第一条消息中所涉及的事件当前发生可能性相对较低（即其发生可能性较低），从而对应着较高的信息传递价值；而在第三条消息中所涉及的特定事件必定会发生（即其发生可能性为100%），因此其携带的信息传递价值则为零。由此可见，在处理不同数量的消息时需要注意区分各个具体事件的可能性大小与其对应的关联性高低之间的关系：即当某一特定事件的发生可能性越低时，则其携带的信息传递价值越高；反之则相反——当某一特定事件的发生可能性越高，则其携带的信息传递价值就越小。
换一个角度来看，在信息论中指出：当事件发生的可能性较低时，则预示着该事件所携带的信息量较大。具体而言，在给定条件下（例如某个系统或模型中），当某件事情发生的可能性越低，则其发生时所带来的信息量就越大。同时，在这种情况下（即当某个事件的概率较高时），该事件本身的不确定性也会相应降低。
Entropy and conditional entropy
上面只是对信息量比较直观的理解，下面是具体的数学定义。
当我们观察到离散型随机变量x的一个具体取值时, 我们接收到的信息量是多少, 即所谓的信息熵。这一概念进一步指出, 在学习该变量x的具体值时所感受到的惊讶程度与其发生概率之间存在密切关系。因此, 在构建衡量这种不确定性大小的信息度量——即所谓的‘信息熵’（通常记作h）——的时候就需要找到这样一个合适的函数, 即满足单调递增关系并能对应相应数值的函数形式。为了构建这样的函数h(x) , 我们需要找到一个关于概率分布p(x) 的单调递增关系, 并确保其计算结果对应于相应的信息熵h.
需要注意的是，在这种情况下h(\cdot)必须满足一定的条件。具体而言，在概率空间中存在两个相互独立的随机变量x和y（即p(x,y)=p(x)p(y)），则根据可加性原则可知，在联合事件(x,y)下所获得的信息量应当等于分别从x和单独从y}中所获得的信息量之和。基于此性质h(\cdot}的一个可能定义即是h(x)= -\log{p}(x}。这一设定不仅保证了信息度量结果始终非负而且具有明确的物理意义。通过这一单一信息度最概念进一步可导出传输某一随机变量取值时其平均信息度最的概念具体而言可以通过对其概率分布p(x}求期望来实现。由此我们便得到了如下的熵（entropy）公式：
H[x] = -\sum_x{p}(x} \log {p}(x})
上述讨论表明信息度最衡量了消息所带来的不确定性而熵则量化了随机变量所包含的不确定性程度。具体而言当熵越大表明该随机变量所能取值的可能性越均匀因而其不确定性越高相反地当某一特定取值的概率趋近于1而其他取值的概率趋近于零时对应的熵则会达到最小值仅为零在这种极端情况下系统的不确定性最低因为几乎确定会发生某一特定结果
此外还可以将这一概念与最短平均编码长度联系起来当概率分布较为均匀时所需的编码长度自然也就较长反之若分布较为集中所需编码长度则会相应减少这与熵的变化趋势呈现高度一致性
为了求解最大熵问题，可以通过Lagrange乘子法进行优化。其Lagrange函数定义为：
\tilde{H} = - \sum_{i} p(x_i) \ln p(x_i) + \lambda \left(\sum_{i}p(x_i) - 1 \right)
通过对上述函数进行极值求解，可得：
\frac{\partial{\tilde{H}}}{\partial{p(x_i)}} = 0
即满足条件：
-1 - \ln p(x_i) + \lambda = 0
由此可知，在达到最大熵时，各状态的概率值相等。也就是说，
p(x_i) = p(x_j), \forall i, j 成立；若随机变量 x 的取值有 M 种情况，则概率分布满足 p(x_i) = \frac{1}{M} 对所有 i,j 都成立。此时对应的熵值为 H = \ln M。
而对于连续型随机变量，则其熵的计算公式为：
H[x] = -\int{p(x) \ln p(x) dx}
特别地，在连续情况下，
这一计算结果被称为微分熵（differential entropy）。而当随机变量服从正态分布时，
微分熵达到最大值。
考虑随机变量 (x, y)， 其联合概率分布为 p(x, y)。如果随机变量 x 的值已知，那么有条件概率 p(y |x)，另外确定 y 的值需要的信息量应该由 - \ln p(y|x) 来衡量，那么平均另外需要的信息量为
\begin{aligned} H[y|x] &= -\iint{p(y,x)\ln p(y|x)\mathrm{d} y\mathrm{d} x} \\ &= - \iint{p(x) p(y|x) \ln p(y|x) \mathrm{d}x \mathrm{d}y} \\ &= -\int p(x_i) H[y | x = x_i] \mathrm{d}x \\ \end{aligned}
也可以称为给定 x 的 y 的条件熵（conditional entropy），也可以理解为 x 给定条件下 y 的条件概率分布的熵对 x 的数学期望。可以看到条件熵满足以下公式：
H[x,y] = H[y|x] + H[x]
其证明可见下面 exercise 1.37的解答。 上式可以理解为描述 x, y 所需要的信息量等于描述 x 所需要的信息量与再给定 x 的情况下另外所需要的信息量的和。
Relative entropy and mutual information
Relative entropy
设有一个未知的概率分布p(x)，并假设我们使用q(x)作为其近似分布，则计算x值所需的信息量为∫p(x) ln q(x) dx这一指标被称为交叉熵；而相对应的信息量为：
\begin{aligned} \mathrm{KL} (p | q) &= - \int{p(x) \ln q(x)} dx + \int{p(x) \ln p(x)} dx \ &= -\int{p(x)}\ln\left(\frac{q(x)}{p(x)}\right) dx \ &=E\left(\ln p(x) - \ln q(x)\right) \end{aligned}
其中即为相对熵（Relative entropy）的定义；而更为常见的是将其称为KL散度（Kullback-Leibler divergence, KL divergence）。这种散度衡量了两个概率分布之间的相似程度；然而值得注意的是其不对称性以及不满足三角不等式特性；因此严格来说它并非距离测度。
应用该不等式进行上述公式计算，则有：
KL(p||q) = -\int p(x)\ln\left(\frac{q(x)}{p(x)}\right)\mathrm d x \ge -\ln\int q(x)\mathrm d x=0
通过上述推导可知KL散度值非负，并且仅当 p(q)=q(q)时才能取到零值。这表明KL散度衡量了两个分布之间的差异程度，在分布越接近的情况下其值越小。
为了估计未知分布 p(x) 的概率密度函数形式, 我们通常会使用带有可调节参数 \theta 的分布族中的某个成员, 比如多元高斯分布族. 选择最优参数的一种常用方法即是通过最小化两个概率分布之间的差异性指标, 而这里的差异性指标被定义为 KL 散度. 然而由于我们无法确切知道真实的数据生成过程, 因此必须依赖于有限的训练样本来进行推断. 在 KL 散度的具体计算中, 我们所使用的定义实际上是将差分函数 \ln p(x) - \ln q(x) 的数学期望进行求解. 这里的期望值可以通过训练数据集提供的样本数据集来进行近似计算, 即采用经验均值 \frac{1}{N}\sum_{n=1}^N f(x_n) 来替代理论上的积分计算. 经过这样的近似处理后, KL 散度就可以表示为:
KL(p \| q) \approx \frac{1}{N}\sum_{n=1}^N \{-\ln q(x_n|\theta) + \ln p(x_n)\}
其中可以看到, 第二个加数项与待优化的参数 \theta 实际上是没有关系的, 而第一个加数项则对应着负对数似然函数的形式. 因此, 最小化 KL 散度的过程实际上等价于最大化似然函数.
Mutual information
我们关注的是两个随机变量 X 和 Y 的联合概率分布 p(X,Y)。当这两个变量相互独立时，满足p(X,Y)=p(X)p(Y)；而当它们之间存在依赖关系时，则可以通过计算两者之间的KL散度来量化它们的独立程度。这一度量特别适合捕捉变量间的非线性统计关联性：互信息这一度量特别适合捕捉变量间的非线性统计关联性：
I[X,Y] = \operatorname{KL}(p(X,Y)\|p(X)p(Y))
由于KL散度始终是非负的，则有I[X,Y]\geq 0；当且仅当x和y独立时等号成立。进一步地，在讨论信息论的基本概念时我们已经了解到条件熵的概念：
I[x,y] = H[x] - H[x|y] = H[y] - H[y|x]
详细证明过程可参考练习1.41。在此基础上我们可以进一步理解：在不确定性理论中随机变量x所携带的信息量可以用其熵来衡量即H[Y]表示了随机变量Y自身的不确定性；而给定已有x的情况下y的信息需求则由条件熵H[Y|X]决定因此我们可以将I[X,Y]解读为：在已知x的情况下y所减少的信息需求量这一观点为我们提供了一个新的视角去理解互信息的本质含义：它反映了系统中各要素之间相互作用所创造的新信息数量即系统整体复杂性的增量
从下面的 Venn 图能直观地解读：例如，在上文中提到 "给定 y 后 x 的信息量减少值"这一概念时，则可理解为：原本 y 的信息量即为图中右侧区域；而在给定 x 后，剩余的信息量仅为右侧 H(y|x) 部分；因此减少的部分即为互信息。
假设将这两个变量对应至训练集中的类别及特征，则其间的互信息等价于决策树学习中的信息增益。对于给定训练集D及特征A而言，在此语境下：
- 表示基于数据集 D 的分类不确定性的是指标 H(D)；
- 而条件熵 H(D|A) 则衡量在已知特征属性 A 的情况下进行分类所带来的不确定性；
- 由此可知，在计算两者的差值时所获得的信息增益即是两者的互相对应关系：
所得的信息增益即代表由于引入属性属性 A 而所导致的数据分类不确定性的降低程度。
总结
这一节的内容是关键性的部分，在此我们探讨信息量的概念。综上所述：
- 熵：衡量随机变量不确定性的重要指标；在最优编码方案下达到的理论极限平均码长。
- 条件熵：已知其中一个随机变量的情况下确定另一个随机变量所需的信息量。
- 相对熵（KL散度）：表征两个概率分布之间差异程度的一个重要指标。
- 互信息：表征两个随机变量间相互依赖程度的重要度量。
Exercise
1.37 Applying the definition (1.111) in conjunction with the product rule of probability, demonstrate the outcome (1.112).
\begin{aligned} H_{y|x} + H_x &= -\left( \iint p(y,x) \log p(y|x) dy dx + \int p(x) \log p(x) dx \right) \\ &= -\left( \iint p(y,x) [\log p(y|x) + \log p(x)] dy dx \right) \\ &= -\iint p(y,x) [\log (p(y|x)p(x))] dy dx = -H_{x,y} \end{aligned}
Applying the sum and product rules of probability theory, demonstrate that the mutual information I(x,y) obeys a specific relationship.
\begin{aligned} I(x,y) &= - \iint{p(x,y) \ln \left( \frac{p(x)p(y)}{p(x,y)}\right) \mathrm{d}x \mathrm{d}y} \\ &= - \iint{p(x,y) \left( \ln(p(y)) - \ln(p(y|x))\right) \mathrm{d}x \mathrm{d}y} \\ &= -\iint{p(x,y) \ln(p(y)) \mathrm{d}x \mathrm{d}y} + \iint{p(x,y)\ln (p(y|x)) \mathrm{d}x \mathrm{d}y} \\ &= -\int{p(y) \ln (p(y)) \mathrm{d}y} + \iint{p(x,y)\ln (p(y|x)) \mathrm{d}x \mathrm{d}y} \\ &= H[y] - H[y|x] \end{aligned}
参考文献
[1] 探讨Kullback-Leibler散度（相对熵）的概念, https://www.jianshu.com/p/43318a3dc715
[2] 详细阐述互信息的定义与意义, https://www.cnblogs.com/gatherstars/p/6004075.html
[3] 统计学习方法（第二版）, 李航
[4] 深入解析交叉熵与相对熵之间的关系, https://www.zhihu.com/question/41252833