考虑一个离散变量 $x$。
对于该变量的一个观测值,我们需要一个量来衡量从这个观测量中得到了多少关于 $x$ 的信息。 从主观意义上来说,一个不常见的观测值所提供的新信息要比常见的观测值要多。
我们的信息量 $h$ 依赖于一个概率分布 $p(x)$,$h(x)$ 需要满足这样的性质:
我们将 $h$ 和 $p$ 之间的关系表示为 $h(p)$,从上面的例子中,我们可以看到
$$ h(pq) = h(p) h(q) $$归纳法不难给出 $h(p^n) = nh(p)$,所以
$$ h(p^{n/m}) = nh(p^{1/m}) = \frac n m h(p^{m/m}) = \frac n m h(p) $$因此由连续性,我们有 $h(p^x) = x h(p)$。
对任意正数 $p,q$,总有 $q^x = p$ 成立,则我们有
$$ \frac{h(p)}{\ln (p)} = \frac{h(q^x)}{\ln (p^x)} = \frac{xh(q)}{x\ln (q)} = \frac{h(q)}{\ln (q)} $$从而 $h(p) \propto \ln p$,即 $h$ 与 $p$ 的对数成正比。
一个可能的定义为
$$ h(x) = - \log_2 p(x) $$负号保证信息量为正且满足单调递减的要求,在这里,我们选取了 2 作为对数的底,因此 $h(x)$ 的单位为比特(bit
)。
有了对于单一的 $x$ 的信息量,更一般的想法是衡量一组 $x$ 的信息量,因此,我们考虑对 x 求期望,得到熵(entropy
):
因为 $\lim_{p\to 0} plnp = 0$,所以如果 $p(x)=0$,那么 $p(x)\ln p(x)=0$
现在假设我们要传送状态变量给一个接收器。
考虑一个有 8 个状态的变量 $x$,每个状态都是等概率的。为了表示这个状态,我们至少需要 3 比特的信息来表示状态,此时熵值为
$$ H[x] = - 8 \times \frac 1 8 \log_2 \frac 1 8 = 3~\text{bits} $$再考虑不等概率的情况,假设状态和概率为
a | b | c | d | e | f | g | h |
---|---|---|---|---|---|---|---|
$\frac{1}{2}$ | $\frac{1}{4}$ | $\frac{1}{8}$ | $\frac{1}{16}$ | $\frac{1}{64}$ | $\frac{1}{64}$ | $\frac{1}{64}$ | $\frac{1}{64}$ |
熵为
$$ H[x] = - \frac{1}{2} \log_2 \frac{1}{2} - \frac{1}{4}\log_2 \frac{1}{4} - \frac{1}{8} \log_2 \frac{1}{8} - \frac{1}{16} \log_2 \frac{1}{16} - \frac{4}{64} \log_2 \frac{1}{64} = 2~\text{bits} $$不等概率的熵要比等概率的熵要小。
考虑字符的霍夫曼编码:
a | b | c | d | e | f | g | h |
---|---|---|---|---|---|---|---|
0 | 10 | 110 | 1110 | 111100 | 111101 | 111110 | 111111 |
其平均字符长度为:
$$ \frac{1}{2} \times 1 + \frac{1}{4} \times 2 + \frac{1}{8} \times 3 + \frac{1}{16} \times 4 + \frac{4}{64} \times 6 = 2~\text{bits} $$因此,熵和霍夫曼编码长度之间存在一定的关系。
Shannon
在 1948 年的 noiseless coding theorem
说明,这样的熵是编码长度的下界。
现在考虑自然对数表示的熵。此时熵的单位是 nat
而不是 bit
。
我们之前用平均信息量的方式引入了熵,事实上熵的概念是从物理上引入的。
假设我们将 $N$ 个相同的小球放入一些容器中,使得第 $i$ 个容器中有 $n_i$ 个球,$\sum_i n_i = N$。
我们按顺序从第 1 个容器开始往里面放入小球,第 1 个有 $N$ 种选择,第 2 个有 $N-1$ 种选择……总共有 $N!$ 种选择。
但是放入每个容器中的 $n_i$ 个球是不区分顺序的,有 $n_i!$ 种可能性放置这些小球,因此总的可能方法有
$$ W = \frac{N!}{\prod_i n_i!} $$定义熵为
$$ H = \frac{1}{N} \ln W = \frac 1 N\ln N! - \frac 1 N \sum_{i} \ln n_i ! $$当 $N \to \infty$ 时,由 Stirling
近似公式:
我们有
$$ H = \lim_{N\to \infty} \frac 1 N (N\ln N - N) - \frac 1 N \sum_{i} (n_i \ln n_i - n_i) = -\lim_{N\to \infty} \sum_i \left(\frac{n_i}{N}\right) \ln \left(\frac{n_i}{N}\right) = -\sum_i p_i \ln p_i $$$p_i = \lim_{N\to\infty} \left(\frac{n_i}{N}\right)$ 是小球放入第 i 个容器的概率。
在物理上,容器中小球的分布叫做微观状态,各个容器中的小球数目叫做宏观状态。
对于一个离散随机变量 $X$ 的取值 $x_i$ 当作一个容器,即有 $p(X=x_i)=p_i$,则它的熵为:
$$ H[p] = - \sum_i p(x_i) \ln p(x_i) $$一般来说,一个离散分布的点越多,分布越均匀,那么对应的熵也越大。
如果其中有一个 $p_i=1$,那么熵取到最小值 0,最大值可以用 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)} = -1 -\ln p(x_i) + \lambda = 0 $$得到最大熵应该满足一个均匀离散分布 $p(x_i)=p(x_j), \forall i,j$。
若状态总数为 $M$,则 $p(x_i) = \frac 1 M$,此时,我们有 $H = \ln M$。
为了验证的确是个最大值,我们可以计算它的二阶导数来验证。
对于连续变量,我们将 $x$ 划分为长度为 $\Delta$ 的小段,积分中值定理告诉我们,在第 $i$ 小段 $(i\Delta, (i+1)\Delta)$ 中存在 $x_i$,使得:
$$ \int_{i\Delta}^{i+1\Delta} p(x) dx = p(x_i) \Delta $$我们可以将落在第 $i$ 小段的 $x$ 对应为 $x_i$,则观测到 $x_i$ 的概率为 $p(x_i) \Delta$,这给出了一个关于 $x_i$ 的离散分布,其熵为:
$$ H_{\Delta} = - \sum_i p(x_i) \Delta \ln(p(x_i) \Delta) = - \sum_i p(x_i) \Delta \ln(p(x_i)) - \ln\Delta $$其中 $p(x_i) \Delta= 1$,现在忽略最后的常数项,然后考虑 $\Delta \to0$ 的情况,我们有
$$ -\lim_{\Delta \to 0} \left\{ \sum_i p(x_i) \Delta \ln(p(x_i) \Delta) \right\} = -\int p(x) \ln p(x) dx $$这一项叫做微分熵(differential entropy
),它与离散熵的差别在于一个 $\ln \Delta$,在 $\Delta \to0$ 时会发散的部分。
对于多元向量 $\mathbf x$,微分熵定义为
$$ H[\mathbf x]=-\int p(\mathbf x) \ln p(\mathbf x) d\mathbf x $$在离散分布的例子中,我们看到最大化熵的分布是均匀离散分布。
为了最大化连续分布的熵,我们需要加上 $p(x)$ 的一阶矩和二阶矩都固定的条件。
考虑一维情况,我们的问题为
$$ \begin{align} \max_{p(x)}~& -\int p(x) \ln p(x) dx \\ s.t.~& 1 = \int_{-\infty}^{\infty} p(x) dx \\ & \mu = \int_{-\infty}^{\infty} xp(x) dx\\ & \sigma^2 = \int_{-\infty}^{\infty} (x-\mu)^2p(x) dx\\ \end{align} $$Lagrange
函数为
令这个泛函对 $p(x)$ 的导数为 0
,得到
从而
$$ p(x) = \exp\left\{1+\lambda_1 + \lambda_2 x + \lambda_3 (x-\mu)^2\right\} $$将这个形式带入约束条件,不难得到
$$ p(x) = \frac{1}{(2\pi\sigma^2)^{1/2}} \exp\left\{-\frac{(x-\mu)^2}{2\sigma^2}\right\} $$即最大熵的分布是高斯分布。
注意到,我们并没有对 $p(x)$ 做非负的约束,但是最大化给出的结果是一个非负的结果。
高斯分布的熵为:
$$ \frac{1}{2} \left\{1+\ln(2\pi\sigma^2)\right\} $$从这个表达式我们可以看出,与离散熵不同,连续熵可以为负值:$\sigma^2 < \frac{1}{2\pi e}, H(x) < 0$,原因是概率密度函数 p(x) 没有小于 1 的限制,因此 $-p(x)\ln p(x)$ 不能保证非负。
假设我们有 $\mathbf{x,y}$ 的联合分布,假设 $\mathbf x$ 已知,那么 $\mathbf y$ 的包含的信息量应当由 $-\ln p(\mathbf{y|x})$ 来衡量,因此我们可以定义其条件期望为给定 $\mathbf x$ 下 $\mathbf y$ 的条件熵(conditional entropy
):
可以计算出,我们有:
$$ H[\mathbf{x, y}] = H[\mathbf{y|x}] + H[\mathbf{x}] $$因此,用来描述 $\mathbf{x,y}$ 的信息量等于描述 $\mathbf x$ 的信息量加上给定 $\mathbf x$ 的条件下描述 $\mathbf y$ 所需的信息量。
假设我们有一个未知分布 $p(\mathbf x)$,然后对它建模得到了一个概率分布 $q(\mathbf x)$。
用 $q(\mathbf x)$ 的分布来传送 $x$ 所用的信息量($q(\mathbf x)$),比用真实的分布 $p(\mathbf x)$ 传送所用的信息量($p(\mathbf x)$)要多一些,多出来的部分为:
$$ \begin{align} KL(p\|q) &= - \int p(\mathbf x)\ln(q(\mathbf x)) dx - \left(-\int p(\mathbf x)\ln p(\mathbf x)\right)\\ &= - \int p(\mathbf x)\ln \left\{\frac{q(\mathbf x)}{p(\mathbf x)}\right\} \end{align} $$这叫做相对熵(relative entropy
)或者 Kullback-Leibler
散度(Kullback-Leibler divergence
)。
K-L
散度不是对称的,即 $KL(p\|q) \neq KL(q\|p)$。
K-L
散度满足 $KL(p\|q) \geq 0$,当且仅当 $p(\mathbf x)=q(\mathbf x)$ 时取等号。
如果一个函数的弦(chord
)始终在函数上或者函数上方,那么这个函数就是凸函数。
一个凸函数的例子如图所示:
import matplotlib.pyplot as plt
import numpy as np
import scipy as sp
%matplotlib inline
fig, ax = plt.subplots()
xx = np.linspace(-3, 4, 100)
yy = xx ** 2
ax.plot(xx, yy, 'r')
ax.set_xlim(-4, 5)
ax.set_yticks([])
ax.set_ylim(-10, 20)
ax.set_xticks([-2, 0.5, 3])
ax.set_xticklabels([r"$a$", r"$x_\lambda$", r"$b$"], fontsize="xx-large")
for i in [-2, 3]:
ax.plot([i, i], [-10, i ** 2], 'g--')
ax.plot([-2, 3], [4, 9], 'b')
ax.plot([0.5, 0.5], [-10, 6.5], 'g')
ax.annotate(
"chord",
fontsize="xx-large",
xytext=(-3, 12),
xy=(-0.2, 6),
arrowprops=dict(arrowstyle="->",
connectionstyle="arc3")
)
plt.show()
在 $x=a$ 和 $x=b$ 的区间内的任意点 $x$ 都可以写成 $\lambda a +(1-\lambda)b, 0\leq\lambda \leq 1$,对应的弦上的值为 $\lambda f(a) +(1-\lambda) f(b)$,函数值为 $f(\lambda a +(1-\lambda)b)$。凸性等价于
$$ f(\lambda a +(1-\lambda)b) \leq \lambda f(a) +(1-\lambda) f(b) $$这也等价于函数的二阶导数非负(如果二阶导数存在)。
证明如下:
假设凸性的式子成立,令 $\lambda = \frac 1 2, b = a + 2\epsilon$,则有:
$$ \begin{align} \frac 1 2f(a)+\frac 1 2f(b) & \geq f\left(\frac 1 2a + \frac 1 2b\right) \\ & = \frac 1 2 f\left((\frac 1 2a + \frac 1 2b\right) + \frac 1 2 f\left((\frac 1 2a + \frac 1 2b\right) \\ & = \frac 1 2 f(a+\epsilon) + \frac{1}{2} f(b-\epsilon) \end{align} $$从而
$$ f(b) - f(b-\epsilon) \geq f(a+\epsilon) - f(a) $$取 $\epsilon\to 0$,我们有
$$ f'(b) \geq f'(a) $$从而
$$ f''(x) \geq 0 $$假设二阶导数非负:$f''(x) \geq 0$,那么由泰勒展开,存在一个 $x^\star$ 使得
$$ f(x) = f(x_0) + f'(x_0)(x-x_0) + \frac 1 2 f''(x^\star) (x-x_0)^2 \geq f(x_0) + f'(x_0)(x-x_0) $$令 $x_0 = \lambda a +(1-\lambda b), x = a$,则有
$$ f(a) \geq f(x_0) + f'(x_0)((1-\lambda)(a-b)) $$令 $x_0 = \lambda a +(1-\lambda b), x = b$,则有
$$ f(b) \geq f(x_0) + f'(x_0)(\lambda(a-b)) $$合并两个不等式,去掉 $f'(x_0)$ 的项:
$$ \lambda f(a) +(1-\lambda) \geq f(b) f(\lambda a +(1-\lambda)b) $$凸函数的例子:
如果等式只在 $\lambda = 1$ 和 $\lambda = 0$ 时成立,则称 $f(x)$ 是严格凸函数。
如果 $f(x)$ 是凸函数,那么 $-f(x)$ 是凹函数。
使用数学归纳法不难证明,对于任意凸函数 $f(x)$,Jensen
不等式成立:
其中 $\lambda_i \geq 0, \sum_i \lambda_i = 1$。等式成立的条件为 $f$ 是线性,或者所有的 $x_i$ 都相等。
证明如下:
$M = 1$ 时显然成立;假设对于某个 $M$ 不等式成立,那么对于 $M+1$ 来说:
$$ f\left(\sum_{i=1}^{M+1} \lambda_i x_i\right) = f\left(\lambda_{M+1} x_{M+1} + \sum_{i=1}^M \lambda _i x_i\right) = f\left(\lambda_{M+1} x_{M+1} + (1-\lambda_{M+1})\sum_{i=1}^M \eta_i x_i\right) $$其中
$$ \eta_i = \frac{\lambda_i}{1-\lambda_{M+1}} $$考虑凸函数性质,我们有
$$ f\left(\sum_{i=1}^{M+1} \lambda_i x_i\right) = f\left(\lambda_{M+1} x_{M+1} + (1-\lambda_{M+1})\sum_{i=1}^M \eta_i x_i\right) \leq \lambda_{M+1} f(x_{M+1}) + (1-\lambda_{M+1}) f\left(\sum_{i=1}^M \eta_i x_i\right) $$再应用假设条件,我们有 $$ f\left(\sum_{i=1}^{M+1} \lambda_i x_i\right) \leq \lambda_{M+1} f(x_{M+1}) + (1-\lambda_{M+1}) f\left(\sum_{i=1}^M \eta_i x_i\right) \leq \lambda_{M+1} f(x_{M+1}) + \sum_{i=1}^M (1-\lambda_{M+1})\eta_i f\left(x_i\right) = \sum_{i=1}^{M+1} \lambda_i f(x_i) $$
如果我们认为 $\lambda_i$ 是某个离散分布取 $x_i$ 的概率,那 Jenson
不等式可以表示为
不等式成立的条件为 $x$ 为常数,或者 $f$ 是线性的。
更一般的,我们有:
$$ f\left(\mathbb E[y(\mathbf x)]\right) \leq \mathbb E[f(y(\mathbf x))] $$对于连续形式,我们有
$$ f\left(\int y(\mathbf x)p(\mathbf x)d\mathbf x\right) \leq \int f(y(\mathbf x))p(\mathbf x)d\mathbf x $$将 Jensen
不等式应用到 K-L
散度($-\ln x$ 是凸函数)上:
因为 $-\ln x$ 是严格凸的,因此等式只能在 $\frac{q(\mathbf x)}{p(\mathbf x)}$ 为常数时成立,考虑到两者都是概率分布(积分都为 1),所以只能有 $p(\mathbf x) = q(\mathbf x)$ 成立。
因此,我们可以将 K-L
散度来衡量两个分布的差异。
另一方面,我们看到,当我们使用真实的数据分布传送数据,所用信息量的期望是最小的。
假设我们有一组从未知分布 $p(\mathbf x)$ 中产生的数据,我们的模型为 $q(\mathbf{x|\theta})$,一个决定参数 $\mathbf \theta$ 的方法就是最小化 $p(\mathbf x)$ 和 $q(\mathbf{x|\theta})$ 的 K-L
散度。
然而我们并不知道 $p(x)$ 的真实分布,一个近似的方法是使用已观测的数据进行模拟:
$$ KL(p|q) \approx \sum_{n=1}^N (-\ln q(\mathbf{x}_n | \mathbf{\theta}) + \ln p(\mathbf x_n)) $$由于右边的部分与 $\mathbf\theta$ 无关,因此,最小化 K-L
散度就相当于最大化似然函数。
考虑两个变量 $\mathbf{x,y}$ 的分布,如果它们独立,则 $p(\mathbf{x,y}) = p(\mathbf{x})p(\mathbf{y})$,如果他们不独立,则我们用 $p(\mathbf{x,y})$ 和 $p(\mathbf{x})p(\mathbf{y})$ 的 K-L
散度来衡量它们接近独立的程度:
这叫做 $\mathbf x$ 和 $\mathbf y$ 的互信息(mutual information
)。从 K-L
散度的性质中我们可以看出,$I[\mathbf{x,y}] \geq 0$,当且仅当 $\mathbf{x,y}$ 是独立的时候等号成立。
另外,我们从定义式中可以得到:
$$ I[\mathbf{x,y}] = H[\mathbf x] - H[\mathbf{x|y}] = H[\mathbf y] - H[\mathbf{y|x}] $$所以我们可以将互信息看成是给定 $\mathbf y$ 后 $\mathbf x$ 信息量的减少值。