达观数据搜索引擎排序实践（下篇）

机器学习排序（Machine Learning to rank， 简称MLR）

机器学习排序系统框架

机器学习排序系统一般分为离线学习系统和在线预测排序系统。离线系统的设计需要靠特征的选择、训练集的标注、MLR方法的选定、确定损失函数、以最小化损失函数为目标进行优化，以获取排序模型的相关参数。在线预测排序系统将待预测结果输入到机器学习得到的排序模型，即可得到结果的相关性得分，进而依据相关性得分得到搜素结果的最终排序。

图4机器学习排序系统框架

排序模型的选择直接影响在线预测的效果。在类似电商时效性强的应用场景中，业务上经常需要根据商品库存、价格等变化及时调整排序结果，由于排序模型的高度复杂性，人工干预只能做局部小范围的调整，更多的还是要对模型进行实时的自动化更新。

对于这个问题，达观数据（www.datagrand.com）在实践中总结出了一个在线-近线-离线的三层系统架构，即Online-Nearline-Offline（在线-近线-离线）三层混合机制。离线系统负责day级全量训练数据的学习、近线系统负责hour级模型的学习与更新、在线系统负责minut级的准实时反馈数据的学习与模型的更新。

特征选取与特征工程

特征是算法、模型的养料之源。特征选择的好坏直接关系到算法训练学习出的模型的效果。与传统的文本分类不同，MLR输出的是给定query的文档集合的排序，不仅要考虑文档自身的特征，还要考虑query与文档关联关系的特征。综合来说，MLR需要考虑三个方面的特征：

1） 文档本身的静态特征，包括文档的文本特征，如带权重的词向量，文档不同域（主标题、段落标题、描述内容、锚文本、URL链接等）的TF、IDF、BM25和其他语言模型得分，也包括文档的质量分、网页文档的PageRank等重要性得分。关于文档的质量分，达观搜索根据不同的业务场景有不同的计算指标，比如电商相关的商品的质量分计算除了要考虑商品本身的文本与图片丰富度，更多的还要考虑商品的各种业务指标如销量变化、收藏、价格、库存、类别、上架时间、评论、商家信誉等级、是否作弊等，而媒体相关的文章的则需要考虑阅读数、转发数、赞数、收藏、评论、发文时间、主题类型等。

2） 文档和query关联的特征，比如query对应文档的TD-IDF score， BM25 score等。

3） query本身的特征，比如文本特征，带权重的词向量，query长度，query所述的分类或主题，query的BM25的sum/avg/min/max/median分数，query上个月的热度等。

在query与文档的特征工程中，除了从词法上分析，还需要从“被阐述”的词法所“真正想表达”的语义即概念上进行分析提取。比如一词多义，同义词和近义词，不同的场景下同一个词表达不同的意思，不同场景下不同的词也可能表达相同的意思。LSA（隐语义分析）是处理这类问题的著名技术，其主要思想是映射高维向量空间到低维的潜在语义空间或概念空间，也即进行降维。具体做法是将词项文档矩阵做奇异值分解（SVD）

C = U∑

其中:

C是以文档为行，词项terms为列的矩阵（假设M x N），元素为term的tf-idf值。C被分解成3个小矩阵相乘；

U的每一列表示一个主题，其中的每个非零元素表示一个主题与一篇文章的相关性，数值越大越相关；

V表示keyword与所有term的相关性；

∑ 表示文章主题和keyword之间的相关性。

MLR算法的选择

MLR一般来说有三类方法：单文档方法（Pointwise），文档对方法（Pairwise），文档列表方法（Listwise）。

Pointwise方法

Pointwise把文档当成单个的点分别进行计算，实际上把一个Ranking 问题转化成二值分类问题、回归问题或多值分类问题。Query与文档之间的相关度作为label，label一般划分为: {Perfect， Excellent， Good， Fair， Bad} 。

Pointwise方法主要包括：Pranking (NIPS 2002)， OAP-BPM (EMCL 2003)， Ranking with Large Margin Principles (NIPS 2002)， Constraint Ordinal Regression (ICML 2005)

Pointwise的不足之处：

Pointwise使用传统的分类，回归或者Ordinal Regression来对给定query下的单个文档的相关度进行建模，没有文档位置对排序结果的影响，而回归和分类的损失函数会尽量拟合所有的数据，算法为了整体损失最小，有可能把排在前面的文档的损失变得更大，或者把排在后面的文档的损失变得更小，从而导致排序难以取得良好的效果。

Pairwise方法

在Pairwise中query与文档对<di， dj>结合，假设在同一Query下，di的相关性大于dj，那么我们可以把 di-dj标记为+1，dj-di标记为 -1，从而可以把原问题转换为一个分类或回归问题。

Pairwise方法主要包括：Ranking SVM (ICANN 1999)， RankBoost (JMLR 2003)， LDM (SIGIR 2005)， RankNet (ICML 2005)， Frank (SIGIR 2007)， GBRank (SIGIR 2007)， QBRank (NIPS 2007)， MPRank (ICML 2007)， IRSVM (SIGIR 2006) 。

Pairwise的不足：

1） 文档较多时，pair的数目是平方级增长的，计算量太大；

2） Pair对不同级别之间的区分度一致对待，没有对排在前面的结果作更好的区分。对于搜索引擎而言，用户更倾向于点击前几页的结果；

3） 相关文档集大小带来模型的偏置。如果一个query下文档远多于另一query， 支持向量就会向该query偏置，导致分类器对后者区分不好。

Listwise方法

Listwise的输入是query对应的一个文档列表，计算每个query对应的文档列表的得分。

Listwise有一种基于文档排列的概率分布进行训练的方法，通过对训练实例的训练找到一个最优的打分函数f， 使得f对query的打分结果的概率分布与训练数据的实际排序尽可能相同。损失是按照训练数据的实际排序概率分布与模型输出的概率分布之间的KL距离来度量的。

Listwise算法主要包括：LambdaRank (NIPS 2006)， AdaRank (SIGIR 2007)， SVM-MAP (SIGIR 2007)， SoftRank (LR4IR 2007)， GPRank (LR4IR 2007)， CCA (SIGIR 2007)， RankCosine (IP&M 2007)， ListNet (ICML 2007)， ListMLE (ICML 2008)，p-ListMLE 。

相比于Pointwise和Pairwise方法，Listwise方法直接优化给定查询下整个文档集合的序列，所以比较好的解决了以上算法的缺陷。Listwise方法中的LambdaMART(是对RankNet和LambdaRank的改进)在Yahoo Learning to Rank Challenge表现出最好的性能。

达观数据（www.datagrand.com）在搜索排序中使用了一种position-aware ListMLE(p-ListMLE)的算法，ListMLE考虑了排序位置信息，但没有对不同位置的重要程度进行区分。达观数据（www.datagrand.com）搜索的实践显示同样的条件下p-ListMLE的搜索效果指标nDCG要优于ListMLE. （达观数据 桂洪冠 陈运文）

点击模型

我们在排序实践中还发现MLR无法充分利用用户对搜索结果的点击反馈。俗话说群众的眼睛是雪亮的，用户对不同位置的搜索结果的点击行为直接反应了搜索结果的好坏。我们根据用户的历史点击记录生成了点击模型，通过点击模型对MLR的结果再进行一次调整。

点击模型又称为点击调权，搜索引擎根据用户对搜索结果的点击，可以挖掘出哪些结果更符合查询的需求。点击模型基于如下基本假设：

1)用户的浏览顺序是从上至下的。

2)需求满足好的结果，整体点击率一定高。

3)同一个query下，用户点击的最后一个结果之后的结果，可以假设用户已经不会去查看了(一定程度上减弱了位置偏见)。

4)用户进行了翻页操作，或者有效的query变换，则可以认为前页的结果用户都浏览过，并且不太满意。

5)用户点击的结果，如果引发后继的转化行为（比如电商搜索中的加购物车），则更有可能是用户满意的结果。

点击模型日志：

图5 点击模型（日志收集）

达观数据（www.datagrand.com）搜索中MLR算法优化+点击模型对结果调权后搜索效果的显著提升。

图6 达观数据搜索上线前后的效果对比

搜索排序效果评估

搜索引擎的排序是一个复杂的过程，特征的选择、算法的变化、模型的更新都会导致排序结果的变化。那如何衡量一个排序结果的好坏呢？ MLR是用机器学习的方法来进行排序，所以评价MLR效果的指标就是评价排序的指标，主要包括一下几种：

1) WTA(Winners take all) 对于给定的查询q，如果模型返回的结果列表中，第一个文档是相关的，则WTA(q)=1，否则为0.

2) MRR(Mean Reciprocal Rank) 对于给定查询q，如果第一个相关的文档位置是R(q)，则MRR(q)=1/R(q)。

3) MAP(Mean Average Precision) 对于每个真实相关的文档d，考虑其在模型排序结果中的位置P(d)，统计该位置之前文档集合的分类准确率，取所有这些准确率的平均值。

4) NDCG(Normalized Discounted Cumulative Gain) 是一种综合考虑模型排序结果和真实序列之间关系的一种指标，也是最常用的衡量排序结果指标，详见Wikipedia。

评价指标的使用

使用评价指标主要有手工标注答案和自动化评估两种。手工标注方式既费时费力，又无法及时进行评估效果反馈。自动化评估方式对提高评估效率十分重要。最常用的自动评估方法是A/B testing系统。

A/B testing系统将用户的流量在算法模型A/B之间进行分配，即将通过用户的分组号(bucket id)将用户流量分别导入不同的算法分支，用户在不同算法分支的行为连同分组号被记录下来，后台分析系统分析这些行为数据可以生成一系列对比指标，通过这些指标可以直观的分析算法模型优劣。

总结

本文从搜索引擎排序的架构、检索模型、机器学习排序模型与算法到搜索效果评估，全面介绍了达观搜索引擎排序实践方面的一些经验。达观数据搜索团队长期致力于基于大数据的搜索算法优化，经过多年的积极探索，目前在开放搜索引擎的系统研发和效果提升方面已经积累了丰富的经验。随着DT时代的到来和深度学习兴起，达观数据（www.datagrand.com）技术团队将在基于大数据的深度挖掘方面不断探索和尝试以给用户带来更好的产品和服务。

作者

桂洪冠，达观数据（www.datagrand.com）联合创始人&技术副总裁，中国计算机学会（CCF）会员。曾服务于阿里、盛大、腾讯几家公司，任腾讯文学、盛大文学数据中心高级研究员、阿里搜索技术专家等职务，主要负责搜索与广告团队。