3.7 进阶：困惑度与熵的关系

第 3.3 节引入困惑度，用它在测试集上评估 n 元模型。更好的 n 元模型会为测试数据分配更高概率，而困惑度是测试集概率经过归一化的版本。困惑度指标实际上源自信息论中的交叉熵（cross-entropy）概念；这解释了困惑度一些看似神秘的属性，例如为何使用概率的倒数，以及它与熵的关系。

熵（entropy）是信息量的一种度量。给定随机变量 $X$ ，它的取值范围是我们要预测的对象（词、字母、词性等）所组成的集合 $\chi$ ，概率函数为 $p(x)$ ，则随机变量 $X$ 的熵是：

H (X) = - \sum_ {x \in \chi} p (x) \log_ {2} p (x)\tag{3.32}

原则上可以使用任意底数计算对数。如果使用以 2 为底的对数，所得熵值以比特（bit）为单位。

理解熵的一种直观方式是：在最优编码方案中，对某项决定或信息进行编码所需比特数的下界。考虑标准信息论教材 Cover and Thomas（1991）中的一个例子。假设我们想对一场赛马下注，但 Yonkers 赛马场太远，于是希望给经纪人发送一条短消息，告诉他应当在八匹马中的哪一匹下注。一种编码方式是直接使用马匹编号的二进制表示：1 号马编码为 001，2 号为 010，3 号为 011，依此类推，8 号编码为 000。如果整天都在下注，而每匹马都用 3 比特编码，那么每场比赛平均发送 3 比特。

还能做得更好吗？假设赔率反映实际下注分布，并把它表示成每匹马的先验概率：

1 号马	$\frac{1}{2}$	5 号马	$\frac{1}{64}$
2 号马	$\frac{1}{4}$	6 号马	$\frac{1}{64}$
3 号马	$\frac{1}{8}$	7 号马	$\frac{1}{64}$
4 号马	$\frac{1}{16}$	8 号马	$\frac{1}{64}$

取值范围为这些马匹的随机变量 $X$ 之熵给出所需比特数的下界：

\begin{array}{l l} H (X) & = - \sum_ {i = 1} ^ {i = 8} p (i) \log_ {2} p (i) \\ & = - \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} - 4 (\frac {1}{64} \log_ {2} \frac {1}{64}) \\ & = 2 \text { 比特} \end{array}\tag{3.33}

要构建一种平均每场比赛只需 2 比特的编码，可以为概率较高的马分配短编码，为概率较低的马分配长编码。例如，最可能获胜的马编码为 0，其余马依次编码为 10、110、1110、111100、111101、111110 和 111111。

如果所有马的概率相同呢？前文看到，使用等长二进制马匹编号时，每匹马需要 3 比特，平均也是 3。此时熵是否相同？每匹马的概率均为 $1/8$ ，所以选择马匹的熵为：

H (X) = - \sum_ {i = 1} ^ {i = 8} \frac {1}{8} \log_ {2} \frac {1}{8} = - \log_ {2} \frac {1}{8} = 3 \text { 比特}\tag{3.34}

到目前为止，我们计算的都是单个变量的熵，但熵的大多数用途涉及序列。例如，对语法而言，需要计算某个词序列 $W=\{w_1,w_2,\ldots,w_n\}$ 的熵。一种做法是让一个变量的取值范围覆盖各个词序列。比如，可以如下计算语言 $L$ 中所有长度为 $n$ 的词序列之随机变量的熵：

H \left(w _ {1}, w _ {2}, \dots , w _ {n}\right) = - \sum_ {w _ {1: n} \in L} p \left(w _ {1: n}\right) \log p \left(w _ {1: n}\right)\tag{3.35}

可以把熵率（entropy rate，也可理解为逐词熵）定义为该序列的熵除以词数：

\frac {1}{n} H (w _ {1: n}) = - \frac {1}{n} \sum_ {w _ {1: n} \in L} p (w _ {1: n}) \log p (w _ {1: n})\tag{3.36}

不过，要衡量一门语言的真实熵，需要考虑无限长的序列。把语言看作产生词序列的随机过程 $L$ ，令 $W$ 表示词序列 $w_1,\ldots,w_n$ ，则 $L$ 的熵率 $H(L)$ 定义为：

\begin{array}{l} H (L) = \lim _ {n \to \infty} \frac {1}{n} H (w _ {1: n}) \\ = - \lim _ {n \to \infty} \frac {1}{n} \sum_ {W \in L} p (w _ {1: n}) \log p (w _ {1: n}) \end{array}\tag{3.37}

Shannon–McMillan–Breiman 定理（Algoet and Cover, 1988; Cover and Thomas, 1991）指出，如果语言在某些方面是规则的——准确地说，同时具有平稳性和遍历性——那么：

H (L) = \lim _ {n \rightarrow \infty} - \frac {1}{n} \log p (w _ {1: n})\tag{3.38}

也就是说，可以采用一个足够长的单一序列，而不必对所有可能序列求和。该定理背后的直觉是：足够长的词序列会包含许多较短序列，而这些较短序列会按照各自概率在长序列中反复出现。

如果一个随机过程为序列分配的概率不随时间索引的平移而改变，就称它具有平稳性（stationarity）。换句话说，时刻 $t$ 的词概率分布与时刻 $t+1$ 的相同。Markov 模型以及 n 元模型都是平稳的。例如，在二元模型中， $P_i$ 只依赖 $P_{i-1}$ ；把时间索引平移 $x$ 后， $P_{i+x}$ 仍只依赖 $P_{i+x-1}$ 。不过，自然语言并不平稳；正如附录 F 所示，后续词语的概率可能取决于距离任意遥远、随时间而变的事件。因此，统计模型只能近似自然语言的正确分布与熵。

总之，借助一些虽然不正确、但很方便的简化假设，可以从某个随机过程的输出中取得很长的样本，再计算其平均对数概率，以此计算该过程的熵。

现在可以引入交叉熵。如果我们不知道生成某些数据的真实概率分布 $p$ ，交叉熵就很有用：它允许使用 $p$ 的模型 $m$ ，也就是对 $p$ 的近似。 $m$ 在 $p$ 上的交叉熵定义为：

H (p, m) = \lim _ {n \rightarrow \infty} - \frac {1}{n} \sum_ {W \in L} p \left(w _ {1}, \dots , w _ {n}\right) \log m \left(w _ {1}, \dots , w _ {n}\right)\tag{3.39}

也就是说，序列按照概率分布 $p$ 抽取，但求和时使用它们在 $m$ 下的对数概率。

同样，依据 Shannon–McMillan–Breiman 定理，对平稳遍历过程有：

H (p, m) = \lim _ {n \to \infty} - \frac {1}{n} \log m (w _ {1} w _ {2} \dots w _ {n})\tag{3.40}

这意味着，与熵一样，我们可以用一个足够长的单一序列估计模型 $m$ 在分布 $p$ 上的交叉熵，而不必对所有可能序列求和。

交叉熵的实用之处在于， $H(p,m)$ 是熵 $H(p)$ 的上界。对任何模型 $m$ ：

H (p) \leq H (p, m)\tag{3.41}

因此，可以用简化模型 $m$ 帮助估计按照概率 $p$ 抽取的符号序列之真实熵。 $m$ 越准确，交叉熵 $H(p,m)$ 就越接近真实熵 $H(p)$ ；二者之差因而可以衡量模型的准确程度。比较模型 $m_1$ 和 $m_2$ 时，交叉熵较低的模型更准确。（交叉熵绝不会低于真实熵，所以模型不会因低估真实熵而出错。）

最后可以说明困惑度与式 3.40 中交叉熵的关系。交叉熵定义于观测词序列长度趋于无穷的极限；我们使用一个足够长、但长度固定的序列来近似它。模型 $M=P(w_i|w_{i-N+1:i-1})$ 在词序列 $W$ 上的交叉熵近似为：

H (W) = - \frac {1}{N} \log_ {2} P (w _ {1} w _ {2} \dots w _ {N})\tag{3.42}

模型 $P$ 在词序列 $W$ 上的困惑度，正式定义为 2 的该交叉熵次幂：

\begin{array}{r c l} \operatorname{Perplexity} (W) & = & 2 ^ {H (W)} \\ & = & P (w _ {1} w _ {2} \dots w _ {N}) ^ {- \frac {1}{N}} \\ & = & \sqrt [ N ]{\frac {1}{P (w _ {1} w _ {2} \dots w _ {N})}} \end{array}