Question

从第 8 章介绍的广告系统架构可以看出，为了达到面向大量中小广告主时良好的扩展性，计算广告采用的是类搜索的技术框架，即检索加排序两段的决策过程。因此，我们有必要对搜索引擎信息检索的基本方法有所了解，这里主要介绍倒排索引和向量空间模型。

10.1.1 倒排索引

倒排索引（inverted index）^[83]是现代搜索引擎的核心技术之一，其核心目的是将从大量文档中查找包含某些词的文档集合这一任务用O（1）或O（log n）的时间复杂度^[2]完成，其中n为索引中的文档数目。也就是说，利用倒排索引技术，可以实现与文档集大小基本无关的检索复杂度，这一点对于海量内容的检索来说至关重要。正是有了倒排索引技术的支撑，互联网才在实时检索大规模数据方面取得了质的飞跃。我们用例子来说明倒排索引的基本概念，假设我们有如下的几篇文档：

D₀=“谷歌地图之父跳槽Facebook”

D₁=“谷歌地图之父加盟Facebook”

D₂=“谷歌地图创始人拉斯离开谷歌加盟Facebook”

D₃=“谷歌地图创始人跳槽Facebook与Wave项目取消有关”

D₄=“谷歌地图创始人拉斯加盟社交网站Facebook”

对每篇文档都进行分词以后，可知这些文档中包含的关键词（term）有：{谷歌，地图，之父，跳槽，Facebook，加盟，创始人，拉斯，离开，与，Wave，项目，取消，有关，社交，网站}。首先，去掉“与”这样的没有实际表意作用的停止词（stop word），我们对每一个词建立一个链表，表中的每个元素都是包含该词的某篇文档的标识。于是，与上面的文档集对应的倒排索引，也就是所有关键词的倒排链集合可以表示如下：

谷歌→{D₁，D₂，D₃，D₄，D₅}，地图→{D₁，D₂，D₃，D₄，D₅}，之父→{D₁，D₂，D₄，D₅}，

跳槽→{D₁，D₄}，Facebook→{D₁，D₂，D₃，D₄，D₅}，创始人→{D₃}，

加盟→{D₂，D₃，D₅}，拉斯→{D₃，D₅}，离开→{D₃}，Wave→{D₄}，

取消→{D₄}，项目→{D₄}，有关→{D₄}，社交→{D₄}，网站→{D₄}。

为了后文一些实例的方便，我们用下面一段代码中的类结构来描述一个倒排索引。这个类结构派生于hash map，其中的键为关键词，即term，典型情况下，该键是string类型，但是在后文介绍的布尔表达式检索等场景中，其键的类型可能会发生变化。因此，为了逻辑统一，我们引入了模板参数来泛化此处的数据类型。而 hash map的值就是倒排链，是一个由索引条目组成的链表。每个索引条目有两个域，第一个是该条目对应的文档的 ID，第二个是一个辅助变量，比如可以用于表示目前关键词在此文档的TD-IDF（参见10.1.2节），在后面提到的其他索引类型中也会有独特的应用。当然，这种结构只是一个概念上的表达，实际的倒排索引还要存储很多其他信息，为了便于突出主要概念，在本书中采用这样简单的概念性描述。

倒排索引最基本的操作有两项：一是向索引中加入一个新文档，二是给定一个由多个关键词组成的查询时，返回对应的文档集合。我们也在下面的代码中对这两项基本功能的实现做了描述。需要注意的是：在倒排索引中，由于文档ID是在加入倒排索引时被在线分配的，因此每个倒排链都可以确保是有序的，这会在后面的应用中得到具体利用。

需要说明，这段代码仅仅是帮助大家了解问题的示例性代码，而实际的倒排索引远比此复杂。其工程难点有很多，比如如何设计精简的数据结构以节省对内存的使用以及如何比较实时地将新的文档加入倒排索引等。这些问题由于是信息检索领域专门的研究课题，并非广告的特殊需求，我们不再深入介绍。需要自行实现广告检索部分的读者可以参考这方面专门的技术文献或者深入学习9.5.3节中介绍的开源的倒排索引工具Lucene。

10.1.2 向量空间模型

如果说倒排索引技术是大规模信息检索的基石，那么向量空间模型（Vector Space Model， VSM）^[71]则是信息检索中最基础且最重要的文档相似度度量方法之一。VSM 的核心有两点：文档的表示方法和相似度计算方法。

首先，我们对每个文档采用词袋（Bag of Words，BoW）假设，即用各个关键词在文档中的强度组成的矢量来表示该文档：

其中x_m一般采用词表中第m个词在d中对应的TF-IDF（Term Frequency-Inverse DocumentFrequency，词频–倒数文档频率）值，这是一种信息检索中最常见的词强度度量，可以分解为两个量的乘积：一个量是词频（Term Frequency，TF），即某文档中该词出现的次数；另一个量是倒数文档频率（Inverse Document Frequency，IDF），即该词在所有文档中出现的频繁程度的倒数。IDF 的引入是考虑到那些广泛出现在各个文档中的常用词对主题的鉴别力并不强，因而需要降低其权重。IDF的计算方法有若干种，最常用的形式为：

其中 DF（m） 为词 m 在其中出现的文档的总数目，N 为总文档数目。在广告应用中如何计算IDF值，在某些情形下需要不同的处理。例如，在处理对广告主有价值的竞价标的词时，可以采用所有广告描述，而不是互联网上的网页作为文档集合。相应地，在根据关键词进行广告检索时，也应该使用这种方法得到的TF-IDF。

这样的BoW文档表示方法是对自然语言最简单粗略的一种近似表示。它完全忽略了词的前后接续关系以及更高阶的语法因素的影响，因而并不太可能具有精细的文档描述能力。不过，这种方法在信息检索中的作用无疑是巨大的，因为它通过极为简单经济的操作对文档进行了简化，同时又比较好地保留了文档的概貌，这对于海量文档数据的处理和索引非常有利。时至今日，虽然学者们在自然语言处理方面取得了许多进展，但这种简单的方法仍然是工程实践中信息检索和文档主题挖掘的最常用文档表示。如果我们考虑更精细的文档描述，可以进一步加入文档的n-gram信息，但是也会带来数据的爆炸式增长和模型估计稳健性上极大的挑战。

采用BoW的文档表示方法，在计算两个文档的相似度时，一般是用其对应矢量的余弦距离：

余弦距离的最显著好处是当两个矢量在尺度上没有归一化时，仍然可以得到比较稳健的结果。比如有两篇一样的文档，将其中的一篇内容重复一遍，再去计算余弦距离仍然是0，而如果采用其他方式，如欧氏距离，结果就不再是0了。再比如两个人对各种电影打分，甲倾向于给较高的分数，乙倾向于给较低的分数，那么在一组3部电影上，甲给出的分数{3.6，3.6，4.8}和乙给出的分数 {3.0，3.0，4.0} 实际上一致程度相当高，这也可以被余弦距离比较公允地度量出来。

了解了上面的这些内容，读者可以建立对海量文档进行检索的基本方案。在离线索引阶段，需要对文档集合分词，并按照BoW模型表示得到每个文档的TF-IDF矢量，对分词后的文档集合建立倒排索引。当在线的查询到来时，也进行分词，从倒排索引中查出所有符合要求的文档候选，并对其中的每个候选评价其与查询的余弦距离，按距离由小到大进行排序。这样的一个基本框架也适用于广告这一大规摸数据挖掘问题，也是图9-2的基本原理。

虽然VSM不是实际系统中对检索候选进行排序的常见方法，不过要提醒大家注意，这是一种简单、无需训练的基线方法。因此，在探索各种数据驱动的精细模型时，要先将它们与VSM方法做比较。