李金忠 刘关俊 闫春钢 蒋昌俊

随着互联网和云计算技术的迅猛发展以及网络用户规模的爆发式增长,互联网已经步入了“大数据”时代.中国互联网信息中心发布第39次中国互联网络发展状况统计报告指出,截至2016年12月底,我国网页数量为2360亿,网民规模达7.31亿,搜索引擎用户规模超过5.93亿.面对互联网上如此海量繁杂的网络大数据与千差万别的网络搜索用户,传统的信息检索模型、机器学习方法在搜索引擎系统中的应用面临着极大的挑战.如何从互联网上的海量数据中,准确、及时、高效地获取用户所需信息是信息检索研究的主要问题,其本质即是信息的排序问题.排序是信息检索和很多实际应用如搜索引擎和推荐系统等所面临的核心问题,排序模型在互联网搜索和推荐中起着关键作用,其排序性能的优劣直接影响互联网用户使用搜索引擎和推荐系统的体验.因此,针对排序技术的研究是基础且关键的研究问题之一.

传统的信息检索排序模型主要有相关性排序模型和重要性排序模型.相关性排序模型主要包括布尔模型、向量空间模型和概率检索模型(BM25和统计语言模型),重要性排序模型主要包括PageRank算法[1]、HITS算法[2]、TrustRank算法[3]、BrowseRank算法[4]和ClickRank算法[5]等网页排名算法模型.

这些传统的排序模型的构建过程一般通过人工依据经验去调整排序模型中所涉及到的一些参数,但这些经验参数不易调节且易产生过拟合;另一方面,尽管这些不同的排序模型大体上都使得排序效果得到了一定的性能提升,但如何将不同排序模型融合在一起以构建一个性能更优的统一排序模型,并不易于处理.同时,随着影响排序性能的排序特征的不断增加,排序特征已有成百上千种,传统的排序模型的构建方法已不再适于处理如此多维和复杂的排序特征.而机器学习方法具有能自动调整参数,融合多个模型的结果,通过规则化的方式避免过拟合等优点.在如此背景下,涌现了大量的研究者运用不同的机器学习技术去训练排序模型以解决信息检索中的排序问题,并由此产生了信息检索与机器学习交叉的一个热点研究领域—排序学习(Learning to rank).排序学习就是利用机器学习方法在排序学习数据集上进行训练,自动产生排序模型,从而解决排序问题.和传统排序模型相比,排序学习的优势在于对众多排序特征进行组合优化,对相应的大量参数自动进行学习,最终得到一个高效精准、更加优化的排序模型.

排序学习是信息检索和机器学习交叉的一个研究热点.近几年,SIGIR、WWW、WSDM、CIKM等国际顶级会议将Learning to rank作为一个主要的Session或Track,特别是在2012年的SIGIR大会上,最佳论文荣誉提名奖[6]和最佳学生论文奖[7]都颁给了Learning to rank方面的论文,SIGIR2015、CIKM2016、KDD2016和 WSDM2016等的最佳(学生)论文奖也颁给了Learning to rank方面的论文[8−11].2010年,Springer期刊Information retrieval以特刊形式在其上刊登了“Learning to rank for information retrieval”[12].同年,Yahoo举办了Yahoo!Learning to Rank Challenge[13]比赛.很多知名的搜索引擎公司、推荐系统和大型电子商务平台等在很大程度上依赖于排序学习方法为用户提供高质量的搜索和推荐结果.

对排序学习的研究方兴未艾,不仅具有重要的理论研究价值,也具有广阔的实际应用前景.尽管排序学习在学术界取得了大量的研究成果和在工业界取得了令人瞩目的成功,但在排序学习的研究领域中仍还有许多相关的问题有待更全面深入地探讨.鉴于此,本文详细分析了当前排序学习的研究进展,并重点对排序学习的发展趋势和有待深入研究的重难点进行了展望,以示抛砖引玉.

本文第1节描述了排序学习问题;第2节对排序学习方法进行了分类;第3节到第5节分别归纳了排序学习的数据集、方法应用和方法软件包.第6节展望了发展趋势;第7节对全文进行了总结.

1 排序学习问题描述

排序学习是利用机器学习方法在数据集上对大量的排序特征进行组合训练,自动学习参数,优化评价指标以产生排序模型.

图1展示了排序学习的一个典型框架,该框架涉及排序学习的三个重要方面—数据集、方法和评价指标.排序学习数据集主要包括训练集(Training set)和测试集(Test set),通常也包括验证集(Validation set).训练集用来训练排序模型,验证集用来选择排序模型(若没有验证集,则训练集也用来选择排序模型),而测试集则用来检验最终选择的排序模型的性能.排序学习数据集由若干维排序特征数据和若干等级的相关性标注数据构成.排序特征数据x描述了查询–文档对q,d〉的特征表示,如tf、idf、BM25、PageRank等特征值;相关性标注数据y描述了文档与对应查询的相关性程度,如两级标注(0和1)或多级标注(0、1、2、3、4等).相关性标注数据多采用人工判断给定(显式标注),也可利用点击数据等获得(隐式标注).排序学习方法从排序学习数据集中学习并获取排序模型,其主要有Pointwise、Pairwise和Listwise三大类,而采用的机器学习技术主要有感知机、神经网络、支持向量机、Boosting、树、极限学习机、贝叶斯和进化算法等.排序学习评价指标用于度量排序模型的性能,如信息检索中常用的准确率(Precesion,P)、召回率(Recall,R)、平均精度均值(Mean average precision,MAP)、归一化折扣累积增益(Normalized discounted cumulated gain,NDCG)、期望倒数排序(Expected reciprocal rank,ERR)等.典型排序学习框架包含一个学习系统(Learning system)和一个排序系统(Ranking system).在学习系统中,通过排序学习方法从训练集中学习排序模型并最终获得最优排序模型;在排序系统中,利用训练出来的最优排序模型对测试集进行排序预测,并通过信息检索评价指标进行度量.从整个排序学习框架来看,最终获得的排序模型的性能取决于训练集(若包含验证集,则取决于训练集和验证集)、排序学习方法和评价指标.在同一数据集上,不同的排序学习方法在不同评价指标上其性能表现有所差异;在不同数据集上,同一排序学习方法在不同评价指标上其性能表现也将会略有不同.

2 排序学习方法分类

从不同的角度,依据不同的分类标准可以将现有排序学习方法划分成不同的类型,如依据输入数据样例或依据采用机器学习技术的不同,可划分成如图2所示的类别.

2.1 依输入数据样例的分类

按照训练模型时输入数据样例的不同,Liu[14]和Li[15]将排序学习方法分为3大类:Pointwise(单文档)、Pairwise(文档对)、Listwise(文档列表).

在Pointwise方法中,将训练集中每一个查询下的每一个文档看做一个训练样例,其输入是单个文档,包括每个文档的特征.Pointwise方法把排序问题转换成分类问题(二值、多值)、回归问题或序数回归问题求解,其目的是将训练样例尽可能准确地映射到区间里.

在Pairwise方法中,将训练集中的每一个查询下的任意两个具有偏序关系的文档对作为一个训练样例,其输入是文档对.Pairwise方法把排序问题主要看成为一个二分类问题,它考虑文档对之间的偏序关系,更接近排序问题的实质.训练排序模型的目标是去追求排序结果列表中不正确的偏序对尽量的少,越少则表明越好.若学习后获得的文档对的偏序关系和它们的真实文档对的偏序关系是完全一致的,则说明结果完全正确.

图1 排序学习典型框架[14]Fig.1 A typical framework of learning to rank[14]

图2 排序学习方法分类Fig.2 Categories of the learning to rank approaches

在Listwise方法中,输入不再是单个文档或文档对,而是一组文档列表,是将每一个查询下对应的所有文档的排序结果列表作为一个训练样例,更加全面地考虑了同一查询下不同文档的序列关系.Listwise方法以不同的方式度量文档排序序列的排序效果,训练排序模型的目标是使得结果列表与真实列表中文档排序顺序越接近越好.Listwise方法也可再细分为两类:直接优化基于排序列表的损失的Listwise方法和直接优化信息检索评价指标的Listwise方法.前类Listwise方法继承了Pointwise和Pairwise方法的研究思路,通过定义Listwise损失函数并最优化该损失函数而求得排序模型,其损失函数构造为用于衡量预测的文档序列与真实的文档序列之间的差异.后类Listwise方法将排序模型的构建与信息检索中的评价指标建立起关联,获得了最优评价值的排序模型被认为是最优排序模型,其基本思想是先定义信息检索中某个具体的评价准则(如NDCG等)的优化目标,再选择适当的机器学习方法和优化算法去学习排序模型以构建更能满足用户需求的最优排序模型.

表1从排序学习的输入数据、样本复杂度、所转化的主要问题和所具有的特点4个方面总结了Pointwise、Pairwise和Listwise三大类排序学习方法.实践经验结果表明,基于Listwise排序学习方法的排序模型的有效性通常要优于Pointwise和Pairwise这两大类排序学习方法的[14−15].当前,Listwise排序学习方法已成为近年来被研究最多的方法.

2.2 依采用机器学习技术的分类

依据训练模型时所采用机器学习技术的不同,我们将排序学习方法分为以下几类:基于感知机、基于神经网络、基于支持向量机、基于极限学习机、基于贝叶斯、基于提升、基于树、基于进化算法的排序学习方法和其他排序学习方法等.

2.2.1 基于感知机的排序学习方法

感知机(Perceptron)是一种二分类的线性判别模型,对应输入空间中将实例划分为正例和负例两类的分离超平面w·x−b=0,其输入和输出分别为样本实例的特征向量和类别.感知机学习旨在追求一个能够将训练数据完全正确线性划分的正、负例分离超平面,即通过学习策略最小化风险以优化模型参数w和b,从而对新的实例实现准确预测.感知机是神经网络与支持向量机的基础.

PRank[16]是基于感知机的排序学习方法的代表之一,它是一种基于感知机同时在线学习线性模型的排序学习方法.该方法的基本思想是利用大量的并行感知机同时在线学习线性模型,每个模型在相邻等级之间做分类,旨在找到一个能成功将全部训练样例准确映射到所定义的k个区间内的感知机模型.PRank方法的目标是最小化排序损失,希望预测排序尽可能接近真实排序.它通过迭代学习来实现,在第t次迭代中,排序模型获取与查询q相关的文档的排序值xt,算法预测其分值ηt=minr∈{1,···,k}{r:wt·xt−btr＜0}, 并获取其真实排序值yt.如果排序模型将xt的分类预测为ηt而不是yt,那么wt·xt的值在btr的错误方,则需修改w和b的值以更新排序规则;否则,设置wt+1=wt,∀r:btr+1=btr.重复迭代,直到训练过程结束, 最终输出H(x)=minr∈{1,···,k}{r:wT+1·x−bTr+1＜0}.PRank方法直观简单,其正确性和收敛性在理论上得到了证明.

文献[17−18]等也利用感知机设计排序学习方法.Gao等[17]提出了基于感知机的算法LDM(Percep)以最小化排序列表中不一致文档对的数量.Xia等[18]针对只利用“正例”排序进行训练的关系排序学习方法R-LTR,进一步改进关系排序模型,提出了基于结构化感知机的排序学习方法PAMM.

基于感知机的排序学习方法简单且易于实现,并可从数学上严格证明算法的收敛性,但收敛速度较慢.设计基于感知机的排序学习方法的难点在于损失函数的定义及如何最小化损失函数.

表1 Pointwise、Pairwise和Listwise排序学习方法对比Table 1 Comparison of Pointwise,Pairwise and Listwise learning to rank approaches

2.2.2 基于神经网络的排序学习方法

神经网络(Neural network,NN)是感知机的无环网络,其中一些感知机的输出结果又作为其他感知机的输入.NN的主要思想是在给定的训练样本下,通过模仿生物神经网络所出现的一些属性,试图构建一个能优化分离数据成正例和反例的n维决策边界面.它根据训练数据来调整神经元之间的“连接权重”以及每个功能神经元的阈值,其学习过程中需使用一些优化方法,如梯度下降法,以找到一个能最大限度地减少错误分类数量的解.

RankNet[19]是基于神经网络的排序学习方法的代表之一,该方法依赖于每一个文档对,定义了一个基于概率的损失函数,运用神经网络和梯度下降法试图最小化一个交叉熵损失函数.在RankNet中,给定关联于偏序文档xu和xv,基于真实标注构建目标概率,它表示文档xu排在文档xv前面的概率;基于由评分函数f计算文档的评分差异定义模型概率Pu,v,即;在文档对上定义损失函数为目标概率和模型概率之间的交叉熵,即,最终目的是优化C的总和,使损失函数最小.在RankNet中,神经网络用于建模,梯度下降法作为优化算法去学习评分函数.优化过程中,在训练数据上使用当前网络去计算评分,使用计算损失,基于相关计算公式更新网络参数.由于RankNet的训练数据为各查询下若干文档对,因此需针对文档对的输入去调整神经网络的权值.

RankNet不仅在理论上是一个很好的模型,而且是第一个应用于互联网搜索引擎的排序学习方法,微软已经将RankNet技术应用于其搜索引擎必应(Bing)中.为了改进RankNet,研究者们又提出了FRank和LambdaRank等排序学习方法以追求更好的排序结果.FRank[20]与RankNet的区别在于所使用的损失函数不同,它采用的是 fidelity函数作为损失函数.LambdaRank[21]是基于RankNet的改进方法,对梯度的计算方式引入信息检索评价指标NDCG,针对迭代过程中所生成的文档列表以及相应的NDCG取值的变化情况来确定每个文档对的梯度,从而体现如何调整文档之间的相对顺序以最大化NDCG,希望所构建的相应损失函数能与最终的评价准则尽可能相一致.

文献[22−25]等也是基于神经网络的排序学习方法.ListNet[22]是基于神经网络和梯度下降的排序学习方法,它将排序问题看作一个排列概率问题,考虑实际排序列表与真实排序列表分别对应的概率分布之间的比较,采用K-L散度来定义排序损失函数.ListMLE[23]则根据实际打分函数计算真实排序列表的概率分布,从而考虑最大化实际理想排序列表的对数似然函数来度量排序损失.Xia等[24]使用神经张量网络为搜索结果多样化建模文档新颖性,基于文档新颖性的新模型,在关系排序学习框架下,设计了两种新的多样性排序学习方法R-LTRNTN和PAMM-NTN.Rigutini等[25]提出了一种基于比较神经网络(CmpNN)的偏序排序学习方法SortNet.

基于神经网络的排序学习方法的学习能力较强,对噪声数据鲁棒性和容错性较强,但需调节的参数较多,训练速度慢,容易过拟合,泛化性能较差,有可能陷入局部极小值.

2.2.3 基于支持向量机的排序学习方法

支持向量机(Support vector machine,SVM)是一种建立在统计学习的VC 维(Vapnikchervonenkis dimension)理论和结构风险最小化原理之上的机器学习方法.SVM的主要思想是在给定训练样本下,构建一个n维超平面作为决策边界曲面,最优化分离这些数据,使得正例和负例之间的隔离边界被最大化.SVM可看成是感知机的一种改进版本,它的目标是构建一个不仅能将正例和负例分开且能使得间隔最大化的分离最优超平面.

Joachims[26]提出了一种基于SVM 的代表性排序学习方法Ranking SVM,该方法从用户的点击序列中获取具有偏序关系的训练样本对,将排序问题转换为一个二值分类问题,并使用SVM 去训练排序模型.给定n个训练查询和每个查询相关联的文档对以及对应的相关性标注,即训练数据,则Ranking SVM的优化问题可数学形式化为:.其中控制模型ω的复杂度.该问题等价于最小化正则化 Hinge损失函数,即,通过解决对偶问题i=1,···,n来获得最优化参数,最终输出排序模型〉. 可知,Ranking SVM继承了SVM的框架和特性,其目标函数非常相似于SVM的,与SVM的差异主要在于约束条件.Ranking SVM的约束条件是从文档对中构建的,其损失函数也是定义在文档对上的Hinge损失.

基于支持向量机的排序学习方法还有文献[27−30]等.SVM-MAP[27]方法定义了评价指标为平均精度均值(MAP)的目标函数,并以此设计了一个基于Hinge的损失函数来替代原MAP的目标函数,利用结构化SVM的框架来设计排序方法,同时使得目标函数中松弛变量的总和上有界约束位置敏感准则(1-AP).SVM-NDCG[28]方法与SVMMAP方法类似,但要求上有界约束位置敏感准则(1-NDCG).Zhao等[29]提出了一种深度特征学习结构化SVM的排序学习方法以同时解决学习有效特征和排序学习的优化问题,该方法在一个联合的学习框架下,通过结构化SVM学习,可同时获得深度线性特征集和构建结构化感知的排序模型.Li等[30]把排序学习问题看作为一个结构化学习问题,基于结构化SVM设计了一个Bregman距离函数以构建排序模型,并为该排序模型开发了一个鲁棒性结构化学习框架,提出了鲁棒性结构化Bregman距离函数的排序学习模型.

基于支持向量机的排序学习方法具有严密的理论基础,较强的泛化能力,且易于使用;小样本数据下可得到较高的准确率,但处理大规模排序学习数据集时显得效率低下.

2.2.4 基于极限学习机的排序学习方法

极限学习机(Extremelearningmachine,ELM)可视为一种新型简单、快速有效的单隐层前馈神经网络的学习方法.与前馈神经网络相比,ELM的主要特点是隐藏结点参数不仅与训练数据无关,而且彼此独立,还有隐藏结点参数在训练数据出现之前可以生成.ELM算法思想是首先给定网络隐层结点参数和激活函数,设置输入结点和隐层结点的连接权重及隐层结点的阈值;然后将网络输入输出关系变成一个矩阵向量形式H·β=O计算隐层输出矩阵H;最后通过β=H+O求解获得网络输出连接权重β,其中H+是H的广义逆运算.

传统的神经网络学习算法,如反向传播算法,需通过人工设置较多的网络训练参数,并且很容易陷入局部最优解.而ELM算法只需设置网络中隐层结点的个数,在其执行过程中,无需去调整网络的输入权重以及隐元的偏置,可随机初始化输入权重和偏置,学习一次就可得到相应的输出权重,即可获得唯一的最优解.ELM算法实际上为广义单隐层神经网络提供了一个统一的解决方案,它是从传统神经网络扩展到正则网络和支持向量网络.

Zong等[31]应用ELM,从Pointwise和Pairwise两个视角分别设计了Pointwise RankELM和Pairwise RankELM两种排序学习方法以解决相关性排序学习问题,并提出了线性随机结点的ELM和线性内核版本的ELM.在Pointwise RankELM排序学习方法中,针对线性随机结点的ELM,先依据给定的训练样本,产生L个带有每个结点随机分配参数(a,b)的隐藏结点,再计算隐层输出矩阵,并计算输出权重和计算测试样例的输出函数f(x)=h(x)·β.而针对线性内核的ELM,计算测试样本的输出函数:·和. 而在Pairwise RankELM排序学习方法中,与Pointwise RankELM 不同的是:1)在线性随机结点中,Pairwise RankELM是构建矩阵w存储查询文档关系的信息,并计算相应的Laplacian矩阵,而计算输出权重β时,是按照进行计算的.2)在线性内核中,Pairwise RankELM首先构建矩阵w存储查询文档关系的信息,并计算相应的Laplacian矩阵,再按照f(x)kernel=去计算测试样本的输出函数f(x).

Chen等[32]提出了一种新的运用ELM的排序学习方法ELMRank,给出定理并证明了ELMRank也继承了ELM 的计算可行性,并针对假设空间能力,确立了ELMRank的泛化分析.

基于极限学习机的排序学习方法只需设定网络的隐层结点数,无需迭代调节隐层结点的学习,只需一次学习就可获得唯一最优解;具有简单易用、训练参数少、学习速度快和泛化性能好且广义逼近能力强的优点,但没有较好的鲁棒性.

2.2.5 基于贝叶斯的排序学习方法

贝叶斯(Bayesian)方法是一种基于假设的先验概率、给定假设下观察到不同数据的概率和观察到的数据本身信息而计算假设概率的方法.该方法首先综合未知参数的先验信息与样本数据信息,然后依据贝叶斯公式去计算后验信息,最后依据所得出的后验信息去推断未知参数.

Guo等[33]提出了BLM-Rank,一种贝叶斯线性模型的排序学习方法,该方法在贝叶斯个性化排序标准的框架下,使用一个线性函数去评分样本的值,依赖于样本的评分建模样本的Pairwise偏好,并采用了随机梯度法去最大化BLM-Rank中的先验概率,且在GPU上实现了该方法.BLM-Rank方法首先从训练数据中构建Pairwise训练样本和构建正偏序对的训练集,然后混排Γ+中的Pairwise训练数据以便于将要遍历的次序是无偏的和随机的,再对每个样例(xi,j,xi,k)∈Γ+,依条件循环执行w=w+α·以获得最终w,最后产生线性函数F(xi,j,w)=wTxi,j.

还有一些基于贝叶斯的排序学习方法,如Cossock等[34]为排序学习设计贝叶斯最优化排序函数,并对贝叶斯最优子集排序作统计分析;Wang等[35]提出了一种简单快速的排序学习模型RankBayes,该模型可以应用朴素贝叶斯算法去实现.

基于贝叶斯的排序学习方法具有坚实的数学基础,计算简单、快速;容易理解和解释,且易构造,估计模型参数时无需复杂的迭代;支持增量学习,但需要计算先验概率,对输入数据的表达形式较敏感.

2.2.6 基于提升的排序学习方法

提升(Boosting)是一类可将弱学习器提升为强学习器的方法,通过线性组合若干个弱学习器,有监督的迭代以改进弱学习器的机器学习方法.Boosting的理论基础是弱可学习理论,其工作机制是:先从初始训练集训练出一个弱学习器,再根据弱学习器的性能调整训练样本分布,使得当前弱学习器做错的训练样本在下一次迭代中受到重点训练,然后基于调整后的样本分布去训练下一个弱学习器;如此循环训练,直至弱学习器的数目达到预先给定的值T,最终将这T个弱学习器进行加权组合以创建一个单一的强学习器使得整体性能得到提升.

RankBoost[36]是基于AdaBoost算法的排序学习方法,通过最小化实例对的分类错误而训练排序模型,其学习目标是通过结合多个弱排序器构成最终唯一的排序模型.RankBoost是Pairwise排序学习方法,实质是在优化文档偏序对间的分类误差,整体还是Boosting框架,在逐层迭代过程中,根据前一阶段的学习情况调整各训练数据的权重.具体来说,RankBoost方法基于分布Dt训练弱学习器ht,得到弱排序器ht:x→R,而后选择合适的αt∈R,再通过更新分布,此处Zt是一个归一化因子.最后,输出最终排序模型:.由上可知,RankBoost排序学习方法是基于当前文档对的分布Dt去学习最优的弱排序器ht,并选择对应弱排序器的权重αt,以便进行线性权值叠加.

AdaRank[37]是一种基于Boosting算法框架、能直接最小化定义在信息检索评价准则上的指数损失函数的Listwise排序学习方法,该方法在调整训练数据权重的基础上不断地构造弱排序器,最终线性组合各弱排序器以用于排序预测.

基于提升的排序学习方法简单易用、设置参数较少、不易过拟合、能有效降低偏差,且具有理论支持,具有较强的特征选择能力和一定的泛化能力,但有效合理地选取损失函数和更紧致的泛化误差界是两大难点问题.

2.2.7 基于树的排序学习方法

树(Tree)是具有相同数据类型的数据元素的集合,树状结构表示数据元素之间存在着“一对多”的树形关系.一般的,一棵树包含一个根结点、若干个内部结点和叶子结点.根结点包含样本全集,叶子结点对应于样本实例,其他结点则对应数据属性.根据数据属性的不同,划分每个结点包含的样本集合到叶子结点中.对于给定的训练样本,根据数据属性采用树状结构建立模型.提升树是以分类树或回归树为基本分类器的提升方法.

基于树的排序学习方法的代表之一是LambdaMART[38−39],该方法是基于RankNet的LambdaRank的提升树版本.LambdaMART方法利用多重加法回归树(Multiple additive regression tree,MART)取代LambdaRank方法中的神经网络以优化目标函数,优化过程中采用近似牛顿迭代法(Newton-Raphson)确定每一个叶子节点的输出值.LambdaMART方法的基本思想是训练一个弱模型的集成,组合每一个弱模型的预测为一个比单个模型的预测更强大和更准确的最终模型.LambdaMART从名字上可拆分成Lambda(即λ)和MART两部分,λ是MART学习过程中所使用的梯度,采用MART去优化λ以训练排序模型.某个查询q下的每个文档对di,dj〉的梯度定义为,其中|∆Mij|表示交换文档di和dj的排序位置后所引起的该查询的有效性M(M可为信息检索中一些常用的有效性评价指标,如归一化折扣累积增益NDCG等)的改变量.每个文档di的梯度定义为,其中I表示某查询q下的所有文档对di,dj〉的下标集合.MART直接在函数空间求解梯度函数,循环构建多棵树,每棵树的拟合目标是损失函数的梯度λ,通过不断叠加学习到的回归树而更新排序模型F,即,其中η表示学习率,γlk表示第k个训练样例的第l个叶子结点的输出值.LambdaMART方法的框架本质是MART算法,其创新在于训练过程中使用λ梯度,其特点是不显式定义损失函数,而是定义损失函数的梯度函数,以解决排序损失函数不易被直接优化的问题.

LambdaMART在解决实际排序问题中已经被证明是一个非常成功的排序学习方法的代表之一,后续出现了较多对该方法的深入研究.Capannini等[40]开发了一个最有效的基于树的学习器的多线程实现的、开源的可提供优化的C++框架,这些学习器包括梯度提升回归树 GBRT、LambdaMART、Oblivious LambdaMART、一种诱导Oblivious回归树的森林算法.Lucchese等[41]提出了一种新的有效排序学习方法X-DART,该方法借用CLEaVER方法中树的剪枝策略以改进DART,最终提供更鲁棒和紧凑的排序模型.

还有许多工作对基于树的排序学习方法进行了研究.Chen等[42]使用随机梯度提升回归树训练排序函数.Kocsis等[43]提出了一种提升树策略的排序学习方法.Asadi等[44]聚焦于使用梯度提升回归树进行排序学习运行时的性能优化.Yin等[8]采用梯度提升决策树和逻辑损失函数设计了排序学习方法LogisticRank以进行搜索结果的排序.Lucchese等[11]为排序学习任务提出了一种有效的树集成的遍历算法QuickScorer以快速排序文档.Dato等[45]扩展了文献[11]的工作,提出了一个利用Oblivious和Non-oblivious回归树加法集成建模的排序函数来对文档进行有效评分的新算法框架,旨在对大型Web搜索引擎返回的查询结果进行快速排序.Lucchese等[46]提出了一个为优化基于回归树集成的机器学习排序模型的新框架,该框架是对树集成的后期学习优化,其目标是去改进排序效率而不影响排序质量.Mohan等[47]提出了一种基于初始化梯度提升回归树的排序学习方法以用于Web搜索,该方法组合了随机森林和梯度提升回归树,首先运用随机森林去学习出一个排序函数,再将该函数作为梯度提升回归树的初始值继续学习更优的排序函数.de S等[48]提出了一个基于Boosting和随机森林排序学习的通用框架以平滑组合加法树集成学习.它使用随机森林模型作为Boosting方法的弱学习器,依赖于通过随机森林所产生的词袋样本以决定最终加法模型中每一个弱学习器的影响和通过一个更可靠的错误率估计以更新样本分布的权值.Ibrahim等[49]深度比较了基于随机森林的Pointwise和Listwise排序学习方法,即RF-point和RF-list,设计了一种能直接优化任意排序标准的基于随机森林的Listwise排序学习方法,还设计了一种能融合不同分裂标准到单棵树中的随机森林的混合排序学习方法,该混合方法结合了树构建的早期的Listwise目标和晚期的Pointwise目标.

基于树的排序学习方法计算简单,易于理解,速度快,学习效果通常较好,但树的分裂标准和剪枝策略对产生的排序模型的性能影响较大,如何选择最优特征来划分特征空间是一大难点;容易发生过拟合,不过,随机森林可以在很大程度上减少过拟合.

2.2.8 基于进化算法的排序学习方法

进化算法(Evolutionary algorithm,EA)是来自于大自然的生物进化灵感的一个“算法簇”,是一类基于遗传和选择等生物进化机制的迭代优化的搜索算法.EA的主要思想是:在搜索最优解的过程中,一般是从原问题的一个解(或解集)进化到另一个较好的解(或解集),再从这个改进的解(或解集)继续进一步迭代进化以获得更优化的解(或解集).EA求解问题的主要步骤是:随机生成一个或一组初始解;评价当前该解或该组解的性能;选择当前该解或从该组解中选择给定数量的解迭代执行进化操作以获取新解;若新解满足给定的停止条件则结束迭代,否则将进化所得到的新解作为当前解再重新迭代执行进化操作.

EA并非直接处理求解问题的具体参数,而是针对求解问题的整个参数空间给出相应的编码方案.它是一种能适应不同问题和环境的鲁棒性智能优化方法,且在大多数情况下都能进化到用户满意的优化解.EA从某个单一的或一组初始点开始搜索,搜索中只要有目标函数值的信息就可优化,可不必用到目标函数的导数信息等,也不必要求目标函数是连续的,且具有较好的全局寻优能力,因而有较多的进化算法应用于排序学习问题中.将进化算法应用于设计排序学习方法,关键问题是解和排序模型的映射问题、适应度函数或优化目标的相应设计问题.

较早的基于进化算法的排序学习的代表性方法之一是Yeh等[50]运用遗传编程技术设计排序学习方法RankGP,该方法将排序模型表示为种群中的个体(解),一个个体I是一个潜在的排序函数,使用3个组件定义一个函数表达I=(Sv,Sc,Sop),其中Sv表示符号标记集,指训练集的特征,Sc表示预定义的实数集,值域∈[0,1],Sop表示算术操作集.I被定义为一个二叉树结构,它的叶子结点是特征或常量,非叶子结点是如+、−、×、÷等操作,利用种群的遗传编程在树上执行排序模型的学习.在进化过程中,通过交叉、变异、复制和选择等进化操作迭代产生一个新种群.在每次迭代中,使用平均精度均值MAP建模适应度函数以评价种群中每个个体在训练集上的性能.当进化结束时,将会产生一个适应度值最优的个体,以此个体作为最优排序模型.

受基于遗传编程的排序学习方法的启发,Lin等[51]运用分层多种群遗传编程改进RankGP方法,提出了排序学习方法RankMGP以学习排序函数.Keyhanipour等[52]提出了一种新颖的排序学习方法MGP-Rank,该方法从任意的基准数据集中,在基于点击数据概念的特征产生框架下产生点击特征,使用一种分层的多种群遗传编程框架去找最优化的排序函数.

借鉴RankGP方法将遗传编程应用于设计排序学习方法的经验,越来越多的基于进化算法的排序学习方法被提出来.Wang等[53]提出了一系列通用定义和一个为进化计算在排序学习研究中应用的共同框架,并基于该框架,提出了一种使用免疫规划的排序函数发现方法.He等[54]提出了一种基于克隆选择算法的排序学习方法RankCSA,直接优化信息检索的性能评价指标(MAP)以学习有效的排序函数.Diaz-Aviles等[55]基于粒子群优化框架,提出了一种新颖的排序学习方法SwarmRank直接最大化信息检索中广泛使用的评价标准以学习排序模型.Alejo等[56]提出了一种基于粒子群优化算法的排序学习方法RankPSO以直接优化评价标准而训练排序模型.Bollegala等[57]提出了一种基于差分进化算法的排序学习方法RankDE去学习排序函数以对所检索的文档进行排序.Wang等[58]提出了一种基于协同进化算法的并行排序学习框架CCRank,目标是显著改进学习的效率且同时保持精度,并采用三种基于进化算法(遗传编程、免疫规划和基于树的几何差分进化)的排序学习方法(RankGP、RankIP和RankGDE)实现了该框架.Ibrahim 等[59]运用进化策略设计排序学习方法ES-Rank以解决排序学习问题.Tian等[60]利用多核处理器将B细胞算法并行化,并将克隆交叉思想融入到并行B细胞算法中,同时提出了一种抗体的先序编码序列将树结构转化为线性结构,进一步设计了基于并行B细胞算法的排序学习方法RankBCA.Li等[61]提出了一种基于现代投资组合理论和归档式多目标模拟退火算法框架的风险敏感的鲁棒性排序学习方法R2Rank,以同时优化增益和风险并获取有效性和鲁棒性之间的均衡.

基于进化算法的排序学习方法可直接优化信息检索的评价标准,往往训练得到的排序模型可获得相对更优的评价性能.但由于该类方法存在大量迭代,通常计算复杂度较高和收敛速度较慢,故需花费的学习时间可能相对较长.可喜的是,由于进化算法通常具有天然的并行性,所以可将该类方法进行并行化,从而提高其效率.而且,进化算法非常适合大数据分析,所以基于进化算法的排序学习方法适合解决大数据排序学习问题.

2.2.9 其他排序学习方法

Moschitti[62]研究了一种具有语法和语义结构的基于核理论的排序学习方法.Ailon等[63]提出了一种有效的两阶段的基于偏好的排序学习方法.Niu等[7]开发了一些混合方法来提高排序学习方法的效果和效率,他们指出排序应是一个top-k的问题,并建立了一个完整的top-k排序框架,提出了若干种Pointwise、Pairwise和Listwise的混合排序学习方法,还阐述了如何获得高效可靠的top-k标注数据,如何设计有效的top-k排序学习模型,对排序结果采用何种评价准则进行可靠地评价等.

还有一些研究排序学习相关问题的工作.Zhou等[64]利用辅助数据进行排序学习.Macdonald等[65]针对不同信息需求类型,不同排序学习方法和不同排序学习语料库,全面调研了如何最佳地部署排序学习以获取有效的排序模型.Lai等[66]通过一个有效的Primal-Dual算法解决稀疏排序学习问题.Lai等[67]为排序学习提出了一种新的特征选择方法.Ma等[68]为排序学习提出了一种新颖的训练查询选择方法.Wang等[69]研究了个性化搜索中具有选择偏见的排序学习问题,在排序学习框架下如何利用稀疏的点击数据.Wu等[70]提出了一种从Listwise训练数据中学习非线性排序模型的分而训练的方法.Joachims等[71]利用有偏反馈数据提出了无偏排序学习.Calumby等[72]评论了交互式信息检索系统中交互式排序学习相关方面,主要集中在概述、最新进展、重要挑战和有前景的研究方向.

表2总结了一些典型排序学习方法所属类别.从表2可以看出,同一排序学习方法,从不同角度看待,分别属于不同类型的排序学习方法,它们之间的关系是交叉重叠的.依据不同角度,排序学习可分为不同的种类,如若按需求场景对排序学习进行分类,则可分为有效性排序学习、鲁棒性排序学习、多样性排序学习、可信性排序学习、时效性排序学习、个性化排序学习和多目标排序学习等方法.若按照所转化的问题不同,可分为基于分类、基于回归、基于序数回归、基于凸优化和基于多目标等的排序学习方法.尽管角度不同,分类不同,但设计排序学习方法的重难点问题仍在于如何构建损失函数(优化目标)和如何对损失函数(优化目标)进行学习以产生性能优良的排序模型.

3 排序学习数据集

目前已有公开的基准排序学习数据集主要包括:LETOR、MSLR-WEB10K 和 MSLRWEB30K、Yahoo! learning to rank challenge set、Yandex internet mathematics 2009、WCL2R以及Istella LETOR和Istella-S LETOR等.

表2 排序学习方法类别及实例Table 2 Categories and instances of the learning to rank approaches

LETOR1https://research.microsoft.com/en-us/um/beijing/projects/letor是由微软亚洲研究院开发的小规模排序学习数据集,于2008年和2009年分别发布了LETOR3.0和LETOR4.0数据集.LETOR3.0是OHSUMED和Gov中的一些数据集,如HP2003和TD2004等;LETOR4.0新发布了两个稍较大的数据集MQ2007和MQ2008,提供了4种排序设置的数据集:监督排序、半监督排序、排序聚合、列表排序,则总共包括了8个数据集.Qin等[73]对排序学习数据集LETOR进行了详细的描述,包括如何选择文档语料和查询集,如何对文档进行采样,如何提取排序学习特征和元信息以及如何划分数据集等.

MSLR-WEB10K和MSLR-WEB30K2https://www.microsoft.com/en-us/research/project/mslr/是由微软亚洲研究院于2010年开发的两个相对较大规模的排序学习数据集.MSLR-WEB30K是规模较大、且公共可利用的排序学习数据集,它包含了3万多个查询和300多万个文档,具有100多维排序特征.MSLR-WEB10K是从MSLR-WEB30K中随机采样的一个子数据集,它包含1万个查询和100多万个文档.每个排序学习数据集都包括从查询–文档对中提取的排序特征向量以及相关性判断标注,相关性判断标注是从微软的商业Web搜索引擎Bing的一个检索标签集中获得的.每个数据集被分成查询数量约相等的5个部分以进行5折(folds)交叉验证.在每个数据文件中,包含若干条记录,每条记录代表一个查询–文档对,它包含查询与文档的相关性程度、查询编号以及表征查询–文档对的136维排序特征.

Yahoo!learning to rank challenge set3http://webscope.sandbox.yahoo.com/catalog.php?datatype=c是2010年举行的Yahoo!排序学习挑战赛所采用的排序学习数据集,包含Yahoo!learning to rank challenge set 1和Yahoo!learning to rank challenge set 2.Chapelle等[13]详细介绍了该数据集的构建,包含查询、文档和相关性等级标注的收集,但没有揭露这些查询、URLs和排序特征的描述,仅仅提供了特征值.

Yandex internet mathematics 2009数据集4http://imat2009.yandex.ru/en/datasets是由俄罗斯的商业Web搜索引擎Yandex所发布的用于“the Yandex internet mathematics competition”的基于机器学习的排序竞赛的排序学习数据集,这些数据由Yandex评估员将查询–文档对的特征向量和相关性等级标注都用实数来表示以用于学习和测试.同Yahoo!learning to rank challenge数据集一样,不包含原始查询和原始文档的URLs,并且也不能揭示特征的语义信息.

WCL2R5http://www.latin.dcc.ufmg.br/collections/wcl2r是由米纳斯吉拉斯联邦大学等单位于2010年开发的具有点击特征数据的用于排序学习研究的基准数据集,它是从一个现实生活的搜索引擎TodoCL日志中提取的点击数据等显著性特征组成的排序学习数据集.Alcntara等[74]对WCL2R 排序学习数据集提供了详细的描述,包括如何获取语料、查询和相关性标注,如何构建可学习的数据特征和如何划分数据集等.

Istella LETOR和Istella-S LETOR6http://quickrank.isti.cnr.it/istella-dataset/是由意大利ISTI-CNR的Istella团队等于2016年开发的两个较大规模的、特别适用于求解排序学习问题的有关效率和可扩展性的大规模实验的排序学习数据集.Istella LETOR是目前规模最大、且公共可利用的排序学习数据集,按80%、20%的模式划分成训练集和测试集;Istella-S LETOR是对Istella LETOR中每个查询平均采样约103个样本的无关对所形成的一个相对较小的排序学习数据集,按60%、20%、20%的模式划分成训练集、验证集和测试集.

表3从查询个数、文档个数、特征个数、相关性等级标注和来源这5个方面总结了各种排序学习数据集的相关信息.从表3中的数据来看,小规模排序学习数据集偏多,查询、文档和特征个数整体都相对较小,缺乏大规模排序学习数据集.

4 排序学习方法应用

对排序学习的研究已不仅限于理论、方法和数据集方面,它正被越来越多地应用于信息检索等领域中解决实际的排序问题.排序是很多实际应用所面临的核心问题,如Web搜索、推荐系统、微博排序、多媒体检索、专家发现、机器翻译、问答系统、计算广告学、摘要提取、查询扩展和重写及建议、生物医学信息学等.

4.1 Web搜索

Web搜索是排序学习方法最早也是目前最成功的实际应用之一.研究提取查询–文档的哪些排序特征以及如何结合排序学习方法训练排序模型以提高用户对Web搜索的结果排序的满意度,成为基于排序学习的Web搜索的主要任务.

很多知名的互联网公司如 Bing、Yandex、Yahoo、百度和搜狗等搜索引擎,都依赖于排序学习方法为用户提供高质量的搜索结果,如排序学习方法RankNet[19]已应用于微软的搜索引擎Bing当中以对Web搜索结果进行优化排序,排序学习方法LogisticRank[8]已应用于雅虎搜索引擎中优化搜索结果的排序.Zhang等[75]在网络搜索实际场景中实证研究了包括线性回归、RankBoost、ListNet、ListMLE 和SVM-MAP这5个代表性的排序学习方法的有效性.Macdonald等[76]为Web搜索研究了排序学习模型的可迁移性.Kang等[77]基于使用成对偏好模型的集成的排序学习模型,对Web搜索中的关联实体进行实体排序.

4.2 推荐系统

将排序学习方法应用于推荐系统中主要需解决两大关键问题:1)挖掘用户和物品(对象)的哪些排序特征?2)运用排序学习方法如何整合这些特征,构建更加贴合用户需求的推荐模型,以提高推荐系统的性能和用户满意度?

Karatzoglou等[78]阐述了不同类别的排序学习方法的关键思想如何应用到具体的协同过滤方法中.Sun等[79]将排序学习方法RankSVM应用于推荐系统中,为用户产生物品的推荐列表.Yao等[80]为物品推荐应用排序学习技术,将用户间的社交信息融入Listwise排序学习模型的训练中以改进物品排序列表的质量.Canuto等[81]应用排序学习技术自动地学习标签排序函数,综合比较了8种不同排序学习方法(包括List-Net、RankSVM、RankBoost、AdaRank、多重加法回归树MART、LambdaMART、随机森林和遗传算法)融入标签推荐中的效果.Ifada等[82]针对基于标签的项目推荐系统,开发了一种新颖的排序学习方法Go-Rank以直接优化等级平均精度GAP,从而产生一个推荐项目的最优化列表.黄震华等[83]对近些年基于排序学习的推荐算法的研究进展进行了综述,对其问题定义、关键技术、效用评价、应用进展等进行概括、比较和分析,并对基于排序学习的推荐算法的未来发展趋势进行了探讨和展望.

表3 排序学习数据集Table 3 Datasets of learning to rank

4.3 微博排序

随着微博用户的剧增和博文数量的指数级增长,越来越多的排序学习方法应用于解决微博的排序问题.Berendsen等[84]研究了为微博搜索而创建伪测试集的方法,利用排序学习技术,使用伪测试集作为训练集去训练和调节微博排序器.Dong等[85]使用具有Freshness特征的Twitter数据,利用排序学习技术(梯度提升决策树)去学习排序函数以用于改进Recency排序.Duan等[86]提取Tweet的内容相关性特征、Tweet用户帐号权威性特征和Tweet的特定特征,使用排序学习方法RankSVM学习排序模型以对微博搜索结果进行排序.

应用排序学习方法解决微博排序问题取得了较好的效果,但仍存在一些难点问题:1)由于微博数据的增量变化,要求能增量地提取微博排序特征以增量构建多维复合特征集,这就要求排序学习方法能支持微博数据集的增量学习;2)由于微博用户和信息数量过大以及各自的动态变化,这就要求排序学习方法能支持排序模型的动态学习.而现有应用于微博排序的的排序学习方法都缺乏对数据和模型的增量和动态性支持,这是未来需要突破的重难点.

4.4 多媒体检索

Chelaru等[87]利用排序学习技术研究了社交特征对视频检索有效性的影响.Yu等[88]利用排序学习技术得到一个用于图像检索的排序模型,该模型共同考虑了图像检索中用户的视觉特征和点击特征.Zhao等[89]运用深度神经网络和潜在的结构化SVM,提出了一种称为深度潜在结构化SVM的新型联合排序学习方法以进行多媒体检索.Karaoglu等[90]使用排序学习方法在计算机视觉中组合不同目标检测器.Wang等[91]将行人再识别任务建模为一个Listwise排序学习问题,集成卷积神经网络学习具有自适应Listwise约束的深度特征.

4.5 专家发现

Volkovs等[92]运用排序学习方法聚合专家偏好.Moreira等[93]探索了排序学习方法和排序聚合方法对学术出版物的数字化图书馆中专家发现任务中的应用.Zheng等[94]从文本内容、专家社区中带有引用模式的图形结构和有关专家的配置文件信息中,探讨了使用排序学习方法组合专家们的多种评估以发现专家.Chen等[95]融合多特征,基于ListNet排序学习方法设计了专家列表排序方法以发现专家.

4.6 机器翻译

Delpech等[96]提出了一种从语料库中,为特定领域的双语词典提取新的组合翻译方法,并采用排序学习技术为候选翻译结果进行排序.Li等[97]将Listwise排序学习方法应用于机器翻译的自动评估.Lee等[98]将排序学习方法应用于英语–韩语机器翻译中解决谓词参数的重排序.Farzi等[99]使用基于语法的排序学习系统改进统计机器翻译.

4.7 问答系统

Wu等[100]提出了一种新的基于意图的语言模型,采用LambdaMART排序学习方法评估该模型参数以提高问答社区中短查询的搜索相关性.Nguyen等[101]运用Ranking SVM 排序学习方法为重排序问题学习的社区问答竞赛进行排序问题学习.Verberne等[102]为问答系统排序答案任务评估了一些排序学习方法,如Ranking SVM 和SVMMAP等.

4.8 计算广告学

Ciaramita等[103]从机器学习的视角研究了赞助商搜索问题,从点击数据中在线学习以解决赞助商搜索问题.Tagami等[104]基于排序学习方法,为上下文广告而提出了一种点击率预测算法.Karimzadehgan等[105]提出了一种随机排序学习方法,并应用于上下文广告中.

4.9 摘要提取

Shen等[106]主要探讨怎样使用支持向量机来训练以查询为主的多文档文摘的特征权重.Zhu等[107]将他们提出的关系排序学习方法应用于基于话题的多文档摘要任务中.Tran等[108]采用自适应排序学习方法为高影响事件的时间轴摘要进行实体排序以均衡新颖性和显著性.Tran等[109]提出了一个优化框架,并阐述了使用排序学习方法在该优化框架下如何从网络新闻事件中自动构建时间轴摘要.

4.10 查询扩展、重写和建议

Xu等[110]提出了一个新颖框架以探索使用排序学习方法去优化伪相关性反馈,为查询扩展比较评估了一些排序学习方法.Lin等[111]基于排序学习方法从社会化标注中进行扩展词提取,并构造词排序模型用于社会化标注查询扩展任务中.Dang等[112]提出使用排序学习方法执行查询重写,用仅有的两个特征重排序通过基于日志的查询扩展技术所产生的重写查询或扩展查询的列表.Santos等[113]提出了一种用于查询建议问题的排序学习方法,该方法利用从候选查询建议的结构化表示中挖掘出的多个排序特征以产生高效的查询建议.

4.11 生物医学信息学

Liu等[114]运用排序学习技术,提出了一种广泛应用于蛋白质远程同源性检测以及蛋白质功能和结构预测的计算方法ProtDec-LTR,该方法在监督学习框架下组合了三种最先进的排序预测器以训练最优排序模型.他们[115]还将基于个人配置信息的伪蛋白融入到排序学习算法框架中改进ProtDec-LTR方法以提高预测性能.Shang等[116]将自动摘要提取看作为一个排序问题,应用排序学习方法自动提取基因摘要.Jing等[117]基于排序学习算法开发了一个软件MQAPRank以用于改进全球蛋白质模型质量评价.

4.12 其他应用

Saleem等[118]使用排序学习方法进行基于个性化决策策略的Web服务选择.Deveaud等[119]通过使用排序学习方法以自动配置任务算法中的参数.Zhou等[120]将排序学习技术应用于关系实体搜索.Chen等[121]将排序学习技术应用于语义关联排序.Kong等[122]采用排序学习方法RankBoost和Ranking SVM获取候选抄袭源文档以解决抄袭检测源检索问题.

由上述归纳可知,排序学习方法已经在不同应用领域中取得了大量的研究成果.概括起来,将排序学习方法用于解决一些实际应用领域中的排序问题时,需要解决两大难点问题:1)针对实际应用,提取哪些排序特征以更好地表征该应用;2)如何针对实际应用,构建损失函数或优化目标以指导排序学习方法训练出更优的排序模型.

5 排序学习方法软件包

近年来,排序学习方法得以迅速发展,并能够广泛地运用于众多的实际应用中解决排序问题,离不开许多精心设计和实现的排序学习方法的开源软件包.目前常用的排序学习方法软件包有RankLib、QuickRank、Lerot、L2RLab、ESRank、LTR、MLR-master和SVMrank等.

RankLib7https://sourceforge.net/p/lemur/code/HEAD/tree/RankLib/是一个优秀的基于Java语言的排序学习方法库的开源实现,隶属于美国的马萨诸塞大学和卡内基梅隆大学合作项目Lemur,该款软件被广泛采用.RankLib是由马萨诸塞大学的研究者vdang开发的一个排序学习方法软件包,当前已经实现了 8种流行的方法,包括 MART、RankNet、RankBoost、AdaRank、ListNet、Coordinate ascent、LambdaMART 和Random forests.它实现了许多信息检索的评价标准,同时还提供了多种执行方式去实施评价.

QuickRank8https://github.com/hpclab/quickrank,9http://quickrank.isti.cnr.it是一款高性能排序学习工具箱,提供了一些排序学习方法的C++多线程实现,能将基于学习树的模型翻译为可用于快速评分文档的高效的C++源代码,注重于效率方面的设计和开发.目前,在该套装工具箱中实现了GBRT、LamdaMART、Oblivious GBRT/LamdaMART、Coordinate ascent、Line search、RankBoost、CLEAVER、X-CLEAVER 和X-DART等方法.QuickRank还引入了前期和后期学习的优化器理念,即排序学习方法可在执行训练阶段之前或之后被执行.优化器可以根据其定义处理数据集或模型,可以通过设置相应的选项同训练阶段一起在流水线上执行,或作为一个独立的进程工作在以前受过训练的模型或数据集上.目前,在QuickRank中已实现了CLEAVER优化器,该优化器在后期学习中剪枝一个集成模型以提高优化器的效率而不会妨碍其有效性.

Lerot10https://bitbucket.org/ilps/lerot软件包是由微软剑桥研究院Katja Hofmann和荷兰的阿姆斯特丹大学Anne Schuth等为信息检索而开发的一个在线排序学习方法框架,该框架是为在线排序学习方法运行实验而设计.Lerot提供了一个对在线排序学习方法进行评估和实验的解决方案,是一个开源的软件,其代码易于加入新的在线排序学习方法和/或反馈机制而被扩展.目前,包括了一些在线学习算法、交互方法和一套完整的评价方法,并已有在线排序学习方法作为插件集成到搜索引擎solr中.

LTR11https://github.com/yaschool/ltr,12http://yaschool.github.io/ltr/index.html软件包是一个用于解决机器学习问题的开源C++算法库,包括排序、分类和回归问题.LTR的主要思想是源代码的易于扩展性和泛化性,通过广泛使用C++模板和多态性而实现的.在当前的LTR算法库中,实现了以下算法:分类 (kNN、Naive Bayes、QDA、Fisher LDA)、回归(LSM)、排序(RankGP 和Linear ranker)、集成(Boosting、Bagging和RSM).用户可以在该软件包中添加自己编写的代码以执行学习和测试,也可以使用该软件包中带有人工可读的配置文件的控制台应用程序.每一个训练有素的排序器/分类器/回归器可以在C++代码中被序列化,以便不依赖于LTR算法库而被使用在其他项目上.

L2RLab[123]是为排序学习所开发的一个集成的实验环境,它集成了新排序学习模型的开发、评估、比较和分析性能以辅助排序学习研究者开展实验.L2RLab软件包主要由两大模块构成:可视化应用程序界面和一个有助于添加由研究人员所开发的新算法和性能度量指标的框架,其主要功能包括数据集的预处理、模型的训练和测试、模型的分析和比较.L2RLab易于添加新的排序学习方法,提供了易于使用的接口以避免实验应用的重新编码,其系统接口允许用户去设置和控制实验执行,执行的结果可以数字和图形的可视化方式展现.目前,L2RLab中包含RankPSO等很少量的排序学习方法.

ESRank13http://www.cs.nott.ac.uk/psxoi/ESRank.zip是英国诺丁汉大学和米尼亚大学的Osman Ali Sadek Ibrahim等实现的基于进化策略的排序学习方法ES-Rank的JAR包.

MLR-master14https://github.com/bmcfee/mlr/软件包由美国加利福尼亚大学的Brian McFee和Daryl Lim开发的一款排序学习方法的工具,包括Metric learning to rank(MLR)和Robust MLR的代码.该软件包基于结构化SVM框架,支持不同排序评价准则,如AUC,Precision@k,MRR,MAP和NDCG.

SVMrank15http://www.cs.cornell.edu/People/tj/svm light/svmrank.html#References是为有效地训练排序SVM 的结构化SVM 的一个实例,由美国康乃尔大学的Thorsten Joachims在具有GNU编译器套件(GCC)的Linux操作系统上开发实现的一个早期的排序学习方法Ranking SVM 的开源软件.后期有研究者开发实现了该方法的C++版16http://dlib.net/svmrankex.cpp.html和Python版17http://dlib.net/svm rank.py.html的代码.

表4从开发语言、特点和来源这3个方面归纳了各种排序学习方法软件包的相关信息.

表4 排序学习方法软件包Table 4 Software packages of the learning to rank approaches

6 排序学习发展趋势

排序学习不仅在学术界得到了积极的研究,而且在工业界也取得了广泛的发展.在排序学习理论与方法方面,研究人员丰富了机器学习的相关理论并提出了多种不同的排序学习方法;在排序学习实际产品应用方面,已经成为各个互联网搜索引擎和推荐系统等应用中网页、物品等对象排序的核心技术,很多知名的互联网公司如Bing、Yandex、Yahoo、百度和搜狗等搜索引擎和大型电子商务平台如eBay、亚马逊、淘宝天猫、1号店、国美等,在很大程度上都依赖于排序学习方法为用户提供高质量的搜索、推荐和广告等排序结果.尽管,排序学习已取得了较多的成果和较大的成功,但在排序学习领域中仍还有许多相关的问题尚未完全探讨,下面分别从排序学习的理论、方法、应用、需求场景、数据集和评价指标等方面总结在未来值得做进一步研究的排序学习问题.

6.1 排序学习理论研究

Chapelle等[124]指出:通过基准实验,许多排序学习方法已被证明是有效的.然而,因为小规模测试数据和训练,有时基准实验是不可靠的.在这种情况下,排序学习理论是必要的,以保证在无限未知的数据训练中排序学习方法的性能.他还指出排序学习理论已经有了一些尝试,但仍还有很大的发展空间去探索以解决以下难点问题:1)关于数据生成(例如,查询和文档)的一个合理假设;2)关于代理损失函数的一个泛化界;3)代理损失函数和排序度量标准之间的关系;4)当文档的数量接近于无限时,排序度量标准的极限的存在性等.

6.2 排序学习方法展望

随着机器学习技术的不断发展和改进,排序学习方法也需不断跟进和完善.基于一些新兴的智能优化算法、深度学习或其他新型机器学习技术,在未来可尝试运用它们开发出新的排序学习方法以追求更高的效果和效率.

6.2.1 基于新兴或混合型智能优化算法的排序学习

当前,虽已有较多的研究成果运用进化算法去设计排序学习方法,但运用新近开发的智能优化算法设计排序学习方法的研究仍还较少.近年来不断涌现出了一些新兴的智能优化算法,如烟花算法、萤火虫算法、布谷鸟搜索算法、随机蛙跳算法、猴子搜索算法、蝙蝠算法、花朵授粉算法、细菌觅食优化算法、稻田算法和智能水滴算法等,如何结合排序学习问题,基于这些新兴的智能优化算法或与已有的智能优化算法融合成更为高效的新型混合智能优化算法去设计排序学习方法,从而更高效地解决信息检索中的排序学习问题,是一个值得去开辟和尝试的研究方向.

6.2.2 基于深度学习的排序学习

深度学习是近年来最受瞩目的技术热点之一,它已经成为了工业界解决众多应用问题的神器.目前,深度学习的主要模型有卷积神经网络、递归神经网络、深度信念网络、限制玻尔兹曼机、自动编码器、长短时记忆网络和生成式对抗网络[125]等.还有一些蓄势待发的基于深度学习与其他方法结合的混合学习方法正在引领前沿,如深度强化学习、深度迁移学习、深度贝叶斯学习和深度森林等.

国际学术界公认的“排序学习”领域的代表人物Li等[126]指出深度学习的一些基本技术(如单词嵌入、递归神经网络和卷积神经网络)已经应用于图像和语音领域、自然语言处理和信息检索领域,如图像搜索、机器翻译和知识问答等.最近有些研究者对深度学习在自然语言处理[127]、控制领域[128]、人体行为识别[129]、视频目标跟踪[130]等领域进行了综述.Wang等[131]为Listwise排序学习方法提出了一种基于注意力的深层神经网络,可更好地将查询和搜索结果的不同嵌入(如卷积神经网络或word2vec模型)与基于注意力的机制进行融合.Severyn等[132]用卷积深神经网络对短文本进行排序学习.程学旗等[133]指出利用深度学习方法自动学习多样性排序特征和样本之间的依赖关系也是一个非常有前景的方向.

这些研究为深度学习技术运用于排序学习问题中开辟了思路,期待开发出更多基于深度学习的排序学习方法以增强大规模排序学习的效果和效率.

6.2.3 基于其他新型机器学习技术的排序学习

近年来,随着云计算技术和大数据的发展,互联网数据量的剧增和机器计算能力的提高,人工智能再次飞速发展,新型机器学习技术和新的机器学习理论框架也不断被提出,比如在线机器学习、对偶学习、对抗学习、指示学习、多视图学习、终身学习、元学习和平行学习[134]等.基于这些新型的机器学习技术和理论框架,结合排序学习问题的特点,开发新型排序学习方法,提高排序学习方法的效果和效率,也许有些新的排序学习方法还是应对大数据时代搜索引擎和推荐系统等实际应用中排序问题的有效途径.

设计排序学习方法关键在于依据排序学习问题所转化为分类、回归、序数回归和凸优化等问题,如何定义输入输出空间、假设空间、损失函数或优化目标.而设计新的排序学习方法的难点问题是如何依据排序学习问题的特点,结合新的机器学习技术,设计出新颖高效的排序学习方法.

6.3 排序学习方法应用领域的拓展及不同排序学习方法的应用检验

目前,有些排序学习方法已经成功应用于较多领域解决相应的一些排序问题,如Web搜索和推荐系统等,渴望能拓展到更多的应用领域中,如资源配置、模式识别等.对于需要排序的应用问题,只要能提取出若干排序特征以构建排序学习数据集,都可尝试运用排序学习方法去解决.针对实际应用问题,提取什么样的排序特征以及如何合理度量排序特征设计损失函数或优化目标是需要解决的难点问题.

虽然排序学习方法已经成功地应用于如Bing,雅虎搜索、百度和Yandex等搜索引擎公司和如eBay、淘宝天猫、1号店、美团和国美等大型电子商务平台,但真正用于具体的排序系统中的排序学习方法却很少,主要是RankNet和LambdaMART等,大部分排序学习方法并没有在实际的排序应用场景中得到相应检验,期待更多真实的搜索引擎或推荐系统等应用中的排序系统将更多的排序学习方法进行性能检验,并将性能最优秀的排序学习方法融入其中.

6.4 排序学习需求场景的探讨

随着互联网上千差万别的网民涌现、排序学习应用领域的不断扩展,所需求的排序场景也趋于多样化,不再只是仅仅追求排序模型的有效性,对排序模型的鲁棒性、多样性和可信性等以及排序学习方法的自适应性和高效率等,在一些实际的应用场景中也是非常重要的.为此,不同排序场景需求的排序学习是未来迫切需要探讨、解决的问题.

6.4.1 鲁棒性排序学习

当前,排序学习方法方面,已有的绝大部分工作中,是去比较和评估多个排序函数,基于一些信息检索度量指标(如NDCG、ERR等)选择一个最佳的排序函数,通过制定先进的排序功能和/或开发复杂的排序学习方法提高检索结果的平均有效性.然而,相对于简单的基准,这些方法通常会提高搜索结果的平均性能,但往往忽视了鲁棒性的重要问题[6].而对于一个商业搜索引擎公司,其真实的场景是更复杂的:伴随着更多的训练数据、新近开发的排序特征、或更神奇的排序算法,需要周期性地更新和改进排序函数,但排序结果不应显著性地发生改变.如此需求将对排序学习领域的鲁棒性带来新的挑战[124]:1)如何度量排序模型的鲁棒性?2)如何学习一个强鲁棒性的排序模型?

研究者们对排序模型的鲁棒性问题进行了积极的探索.TREC 2013 web track和TREC 2014 web track都为Web评价算法提出了一个风险敏感的检索任务.Wang等[6]讨论了排序学习中的鲁棒性问题.Din¸cer等[135−137]从风险敏感参数加权线性组合、学生t检验和卡方统计等理论中提出了一些风险敏感的度量和选择单/多基准来研究检索系统的鲁棒性.Ding等[138]从噪音数据中进行排序学习.Li等[61]提出了一种风险敏感的鲁棒性排序学习方法以均衡有效性和鲁棒性.尽管已取得了一些研究成果,但更合理地度量排序模型的鲁棒性和更好地学习一个强鲁棒性的排序模型是值得进一步作深入探讨的研究问题.因此,设计更优秀的鲁棒性排序学习方法是一项具有挑战性的创新工作.

6.4.2 多样性排序学习

现有排序学习方法主要关注于检索结果的有效性,大部分缺乏考虑多样性等质量指标,导致所呈现给用户的检索结果较单一,难以满足用户的不同信息需求.考虑多样性质量指标也逐渐成为衡量搜索引擎和推荐系统好坏的重要因素,为此有必要建立符合实际需求的优化目标.考虑多样性质量指标时,难以合理有效地度量和均衡.这也将带来新的挑战:如何度量排序模型的多样性?如何学习相应的多样性排序函数?

在排序结果的多样化方法方面,Liang等[139]提出多元数据融合方法以提升搜索结果的多样性.Liang等[140]使用监督学习策略解决个性化的搜索结果多样化问题.Wu等[141]提出了一类支持结果多样化的数据融合方法.Deng等[142]调研了查询结果多样化的复杂性问题.

中科院计算所研究员程学旗团队在多样性排序学习方面做出了突出的贡献.他们考虑排序结果的多样化,提出了一种通过直接优化任意多样性评估度量指标学习关系排序模型的新的多样性排序学习的通用框架[143]和3种多样性排序学习方法[18,24,144],他们分别采用随机梯度下降法、感知机和神经张量网络去学习排序模型,取得了很好的效果.同时,他们团队[133,145]指出由于搜索结果多样化任务本身的复杂性,多样化评价准则本身不可导和不连续,使得直接对其进行优化仍然存在许多有待解决的困难,并指出多样化是排序学习发展的一个新方向,还面临很多挑战,需要不断探索.

6.4.3 可信性排序学习

互联网中蕴藏着海量的网页资源,其中不乏作弊、不可信和恶意网页(Web spam),其信息良莠不齐,将严重影响排序结果的质量.同时,网页信息的可信与否难以确定、可信与不可信也不好度量.若一个检索结果中充斥了大量的不可信信息,将增加用户检索有用信息的难度,严重恶化用户的检索体验,是互联网信息检索所面临的最大挑战之一.因此,研究可信性排序学习问题,设计可信性度量指标和可信性排序学习方法以训练可信性排序模型,从而提高排序结果的可信性,对改善用户体验具有重要意义.

现有相关工作往往忽略了网页信息的可信性,已公开发表的考虑可信性质量指标的排序学习问题的研究成果较少,大多是对Web spam进行检测过滤,即使有的研究考虑到搜索结果的可信性,但大多是将可信性和相关性各质量指标聚合在单个目标中,掩盖了各单个质量指标的值.针对可信性排序学习问题,所要解决的重难点问题主要是可信和不可信排序特征的提取和度量、排序模型的可信性度量以及高可信排序模型的学习.

6.4.4 多目标排序学习

近年来,为了更进一步提高用户对信息需求的满意度,研究人员不仅考虑搜索结果质量的相关性,且更多地关注于排序结果的多样性、新鲜性等方面,也掀起了一些多目标排序学习方面的研究.Dai等[146]指出监督排序学习方法通常追求高相关性的优化而忽略搜索结果质量的其他方面,如新鲜性和多样性.他们通过开采混合标注,将多个方面(如新鲜性与相关性)的目标进行组合以产生总的质量,使用排序学习方法RankSVM去优化模型参数.Svore等[147]考虑了多个度量策略作为训练目标,提供了在多个被分级的度量策略上进行优化的解决方案,将多种度量合并成可以学习的一个单一的梯度度量,采用LambdaMART排序学习方法去优化.Kang等[148]提出了一种在排序学习场景中垂直搜索的多方面(如匹配度、距离、声誉等)相关性构想.还有如前所指出的鲁棒性排序学习、多样性排序学习和可信性排序学习,都可考虑转化为多目标排序学习.

上述研究虽然在排序学习方法中同时考虑了相关性和其他多方面质量指标,但其优化的目标仅为一个融合多方面质量指标的目标函数,这带来了如何为各质量指标合理设置权重的难点问题,在用户缺乏先验知识的情况下难以处理.因此,为有效地均衡相关性和多方面质量指标,需寻求可同时优化多个独立的目标函数的多目标排序学习方法,这也是一项具有挑战性的创新工作.设计多目标排序学习方法的难点在于排序模型的多个优化目标函数的合理设计和均衡以及排序模型的效果和排序学习的效率之间的均衡.

6.4.5 自适应排序学习

现有主流的检索系统通常只有一个通用的排序特征集和从这些特征集中所学到的或经验得到的相同排序模型.不同的查询词在同一排序模型下的性能表现大体上也是不同的,采用同一排序模型是难以保证为所有的用户和查询都能较好的工作,缺少针对不同场景的不同排序模型.为此,可针对不同场景(如凸显鲁棒性、多样性、可信性和马太效应等)应用不同排序特征去训练相应排序模型,依据查询词所属场景选择不同的排序模型.那么,如何使检索信息匹配检索场景,以感知不同的应用场景而自适应地调用不同的排序模型?为此,需提出基于多维度质量指标的自适应排序学习以感知不同需求场景而自适应地调用不同场景的排序模型.如何正确地识别需求场景,并能自适应地调用对应场景的排序模型是需解决的难点问题.期待出现更多应用场景、更炫的自适应排序学习方法,推动排序学习研究向实用化迈进,以应对更复杂的真实搜索、推荐场景,以进一步提高排序结果质量和用户满意度.

6.4.6 大数据排序学习

随着互联网大数据的快速发展,可构建的排序学习大数据越来越大,其类型也越来越多.现有排序学习方法绝大部分存在高度迭代,面对大数据,如此排序学习方法训练排序模型时间较长,内存消耗较大,效率低下,尤其是在需要实时处理数据的领域,问题尤为突出.为了维持在大数据上的排序速度,传统的以效果为中心的排序学习方法需要额外的硬件和能耗,所付出的代价昂贵[149].为了取得排序的效果和效率的持续改进,在保证一定排序效果的前提下,并行化排序学习方法以加快排序模型的训练速度,可提高排序学习方法的效率.Wang等[149]针对大数据环境,提出了一个共同优化有效性(相关性)和效率(速度)的排序学习的统一框架和能捕获这两个竞争目标间均衡的新度量标准.Cao等[150]提出了一种大数据环境下的分布式排序学习方法.

由于现有排序学习方法大多是基于内存的,无法将大数据一次性装载进计算机内存,故需提出新型数据并行、模型并行的排序学习方法以适应大数据处理的需求.在大数据时代,大数据排序学习是未来的发展趋势之一,其关键在于突破内存限制,设计能快速有效均衡效果和效率的大数据排序学习方法.

6.4.7 大规模分布式并行排序学习

现有大部分排序学习方法是以串行方式训练排序模型的,当面对大规模排序学习数据集时,这是很难去保证其学习效率.随着多核处理器、云计算技术、并行编程模型等的快速发展,为开发大规模分布式并行排序学习方法提供了一条可行之道.可将适用于处理大规模数据的机器学习方法,如感知机、神经网络、支持向量机、梯度提升决策树、随机森林和进化算法等在并行编程模型如MapReduce和Spark等框架下,将它们并行化,设计分布式并行排序学习方法.目前,研究者们已开发了少量的分布式并行排序学习方法.Sculley[151]关注于在大规模数据集上进行学习的排序学习方法.通过从一个隐式的Pairwise扩展索引中采样样本对,并应用有效的随机梯度下降学习器去学习排序模型,从而提高大规模排序学习的效率.Shukla等[152]在Spark分布式集群计算系统上并行化ListNet排序学习方法.Wang等[59]提出了一种基于协同进化算法的并行排序学习框架.Tian等[60]设计了基于并行B细胞算法的排序学习方法以改进收敛率和运行速度,提高最优解的质量.

再者,由于现实世界中待排序样本大量涌现,因此算法的可扩展性成为更加棘手的问题,目前随机、在线等优化策略已经在解决大规模分类问题中表现出优越性,如何结合这些技术并且有针对性地设计大规模分布式并行排序学习方法也将是我们今后的研究方向,其思路可从数据并行、算法并行和数据算法混合并行三方面去开展该研究.

6.4.8 在线增量式排序学习

传统上,排序学习方法以批处理模式在一个由查询和文档对以及与它们相关联的手动创建的相关性标注所构建的完整数据集上被训练,是一种离线方式.这种方式有许多缺点,且在许多情况下是不切实际的.首先,创建如此数据集是昂贵的,因此对于较小的搜索引擎,比如小的网络存储搜索引擎,是不可行的.其次,对于专家标注文档相关性,如在个性化搜索的情况下,它也许是不可能的.再者,文档对查询的相关性会随着时间的推移而改变,如在新闻搜索引擎中[153].因此,许多在线排序学习方法开发出来以解决此问题.

Suhara等[154]提出了在线排序学习方法.Hofmann等[155]给出了如何平衡信息检索中Listwise和Pairwise在线排序学习的勘探和开采.Chen等[156]提出了在线排序学习方法,并比较了在线排序学习的绝对反馈和相对反馈方法.Grotov等[153]总结了在线排序学习所使用的一些算法,如Bandit算法、决斗强盗梯度下降(Dueling bandit gradient descent,DBGD)等.Schuth等[157]扩展了DBGD为概率多级梯度下降,提出了一种多级梯度下降的快速在线排序学习方法.Zhao等[10]通过构建鲁棒的梯度探索方向,提出了两种方法改进在线排序学习方法.

通常,在线排序学习方法是从用户的交互数据中而不是从已标注的数据集中学习,基于用户实时点击反馈数据进行增量学习,它能快速学习原始排序列表的前端的最佳重排序.增量学习强调如何基于环境而行动,以取得最大化的预期利益.Keyhanipour等[158]提出了一种在增量学习框架下具有点击特征的排序学习方法.尽管现已开发出一些在线排序学习方法,但由于用户交互数据具有偏见和噪音,如何尽可能地消除偏见和噪音的影响,开发更优秀的在线增量式排序学习方法以快速可靠地从用户交互数据中学习仍是一个主要挑战.

6.4.9 基于用户行为的个性化排序学习

传统搜索引擎对不同用户的查询所返回的搜索结果的排序是相同的,然而有时不同用户对相同查询会有不同的意图,这就要求排序学习方法能适应个性化搜索和推荐等服务,能针对不同用户的查询和信息需求,呈现出可满足不同用户个性化偏好的排序结果.为此,可将个人信息和用户行为等融入到排序学习中,设计基于用户行为的个性化排序学习方法,最终达到个性化排序的要求,这是一个有挑战的任务,其关键是要解决如何正确地从用户行为中识别用户真实意图以及如何融入用户行为设计感知用户意图的个性化排序学习方法这两个重点问题.

6.4.10 其他需求场景

时效性排序学习、交互式排序学习、上下文排序学习、多任务排序学习、稀疏排序学习、关联排序学习、语义感知的排序学习、地理位置感知的排序学习等都值得作进一步的研究.

总之,设计不同需求场景的排序学习方法的难点在于如何将不同需求场景的实际情况与构建的损失函数或优化目标有机融合,从而指导排序学习方法学得一个能满足需求场景的更优的排序模型.

6.5 大规模排序学习数据集的构建

从表2中总结的排序学习数据集可看出,现有排序学习数据集的查询和文档总数并不多,总体规模比较小,最大的数据集也难以满足网络大数据的要求,难以全面可靠地反映出排序学习方法的真实性能.为了更准确可靠地评价排序学习方法的整体性能和提高排序学习方法在实际应用场景中的性能,应在大规模的排序学习数据集上进行训练和测试.更大的数据量、更丰富的数据多样性,可以保障算法获得足够多的训练,让它们变得更加智能.为此,需尽可能开采互联网上广泛的信息资源,使用更多数量和种类的查询,更多数量和种类的网页信息,提取更丰富的排序特征(如多样性、时效性、可信性特征,语义特征,基于点击、浏览、Session等用户行为特征,社交关系特征等)以及未标签的数据去构建大规模排序学习数据集.基于大规模排序学习数据集训练准确可靠的排序模型,为测试未知数据的排序提供保障.目前,如此大规模排序学习数据集仍还非常稀缺,其难点在于如何从大规模查询–文档对中提取丰富多样的排序特征和设计新的排序特征以更好地描述数据集,以及如何最小化噪音数据.解决好这些难点问题,有利于构建高质量的排序学习数据集,从而可更有效地构建高效的排序模型.因此,构建大规模排序学习数据集仍是一个开放问题.

6.6 排序学习评价指标

排序学习性能的评价是一个非常重要的问题,它是衡量各种排序学习方法优劣的量化指标.在信息检索领域,传统评价指标主要有精度(P)、平均精度(Average precision,AP)、平均精度均值(MAP)、召回率(R)、调和平均值F指标(F-measure)、排序倒数(Reciprocal rank,RR)、平均排序倒数(Mean reciprocal rank,MRR)、期望排序倒数(ERR)、排序偏好精度(Rank biased precision,RBP)、累积增益(Cumulated gain,CG)、折扣累积增益(Discounted cumulated gain,DCG)、理想折扣累积增益(Ideal discounted cumulated gain,IDCG)和归一化折扣累积增益(NDCG)以及一些意图感知(Intent aware,IA)的多样性评价指标,如Precision-IA、MAP-IA、α-NDCG、ERR-IA等.这些信息检索的评价指标都可用于评价排序学习方法的性能.

随着排序学习场景需求的增多,需更多新的评价指标来评估排序学习方法的优劣,如可信性排序学习场景需求中就需要评价排序模型的可信性指标,而在马太效应需求的排序场景中需要能评价排序模型的马太效应的指标等.为此,我们需针对不同需求场景来设计一些新的评价指标以衡量排序模型的优劣.如何将排序学习的需求场景特性融入评价标准中以设计出能合理有效度量排序模型性能的新评价指标,是一个关键难点.

总之,对排序学习的研究,既要注重对排序学习的理论研究,也要注重对排序学习方法和排序学习数据集的研究,还要检验和拓宽排序学习方法在实际排序场景中的应用.应加强应用于排序学习中统计学习理论的推导和证明,各种排序学习方法之间的对比和集成,各种排序学习数据集中查询量、文档量和特征维数等之间的对比和分析,改进和完善已有的各种排序学习方法和尽可能开发新的具有更强表征力的排序特征,继续探索和开发更高级的新排序学习方法,使排序学习方法不断得到丰富和发展,并在实际应用中得到检验.

7 结束语

排序学习是信息检索、机器学习和数据挖掘等领域中的一个重要问题,它在当代搜索引擎和推荐系统等实际应用中占有举足轻重的地位.本文对排序学习所涉及的较多方面的研究现状和进展进行了归纳和分析,并详细探讨了排序学习的未来发展趋势,希望能起到抛砖引玉的作用,能对学术界和工业界的相关研究人员提供有益帮助.期待学术界和工业界的研究者们应用更富有创造性的机器学习算法,更神奇的排序特征,以及更加强大的计算力,开发高效且接地气的排序学习方法,开创排序学习的一片新天地.