机器学习排序

排序学习可以是监督,半监督或强化学习,用于构建信息检索系统的排名模型。训练数据通常为包含部分排序信息的列表,该排序通常表示为对每个物体都使用一个数字或序号表示的分数,或者是二元判断(相关或不相关)。排序模型的最终目的是得到可靠的排序,即便列表中的物体未曾出现过。常用的排序学习方法主要有:逐个的(PointWise),逐对的(PairWise)和逐列的(ListWise)。

来源:Wikipedia
简介

在信息检索(IR)领域,常用的排名模型大部分都包含参数,如PageRank中包含参数α。早期检索模型靠人工拟合排序公式,并通过不断的实验确定最佳的参数组合;而机器学习(ML)算法则可以自动调整参数,随着搜索引擎的发展,机器学习的优势逐渐体现出来。因此近年来,越来越多的ML技术被用于训练排序模型,并且机器学习排序这个新研究领域也逐渐出现。

总的来说,我们可以将所有使用ML技术的解决排序问题的方法称为机器学习排序,如能自动调优现有IR模型的参数的算法。更具体的来说,若排名方法具有以下两个特征,我们可以称之为机器学习排序方法:

  1. 排名方法是基于特征的(Feature based):所有被搜索的文档都由特征向量表示,该向量反映文档与查询的相关性。也就是说,对于给定的查询q,其关联的文档d可以用向量x = Φ(d,q)表示,其中Φ是特征提取方程(feature extractor)。常用的特征有查询词在文档中出现的频率等。对于机器学习排序方法来说,能够组合大量特征的能力是一个非常重要的优势,因为像传统算法中依靠人工将几十种考虑因素拟合出排序公式是不现实的, 而目前的搜索引擎的发展又需要考虑到大量特征。
  2. 排名方法是判别训练(Discriminative training):排名方法的学习应该都够划分为判别学习的四个部分,即输入空间(input space)、输出空间(output space)、假设空间(hypothesis space)和损失函数(loss function)。

下图给出了典型的机器学习排序流程。从图中我们可以看出,学习排名是一种监督式学习,需要一套训练集。

训练集的结构与测试集非常相似,例如,典型的训练集由n个训练查询(queries) q_i(i = 1,...,n)组成,其相关文档由根据特征向量x^(i)= {x_j^(i)} _{j = 1}^m(i)计算的相应的相关性判断表示,其中m(i)是与查询q_i相关联的文档的数量,即在第i次查询中有m(i)个相关文档。然后,系统使用特定的学习算法来学习排名模型,使得排名模型的输出可以尽可能准确地预测训练集中排序结果。在测试阶段,当新的查询输入时,在训练阶段学习到的模型对文档进行排序,并将相应的排名列表作为对查询的响应返回给用户。

机器学习排序可以分为 Pointwise、Pairwise 和 Listwise 三种模型。

[图片及描述来源:Liu, T-Y. (2009). Learning to Rank for Information Retrieval. Springer.]

发展历史

Norbert Fuhr在1992年介绍了机器学习排序的总体思想,将信息检索中的学习方法描述为参数估计的一般化。 Bill Cooper在1992年也同样提出了逻辑回归,并将其与伯克利研究小组一起使用,成功地为TREC(Text REtrieval Conference)提供了排名功能。 不过当时机器学习排序的算法并不突出,主要是因为当时可用的数据集很有限。自2000年中期以来,NIPS,SIGIR和ICML等一些会议举办了机器学习排序的专项研讨会。商业网络搜索引擎也是在这时开始使用机器学习排名系统。最早开始使用它的搜索引擎之一是AltaVista(后来它的技术被Overture和雅虎收购),它在2003年4月推出了使用梯度增强(gradient boosting)训练的排名功能。

针对训练集获取困难的问题,Thorsten Joachims提出了了SVM Rank 算法,这是一种 Pointwise模型,使用点击数据自动优化搜索引擎检索质量。2003年,Yoav Freund和Yoram Singer等学者提出了RankBoost,使用了现在Pairwise Learning to rank的常规思路,即构造目标分类器,将排序问题转化为分类问题。

2005年,微软提出RankNet,也是pairwise模型,不同之处在于RankNet使用概率损失函数学习排序函数,并使用神经网络实现模型。

基于RankNet,Christopher J.C. Burges等人提出了LambdaRank,LambdaRank是一个经验算法,它不是通过定义损失函数再求梯度的方式对排序问题进行求解,而是分析排序问题需要的梯度的物理意义,直接定义梯度,即Lambda梯度。Lambda梯度的使用可以量化一个待排序的文档在下一次迭代时应该调整的方向和强度。 因而效果更好,并且训练速度更快。LambdaMART是LambdaRank的增强树版本,由Qiang Wu和Christopher J. C. Burges等人于2010年提出,结合了Jerome H. Friedman于2001年提出的MART和LambdaRank。MART的原理是直接在函数空间对函数进行求解,模型结果由许多棵树组成,每棵树的拟合目标是损失函数的梯度,在LambdaMART中中间计算的梯度使用的是Lambda。

其他的常用算法还有2007年微软亚洲研究院的的徐君和李航提出的AdaRank,利用boosting算法的思想在机器学习排序里直接优化评价方法,和2008年Michael Taylor等人提出的SoftRank等。

2009年,刘铁岩发表了Learning to Rank for Information Retrieval,系统性的介绍了机器学习排序,并对对典型的学习 - 排序方法进行实证评估。

2017年,来自英国伦敦大学、上海交大、阿里等的学者应用 GAN 的思想提出了IRGAN,引入博弈论中的 minmax 博弈,来将生成式 IR 模型和判别式 IR 模型进行结合。他们两个模型定义一个共同的检索函数(例如基于判别的目标函数)。一方面,判别模型 旨在通过从标记数据中学习来最大化目标函数,并为生成模型提供训练的指导性信息。另一方面,生成模型 充当挑战者,不断地将判别器的 decision boundary 推向其极限它为判别器迭代地提供最困难的情况,判别器通过对抗的最小化目标函数来重新训练自身。

主要事件

年份事件相关论文/Reference
1992Norbert Fuhr介绍了机器学习排序的总体思想,将信息检索中的学习方法描述为参数估计的一般化Fuhr, N. (1992). Probabilistic Models in Information Retrieval.Computer Journal,35(3): 243–255,
1992Bill Cooper使用提出了逻辑回归与伯克利研究小组一起成功地为TREC(Text REtrieval Conference)提供了排名功能Cooper, W.S., Gey, F.C., Dabney, D.P. (1992). Probabilistic retrieval based on staged logistic regression. In: Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 1992), pp. 198–210.
2002Thorsten Joachims提出了SVM Rank 算法Joachims, T. (2002). Optimizing Search Engines Using Clickthrough Data, Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD).
2003Yoav Freund和Yoram Singer等学者提出了RankBoostFreund, Y. (2003).An Efficient Boosting Algorithm for Combining Preferences.Journal of Machine Learning Research. 4: 933-969.
2005微软提出RankNetBurges, C. et al. (2005).Learning to Rank using Gradient Descent. ICML.
2006基于RankNet,Christopher J.C. Burges等人提出了LambdaRankBurges, C. J. C.; Ragno R. and Le, Q. V. (2006). Learning to Rank with Non-Smooth Cost Functions. Advances in Neural Information Processing Systems.
2007微软亚洲研究院的的徐君和李航提出的AdaRankXu, J.; Li H. (2007).AdaRank: a boosting algorithm for information retrieval. SIGIR.
2009刘铁岩发表了Learning to Rank for Information Retrieval,系统性的介绍了机器学习排序,并对对典型的学习 - 排序方法进行实证评估Liu, T-Y. (2009). Learning to Rank for Information Retrieval. Foundations and Trends® in Information Retrieval. 3(3): 225-331.
2010Qiang Wu和Christopher J. C. Burges等人提出LambdaMARTWu, Q.; Burges, C.J.C.; Svore, K.M. et al. (2010).Adapting boosting for information retrieval measures. Inf Retrieval (2010) 13(3):254–270.
2017来自英国伦敦大学、上海交大、阿里等的学者应用 GAN 的思想提出了IRGANWang, J. et al.(2017).IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models.arXiv:1705.10513v2.


发展分析

瓶颈

如前文所述,人工标注大量的高质量数据集是非常昂贵的,因此现在在实际工作中往往使用搜索引擎的日志作为数据,但其中往往含有很多噪声,机器学习排序模型还不能从其中有效地获取有用的信息。另外,在将机器学习排序算法应用于实际问题时,研究者需要经过一系列操作,包括建立训练数据、提取特征、建立查询、文档选择和特征选取等,有时略显繁琐。

未来发展方向

考虑到数据集中的噪声,建立能够过滤这些噪声的模型是一个可能的发展方向;此外,作为信息检索的核心,排序算法的训练速度、运行速度、轻量化、扩展性等,以及无监督、半监督学习和主动学习方向都值得关心。

Contributor:Yuanyuan Li

相关人物
Yoram Singer
Yoram Singer
普林斯顿大学计算机科学系教授、谷歌研究科学家。他领导了一个小型研究小组,该小组专注于谷歌大脑团队中的有效机器学习原则。加入谷歌之前,他是耶路撒冷希伯来大学的计算机科学教授。
托尔斯滕·乔阿吉姆
托尔斯滕·乔阿吉姆
美国康奈尔大学计算机科学系、信息科学系教授,ACM Fellow、AAAI Fellow、Humboldt Fellow。他与学生和合作者合著的论文曾获得8次最佳论文奖项和4次Test-of-Time奖。Thorsten Joachims的研究主题为机器学习方法和理论、从人类行为数据和隐性反馈中学习、将机器学习技术应用于搜索、推荐、教育和其他人类主导任务。
李航
李航
李航,毕业于日本京都大学电气电子工程系,日本东京大学获得计算机科学博士学位。北京大学、南京大学兼职教授。曾任日本NEC公司中央研究所研究员,微软亚洲研究院高级研究员与主任研究员、华为技术有限公司诺亚方舟实验室主任,是《统计学习方法》作者。
刘铁岩
刘铁岩
刘铁岩博士毕业于清华大学电子工程系。现任微软亚洲研究院主任研究员,互联网经济与计算广告学研究组负责人。他是美国计算机学会(ACM)、国际电子电气工程师学会(IEEE)、和中国计算机学会(CCF)的高级会员。中国科技大学和南开大学的客座教授。
简介
相关人物