11.1 信息检索 - SLP3 中文翻译

信息检索（information retrieval, IR）是一个领域的名称，它涵盖根据用户的信息需求检索各种媒介的任务。由此得到的 IR 系统通常称为搜索引擎。本节旨在充分概述 IR，以说明它如何用于帮助大语言模型满足用户的信息需求。对信息检索本身更感兴趣的读者，可参阅本章末尾的“历史说明”。

我们讨论的 IR 任务称为临时检索（ad hoc retrieval）：用户向检索系统提出一个查询（query），系统随后从某个集合（collection）中返回一组有序的文档（document）。文档是系统建立索引并检索的任意文本单位，可以是网页、科学论文、新闻报道，甚至是段落等更短的篇章。集合是用于满足用户请求的一组文档；它可以指整个互联网，此时我们进行的是网络搜索，也可以是较小的企业资料库，甚至是某个人使用的一组文档。词项（term）通常指集合中的一个词，但也可以包括短语。最后，查询用一组词项表示用户的信息需求。

图 11.1 临时 IR 系统的架构。文档排序的方法是：给定查询，为每篇候选文档计算一个分数，表示该文档与用户信息需求可能具有多大的相关性。根据查询与文档向量的两种表示，IR 系统可分为两类：稀疏向量系统和稠密向量系统。这两类检索在索引和评分机制的细节上有所不同。

图 11.1 展示了临时检索引擎的高层架构，并抽象概括了基于两类向量表示查询和文档的两类 IR 系统：稀疏向量与稠密向量。在稀疏检索（sparse retrieval）中，我们使用由 tf-idf 或 BM25 加权的计数向量表示文档和查询；在稠密检索（dense retrieval）中，则使用语言模型（编码器或解码器模型）计算出的嵌入表示文档和查询。本节余下部分讨论稀疏检索，11.3 节再转向稠密检索。

11.1.1 将文档表示为向量¶

在信息检索的向量空间模型（vector space model）（Salton, 1971）中，文档表示为其中各词出现次数构成的向量。

我们有时把这种模型称为词袋模型（bag-of-words model）。图 11.2 展示了其中的直觉：我们把一篇文本文档表示成一袋词，即忽略词的位置，把文本视为无序词集，只保留每个词在文档中的频率。在图中的例子里，我们不表示“It manages to be whimsical and romantic”等短语中的词序，而只记录 it 在整个选段中出现 5 次，love、recommend 和 movie 各出现 1 次，依此类推。

图 11.2 经典向量空间模型用于单篇文档时的直观解释。词的位置被忽略（词袋假设），只使用每个词的频率。

因此，可以设想用向量 [1 3 1 1 1 1 1 5 6 1 2 1 4 1 3 1 1 1] 表示图 11.2 中的文档（假设仅使用这 18 个维度，并忽略英语中的其他所有词）。

更一般地，我们可以用词项—文档矩阵（term-document matrix）表示一组文档，其中每一行代表词表中的一个词，每一列代表某个文档集合中的一篇文档。图 11.3 展示了一个词项—文档矩阵的小片段，其中包含四个词在莎士比亚四部戏剧中的出现次数。矩阵中的每个单元格表示某个特定词（由行定义）在某篇特定文档（由列定义）中出现的次数。因此，fool 在 Twelfth Night 中出现了 58 次。

文档表示为计数向量，即图 11.4 中的一列。为使文档向量能放在页面上，图 11.4 的例子只选用了 4 个维度；在真实的词项—文档矩阵中，文档向量的维数应为词表大小 V。这两个向量的第一个维度都对应 battle 的出现次数。我们可以逐维比较，例如 As You Like It 与 Twelfth Night 的向量在第一个维度上的值很相近，分别为 1 和 0。

图 11.3 四个词在莎士比亚四部戏剧中的词项—文档矩阵。每个单元格包含该词（行）在该文档（列）中出现的次数。

图 11.4 四个词在莎士比亚四部戏剧中的词项—文档矩阵。红框表明，每篇文档表示成一个长度为 4 的列向量。

四维空间很难可视化，因此图 11.5 在二维空间中显示了四个文档向量；这里任意选择了对应 battle 和 fool 的两个维度。

图 11.5 莎士比亚四部戏剧文档向量的空间可视化，只展示与 battle 和 fool 对应的两个维度。喜剧在 fool 维度上取值较高，在 battle 维度上取值较低。

相似的文档往往包含相似的词；如果两篇文档包含相似的词，它们的列向量也往往相似。喜剧 As You Like It 的向量 [1,114,36,20] 与 Twelfth Night 的向量 [0,80,58,15] 彼此十分相似（fool 和 wit 较多，battle 较少），而与 Julius Caesar 的 [7,62,1,2] 或 Henry V 的 [13,89,4,3] 差异较大。

11.1.2 词项加权：tf-idf 与 BM25¶

实际的 IR 系统不会直接使用原始词频，如 As You Like It 的 [1 114 36 20]，或图 11.2 中文档的 [1 3 1 1 1 1 1 5 6 1 2 1 4 1 3 1 1 1]，而会为每个文档词计算词项权重（term weight）。常见的词项加权方案有两种：tf-idf，以及 tf-idf 的一种变体 BM25。

tf-idf（其中的“-”是连字符，不是减号）是两项的乘积：词频（term frequency, tf）与逆文档频率（inverse document frequency, idf）。

词频表示一个词出现得有多频繁；在文档中出现越多的词，越可能包含有关文档内容的信息。我们通常使用词频的 $\log _ { 10 }$ ，而不是原始计数。其直觉是：一个词在文档中出现 100 次，并不会使它与文档意义相关的可能性变成 100 倍。由于无法计算 0 的对数，还必须特殊处理计数为 0 的情况。^[3] 若用 $\operatorname{count}(t,d)$ 表示词项 $t$ 在文档 $d$ 中的原始计数，则词项 $t$ 在文档 $d$ 中的 tf，即 $\mathrm {tf}_{t,d}$ ，为：

\operatorname{tf} _ {t, d} = \left\{ \begin{array}{l l} 1 + \log_ {10} \operatorname{count} (t, d) & \text { if } \operatorname{count} (t, d) > 0 \\ 0 & \text { otherwise } \end{array} \right.\tag{11.4}

采用对数加权时，在文档中出现 0 次的词项有 $\operatorname{tf}=0$ ；出现 1 次时， $\operatorname{tf}=1+\log_{10}(1)=1$ ；出现 10 次时， $\operatorname{tf}=1+\log_{10}(10)=2$ ；出现 100 次时， $\operatorname{tf}=3$ ；出现 1000 次时， $\operatorname{tf}=4$ ；依此类推。

词项 t 的文档频率 $\mathrm{df}_t$ 是包含它的文档数。只出现在少数文档中的词项，有助于把这些文档与集合中的其他文档区分开；贯穿整个集合的词项则帮助不大。逆文档频率（idf）词项权重（Sparck Jones, 1972）定义为：

\mathrm{idf} _ {t} = \log_ {10} \frac {N}{\mathrm{df} _ {t}}\tag{11.5}

其中，N 是集合中的文档总数， $\mathrm{df}_t$ 是词项 t 出现过的文档数。一个词项出现的文档越少，该权重越高；若词项出现在每篇文档中，则被赋予最低权重 0。

下表给出了莎士比亚戏剧语料库中一些词的 idf 值：从只出现在一部戏剧中、信息量极大的 Romeo，到出现在少数戏剧中的 salad 或 Falstaff，再到很常见的 fool，以及 good 或 sweet 这种出现在全部 37 部戏剧中、完全没有区分能力的词。^[4]

词	df	idf
Romeo	1	1.57
salad	2	1.27
Falstaff	4	0.967
forest	12	0.489
battle	21	0.246
wit	34	0.037
fool	36	0.012
good	37	0
sweet	37	0

词 t 在文档 d 中的 tf-idf 值，就是词频 $\mathrm{tf}_{t,d}$ 与 idf 的乘积：

\operatorname{tf-idf} (t, d) = \operatorname{tf} _ {t, d} \cdot \operatorname{idf} _ {t}\tag{11.6}

11.1.3 文档评分¶

将每篇文档和查询表示成加权向量后，我们需要为每篇文档评分。目标是衡量文档与用户通过查询表达的信息需求之间的相关性。在经典 tf-idf 模型中，我们通过测量文档与查询在向量空间中的几何相似度来估计这种相关性。换言之，我们采用一种简化假设：与查询包含相似词语的文档，对用户而言更相关。

我们使用第 5 章介绍的余弦相似度函数，以文档向量 d 与查询向量 q 的余弦为文档 d 评分：

\operatorname{score} (q, d) = \cos (\mathbf {q}, \mathbf {d}) = \frac {\mathbf {q} \cdot \mathbf {d}}{| \mathbf {q} | | \mathbf {d} |}\tag{11.7}

也可以把余弦计算理解为单位向量的点积：先把查询向量和文档向量分别除以自身长度，将二者归一化为单位向量，再计算点积：

\operatorname{score} (q, d) = \cos (\mathbf {q}, \mathbf {d}) = \frac {\mathbf {q}}{| \mathbf {q} |} \cdot \frac {\mathbf {d}}{| \mathbf {d} |}\tag{11.8}

把 tf-idf 值代入式 11.8，并将点积展开为乘积之和，可得：

\operatorname{score} (q, d) = \sum_ {t \in \mathbf {q}} \frac {\operatorname{tf-idf} (t , q)}{\sqrt {\sum_ {q _ {i} \in q} \operatorname{tf-idf} ^ {2} (q _ {i} , q)}} \cdot \frac {\operatorname{tf-idf} (t , d)}{\sqrt {\sum_ {d _ {i} \in d} \operatorname{tf-idf} ^ {2} (d _ {i} , d)}}\tag{11.9}

下面使用式 11.9 演示一个微型查询在 4 篇纳米级文档组成的集合中进行检索的例子：我们将计算 tf-idf 值，并查看文档的排名。假设以下查询和文档中的所有词都已转成小写，标点也已删除：

查询：sweet love
文档 1：Sweet sweet nurse! Love?
文档 2：Sweet sorrow
文档 3：How sweet is love?
文档 4：Nurse!

图 11.6 展示了查询与文档 1、文档 2 之间 tf-idf 余弦的计算。余弦是 tf-idf 值的归一化点积，因此进行归一化时，需要使用式 11.4、11.5、11.6 和 11.9，计算查询和前两篇文档的向量长度 $|q|$ 、 $|d_1|$ 与 $|d_2|$ （文档 3、4 也需计算，但留作练习）。向量的点积是在所有维度上，对两个 tf-idf 向量在该维度的值求乘积，再把这些乘积相加。只有查询和文档的值都非零时，乘积才非零。因此在本例中，查询里只有 sweet 和 love 的值非零，点积就是每个文档向量中这两个元素分别与查询向量对应元素之积的总和。

文档 1 与查询的余弦（0.747）高于文档 2 与查询的余弦（0.0779），所以 tf-idf 余弦模型会把文档 1 排在文档 2 之前。按向量空间模型来看，这一排名很直观：文档 1 同时包含两个查询词项，其中 sweet 还出现了两次；文档 2 则缺少一个词项。文档 3、4 的计算留给读者练习。

图 11.6 使用式 11.4、11.5、11.6 和 11.9，计算查询与纳米文档 1（0.747）、文档 2（0.0779）之间的 tf-idf 余弦分数。

实际应用中，式 11.9 有许多变体和近似形式。例如，我们可以删除某些项来简化处理。先把式 11.6 中的 tf 与 idf 项显式代入式 11.9：

\operatorname{score} (q, d) = \sum_ {t \in \mathbf {q}} \frac {\operatorname{tf} _ {t , q} \cdot \operatorname{idf} _ {t}}{\sqrt {\sum_ {q _ {i} \in q} \operatorname{tf-idf} ^ {2} \left(q _ {i} , q\right)}} \cdot \frac {\operatorname{tf} _ {t , d} \cdot \operatorname{idf} _ {t}}{\sqrt {\sum_ {d _ {i} \in d} \operatorname{tf-idf} ^ {2} \left(d _ {i} , d\right)}}\tag{11.10}

例如，在 tf-idf 余弦的一种常见变体中，我们去掉文档一侧的 idf 项。消除 idf 项的第二份副本（因为查询一侧已经计算了相同的项），有时反而会带来更好的性能：

\operatorname{score} (q, d) = \sum_ {t \in \mathbf {q}} \frac {\operatorname{tf} _ {t , q} \cdot \operatorname{idf} _ {t}}{\sqrt {\sum_ {q _ {i} \in q} \operatorname{tf-idf} ^ {2} \left(q _ {i} , q\right)}} \cdot \frac {\operatorname{tf} _ {t , d}}{\sqrt {\sum_ {d _ {i} \in d} \operatorname{tf-idf} ^ {2} \left(d _ {i} , d\right)}}\tag{11.11}

tf-idf 的其他变体还会消除各种其他项。

tf-idf 家族中稍复杂的一种变体是 BM25 加权方案；它有时也称为 Okapi BM25，得名于最早引入它的 Okapi IR 系统（Robertson et al., 1995）。BM25 增加了两个参数：k 用于调节词频与 IDF 之间的平衡，b 用于控制文档长度归一化的重要性。给定查询 q，文档 d 的 BM25 分数为：

\sum_ {t \in q} \overbrace {\log \left(\frac {N}{\mathrm{df} _ {t}}\right)} ^ {\text { IDF }} \overbrace {\frac {\operatorname{tf} _ {t , d}}{k \left(1 - b + b \left(\frac {| d |}{| d _ {\text {avg}} |}\right)\right) + \operatorname{tf} _ {t , d}}} ^ {\text { weighted tf }}\tag{11.12}

其中， $|d_{\mathrm{avg}}|$ 是平均文档长度。 $k$ 为 0 时，BM25 不使用词频，而只对查询中的词项作二元选择（再加上 idf）；较大的 k 会使其趋向使用原始词频（再加上 idf）。 $b$ 的取值范围从 1（按文档长度缩放）到 0（不按长度缩放）。Manning et al.（2008）建议的合理取值为 $k=[1.2,2]$ 、 $b=0.75$ 。Kamphuis et al.（2020）对 BM25 的许多细微变体作了很好的总结。

停用词。 过去，人们通常会在表示查询和文档之前，从二者中删除高频词。待删除的高频词列表称为停用词表（stop list）。其直觉是，高频词项（通常是 the、a、to 等功能词）语义权重很小，可能无助于检索；删除它们还可以缩小下文所述的倒排索引文件。使用停用词表的缺点是，它使包含停用词的短语难以搜索。例如，常见停用词表会把短语 to be or not to be 缩减为 not。现代 IR 系统很少再使用停用词表，一方面是因为效率有所提高，另一方面是因为 IDF 加权已经承担了大部分相同功能：出现在每篇文档中的功能词会被降低权重。尽管如此，移除停用词偶尔仍对各种 NLP 任务有用，因此值得了解。

11.1.4 高效查找文档：倒排索引¶

为了计算分数，我们需要高效找出包含查询词的文档。（不包含任何查询词项的文档分数为 0，可以忽略。）因此，IR 中的基本搜索问题是：找出包含某个词项 $q\in\mathcal{Q}$ 的所有文档 $d\in C$ 。

用于这一任务的数据结构是倒排索引（inverted index）。它不仅能提高搜索效率，还能方便地存储文档频率、每个词项在每篇文档中的计数等有用信息。

给定一个查询词项，倒排索引会给出包含该词项的文档列表。它由两部分组成：词典（dictionary）与倒排记录（postings）。词典是一个为高效访问而设计的词项列表，每个词项都指向相应的倒排记录表（postings list）。倒排记录表包含与该词项关联的文档 ID，也可以包含词频乃至词项在文档中的确切位置等信息。词典还可以存储每个词项的文档频率。例如，对于上面的 4 篇示例文档，一个简单的倒排索引可以如下所示：每个词后用 {} 标注文档频率，其指向的倒排记录表用 [] 标注文档 ID 与词项计数。

\begin{array}{l l} \text {how \{1\}} & \to 3 [ 1 ] \\ \text {is \{1\}} & \to 3 [ 1 ] \\ \text {love \{2\}} & \to 1 [ 1 ] \to 3 [ 1 ] \\ \text {nurse \{2\}} & \to 1 [ 1 ] \to 4 [ 1 ] \\ \text {sorrow \{1\}} & \to 2 [ 1 ] \\ \text {sweet \{3\}} & \to 1 [ 2 ] \to 2 [ 1 ] \to 3 [ 1 ] \end{array}

给定查询中的词项列表，我们可以非常高效地取得所有候选文档列表，以及计算所需 tf-idf 分数所必需的信息。

11.1.5 小结：排序检索¶

把上述组件整合起来，就得到一个完整的排序检索（ranked retrieval）系统。在初始化阶段，系统接收一个文档集合，并为其创建倒排索引。

随后在检索阶段，给定用户查询，检索系统使用倒排索引找出所有包含查询关键词的候选文档。系统通过计算每篇候选文档与用户查询向量之间的 tf-idf（或 BM25）余弦，为文档赋分，估计其与用户需求的相关性。文档按照相关性分数从高到低排序，再将整个列表（或其中前 N 篇文档）返回给用户。

Footnotes¶

我们也可以采用另一种公式；本书的早期版本使用的就是这种形式： $\mathrm{tf}_{t,d} = \log_{10}(\operatorname{count}(t,d)+1)$ 。
↩
Sweet 是莎士比亚最喜爱的形容词之一；这一事实可能与 16 世纪之交欧洲食谱中糖的使用日益增多有关（Jurafsky, 2014, p. 175）。
↩