PRML读书笔记(3) - 深度理解机器学习之信息论(Information Theory)

「总结自经典教材《Pattern Recognition and Machine Learning》以及김동국教授的人工神经网络纯理论课程。在此感谢作者及教授的辛苦教学。本篇内容很多东西没有很明确地说明，可能会有很多不正确的地方，欢迎指正。」

前一篇文章是从决策论的角度介绍了一些与机器学习相关的知识。这篇文章将介绍一些额外的信息领域的核心知识，这些知识对我们学习模式识别和机器学习技术也很有用。

熵 Entropy

从一个简单的离散变量 x 开始，我们也许会问当我们观察这个变量的时候，会从中获得多少信息量？通常，信息量可以看成是从 x 变量中获得的惊喜程度（degree of surprise）。比如，如果我们被告知刚刚发生了一个非常不可能的事件，我们将收到的信息量比我们被告知一些非常可能的事件刚刚发生的情况要多，如果我们知道该事件肯定会发生的话，我们将不会收到任何信息量。

因此，我们对信息内容的评估将取决于一个概率分布 p(x)。所以，我们要寻找一个函数 h(x)，其是概率 p(x) 的单调函数并且表示信息内容。如果我们有两个不相关的事件 x 和 y，则观察它们两者的信息增益应该是从每个事件中获得的信息的总和，所以有 h(x,y)= h(x) + h(y)。两个不相关的事件是相互独立的，所以有 p(x,y)= p(x)p(y)。从这两个关系中可以容易得出 h(x) 与 logp(x) 之间的关系式： h(x) = -log2p(x)。从该式子中也可以看出：低概率意味着高信息内容。

现在假设发送者希望将随机离散变量的值发送给接收者。它们在过程中传输的平均信息量是通过对分布 p(x) 采用 h(x) = -log2p(x) 的期望得到的，并由下式给出：H[x] = -∑x p(x) log2p(x)。H[x] 称为变量 x 的 熵（Entropy）。而对于连续变量来说，熵的公式为：H[x] = - ∫ p(x) log2p(x)dx。

相对熵和 KL 散度

考虑一些未知的分布 p(x)，并假设我们使用近似分布 q(x) 对其进行建模。如果我们使用 q(x) 来构造一个编码方案以便于将 x 的值传送给接受者，那么指定 x 的值所需的平均附加信息量（假设我们选择有效的编码方案） 作为使用 q(x) 而不是真实分布 p(x) 的结果由下式给出：

KL(p||q) = - \int p(\mathbf{x})lnq(\mathbf{x})d\mathbf{x}- (- \int p(\mathbf{x})lnp(\mathbf{x})d\mathbf{x}) = - \int p(\mathbf{x})ln \frac{q(\mathbf{x})}{p(\mathbf{x})}d\mathbf{x}

该式就是相对熵，也称为 KL 散度。

相对熵（relative entropy），又称为 KL 散度（KL Divergence），简称 KLD。 KL 散度是两个概率分布 P 和 Q 差别的非对称性的度量。典型情况下，P 表示数据的真实分布，Q 表示数据的理论分布。- 摘自维基百科

相对熵有以下 3 个性质：

KL(p||q) \not\equiv KL(q||p)

KL(p||q) \geq 0

p(\mathbf{x}) = q(\mathbf{x}), KL(p||q) = 0

第一条和第三条性质可以很直观的得出来，下面具体证明第二条性质。

Convex 函数

形如下面的函数称为 Convex 函数，与之相反的函数称为 Concave 函数。此处会应用 Convex 函数的性质来推导出上面 KL 散度的第二条性质。

假设 xλ 在 [a, b] 范围之内。现有 0 ≤ λ ≤1 ，所以有：

x_λ = λa + (1-λ)b, a ≤ x_λ ≤b

依据图中的所示，可以得出：

f(λa + (1-λ)b) ≤ λf(a) + (1-λ)f(b)

可以将 Convex 函数的性质归纳成下述公式：

f(\sum_{i=1}^{M}λ_ix_i) ≤ \sum_{i=1}^{M}λ_if(x_i),where λ_i ≥ 0, \sum_iλ_i = 1

该式子就是著名的詹森不等式（Jensen's inequality）。对于连续变量，詹森不等式可以写成下面这样：

f(\int xp(x)dx) ≤ \int f(x)p(x)dx

现在使用詹森不等式来证明 KL 散度的第二条性质:

KL(p||q)=- \int p(\mathbf{x})ln \frac{q(\mathbf{x})}{p(\mathbf{x})}d\mathbf{x} ≥ - ln \int q(\mathbf{x})d\mathbf{x}=0

其中依据 lnx 是 Convex 函数 且 ∫ q(x)dx = 1，所以很容易证明 KL(p||q) ≥ 0。