3.1 n 元语法
先从计算 P ( w ∣ h ) P(w|h) P ( w ∣ h ) h h h w w w h h h
P ( blue ∣ The water of Walden Pond is so beautifully ) (3.1) P (\text { blue } | \text { The water of Walden Pond is so beautifully })\tag{3.1} P ( blue ∣ The water of Walden Pond is so beautifully ) ( 3.1 ) 一种估计方法是直接使用相对频次：取一个非常大的语料库，统计 The water of Walden Pond is so beautifully 出现了多少次，再统计它后面跟着 blue 的次数。这相当于回答：“在看到历史 h h h w w w
P ( blue|The water of Walden Pond is so beautifully ) = C ( The water of Walden Pond is so beautifully blue ) C ( The water of Walden Pond is so beautifully ) (3.2) \begin{array}{c} P (\text {blue|The water of Walden Pond is so beautifully}) = \\ \frac {C (\text {The water of Walden Pond is so beautifully blue})}{C (\text {The water of Walden Pond is so beautifully})} \end{array}\tag{3.2} P ( blue|The water of Walden Pond is so beautifully ) = C ( The water of Walden Pond is so beautifully ) C ( The water of Walden Pond is so beautifully blue ) ( 3.2 ) 如果语料库足够大，就可以计算这两个计数，并依据式 3.2 估计概率。然而，即使整个网络也不足以让我们准确估计完整句子的计数。原因在于语言具有创造性：新句子不断产生，我们无法期望对整个句子这样庞大的对象取得准确计数。因此，要估计给定历史 h h h w w w W W W
首先约定一些记法。本章仍会沿用“词”这一说法，尽管实践中的语言模型通常在第 2 章介绍的 BPE 词元等词元上计算。对于随机变量 X i X_i X i P ( X i = " t h e " ) P(X_i="the") P ( X i = " t h e " ) P ( t h e ) P(the) P ( t h e ) n n n w 1 … w n w_1\ldots w_n w 1 … w n w 1 : n w_{1:n} w 1 : n w 1 : n − 1 w_{1:n-1} w 1 : n − 1 w 1 , w 2 , … , w n − 1 w_1,w_2,\ldots,w_{n-1} w 1 , w 2 , … , w n − 1 w < n w_{<n} w < n w 1 w_1 w 1 w n − 1 w_{n-1} w n − 1 w w w P ( X 1 = w 1 , X 2 = w 2 , … , X n = w n ) P(X_1=w_1,X_2=w_2,\ldots,X_n=w_n) P ( X 1 = w 1 , X 2 = w 2 , … , X n = w n ) P ( w 1 , w 2 , … , w n ) P(w_1,w_2,\ldots,w_n) P ( w 1 , w 2 , … , w n )
怎样计算 P ( w 1 , w 2 , … , w n ) P(w_1,w_2,\ldots,w_n) P ( w 1 , w 2 , … , w n ) 链式法则 （chain rule）分解它：
P ( X 1 . . . X n ) = P ( X 1 ) P ( X 2 ∣ X 1 ) P ( X 3 ∣ X 1 : 2 ) … P ( X n ∣ X 1 : n − 1 ) = ∏ k = 1 n P ( X k ∣ X 1 : k − 1 ) (3.3) \begin{array}{l l} P (X _ {1}... X _ {n}) & = P (X _ {1}) P (X _ {2} | X _ {1}) P (X _ {3} | X _ {1: 2}) \dots P (X _ {n} | X _ {1: n - 1}) \\ & = \prod_ {k = 1} ^ {n} P (X _ {k} | X _ {1: k - 1}) \end{array}\tag{3.3} P ( X 1 ... X n ) = P ( X 1 ) P ( X 2 ∣ X 1 ) P ( X 3 ∣ X 1 : 2 ) … P ( X n ∣ X 1 : n − 1 ) = ∏ k = 1 n P ( X k ∣ X 1 : k − 1 ) ( 3.3 ) 把链式法则应用于词，得到：
P ( w 1 : n ) = P ( w 1 ) P ( w 2 ∣ w 1 ) P ( w 3 ∣ w 1 : 2 ) … P ( w n ∣ w 1 : n − 1 ) = ∏ k = 1 n P ( w k ∣ w 1 : k − 1 ) (3.4) \begin{array}{l l} P (w _ {1: n}) & = P (w _ {1}) P (w _ {2} | w _ {1}) P (w _ {3} | w _ {1: 2}) \dots P (w _ {n} | w _ {1: n - 1}) \\ & = \prod_ {k = 1} ^ {n} P (w _ {k} | w _ {1: k - 1}) \end{array}\tag{3.4} P ( w 1 : n ) = P ( w 1 ) P ( w 2 ∣ w 1 ) P ( w 3 ∣ w 1 : 2 ) … P ( w n ∣ w 1 : n − 1 ) = ∏ k = 1 n P ( w k ∣ w 1 : k − 1 ) ( 3.4 ) 链式法则揭示了计算序列联合概率与计算给定先前词语时某个词的条件概率之间的联系。式 3.4 表明，可以把许多条件概率相乘，估计整个词序列的联合概率。然而，使用链式法则似乎并没有真正解决问题！我们仍不知道怎样计算给定一长串先前词语时某个词的精确概率 P ( w n ∣ w 1 : n − 1 ) P(w_n|w_{1:n-1}) P ( w n ∣ w 1 : n − 1 )
3.1.1 Markov 假设 ¶ n 元模型背后的直觉是：不再依据一个词的完整历史计算其概率，而只用最后几个词来近似这段历史。
例如，二元模型只使用给定前一个词时的条件概率 P ( w n ∣ w n − 1 ) P(w_n|w_{n-1}) P ( w n ∣ w n − 1 ) P ( w n ∣ w 1 : n − 1 ) P(w_n|w_{1:n-1}) P ( w n ∣ w 1 : n − 1 )
P ( blue ∣ The water of Walden Pond is so beautifully ) (3.5) P (\text { blue } | \text { The water of Walden Pond is so beautifully })\tag{3.5} P ( blue ∣ The water of Walden Pond is so beautifully ) ( 3.5 ) 而使用下面的概率进行近似：
P ( blue ∣ beautifully ) (3.6) P (\text { blue } | \text { beautifully })\tag{3.6} P ( blue ∣ beautifully ) ( 3.6 ) 因此，使用二元模型预测下一词的条件概率时，会作出如下近似：
P ( w n ∣ w 1 : n − 1 ) ≈ P ( w n ∣ w n − 1 ) (3.7) P (w _ {n} | w _ {1: n - 1}) \approx P (w _ {n} | w _ {n - 1})\tag{3.7} P ( w n ∣ w 1 : n − 1 ) ≈ P ( w n ∣ w n − 1 ) ( 3.7 ) 一个词的概率只取决于前一个词，这项假设称为 Markov 假设 （Markov assumption）。Markov 模型 （Markov model）是一类概率模型，它们假设无需向过去回看太远，就能预测未来某个单位的概率。二元模型回看一个词；我们可以把它推广为回看两个词的三元模型，并进一步推广为回看 n − 1 n-1 n − 1
下面给出使用 n 元语法近似序列中下一词条件概率的一般公式。这里用 N N N N = 2 N=2 N = 2 N = 3 N=3 N = 3
P ( w n ∣ w 1 : n − 1 ) ≈ P ( w n ∣ w n − N + 1 : n − 1 ) (3.8) P (w _ {n} | w _ {1: n - 1}) \approx P (w _ {n} | w _ {n - N + 1: n - 1})\tag{3.8} P ( w n ∣ w 1 : n − 1 ) ≈ P ( w n ∣ w n − N + 1 : n − 1 ) ( 3.8 ) 利用单个词概率的二元假设，把式 3.7 代入式 3.4，即可计算完整词序列的概率：
P ( w 1 : n ) ≈ ∏ k = 1 n P ( w k ∣ w k − 1 ) (3.9) P (w _ {1: n}) \approx \prod_ {k = 1} ^ {n} P (w _ {k} | w _ {k - 1})\tag{3.9} P ( w 1 : n ) ≈ k = 1 ∏ n P ( w k ∣ w k − 1 ) ( 3.9 ) 3.1.2 如何估计概率 ¶ 怎样估计二元或 n 元概率？一种直观方法称为最大似然估计 （maximum likelihood estimation，MLE）。为了得到 n 元模型参数的 MLE 估计，我们从语料库取得计数，再把计数归一化到 0 与 1 之间。对概率模型而言，归一化就是除以某个总计数，使所得概率位于 0 与 1 之间，且总和为 1。
例如，要计算给定前一个词 w n − 1 w_{n-1} w n − 1 w n w_n w n C ( w n − 1 w n ) C(w_{n-1}w_n) C ( w n − 1 w n ) w n − 1 w_{n-1} w n − 1
P ( w n ∣ w n − 1 ) = C ( w n − 1 w n ) ∑ w C ( w n − 1 w ) (3.10) P (w _ {n} | w _ {n - 1}) = \frac {C (w _ {n - 1} w _ {n})}{\sum_ {w} C (w _ {n - 1} w)}\tag{3.10} P ( w n ∣ w n − 1 ) = ∑ w C ( w n − 1 w ) C ( w n − 1 w n ) ( 3.10 ) 由于以给定词 w n − 1 w_{n-1} w n − 1 C ( w n − 1 ) C(w_{n-1}) C ( w n − 1 )
P ( w n ∣ w n − 1 ) = C ( w n − 1 w n ) C ( w n − 1 ) (3.11) P (w _ {n} | w _ {n - 1}) = \frac {C (w _ {n - 1} w _ {n})}{C (w _ {n - 1})}\tag{3.11} P ( w n ∣ w n − 1 ) = C ( w n − 1 ) C ( w n − 1 w n ) ( 3.11 ) 下面用一个只含三个句子的微型语料库完成示例。首先，需要在每个句子开头加入特殊符号 ⟨ s ⟩ \langle s\rangle ⟨ s ⟩ ⟨ / s ⟩ \langle/s\rangle ⟨ / s ⟩ [1]
⟨ s ⟩ I am Sam ⟨ / s ⟩ ⟨ s ⟩ Sam I am ⟨ / s ⟩ ⟨ s ⟩ I do not like green eggs and ham ⟨ / s ⟩ \begin{array}{l} \langle s \rangle \text {I am Sam} \langle / s \rangle \\ \langle s \rangle \text {Sam I am} \langle / s \rangle \\ \langle s \rangle \text {I do not like green eggs and ham} \langle / s \rangle \end{array} ⟨ s ⟩ I am Sam ⟨ / s ⟩ ⟨ s ⟩ Sam I am ⟨ / s ⟩ ⟨ s ⟩ I do not like green eggs and ham ⟨ / s ⟩ 下面计算这个语料库中的若干二元概率：
P ( I ∣ < s > ) = 2 3 = 0.67 P ( S a m ∣ < s > ) = 1 3 = 0.33 P ( a m ∣ I ) = 2 3 = 0.67 P ( < / s > ∣ S a m ) = 1 2 = 0.5 P ( S a m ∣ a m ) = 1 2 = 0.5 P ( d o ∣ I ) = 1 3 = 0.33 \begin{array}{l l l} P (\mathsf {I} | <\mathsf {s}>) = \frac {2}{3} = 0.67 & P (\mathsf {Sam} | <\mathsf {s}>) = \frac {1}{3} = 0.33 & P (\mathsf {am} | \mathsf {I}) = \frac {2}{3} = 0.67 \\ P (</\mathsf {s}> | \mathsf {Sam}) = \frac {1}{2} = 0.5 & P (\mathsf {Sam} | \mathsf {am}) = \frac {1}{2} = 0.5 & P (\mathsf {do} | \mathsf {I}) = \frac {1}{3} = 0.33 \end{array} P ( I ∣ < s > ) = 3 2 = 0.67 P ( < / s > ∣ Sam ) = 2 1 = 0.5 P ( Sam ∣ < s > ) = 3 1 = 0.33 P ( Sam ∣ am ) = 2 1 = 0.5 P ( am ∣ I ) = 3 2 = 0.67 P ( do ∣ I ) = 3 1 = 0.33 对于 MLE n 元参数估计的一般情形（N = 2 , 3 , … N=2,3,\ldots N = 2 , 3 , …
P ( w n ∣ w n − N + 1 : n − 1 ) = C ( w n − N + 1 : n − 1 w n ) C ( w n − N + 1 : n − 1 ) (3.12) P (w _ {n} | w _ {n - N + 1: n - 1}) = \frac {C (w _ {n - N + 1 : n - 1} w _ {n})}{C (w _ {n - N + 1 : n - 1})}\tag{3.12} P ( w n ∣ w n − N + 1 : n − 1 ) = C ( w n − N + 1 : n − 1 ) C ( w n − N + 1 : n − 1 w n ) ( 3.12 ) 式 3.12 与式 3.11 一样，用某个特定序列的观测频次除以其前缀的观测频次来估计 n 元概率。这个比值称为相对频次 （relative frequency）。前文已经指出，这种使用相对频次估计概率的方法是最大似然估计的一例。在 MLE 中，所得参数集合会使给定模型 M M M T T T P ( T ∣ M ) P(T|M) P ( T ∣ M ) 400 / 1 , 000 , 000 = 0.0004 400/1,000,000=0.0004 400/1 , 000 , 000 = 0.0004
下面考察一个真实但很小的语料库示例。它取自现已停止运行的 Berkeley Restaurant Project；这是上个世纪的一个对话系统，可以回答有关加利福尼亚州伯克利餐馆数据库的问题（Jurafsky et al., 1994）。下面是几条用户查询样例；文本已经过规范化，转换为小写并去除标点（网站上提供了 9,332 个句子的样本）：
can you tell me about any good cantonese restaurants close by
tell me about chez panisse
i’m looking for a good place to eat breakfast
when is caffe venezia open during the day
图 3.1 展示根据经过文本规范化的 Berkeley Restaurant Project 句子构建的二元语法中，部分词的二元计数。请注意，大多数值为零。事实上，这里特意选择了彼此能够形成搭配的样例词；如果从八个随机词中选择，矩阵还会更加稀疏。
i want to eat chinese food lunch spend i 5 827 0 9 0 0 0 2 want 2 0 608 1 6 6 5 1 to 2 0 4 686 2 0 6 211 eat 0 0 2 0 16 2 42 0 chinese 1 0 0 0 0 82 1 0 food 15 0 15 0 1 4 0 0 lunch 2 0 0 0 0 1 0 0 spend 1 0 1 0 0 0 0 0
图 3.1 Berkeley Restaurant Project 的 9,332 句语料库中，词表 V = 1446 V=1446 V = 1446
图 3.2 展示归一化后的二元概率，即把图 3.1 中的每个单元格除以对应行的一元计数；所使用的一元计数如下：
i want to eat chinese food lunch spend 2533 927 2417 746 158 1093 341 278
i want to eat chinese food lunch spend i 0.002 0.33 0 0.0036 0 0 0 0.00079 want 0.0022 0 0.66 0.0011 0.0065 0.0065 0.0054 0.0011 to 0.00083 0 0.0017 0.28 0.00083 0 0.0025 0.087 eat 0 0 0.0027 0 0.021 0.0027 0.056 0 chinese 0.0063 0 0 0 0 0.52 0.0063 0 food 0.014 0 0.014 0 0.00092 0.0037 0 0 lunch 0.0059 0 0 0 0 0.0029 0 0 spend 0.0036 0 0.0036 0 0 0 0
图 3.2 Berkeley Restaurant Project 的 9,332 句语料库中八个词的二元概率。零概率以灰色表示。
下面是另外几个有用的概率：
P ( i ∣ < s > ) = 0.25 P ( english|want ) = 0.0011 P ( food|english ) = 0.5 P ( < / s > ∣ food ) = 0.68 \begin{array}{l l} P (\mathrm{i} | <\mathrm{s}>) = 0.25 & P (\text {english|want}) = 0.0011 \\ P (\text {food|english}) = 0.5 & P (</\mathrm{s}> | \text {food}) = 0.68 \end{array} P ( i ∣ < s > ) = 0.25 P ( food|english ) = 0.5 P ( english|want ) = 0.0011 P ( < / s > ∣ food ) = 0.68 现在，只需把相应二元概率相乘，就能计算 I want English food 或 I want Chinese food 等句子的概率：
P ( < s > i want english food < / s > ) = P ( i ∣ < s > ) P ( want ∣ i ) P ( english ∣ want ) P ( food ∣ english ) P ( < / s > ∣ food ) = 0.25 × 0.33 × 0.0011 × 0.5 × 0.68 = 0.000031 \begin{array}{r l} P (<\mathrm{s}> \text {i want english food} </\mathrm{s}>) & \\ = P (\mathrm{i} | <\mathrm{s}>) P (\text {want} | \mathrm{i}) P (\text {english} | \text {want}) & \\ P (\text {food} | \text {english}) P (</\mathrm{s}> | \text {food}) & \\ = 0.25 \times 0.33 \times 0.0011 \times 0.5 \times 0.68 & \\ = 0.000031 & \end{array} P ( < s > i want english food < / s > ) = P ( i ∣ < s > ) P ( want ∣ i ) P ( english ∣ want ) P ( food ∣ english ) P ( < / s > ∣ food ) = 0.25 × 0.33 × 0.0011 × 0.5 × 0.68 = 0.000031 练习 3.2 要求计算 i want chinese food 的概率。
这些二元统计捕捉了哪些语言现象？上面的一些二元概率编码了通常被视为纯句法的事实，例如 eat 后面通常是名词或形容词，to 后面通常是动词。另一些概率可能反映个人助理任务，例如句子以 I 开头的概率很高。还有一些甚至可能属于文化事实而非语言事实，例如人们寻找中餐的概率高于寻找英餐的概率。
3.1.3 处理大型 n 元模型的规模问题 ¶ 实践中的语言模型可能非常大，从而引发一系列实际问题。
对数概率 语言模型的概率总是以对数概率 （log probability）形式存储，并在对数空间中计算。这是因为概率按定义小于或等于 1，相乘的概率越多，乘积就越小。把足够多的 n 元概率相乘会造成数值下溢。在对数空间中相加等价于在线性空间中相乘，因此我们通过加法组合对数概率。对数概率相加所得结果不会像概率乘积那么小。所有计算和存储都在对数空间中进行；只有最终需要报告概率时，才对对数概率取指数，转换回普通概率：
p 1 × p 2 × p 3 × p 4 = exp ( log p 1 + log p 2 + log p 3 + log p 4 ) (3.13) p _ {1} \times p _ {2} \times p _ {3} \times p _ {4} = \exp (\log p _ {1} + \log p _ {2} + \log p _ {3} + \log p _ {4})\tag{3.13} p 1 × p 2 × p 3 × p 4 = exp ( log p 1 + log p 2 + log p 3 + log p 4 ) ( 3.13 ) 本书在没有指定底数时，用 log 表示自然对数 ln。
更长的上下文 为便于教学，前文只介绍了二元模型；当训练数据充足时，通常会使用以前两个词为条件的三元模型，或 4 元、5 元模型。使用这些更大的 n 元语法时，需要在句子左右边界假定额外上下文。例如，为计算句子最开头的三元概率，会为第一个三元语法使用两个伪词，即 P ( I ∣ ⟨ s ⟩ ⟨ s ⟩ ) P(I|\langle s\rangle\langle s\rangle) P ( I ∣ ⟨ s ⟩ ⟨ s ⟩)
研究者已经创建了一些大型 n 元数据集。例如，从精心整理、包含 10 亿词的美国英语语料库 COCA（Corpus of Contemporary American English）中抽取的最高频 100 万个 n 元语法（Davies, 2020）；从 1 万亿词英语网络文本中抽取的 Google Web 5-gram 语料库（Franz and Brants, 2006）；以及 Google Books Ngrams 语料库，其中包含来自汉语、英语、法语、德语、希伯来语、意大利语、俄语和西班牙语的 8000 亿个词元（Lin et al., 2012a）。
甚至可以使用距离极远的 n 元上下文。无限元语法 （infini-gram，∞-gram）项目（Liu et al., 2024）允许 n 元语法具有任意长度。其核心思想是避免提前计算代价高昂（占用大量空间和时间）的巨型 n 元计数表；系统转而使用一种称为后缀数组 （suffix array）的高效表示，在推理时快速计算任意 n n n
构建大型 n 元语言模型时，效率十分重要。标准做法包括：只使用 4～8 位量化概率，而不是 8 字节浮点数；把词语字符串存储在磁盘上，在内存中只用 64 位哈希表示；使用“反向 trie”等特殊数据结构表示 n 元语法。语言模型也经常进行剪枝 （pruning），例如只保留计数超过某个阈值的 n 元语法，或者用熵剪除不太重要的 n 元语法（Stolcke, 1998）。KenLM 等高效语言模型工具包（Heafield, 2011; Heafield et al., 2013）使用有序数组，并借助归并排序，以尽可能少的语料库遍历次数高效构建概率表。