文章介绍了雅虎在优化搜索引擎排序的部分工作，主要介绍了排序函数(ranking function), 语义相似特征(semantic matching features), 改写(query rewriting)。给出了检索结果同时满足时效性和地理位置相关度的解决方案。

背景介绍，搜索引擎中query检索的主要问题：

1. query和document构词不太一样。例如query中为”how much tesla”，而文档中更多的是”price of tesla”。
2. 低频长尾网页的用户点击不可用，click modeling失效
3. 用户的一些提问表达或者口语化表达，如何进行意图理解
4. 时间维度的满足，例如”the safest cat”，返回”the safest cat is the 1998 toyota celica”可能不满足用户的需求。
5. 空间维度的满足，当用户搜索”restaurant”和”walmart”的时候，可能需要从搜索引擎中得到结果，按地理位置就近满足

文章对于上述问题展开了叙述

1. 介绍了雅虎最work的排序函数，提出线下评估结果和在线搜索体验的优化点。
2. 探索如何将用户的点击信息从高频query转移到低频query。
3. 通过改写提高相关性，尤其是低频query的相关性。
4. 提出了时间空间(LBS)相关性的解决方案

搜索引擎基础知识：

1. 搜索引擎的整体架构：
   采用分治思路，文档通过url计算md5，根据md5进行分布式存储，每个机器视为一个节点，可以并行工作。当发生query查询时，第一轮粗排序，先在每个节点中找到所有匹配该query的文档，这个过程完成文档召回，这里会对文档进行一个简单的打分和去重，返回指定数目的候选文档，同时对这些选定文档进行query相关特征抽取。进入第二轮精排序使用一个核心排序函数(Core Ranking Function)打分，得到最佳的文档。

2. 所用到的特征如下：

   1. Web graph, 通过www的链接情况进行文档质量打分，这里有大名鼎鼎的pagerank
   2. Document statistics，一些文档相关的基础统计特征，如词频，词的数目等等
   3. Document classifier，会用到一系列分类器，判断是否作弊文档，是否色情，文档语言，主题，质量和页面类型。
   4. Query features， 词的数目，query频次和其中不同词的词频
   5. Text match， 包括词之间的匹配，例如(query-doc.title), (query-doc.url), (query, doc.keywords), (query, doc.abstract)等等。这些特征可以进行组合形成新的特征，例如BM25. 以此判断文档和query的匹配程度
   6. Topical matching， 语义层面的匹配。
   7. Click， 利用用户的点击信息，预测包括prob of click, first click, last click, long dwell time click or only click。
   8. Time， 对于强时效性需求的query，文档的时效性要求很高。

3. 排序结果的评价指标–搜索相关性
   逐条对搜索结果进行分等级的打分, 分数有五档{Perfect: 5分, Excellent: 4分, Good: 3分, Fair: 2分, Bad: 1分}，假设文档在排序后的结果列表中位置为[1,N]，用如下DCG(Discounted Cumulative Gain)作为衡量指标：

   $$DC{G_N} = \sum\limits_{i = 1}^N {{{{G_i}} \over {{{\log }_2}\left( {i + 1} \right)}}} $$

   按：为了使得不同query下的结果容易比较，对DCG进行归一化得到$NDCG = {{DCG} \over {\max \_DCG}}$。作者为了评估时间相关性，引入时间的评价指标DCR和二者的综合指标RDDCG，后续内容会进一步介绍。
   下面介绍下测试集，从一年log里面随机抽取出2000query，按query的频次又可以细分为高频，中频，低频三档。中频query基本上一年就几次点击，低频的话平均一年不到一次用户点击，用户点击信息对低频query基本无效。文章主要对中低频query相关性进行优化。

用于排序的机器学习模型–gradient boosting decision trees

GBDT作为第二轮排序的打分模型，为了减少bad/fair url，作者选用(logistic loss)损失函数。如果将五档打分中的{perfect, excellent, good}视为正例(positive, +1)，{fair, bad}视为负例(negative, -1)，得到的损失函数为：
$$L\left( {y,F} \right) = \log \left( {1 + \exp \left( { - yF} \right)} \right),y \in \left\{ {1, - 1} \right\}$$
在训练阶段第$m$轮的学习目标pseudo-residuals，即梯度为：$$ - {g_m}\left( {{x_i}} \right) = - {\left[ {{{\partial L\left( {{y_i},F\left( {{x_i}} \right)} \right)} \over {\partial F\left( {{x_i}} \right)}}} \right]_{F\left( x \right) = {F_{m - 1}}\left( x \right)}} = {{yi} \over {1 + \exp \left( {{y_i}{F_{m - 1}}\left( {{x_i}} \right)} \right)}}$$
Logistic loss在2分类问题中，能有效降低不相关url在排序结果中头部占比，该loss除了用在分类，还能提供较为可靠的排序。和hinge loss不同，它能将positive/negative往positive/negative两个方向拉开，这样的话，如果一个url的相关性是perfect，那么它会距离决策平面远一些（按：放到下一篇进一步探讨）。
当然仅有正负二类对于排序而言是不足的，为了刻画{perfec, excellent,good}三种不同的相关性label，作者引入了梯度scale因子，对于不同的label给予不同的梯度scale因子{例如：perfect:3, excellent:2, good:1}。经过调整以后，第$m$轮的学习目标pseudo-residuals为：
$$pseudo - residuals\left( x \right) = - {g_m}\left( {{x_i}} \right) \times scale\left( {label} \right)$$
其中：scale(perfect)=3，scale(excellent)=2，scale(good | fair | bad )= 1.这种方法等价于给不同的label样本进行加权，影响每一轮树的构造。scale因子在传统GBDT训练过程中(步骤2.1)发生作用。作者将这种方法命名为LogisticRank。附上传统GBDT训练伪代码(wikipedia)：
实验设定：
参照模型1 GBrank[34]：loss为pointwise+pairwise。参照模型2 LambdaMart[4]

作者观察实验中LogisticRank主要收益在排除不相关的结果。实验环境和线上真实环境不一样，意味着线下有这么大提升，线上的提升幅度可能没那么乐观。下面的实验中模型固定为LogistcalRank，在这个基础上展开其他方面的探索。

基于上下文的重排序(Contextual Reranking)

我们前面介绍过检索的两层结构，第一层粗排序，第二层精排序。这两层所用到的特征为的匹配特征，url表示文档。同一个query召回的其他url这部分上下文信息没有利用到。接下来，介绍基于上下文的重排序过程。
这个过程中的候选是来自精排序的top-N结果(例如N=30)。主要用到的特征有：

1. 位置：url在精排序中的位置
2. 均值：精排序中各个特征的均值
3. 方差：精排序中各个特征的方差
4. 归一化特征：通过标准差和均值归一化后的特征
5. 主题模型特征：将top30url的主题分布累加起来作为query的topic分布，单独计算各url与query的topic分布的相似度
   作者解释为什么使用第二轮的排序位置而不是模型打分作为重排序的输入，主要是实践结论，尽管模型打分包含更完整的信息，但是这个值很容易发生波动。（按：原文Though the core-ranking phase score is more informative than the rank, its value can drift as the index refreshes, degrading third phase performance索引这里猜测是建库的索引，只是query-url应该不受影响，费解）。实验结果显示在table2，在部署的时候，精排序的模型打分可以并行进行，但重排序只能在一个机器节点中完成，Yahoo在重排序中用了30-50组原始特征。

语义匹配特征

这部分特征主要解决长尾query中缺少用户行为信息，url文本信息例如anchor文本缺失等，以及文本匹配中长尾query表达和url表达不同。三类语义匹配特征：点击相似(click similarity)、翻译文本匹配度(translated text matching)、深层语义匹配(deep semantic matching)。
点击特征(click similarity)
作者使用query的词表(vocabulary)将query, document表示在同一个向量空间中。query和document之间可以通过点击行为建一个二部图。边上的点击次数越多，表示文档和query越接近。
构成这个二部图的出发点，在这个向量空间中，document连接着相同的query越多，越相似。对query也一样，连接的相同的document越多，意图也越发相近。意味着可以从document向量中将词义转赋给相连的query，那么因为document产生相互联系的query可以表出在向量空间中的相似度。
二部图记为$G$，图中的点$V = D \cup Q$ $D$表示document，$Q$表示query。$C$表示邻接矩阵。$Q{V^n}$是一个$\left| Q \right| \times V$矩阵，其中第$i$列$QV_i^n$表示在第$n$轮迭代query向量$q_i$。同样的，$DV$是$\left| D \right| \times V$矩阵，每一行都是一个document向量。
每个向量都进行了归一化，初始的query矩阵为$Q{V^0}$，在第$n$轮迭代中，$DV_i^n$更新公式为：
$$DV_i^n = {1 \over {{{\left\| {\sum\nolimits_{i = 1}^{\left| Q \right|} {{C_{ij}} \cdot QV_i^n} } \right\|}_2}}}\sum\nolimits_{i = 1}^{\left| Q \right|} {{C_{i,j}} \cdot QV_i^n} $$
再通过累加与query相连的document向量进行query向量的更新：
$$QV_i^{n + 1} = {1 \over {{{\left\| {\sum\nolimits_{j = 1}^{\left| D \right|} {{C_{ij}} \cdot DV_j^n} } \right\|}_2}}}\sum\nolimits_{j = 1}^{\left| D \right|} {{C_{i,j}} \cdot DV_j^n} $$
在这个迭代的过程中，query得到新的terms同时还能得到权重。document也从query中得到更丰富的terms。如此对query和document同步进行了语义表达上的补全。实践中，因为为零的项太多，对权重使用稀疏表达方式存储。由于少数的词(term)拥有最大量的权重，其他的terms都很小，我们在每轮迭代中保留权重top-K的词(terms)。这个剪枝优化加速了收敛。
评估：得到query和document向量表达之后，通过点击可以得到其相似度，记为特征CS。在精排序中实验效果如下表：

可以看到在torso和tail部分提升比较明显。在所有特征重要性中，CS特征排第一位。实践中对query/document向量按月进行例行更新。
翻译文本匹配度(TTM)
CS特征无法用在未出现在点击日志的query和document之间。统计机器翻译将query翻译到document，通过机器翻译带来一系列特征，称为”Translated Text Matching(TTM)”.
使用query和点击title训一个翻译模型，对于任一query我们通过翻译模型得到$\left\{ {q_w^1,...,q_w^k} \right\}$这个向量空间为document标题的，给定document $d$，我们通过计算 $d$的标题和$\left\{ {q_w^1,...,q_w^k} \right\}$中每一个query的相似度得到$\left\{ {{s_1},...,{s_k}} \right\}$。最终的相似度打分函数为$F\left( {\left\{ {{s_1},...,{s_k}} \right\}} \right)$。 $F$表示一组函数，例如：max, average, median等等操作。 特征生成如下图。
实验中设定$k=10$取前10个改写后的query，尝试了多种特征组合，最成功的特征为 EXT_Q_TLM_1改写后query与document标题的最大相似度作为特征。AGG_Q_TLM集合相似度，使用标题LM改写后的query与给定document得到10个使用queryLM改写后的标题计算相似度。实验效果如上面的表中第二行。在特征重要性评估中，EXT_Q_TLM_1，AGG_Q_TLM分列第7和第10.具体部署中有些工程优化，下文介绍改写模型的时候一并描述。
深层语意匹配
CS特征和TTM部分解决了中长尾query的文本和用户行为信息不足，CS用来平滑点击信息并去除噪音点击，而TTM是query改写的一个应用。这些方法停留在词级别。我们需要进行语意级别的匹配，这里用DSSM[13]进行学习。(按：DSSM可以看高剑锋老师的报告，在度学堂有)，记query集合$Q$和其候选document集合${D_ \pm }$。得到query和document的向量表达之后用如下softmax函数计算似然：
$$L\left( {{D_ + }|Q} \right) = {{\exp \left( { - \cos \left( {{V_Q},{V_{D + }}} \right)} \right)} \over {\sum\nolimits_{D \pm } {\exp \left( { - \cos \left( {{V_Q},{V_{D \pm }}} \right)} \right)} }}$$
训练样本则通过在有序结果列表中以10-窗口滑动的方式产生，第1个为正例，后续9个样本为负例，最后得到30亿query-10-document样本。input为 query, document的标题和主域(例如：wiki, weather, imdb等)。模型使用tri-letter词表，每一个样本表达为tri-letter的组合，具体细节看DSSM的参考文献[13]（按：模型图中对中间两层做了抽象，实际上并非公用两个隐含层，也并非同时输入正负例）。

评估：上表中，DSM带来1.69%的DCG5收益。在高中低频query中都有收益。这维特征在全部特征中重要性处于第7位。在具体线上应用时，可以将document的向量表示先计算并存储在服务器中。当查询发生时，实时计算query的向量，计算内积作为GBDT模型输入。

query改写

由于query和document的行文风格不同，例如用户可能是输入”how much tesla”，而document对其满足较好的内容为”price of tesla”。改写的目的是为了扩大召回。Query改写(Query Rewrite, QRW)可以看成一种机器翻译(MT)问题，分为学习和解码两个阶段。
学习阶段：
改写的语料不太适合人工标注，其一，翻译语料需要大量的训练数据。其二，人工选择候选query的效率较低。这里采用点击行为收集语料，用户query和用户点击document的标题title。在query-title中，进行对齐、对齐片段抽取、片段打分。title经常大于query的长度，这里引入null空串，过滤错误的对齐。
解码阶段：
给定一个原始query，记为$q$，可能有不同的切分方式，召回不同的片段，可以轻松构成上百个候选。解码阶段需要找到最合适的候选$q_w$。定义每个候选$q_c$通过特征的线性组合得到。那么解码问题可以表述如下：
$${q_w} = \mathop {\arg \max }\limits_{{q_c}} \sum\nolimits_{i = 1}^m {{\lambda _i}{h_i}\left( {{q_c},q} \right)} $$
其中${{h_i}\left( {{q_c},q} \right)}$，为第$i$个特征函数，$\lambda_i$是权重，通过loss函数学习得到。
用到的特征函数有：

1. query feature functions: query $q$中词数目，停用词数目，语言模型打分，query频次，词的平均长度
2. rewrite query feature functions：改写后query $q_c$中词数目，停用词数目，语言模型打分，query频次，词的平均长度
3. pair feature functions：$h_{11}$：在query-url连接图中$q$和$q_c$的jaccard相似度。$h_{12}$原始query $q$与改写后$q_c$的频次的差、$h_{13}$二者词级别的cos相似度、不相同的词个数、相同词的个数、语言模型打分的差，停用词数目的差、平均词长度的差。
   实践中$h_{11}$、$h_{12}$、$h_{13}$是三个最有影响的特征。

改写的应用
假设我们有$q$和改写得到的$q_w$，各自召回top-N结果，进行归并，归并时遇到相同的url将保留打分高的分值。将最后的结果中选择top-N作为原始query的候选url返回。
实验效果下表，其中QRW是前述合并策略，QRW-RE表示将改写后query $q_c$用于发起新检索得到的结果。

线上优化
如何减少解码过程的时延，是部署改写模型的关键。给定query，在模型不变时，改写的候选和打分是一样的。为了线上部署，将1亿query的改写候选和打分存储在cache中。当发生miss情况时，仍会有较大延时。作者对候选词表进行剪枝，同时在解码的时候，使用beam search，对于少数特别慢的case直接舍弃。

组合实验

前面单独介绍很多特征，实践中经常有特征是有相关性的，效果不会简单线性累加，需要综合特征进行考察。下面是四个实验组
“base”：仅LogistcRank
“GBrank”：为传统的GBDT用于排序。
“base+feat”： LogistcRank+语意特征(CS, TTM, DSM)。
“base+all”： LogistcRank+语意特征(CS, TTM, DSM)+改写，

从效果上看，”base+feat”效果在DCG1、DCG3、DCG5三点上都优于”base”。语义匹配三个特征其综合效果高于各自单独的实验效果，证明这三种相互之间是有补充效果的。表为在query “how much tesla”下，”GBrank”VS”base+all”的结果对比图。

时效性满足排序

背景介绍的时候，提过时效性(recency)和空间位置(location)的满足。作者在这方面也做了探索。对于时效性的打分，定义了五个档级：”very fast(VF)”、”fresh(F)”、”slightly outdated”、”stale”、”non-time-sensitive”，引入了DCR（把DCG公式中的相关性指标换成时效性）和RDDCG（综合考虑DCG和DCR，具体解读如下表）

要进行时效性的排序，需要有这部分训练数据，在这份数据上，作者单独训练了一个时效性的打分函数（LogisticRank），记为${r_{fresh}}\left( x \right)$。此外引入时效性打分分类器的结果${c_{ts}}\left( x \right)$，新增的两个打分以如下方式结合：
$$f\left( x \right) = \left\{ {\matrix{ {{f_{relative}}\left( x \right) + {r_{fresh}}\left( x \right)\;\;if\;{c_{ts}}\left( x \right) > 0} \cr {{f_{relative}}\left( x \right)\;\;\;\;\;\;\;\;\;\;elsewise.} \cr } } \right.$$
当 ${c_{ts}}\left( x \right)$显示query是有时效性需求的时候才加上时效性打分函数的结果，以最后的分数进行排序。
实验是在500个有时效性需求的query上进行的，第一个表是在(DCG5、DCR5、RDDCG5)三个指标上的打分。后一个表是关于query “holly bobo”的结果对比，(按：这是一个杀人新闻，非名人的话，用于说明时效性满足是恰当的)。

空间位置满足排序

空间位置满足排序的目的是为了解决用户在搜索”宾馆”等query的时候，背后暗含的地理位置近优先的需求。为了计算空间位置相关性，需要在query-document两端进行地理位置信息抽取。首先从用户的query中抽取出显示地址，或者用用户所在地址代替隐式地址。而网页的地址则可以通过query-url 点击图，进行抽取，给定一个url，从其连接的query中可以得到地址，通过query地址描述url的位置信息。此外还有从url中之间挖掘的位置地理信息。
和时效性满足区别在于作者设定如果有地理位置需求，且相关性好，才能对排序结果产生影响，这一要求会体现在loss函数上。引入$d\left( {QUERY,URL} \right)$描述query-url的地理位置匹配程度，归一化到[0, 1]区间，记为$\hat d\left( {QUERY,URL} \right)$（值越大，表示地理位置相关性越强）。（按：这个打分细节没描述，猜想如果query无位置信息则0，如果有，那么按地图POI可以计算实际距离，再进行归一化及反比例变换，使得打分$\hat d\left( {QUERY,URL} \right)$具有[0,1]且值越大，距离越近）。
$$f\left( x \right) = {f_{relative}}\left( x \right) + w{1 \over {1 + {e^{\alpha {f_{relative}}\left( x \right) + \beta }}}}\hat d\left( {QUERY,URL} \right)$$
PS.作者论，改进后的logistic函数根据$f_{relative}( x )$控制地理位置相关性打分。
参数$w$, $\alpha$, $\beta$训练得到，训练的目标为$$\min \sum\nolimits_{\left( {{p_i},{p_j}} \right) \in P} {\max {{\left( {0,\;1 - f\left( {{x_i}} \right) + f\left( {{x_j}} \right)} \right)}^2}} $$
pair-wise训练，其中$P = \left\{ {\left( {{p_i},{p_j}} \right)|\;{p_i} > {p_j}} \right\}$为一个query下的偏序关系的url-pair。${p_i} > {p_j}$表示给定query下${p_i}$比${p_j}$结果更好，使用随机梯度下降(SGD)可以解之。
（按，感觉这个打分的设计有点复杂，可以再考虑简化下）。
评估测试集为500有地理位置需求的query。新的排序函数提升DCG5达6.92%。作者在小流量实验中，线上收益CTR提升4.78%，可想效果确实显著。下表是地理位置满足的一例case，检索”cvs”时baseline与location boosting的不同结果展示：

总结：这些方法高效且接地气，不限于搜索引擎，也可以用在垂搜领域。

按：
1.gbrank中怎么加入pointwise信息，后续了解
2.丝路搜索中看holly bobo，百度对英文时效性query是否有进行类似的调整。也可能是时效性需求识别未召回。
3.百度在中文检索中进行的探索深度和复杂程度不局限于作者提的这些方法和特性，例如色情类query屏蔽（国际化搜索则称色情query满足）、图片需求类query、用户个性化等等。wise端的场景更加丰富和具有挑战。

原文及部分引文：

[0]Yin, Dawei, Hu, Yuening, Tang, Jiliang, et al. Ranking Relevance in Yahoo Search[C] ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016.
[4]C. J. C. Burges. From RankNet to LambdaRank to LambdaMART: An overview. Technical report, Microsoft Research, 2010.
[13]P.-S. Huang, X. He, J. Gao, L. Deng, A. Acero, and L. Heck. Learning deep structured semantic models for web search using clickthrough data. In CIKM ’13.
[34]K. Zhou, X. Li, and H. Zha. Collaborative ranking: Improving the
relevance for tail queries. In CIKM ’12.