NO.37.tip： 熵

背景

我们将讨论分布 $p$ 的熵（entropy），这个熵的概念只是概率分布和均匀分布之间 KL 散度的移位和缩放版本。

定义

$K$ 个状态上分布为 $p$ 的离散随机变量 $X$，其熵的定义为：

$$\mathbb{H}(X)\triangleq -\sum _{k=1}^{K}p(X=k)\log p(X=k)=-{\mathbb{E}}_X[\log p(X)]\text{\hspace{1em}(1)}$$

我们可以使用任何底数的对数，但通常使用以 2 为底的对数，在这种情况下，单位称为比特；或者使用以 $\mathrm{e}$ 为底的对数，在这种情形下，单位称为奈特。

熵等于一个常数减去均匀分布的 KL 散度：

$$\mathbb{H}(X)=\log K-D_{\mathrm{KL}}(p(X)\Vert u(X))\text{\hspace{1em}(2)}$$

$$D_{\mathrm{KL}}(p(X)\Vert u(X))=\sum _{k=1}^{K}p(X=k)\log \frac{p(X=k)}{\frac{1}{K}}\text{\hspace{1em}(3)}$$

$$=\log K+\sum _{k=1}^{K}p(X=k)\log p(X=k)\text{\hspace{1em}(4)}$$

如果 $p$ 是均匀分布，则 KL 为零，并且我们看到熵达到其 $\log K$ 的最大值。

对于二元随机变量的特殊情况，$X\in \{0,1\}$，我们可以记作 $p(X=1)=\theta$ 和 $p(X=0)=1-\theta$。因此熵变为：

$$\mathbb{H}(X)=-[p(X=1)\log p(X=1)+p(X=0)\log p(X=0)]\text{\hspace{1em}(5)}$$

$$=-[\theta \log \theta +(1-\theta )\log (1-\theta )]\text{\hspace{1em}(6)}$$

这被称为二元熵函数（binary entropy function），也被记作 $\mathbb{H}(\theta )$。

源与流

连续随机变量的微分熵

如果 $X$ 是一个具有概率密度函数 $p(x)$ 的连续随机变量，我们将微分熵（differential entropy）定义为：

$$h(X)\triangleq -{\int }_{\mathcal{X}}\mathrm{d}xp(x)\log p(x)\text{\hspace{1em}(7)}$$

假设这个积分存在。

例如，可以证明 $d$ 维高斯分布的熵是：

$$h(\mathcal{N}(\mathbf{\mu },\mathbf{\Sigma }))=\frac{1}{2}\log |2\pi \mathrm{e}\mathbf{\Sigma }|=\frac{1}{2}\log [(2\pi \mathrm{e}{)}^d|\mathbf{\Sigma }|]=\frac{d}{2}+\frac{d}{2}\log (2\pi )+\frac{1}{2}\log |\mathbf{\Sigma }|\text{\hspace{1em}(8)}$$

在一维高斯分布的情况下，该式变为：

$$h(\mathcal{N}(\mu ,{\sigma }^2))=\frac{1}{2}\log [2\pi \mathrm{e}{\sigma }^2]\text{\hspace{1em}(9)}$$

请注意，与离散情况不同，微分熵可以是负值。这是因为概率密度函数可能大于 1。例如，假设 $X\sim U(0,a)$，于是有：

$$h(X)=-{\int }_0^a\mathrm{d}x\frac{1}{a}\log \frac{1}{a}=\log a\text{\hspace{1em}(10)}$$

如果设置 $a=1/8$，那么我们有 $h(X)={\log }_2(1/8)=-3$ 比特。

理解微分熵的一种方法是认识到所有实数只能表示为有限精度。可以证明，连续随机变量 $X$ 的 $n$ 比特量化的熵大约为 $h(X)+n$。例如，假设 $X\sim U(0,\frac{1}{8})$。于是，在 $X$ 的二进制表示中，二进制点右侧的前 3 比特必须为 0（因为数字 $\le 1/8$）。描述 $X$ 到 $n$ 个比特的精度只需要 $n-3$ 比特，这与上面计算的 $h(X)=-3$ 完全一致。

连续熵也缺乏 KL 散度的重新参数化独立性。特别地，如果我们变换随机变量 $y=f(x)$，那么熵就会随之变换。为了理解这一点，请注意变量的变化实际上表明：

$$p(y)\mathrm{d}y=p(x)\mathrm{d}x\Rightarrow p(y)=p(x){\left|\frac{\mathrm{d}y}{\mathrm{d}x}\right|}^{-1}\text{\hspace{1em}(11)}$$

因此，连续熵变换如下：

$$h(X)=-\int \mathrm{d}xp(x)\log p(x)=h(Y)-\int \mathrm{d}yp(y)\log \left|\frac{\mathrm{d}y}{\mathrm{d}x}\right|\text{\hspace{1em}(12)}$$

对于变换的雅可比行列式，我们在其对数的连续熵中选取一个因子。即使是简单地重新缩放随机变量，也会改变连续熵的值，例如当我们仅仅改变单位时。

典型集

对于概率分布的典型集（typical set），该集合中的元素具有这样的信息内容：信息内容接近于来自分布的随机样本的期望信息内容。更准确地说，对于支撑集 $x\in \mathcal{X}$ 的分布 $p(x)$，$p(x)$ 的 $ϵ$-典型集合 ${\mathcal{A}}_{ϵ}^N\in {\mathcal{X}}^N$ 是所有长度为 $N$ 的序列的集合，并满足：

$$\mathbb{H}(p(x))-ϵ\le -\frac{1}{N}\log p(x_1,\cdots ,x_N)\le \mathbb{H}(p(x))+ϵ\text{\hspace{1em}(13)}$$

如果我们假设 $p(x_1,\cdots ,x_N)={\prod }_{n=1}^{N}p(x_n)$，那么可以将中间的项解释为熵的 $N$-样本经验估计。渐近均分性质（Asymptotic Equipartition Property, AEP）表明，当 $N\to \infty$ 时，这将在（概率上）收敛到真正的熵。因此，典型集的概率接近 1，同时也是对 $p(x)$ 所生成内容的简明总结。

交叉熵与困惑度

衡量模型 $q$ 与真实分布 $p$ 接近程度的标准方法是使用 KL 散度，由下式给出：

$$D_{\mathrm{KL}}(p\Vert q)=\sum _{x}p(x)\log \frac{p(x)}{q(x)}={\mathbb{H}}_c(p,q)-\mathbb{H}(p)\text{\hspace{1em}(14)}$$

其中，${\mathbb{H}}_c(p,q)$ 是交叉熵：

$${\mathbb{H}}_c(p,q)=-\sum _{x}p(x)\log q(x)\text{\hspace{1em}(15)}$$

并且，$\mathbb{H}(p)={\mathbb{H}}_c(p,p)$ 是熵，是独立于模型的常数。

在语言建模中，通常会报告一种称为困惑度（perplexity）的替代性能度量。困惑度被定义为：

$$\text{perplexity}(p,q)\triangleq 2^{{\mathbb{H}}_c(p,q)}\text{\hspace{1em}(16)}$$

我们可以按照如下方法计算交叉熵的经验近似值。基于从 $p$ 采样的数据，假设我们使用该数据的经验分布来近似真实分布：

$$p_{\mathcal{D}}(x|\mathcal{D})=\frac{1}{N}\sum _{n=1}^N\mathbb{I}(x=x_n)\text{\hspace{1em}(17)}$$

在这种情况下，交叉熵由下式计算而得：

$$H=-\frac{1}{N}\sum _{n=1}^N\log p(x_n)=-\frac{1}{N}\log \prod _{n=1}^{N}p(x_n)\text{\hspace{1em}(18)}$$

相对应的困惑度的计算公式为：

$$\text{perplexity}(p_{\mathcal{D}},p)=2^{-\frac{1}{N}\log \left({\prod }_{n=1}^{N}p(x_n)\right)}=2^{\log {\left({\prod }_{n=1}^{N}p(x_n)\right)}^{-\frac{1}{N}}}\text{\hspace{1em}(19)}$$

$$={\left(\prod _{n=1}^{N}p(x_n)\right)}^{-1/N}=\sqrt[N]{\prod _{n=1}^N\frac{1}{p(x_n)}}\text{\hspace{1em}(20)}$$

在语言模型的情况下，我们在预测下一个单词时通常以前一个单词为条件。例如，在二元模型中，我们使用形式为 $p(x_n|x_{n-1})$ 的二阶马尔可夫模型。我们将语言模型的分支因子（branching factor）定义为任何给定单词后可能出现的单词的数量。例如，假设模型预测每个单词具有相等的可能性，且与上下文无关，因此 $p(x_n|x_{n-1})=1/K$，其中 $K$ 是词汇表中的单词数量。那么困惑度就是 $((1/K{)}^N{)}^{-1/N}=K$。如果某些符号比其他符号更有可能，并且模型正确地反映了这一可能性，那么所得到的困惑度将低于 $K$。然而，我们有 $\mathbb{H}(p^{\ast })\le {\mathbb{H}}_c(p^{\ast },p)$，所以我们永远无法将困惑度降低到 $2^{-\mathbb{H}(p^{\ast })}$ 以下。