我们在 3.3 节中引入了困惑度，用于在测试集上评估 n-gram 模型。 更好的 n-gram 模型赋予测试数据更高的概率，测试集上获取的概率归一化后，就是困惑度。 实际上，困惑度这一度量源自信息论中的交叉熵（cross-entropy）概念，这一概念可以解释困惑度中一些看似神秘的特性（例如，为何要使用逆概率？），以及它与熵之间的关系。 熵（entropy）是信息量的一种度量。 给定一个随机变量 $X$，它的取值是需要预测的对象（如单词、字母、词性等），我们将这个集合记作 $\chi$，并设 $X$ 的概率分布为 $p(x)$，那么随机变量 $X$ 的熵定义为：
$$ H(X) = -\sum_{x \in \chi} p(x) \log_2 p(x) \tag{3.33} $$理论上，对数的底数可以任意选择。 如果使用以 2 为底的对数，那么熵的单位就是比特（bits）。
理解熵的一种直观方式是：它表示在最优编码方案下，编码某个决策或信息所需的最少比特数的下限。
我们借用信息论经典教材 Cover 和 Thomas（1991）中的一个例子来说明。
假设我们要对一场赛马下注，但距离太远无法亲自前往扬克斯赛马场（Yonkers Racetrack），因此我们想给博彩商发送一条简短的消息，告诉他该为八匹马中的哪一匹下注。
一种编码方式是直接使用马匹编号的二进制表示作为编码：例如，1 号马是001，2 号马是 010，3 号马是 011，依此类推，8 号马则编码为 000。
如果我们整天都在下注，且每匹马都用 3 个比特编码，那么平均每场比赛我们需发送 3 个比特。
能否做得更好？假设“赔率分布”反映了实际投注的分布情况，我们可以将其表示为每匹马的先验概率，如下所示：
- 1 号马 $\frac{1}{2}$
- 2 号马 $\frac{1}{4}$
- 3 号马 $\frac{1}{8}$
- 4 号马 $\frac{1}{16}$
- 5 号马 $\frac{1}{64}$
- 6 号马 $\frac{1}{64}$
- 7 号马 $\frac{1}{64}$
- 8 号马 $\frac{1}{64}$
设随机变量 $X$ 的取值是马匹编号，$X$ 的熵给出了编码所需比特数的下限，计算如下：
$$ \begin{align*} H(X) &= -\sum_{i=1}^{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\left(\frac{1}{64} \log_2\frac{1}{64}\right) \\ &= 2 \texttt{ bits} \tag{3.34} \end{align*} $$我们可以设计一种编码方案，对更可能获胜的马使用较短的编码，对较不可能的马使用较长的编码，从而实现平均每场比赛仅需 2 个比特。
例如，可以将最可能赢的马编码为 0，其余的马分别编码为 10、110、1110、111100、111101、111110 和 111111。
如果所有马获胜的概率相等呢？ 前面我们看到，若使用等长的二进制编码，每匹马需要 3 个比特，因此平均为 3 比特。 此时的熵是否相同？ 在这种情况下，每匹马的概率都是 $\frac{1}{8}$。 马匹选择的熵为：
$$ \begin{align*} H(X) &= -\sum_{i=1}^{8} \frac{1}{8} \log_2 \frac{1}{8} \\ &= -\log_2 \frac{1}{8} \\ &= 3 \texttt{ bits} \tag{3.35} \end{align*} $$到目前为止，我们计算的都是单个随机变量的熵。 但实际中使用熵时，更多涉及的是序列。 例如，对于某种语法，我们会计算某个词序列 $W = \{w_1, w_2, ..., w_n\}$ 的熵。 一种方法是定义一个随机变量，其取值是整个词序列。 例如，针对某种语言 $L$，设一个随机变量的取值是所有长度为 n 的单词序列，计算这个随机变量的熵：
$$ H(w_1, w_2, ..., w_n) = -\sum_{w_{1:n} \in L} p(w_{1:n}) \log p(w_{1:n}) \tag{3.36} $$我们可以定义熵率（entroy 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.37} $$但要衡量一种语言的真实熵，需要考虑无限长的序列。 如果把一种语言看作一个生成词序列的随机过程 $L$，并用 $W$ 表示序列 $w_1, ..., w_n$，那么语言 $L$ 的熵率 $H(L)$ 定义为：
$$ \begin{align*} 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}) \tag{3.38} \end{align*} $$香农-麦克米伦-布赖曼定理（Shannon-McMillan-Breiman Theorem，Algoet 和 Cover，1988；Cover 和 Thomas，1991）指出，如果语言在某些方面具有规律性（确切地说，如果它是平稳的（stationary）且各态历经的（ergodic）），那么：
$$ H(L) = \lim_{n \to \infty} -\frac{1}{n} \log p(w_{1:n}) \tag{3.39} $$也就是说，我们可以使用一个足够长的单一序列，而不必对所有可能的序列求和。 该定理的依据是，一个足够长的词序列本身会包含许多较短的子序列，而这些子序列会根据各自的概率反复出现在长序列中。
如果一个随机过程对任意词序列所赋予的概率不随时间起点的改变而变化（即序列的统计特性与它在文本中的位置无关），则称该过程是平稳的（stationary）。 换句话说，单词在时刻 $t$ 的概率分布与时刻 $t+1$ 的概率分布相同。 马尔可夫模型以及 n-gram 模型都是平稳的。 例如，在一个 bigram 模型中，$P_i$ 仅依赖于 $P_{i-1}$。 因此，如果我们把时间起点移动 $x$，$P_{i+x}$ 仍然只依赖于 $P_{i+x-1}$。 然而，自然语言并不是平稳的，正如我们在附录 D 中所展示的那样，后续词语出现的概率可能依赖于任意遥远且与时间相关的事件。 因此，我们的统计模型只能近似地反映自然语言的真实概率分布和熵值。
总结一下，通过做出一些虽不准确但便于处理的简化假设，我们可以通过对某个随机过程的输出取一个足够长的样本来计算其熵，并求其平均对数概率。
现在我们准备引入交叉熵（cross-entropy）的概念。 在不知道生成某些数据的真实概率分布 $p$ 时，交叉熵就变得非常有用。 它允许我们使用一个模型 $m$ 来近似 $p$（即 $m$ 是对 $p$ 的一种逼近）。 模型 $m$ 相对于真实分布 $p$ 的交叉熵定义如下：
$$ H(p,m) = \lim_{n \to \infty} -\frac{1}{n}\sum_{W \in L} p(w_1,..., w_n) \log m(w_1,..., w_n) \tag{3.40} $$也就是说，我们按照真实分布 $p$ 生成序列，但在计算对数概率之和时使用的是模型 $m$ 的概率。
再次依据香农-麦克米伦-布赖曼定理，对于一个平稳且各态历经的过程：
$$ H(p,m) = \lim_{n \to \infty} -\frac{1}{n} \log m(w_1w_2 ... w_n) \tag{3.41} $$这意味着，与熵类似，我们可以通过一个足够长的单一序列来估计模型 $m$ 在分布 $p$ 上的交叉熵，而无需对所有可能的序列求和。
交叉熵之所以有用，是因为交叉熵 $H(p,m)$ 是真实熵 $H(p)$ 的一个上界。对于任意模型 $m$，都有：
$$ H(p) \leq H(p,m) \tag{3.42} $$这表明，我们可以利用某个简化模型 $m$，来估计根据概率 $p$ 生成的符号序列的真实熵。 模型 $m$ 越准确，交叉熵 $H(p,m)$ 就越接近真实熵 $H(p)$。 因此，$H(p,m)$ 与 $H(p)$ 之间的差距可以衡量模型的准确性。 在两个模型 $m_1$ 和 $m_2$ 之间，交叉熵更低的那个模型更准确。（交叉熵永远不会低于真实熵，因此模型不可能低估真实熵。）
最后，我们终于可以揭示困惑度与交叉熵之间的关系，正如公式 (3.41) 所示。 交叉熵是在观测词序列长度趋于无穷时的极限定义。 我们可以依赖一个（足够长的）固定长度序列，来近似这个交叉熵。 对于一个模型 $M = P(w_i|w_{i-N+1:i-1})$ 在词序列 $W$ 上的交叉熵，其近似定义为：
$$ H(W) = -\frac{1}{N} \log P(w_1w_2 ... w_N) \tag{3.43} $$现在，模型 $P$ 在词序列 $W$ 上的困惑度被正式定义为 2 的该交叉熵次幂：
$$ \begin{align*} \text{Perplexity}(W) &= 2^{H(W)} \\ &= P(w_1w_2 ... w_N)^{-\frac{1}{N}} \\ &= \sqrt[N]{\frac{1}{P(w_1w_2 ... w_N)}} \end{align*} $$