Question

大量中小广告主参与的竞价广告市场中，复杂的定向条件对检索技术提出了新的要求。倒排索引是搜索引擎的关键技术，而广告的检索上也采用这样的框架。但是广告的检索问题也有一些自身的特点和需求，基本的倒排索引技术在广告检索中遇到了两个新问题。

（1）广告的定向条件组合可以看成是一个由与或关系连接的布尔表达式，这样的文档显然与搜索引擎面对的BoW文档不太一样，这里存在着有针对性的检索性能优化空间。

（2）在上下文关键词或和用户标签比较丰富时，广告检索中的查询可能相当长，甚至会由上百个关键词组成，这种情况下的检索也与搜索引擎中主要由 1～ 4个关键词组成的查询有很大区别。试想，如果将 100 个关键词同时输入搜索框中，返回的结果会是你想要的吗？

这些差异使得广告中使用的检索技术在基本的倒排索引之上有所发展，下面将具体讨论上面两个问题。

13.4.1 布尔表达式的检索

广告检索与普通搜索引擎检索的第一个不同是布尔表达式的检索问题。在受众定向的售卖方式下，一条广告文档不能再被看成是 BoW，而是应该被看成一些定向条件组合成的布尔表达式，如下面的几个例子。

a₁=（age∈{3}∩geo∈{北京}）∪（geo∈{广东}∩gender∈{男}）

a₂=（age∈{3}∩gender∈{女}）∪（geo /∈{北京，广东}）

a₃=（age∈{3}∩gender∈{男}∩geo /∈{广东}）∪（state∈{广东}∩gender∈{女}）

a₄=（age∈{3，4}）∪（geo∈{广东}∩gender∈{男}）

a₅=（state /∈{北京，广东}）∪（age∈{3，4}）

a₆=（state /∈{北京，广东}）∪（age∈{3}∩state∈{北京}）∪（state∈{广东}∩gender∈{男}）

a₇=（age∈{3}∩state∈{北京}）∪（state∈{广东}∩gender∈{女}）

这些例子用布尔表达式表示广告的定向人群，并且写成析取范式（Disjunctive Normal Form，DNF）的形式。在这样的表达形式中，先要解释以下两个概念。

（1）每个 DNF 都可以分解成一个或多个交集（conjunction）的并，如 a₁ 可以分解成j₁=（age∈{3}∩geo∈{北京}）和k₂=（geo∈{广东}∩gender∈{男}）这两个交集。

（2）每个交集又可以进一步分解为一个或多个赋值集（assignment）的交，以 j₁ 为例，可以分解为 age∈{3}和 geo∈{北京 }这样两个赋值集。为了后面算法描述方便，我们定义Assignment、Conjunction和DNF的数据结构如下。

布尔表达式检索的问题有两个特点，这两个特点是设计算法的重要依据。首先，当某次广告请求的定向标签满足某个 Conjunction 时，一定满足包含该 Conjunction 的所有广告，这说明只要对Conjunction建立倒排索引，并加上一层Conjunction→AD的辅助索引即可。其次，在 Conjunction 的倒排索引中，有一项直觉可以帮助我们减少计算：令 sizeof（query）表示广告请求中的定向标签个数，而sizeof（Conjunction）表示某Conjunction中的含有“∈”的Assignment数目，当sizeof（query）<sizeof（Conjunction）时，该Conjunction一定不满足该次请求。

根据上述两个重要特点，可以设计出为布尔表达式检索定制的算法。我们以参考文献[76]中的算法为例介绍这种思路。该算法维护一个两层的倒排索引，即上面所说的 Conjunction和AD两层索引，后一个索引按照“或”的关系进行检索，而前一个索引有不太一样的结构：在Conjunction的索引中，把每个Conjunction分解成一组（键，值）对，例如，将age∈{3，4}分解成age∈{3}和age∈{4}两个Term，这些Term即是倒排索引的键，而“∈”和“/∈”操作符放在倒排链表的具体元素上。利用上文所说的 Assignment个数的约束，我们可以做的优化是将这一倒排索引按照sizeof（Conjunction）分成若干部分，以提高检索效率。仍然以上文的一组广告为例，这组广告的DNF可以按如下的方式分解成一些Conjunctions：

a₁=j₁∪j₄ ，a₂=j₂∪j₆ ，a₃=j₃∪j₇ ，a₄=j₅∪j₄ ，a₅=j₆∪j₅ ，a₆=j₆∪j₁∪j₇ ，a₇=j₁∪j₇

其对应的倒排索引也可以很容易地写成下面的形式：

j₁→{a₁，a₆，a₇}，j₂→{a₂}，j₃→{a₃}，j₄→{a₁，a₄，a₇}，j₅→{a₄，a₅}，j₆→{a₂，a₅，a₇}，

j₇→{a₃ ，a₆}

可以注意到，所有Conjunction中最大的size为2，可以将倒排索引分成3部分，每部分中所有的Conjunction其size都一样，按照这样的准则，最终形成的Conjunction倒排索引应为下面的形式：

size=0:（geo，北京）→{（j₆ ，/∈）}，（geo，广东）→{（j₆ ，/∈）}，Z→{（j₆ ，∈）}

size=1:（age，3）→{（j₅ ，∈）}，（age，4）→{（j₅ ，∈）}

size=2:（age，3）→{（j₁ ，∈），（j₂ ，∈），（j₃ ，∈）}，（geo，北京）→{（j₁ ，∈）}，（gender，女）→{（j₂ ，∈），（j₇ ，∈）}，（gender，男）→{（j₃ ，∈），（j₄ ，∈）}，（geo，广东）→{（j₃ ，/∈），（j₄ ，∈），（j₇ ，∈）}

其中 size 为 0 的部分包含哪些所有只有“/∈”操作符的 Conjunction。为了保证给定一个Assignment，size为0的Conjunction至少出现在一个倒排表中，算法引入Z 为一个特殊的Term，并且将所有size为零的Conjunction都放在其倒排表中，并赋以一个“∈”操作符。

在第 10 章的标准倒排索引类基础上加以改进，将 DNF 索引类的代码列在下面，方便大家参考。在这段代码中，IndexDNF对应上面提到的DNF的倒排索引，而IndexConj对应于Conjunction的一组倒排索引，其中每一个倒排索引中所有的Conjunction都具有相同的size。

13.4.2 相关性检索

竞价广告与搜索的检索问题还有一点不同，有时，竞价广告系统需要处理很多个标签组成的查询。让我们考虑上下文定向的情形：当通过网页内容的关键词来匹配广告候选时，往往需要用十多个甚至几十个关键词去查询广告，再进行eCPM排序。在这一情形下，如果仍然采用一般搜索引擎对查询的处理办法，则会陷入两难的境地。如果假设各个关键词之间是“与”的关系，基本上不可能得到任何匹配的结果；如果假设各个关键词之间是“或”的关系，那么在检索阶段就会返回大量相关性很差的候选，给后续排序的效率带来很大的挑战。

同样地，当用户的兴趣标签较丰富时，也存在类似的挑战。简单地比较一下搜索与搜索重定向广告就可以理解为什么展示广告的查询信号会丰富很多：在搜索中，仅仅需要根据用户当前输入的关键词进行检索；而在搜索重定向广告中，虽然用的也是搜索信号，但是需要将用户一段时间内的搜索关键词全部考虑，显然这样的查询要长了很多。在此也可以看出，搜索广告完全可以采用一般的检索技术，但是展示广告需要有新的方案。

考察上面问题产生的原因会发现，在长查询的检索情形下，我们实际上希望的是查询与广告候选间的相似程度尽可能高，但任何一个关键词是否出现在文档中其实都不关键。这样以查询和文档间的相似程度为目标的检索问题称为相关性检索。

解决相关性检索的基本思路是在检索阶段就引入某种评价函数，并以此函数的评价结果决定返回哪些候选。评价函数的设计有两个要求：一是合理性，即与最终排序时使用的评价函数近似；二是高效性，即需要在检索阶段实现快速评价算法，否则就与在排序阶段对每个候选分别计算没有差别了。研究表明，当选用线性评价函数（变量为各标签或关键词）且各权重为正时，是可以构造出这样的快速检索算法的。假设线性评价函数的形式如下式所示：

其中F（a）和F（c）分别表示广告文档a和上下文特征c上不为零的特征集合，比如查询中的关键词，而v_t（a）表示t这一特征在a广告上的贡献值。常用的VSM模型不符合这一要求，但是如果不考虑余弦距离中的归一化分母，可以用这一线性函数在检索阶段做近似的预评估。这种情况下，α_t 即为关键词t在上下文中的TF-IDF，而v_t（a）即为t在某广告a中的TF-IDF。虽然α_t 在不同的查询中取值不同，但在同一次查询中是一组常数。

将线性函数评价过程加速的关键在于使用两个上界：一是某个关键词 t 在所有文档上贡献值的上界，记为u_t；二是某个文档中所有关键词的上界的和，这实际上是该文档对当前查询评价函数的上界，记为 U_a。巧妙地利用这两个上界可以在检索过程中排除掉大量不可能胜出的候选，从而达到快速评价的目的。这一方法即为Andrei Broder等人提出的WAND（Weak AND）算法^[15]，也是上下文定向广告和内容推荐产品中非常实用的快速检索算法，我们以此算法为例，介绍一下相关性检索的算法过程。

WAND的检索过程如图13-4所示，图中每个关键词（Term）带有一条倒排链，链表中的每一项是包含此关键词的文档ID，用阴影表示。WAND算法用到一个小顶的排序堆结构：该堆维护着到目前为止的 top-K 结果，当新的候选产生时，如果堆尚未装满或相关度大于堆顶文档的相关度，则采用堆排序的方法将其插入堆，否则就可以直接抛弃此候选。检索过程迭代地执行下面两个步骤。

（1）将各关键词对应的倒排链按照其最小的文档ID升序排列。

（2）按前面的升序依次访问各关键词t，并累加其对应的u_t至U ，直至U 大于堆顶。设此时到达第 n−1个关键词（图13-4中 n=3），如果此时第 0个关键词倒排链和第 n−1个关键词倒排链的最小文档 ID一致，则计算该文档准确的相关性，如果仍然大于堆顶，则该文档推入堆；如果最小文档ID不一致，说明该候选无胜出的可能，于是在前n个关键词倒排链中挑选一个，将链表头跳到第 n−1 个关键词倒排链的最小文档 ID，然后流程跳转至第1步。

图13-4 WAND相关性检索过程示意

读者可以自行验证，WAND算法的执行过程能够利用两个上界在检索过程中快速地排除大部分候选。此算法执行过程的伪代码如下。

这里讨论的相关性检索技术仅仅考虑了相关性评价函数为线性的情况。虽然这一条件严格限制了评价函数的适用范围，然而，如果考虑到广告的排序模型经常采用广义线性模型的建模方法的话，线性评价函数的适用范围就会大大扩展。我们采用后面提到的基于广义线性模型的CTR预测模型也可以套用此框架。