郭治焱

郭治焱

我要成为一名优秀的算法工程师！

Ranking Relevance in Yahoo Search

6 minute read

Published:

来自 Yahoo 搜索的一篇论文, KDD’16 的 bset paper.

论文基本信息:

  • 论文地址：https://dl.acm.org/doi/pdf/10.1145/2939672.2939677

  • 来源：KDD, 2016

  • 关键词：learning to rank, query rewriting, semantic matching

    该论文由雅虎搜索提出, 还获得了那年 KDD 的 Best Paper. 相关性 (relevance) 是搜索引擎里的一个核心问题, 但在现代的搜索引擎里 relevance 并不只是简单的文本匹配. 这篇论文对 Yahoo 搜索里的相关性解决方案给出了一个概览, 主要分成三部分: ranking functions, semantic matching features 和 query rewriting.

1. Motivation

早期搜索引擎主要是通过文本匹配来计算 relevanc, 如 BM25, 概率模型, 向量空间模型等, 也有一些工作将用户行为用于计算相关性, 如用户的点击数据. relevance 真的就只是文本匹配和点击模型那么简单吗? 一些挑战:

  • Semantic gap. query 与 doc 之间的语义差距. query 的语言表达通常与 doc 的表达是不一样的, 虽然表达不一样但却可以是相关的, 如果直接进行文本匹配效果则可能不理想. 其实这也是近年来深度学习在 NLP 领域大放光彩的原因 — 能够挖掘文本之间深层次的语义关系;
  • Long tail distribution. query 是符合长尾分布的 (万物皆长尾), 大部分的 query 出现的频率都很低;
  • 用户通常将搜索引擎当成通用的问答系统, 因此 query 通常都是自然语言的形式, 在进行搜索前需要理解 query 真正想要查询的是什么. 比如最经典的例子, apple;

当然, 以上只是一些比较大的问题, relevance 还需要考虑时间和空间, 即查询的时效性和与用户当前所处的位置有关. 比如在手机上搜索周围的超时.

这篇论文针对以上围绕 relevance 问题, 分享了 Yahoo 搜索在实践中的经验.

2. Overview of Architecture

Yahoo 搜索通过读个服务器并行地为每个 query 服务. 整个文档集被切分成很多个切片 (shard). 从输入一个 query 到返回结果集可以分成两个阶段. 在第一个阶段叫召回. 在每个切片中通过倒排索引找到与 query 相关的文档, 再使用一个简单的打分函数对文档进行打分作为文档的排序依据, 排序后选取一些 top 结果返回. 当然这还没有结束, 汇集多个 shard 的结果后还可以继续进行排序, 但由于候选集大大减小, 此时可以使用更复杂的特征和模型对文档进行排序, 这就是第二回合. 其实就是: 召回 $\Longrightarrow$ 粗排 $\Longrightarrow$ 精排.

3. Ranking Features

这一节介绍了在搜索中常用到的一些特征.

  • Web graph. 基于文档之间的链接关系, 获得文档的质量和流行度, 如 PageRank;
  • Document statistics. 文档的一些统计特征, 如文档的长度, 包含的不同领域的词的数量;
  • Document classifier. 对文档进行分类的一些特征, 如其所属的领域, 话题, 质量等;
  • Query Features. 用于刻画 query 的类型, 如长度, query 出现的频率, 点击率等;
  • Text match. 基本的文本匹配特征, 如根据文本的不同部分 (标题, 摘要, 正文等) 计算出来的相关性. 这种特征可以用 BM25 及其变体来计算;
  • Topical matching. 除了词层级的相似性 / 匹配程度, 还可以计算话题粒度的匹配程度;
  • Click. 这类特征主要通过用户的反馈数据得到, 如 query 与 doc 之间的点击率, 停留时间等;
  • Time. 对于一些时间敏感的 query, 文档的新鲜度是很重要的, 例如页面第一次出现的时间.

4. Evaluation of Search Relevance

这里就简单介绍了一下 DCG.

5. Core Ranking

在搜索中, 通常将排序任务转化为分类任务, 例如 pair-wise 形式的 ltr 模型中, 通常转化为文档对儿之间的偏序关系的分类. 当然也有其他的转化形式, 例如将 query 与 doc 之间的相关性分为两类: Perfect, Excellent, Good 作为 +1, Fair, Bad 作为 -1. 这种方式能够刻画相关与不相关文档之间的分界, 即能够区分出相关和不相关, 但是这种形式有一个问题: 不能对相关文档进行较好的排序. 其实也可以理解, 因为直接将 Perfect, Excellent, Good 作为 +1, 相当于忽略了这几种不同相关等级的文档之间的差异, 也就不能对这几类文档进行很好的排序. 这个问题在搜索中是很严重的, 可能用户在浏览前几个结果后没有找到合适的结果就不会继续浏览了. 论文将搜索的排序任务转化为上述的二分类任务, 并引入到 GBDT 模型中, 但是做了一定的改进.

对于二分类任务常用的损失函数是交叉熵损失, 但是如果正样本为 +1, 负样本为 -1, 损失函数的形式略有不同, 此时损失函数称为 Logistic Loss:

\[L(y, F) = log(1 + e^{- y F}),\:\: y \in \{+1, -1\}\]

其中 $F$ 是模型的预测结果. 该损失对 $F$ 的负一阶梯度为:

\[-g_m(x_i) = -[ \frac{\partial{L(y_i, F(x_i))}}{\partial F(x_i)} ]_{F(x) = F_{m-1}(x)}\]

其中 $F_{m-1}$ 表示前 $m$ 轮学习到的模型. 为了解决上述的问题, 文中引入了 gradient scale, 即对不同类别的样本赋予不同的权重, 即: $-g_m(x_i) \times scale(label)$. 例如, scale(Perfect) = 3, scale(Excellent) = 2, scale(Good) = 1. 其实就等价于为不同样本赋予不同的权重. 文中将之称为 LogisticRank.

关于 logistics loss 的参考:

6. Contextual Reranking

在 Core Ranking 阶段, 可能只考虑了 query 和 doc 之间的特征, 而忽略了针对同一个 query 的候选集的上下文特征. 在 Core Ranking 后, 候选集已经缩小到几十个文档了, 这个时候可以进行 reranking 了. 文中从实践的角度提出了几种 contextual 特征:

  • Rank. 根据某个特征的取值对文档进行排序, 将序数值作为特征;
  • Mean. 计算某个特征的均值;
  • Variance. 计算某个特征的方差;
  • Normalized Feature. 利用上述计算的均值与方差对特征就像规范化;
  • Topic model feature. 利用候选集计算一个话题分布向量, 再与每一个结果计算其与话题向量的相似性.

注意, 以上的计算都是在 reranking 的候选集上计算的.

7. Semantic Matching Features

之前提到的 contextual feature 有一些缺陷: 对于处于短尾位置的 query, 用户的行为数据并没有很大帮助, 因为数据太稀疏且噪声较大 (一方面, 稀疏就会导致噪声大). 与 tail query 相关的文档通常都都缺少 anchor text (比如 url 所对应的文本). 且 query 和 doc 在用词, 语言表达风格上的差距都会增大文本匹配的难度. 文中针对这个问题提出了三种特征: click similarity, translated text matching, deep semantic matching.

7.1. click similarity

既然叫 click similarity, 那肯定是要利用点击日志的. 文中根据点击日志中的数据构建一个二部图, 节点是 query / doc, 边由点击关系构建, 边的权重来自点击次数, 如 click graph 所示. 在这个点击图上, 每个结点由一个向量来表示, 经过多轮的信息传播, 获得 query 和 doc 的向量表示, 然后计算 query 与 doc 之间的相似性作为 click similarity 特征加入到排序模型中. 以上便是 click similarity 的核心思想, 细节如下.

An example of click-through bipartite graph

上述实现两个实现的重点: 结点的向量表示和信息传播过程. 先来看看向量表示. 由于 query 和 doc 都是文本, 一个朴素的想法就是用一个很长的向量来表示一个结点, 向量中的每一位对应一个词, 取值对应该词在节点中出现的次数. 但是这样有一个问题: query 和 doc 的词汇表是不匹配的, 二者的分布不太一致. 文中的做法是只用 query 来构建词汇表, doc 则使用该词汇表来表示. query 可以直接根据其自身的词来构建向量 (构建方式就是上述的朴素做法), 那 doc 怎么构建呢? 文中的做法: 看 doc 与哪些 query 有点击关系, 从这些 query 中抽取词作为 doc 的表示. 好, 下一个问题, 如何进行信息传播? 每一轮的传播分为两个阶段, 先聚合与 doc 相关的 query 的向量来更新 doc 的向量, 再聚合与 query 相关的 doc 的向量来更新 query 的向量. 通过信息传播, query 的信息逐渐丰富, 即与该 query 相关的词的位置也会变成非零值. 聚合的过程还是比较简单的, 文中的做法是邻居信息的加权求和与 $l_2$ 规范化. 其实在结点表征发展了几年之后, 可以有更好的选择, 如早期的 node2vec, deepwalk 到现在的 GNN. 关于结点的向量表示, 文中提到了一个实践中的做法: 存储时通常是以稀疏矩阵的形式存储结点的向量, 但此时非零元素还是占比很大, 因此文中按照词的权重对此进行排序, 只保留向量中 top $K$ 个词的值. 因此计算时相等于只考虑了同时出现在 query 和 doc 中的 top $K$ 个词.

这里有个小问题: query 和 doc 的长度一般相差很大, 不会影响相似性的计算吗? 自问自答一下: 由于信息传播的存在, 短 query 的表示被丰富了!

7.2. translated text matching

注意到新来的 query / doc 是不会出现在点击日志中的. 为了减小 query 和 doc 之间词汇表的差距, 文中利用机器翻译将 query 翻译成 doc 的 title 或者反之. 如 Translated Text Matching 所示, 给定一个 query, 利用统计机器学习模型将 query 翻译成 $k$ 个候选的 query, 计算 doc 的 title 与这 $k$ 个 query 的相似性分数 ${s_1, s_2, …, s_k}$, 在这 $k$ 个相似性分数的基础上衍生出一些特征, 如 max, mean 等.

Translated Text Matching (TTM) feature

7.3. deep semantic matching

以上的两种特征主要解决的是处于长尾分布中后部分的 query: click similarity 通过点击图对信息进行了平滑并可以抵抗一部分噪声, TTM 利用 query 重写减小了尾部 query 的稀疏问题. 但是以上两种方法都是在词的层级缓解词汇表的 gap 和 尾部 query 的稀疏问题, deep semantic matching 通过挖掘 query 与 doc 之间深层次的语义匹配信息来构建特征. 文中利用 DSSM 模型来获得 query 和 doc 的向量, 将二者的余弦相似性作为一个特征加入到排序模型中. query 和 doc 表征的获得可以用以往的点击数据进行训练来获得. 在实践中, 每次只需要获得 query 的表征, 再与保存好的 doc 表征做内积即可.

8. Query Rewriting

虽然上述步骤能缓解 query 和 doc 之间的 gap, 但是在实践中, 在 query-doc 进入排序函数之前, 是要经过一系列处理的: 过滤, 预选等. 例如只有包含 query 中所有词的 doc 才能通过预选阶段. 这个问题通常出现在召回阶段. Query rewriting (QRW): 对当前的 query 进行改写, 生成与 $q$ 相关的 query 作为原 query 的补充. 文中将 QRW 作为一个机器翻译的问题, 将用户的 query 空间翻译到 doc 的 title 空间. 文中给出的具体做法: 利用之前提到的点击图来构造训练样本来学习一个基于短语的翻译模型. 对于一个查询 $q$, 从翻译后的 query 候选集中选择最相似的作为 $q$ 的重写后的查询 $q_w$, 文中选择 $q_w$ 的方式: 计算 $q, q_c$ 之间多个特征函数的组合来对候选集打分, 选择最高的作为 $q_w$. 即:

\[q_w = \mathop{arg\ max}_{q_c} \sum_i^m \lambda_i h_i(q_c, q)\]

其中 $h_i$ 就是特征函数, 衡量的是 $q_c, q$ 之间的一个分数, 具体的定义视情况而定, 文中给出了三种特征函数: $q$ 的特征函数, $q_c$ 的特征函数, $q, q_c$ 之间的特征函数. $\lambda_i$ 是特征函数的重要性, 可以手动设定也可以通过学习得到.

得到 $q_w$ 后怎么使用呢? 文中的方法: 分别使用 $q, q_w$ 抽取出 top $N$ 个 doc, 并利用前述的 Core Ranking 对 doc 进行打分, 保留在 $q, q_w$ 中都出现了的 doc, 并将其得分置为较高的值 (注意打分时是 query-doc 作为一个 pair 进行打分的, 因此交集的那些 doc 会有两个得分). 融合之后的结果作为 $q$ 的抽取结果.

9. Recency-sensitive ranking

对一些 query 而言, 时效性是很重要的. 文中为 doc 定义了其新鲜度: very fresh(VF), fresh(F), slightly outdated(SO), stale(S), non-time-sensitive(NT). 文中给出了一个 doc 的相关性与新鲜度的关系 — 加上新鲜度后 doc 的相关性如何变化, 基本原则就是如果其新鲜度为 VF, F 时其相关性等级不变, 或者其该 doc 是时效无关的, 其相关性等级也不变. 当其新鲜度为 SO, S 时则其相关度等级下降一个等级. 简单来讲就是: 对于时效相关的, 若其比较新鲜, 则维持或提高其相关度, 若不过时了则降低相关度, 对于时效无关的, 则不改变其相关度. 为了考虑新鲜度的影响, 文中的做法是: 通过一个时间敏感的分类器对 doc 进行二分类, 若其是时间敏感的则在相关性分数的基础上加上新鲜度分数, 否则只使用相关性分数.

10. Location-Sensitive Ranking

除了时间, 有时候空间也是很重要的, 例如在手机端查询 “饭店”, 这个时候用户的意图可能是搜索附近的 “饭店”. 因此, 在给定 query 对 doc 进行排序时, 还希望能够考虑位置信息. 文中将位置敏感的 query 分为两种: 显式位置的 query , 如 “饭店 岳麓山”, 隐式位置的 query, 如 “饭店”. 如何提高位置敏感的 query 的排序过程呢? 一个朴素的做法是将 query-doc 之间的距离作为一个特征加入到排序模型中. 但是之前提到的特征可能会主导模型的排序结果, 因此文中提出了一个位置增强的排序模型来提升模型对位置敏感的 query 的排序能力:

\[f(x) = f_b(x) + w \frac{1}{1 + e^{\alpha f_b (x) + \beta} } \hat{d}(\text{query}, \text{doc})\]

其中 $\hat{d}(\text{query}, \text{doc}) \in [0, 1]$ 表示归一化后的 query 与 doc 之间的远近, 距离越近该值越大. 该值的计算方式: 抽取 query 和 doc 的位置信息构成位置向量来计算. query 的位置信息通过 query 中的显示位置或者用户的位置来得到, doc 的位置信息通过点击图中与之相连的 query 的位置信息和其本身的位置信息来得到. 其中 $\alpha, \beta$ 是学习得到的参数.

11. Conclusion

这篇文章虽然只有十页, 但是内容却异常的丰富, 一个是其中没有过多的实验及分析, 讲述的内容也大多是 Yahoo 搜索在实践中探索的一些经验. 总的来说, 这篇论文围绕 query 和 doc 的相关性展开的, 如何构建一个更好的排序模型. 论文从相关性的基础讲起, 到如何解决 query 的长尾分布, 再到构建 query-doc 之间的深层次的匹配, 再到通过 query 重写来解决尾部 query 数据稀疏的问题, 最后再解决时间和位置敏感的 query.

其实通篇看下来, 主要是为了解决两个问题: 1) 中部和尾部 query 的排序问题; 2) 时间和空间敏感的 query 的排序问题. 关于排序模型介绍的还是比较少的, 对于上述两个问题更多解决方法还是构造特征以及将时间和空间的相关性加在基础相关性上.

You May Also Enjoy

Addictive & Multiplicative in NN

less than 1 minute read

Published:

特征交叉是特征工程中的重要环节，在以表格型（或结构化）数据为输入的建模中起到了很关键的作用。

Year’s moments

less than 1 minute read

Published:

用照片记录 2023 的一些时刻

庐陵乡土“订婚”文化简记

less than 1 minute read

Published:

成长于乡村的我，对农村及其承载的传统文化一直很好奇。很多时候也和别人说过，如果能够不受限的选择专业，或许我会选择社科类的专业，研究中国各地的乡土文化（想起了高中时看的《乡土中国》），希望能更详细地了解并记录各地地文化，追溯它们地起源和演变，并以更好的方式，让更多的人能够见证，以纪念正在逐步凋零的中国乡村。