信息检索中的排序问题概述

胜紫菡

摘要：近年来，信息检索中的排序学习受到越来越广泛的关注.本文将在机器学习的框架下介绍排序学习，基于机器学习方法的排序算法称为“学习排序法”.学习排序法的两个主要特点是：一是基于特征的特点：训练文本是用特征向量来表示的;二是判别训练：“学习排序法”有自己的输入空间，输出空间，假设空间和损失函数.本文将针对不同的学习算法详细阐述这四个主要成分。

关键词：机器学习;排序问题;信息检索

排序学习是典型的有监督学习，训练集是由查询，与查询相关的文档和相应的相关性判断标准组成.排序模型可以通过一个排序算法来预测训练集的真实标签.当给定一个新的查询时，就可以根据排序模型对文档进行排序.不同的排序算法定义不同的输入空间和输出空间，并且使用不同的假设空间和不同的损失函数.因此在机器学习框架下，我们将“排序学习”分为以下两类：

基于单个文档的排序方法（Pointwise approach）

基于配对文档的排序方法（Pairwise approach）

1.基于单个文档的排序方法

基于单个文档的排序方法是排序学习最早提出的算法，其基本思想是将训练集中的每个查询/文档对作为训练数据，再应用合适的算法来学习一个排序模型.因为每个查询/文档对都被看做一个单独训练样本，所以称这种方法为Pointwise方法.Pointwise方法的四个主要组成成分：

（1）输入空间：包含单个查询/文档对的特征向量

（2）输出空间：包含单个查询/文档对的相关度得分

（3）假设空间：包含映射函数，它将每个查询/文档对的特征向量作为输入，通过一个函数来预测排序得分.我们称这个映射函数为得分函数，基于得分函数可以对文档进行排序。

（4）损失函数：衡量查询/文档对的预测得分与实值标签之间的差异.在不同的Pointwise算法中，排序分别被看做是回归、分类问题，相应的回归、分类损失就是排序损失.根据机器学习的不同方法，Pointwise方法可以被分为三种类型：

1.1基于回归的排序算法

基于回归的排序算法，它的输出空间是由实值相关度得分组成的.将排序问题转化为回归问题来考虑，他们把查询/文档对的相关度得分看作是一个连续变量，使用最小二乘损失来寻找最优排序函数.在此基础上，他们还提出了重要性加权回归模型来学习排序问题，并对最小二乘损失和排序误差界进行了理论研究。

1.2基于分类的排序算法

对基于分类的算法排序而言，它的输出空间是由类别标签组成的.提出了基于二分类的排序问题，他将训练集的类标签分为“相关”和“不相关”两类，通过SVM方法进行二分类学习来完成排序任务.在中提出了应用多类别分类问题来学习排序问题.他们提出了一个概率模型，以分类损失作为排序损失，并应用加权组合得分函数给出每个查询/文档对的得分，最终根据得分函数完成排序任务。

1.3基于顺序回归的排序算法

当把排序问题转化为顺序回归时，我们考虑实值标签的顺序来学习排序模型.提出了基于感知器的排序算法，也称为PRanking.其主要目的是通过迭代过程寻找一个参数向量和一些单调递增的临界值，根据每个查询/文档对的得分来判断其属于哪两个临界值之间，据此对查询/文档对进行排序。

2.基于配对文档的排序方法

基于配对文档的排序算法简称为Pairwise方法.Pairwise方法不同于Pointwise方法考虑每个查询/文档对的相关度，而是针对每个查询考虑两个文档间的偏序关系，其目标是使得最终的排序列表中逆序的文档对越少越好.基于Pairwise法的排序学习也称为配对偏序关系学习.Pairwise方法的四个主要组成成分：

（1）输入空间：包含每个查询所对应的配对文档的特征向量

（2）输出空间：包含每个查询所对应的配对文档的偏序关系

（3）假设空间：一个二变量函数，它输入一对文档，输出他们之间的偏序关系

（4）损失函数：衡量输出的偏序关系与实际偏序关系之间的不一致程度.在许多Pairwise排序算法中，排序问题被看做是Pairwise分类问题，相应的分类损失就是排序损失.目前信息检索中的排序算法有很大一部分都是基于Pairwise方法。

2.1Ranking SVM算法

Ranking SVM是由首次提出的.他是以SVM为工具，以每个查询的配对文档偏序关系为训练数据，基于顺序回归的方法将排序问题转化为分类问题来求解.在此基础上，进一步使用了Ranking SVM算法，他从用户的点击量数据中获取具有偏序关系的配对文档作为训练数据，同样将排序问题转换成一个二分类问题，并使用SVM来求解。

2.2RankBoost算法

RankBoost算法是在中提出的，其基本思想仍然是将排序问题转化为配对文档的二分类问题，但不同于Ranking SVM解决一个顺序回归问题，RankBoost直接求解偏序学习问题.他将AdaBoost应用到分类问题中，与所有的Boosting算法一样，RankBoost通过结合多个弱排序结果构成唯一的排序结果.这是通过多次迭代实现的，每一次迭代过程都通过更新文档对的分布得到一个弱排序，算法最终的排序结果是这些弱排序的加权线性组合。

3.小结

Pointwise 方法是排序学习最早提出的算法.他输入单个查询/文档对，根据得分函数输出其相关度得分，对得分按降序排列，據此来学习排序模型.Pointwise 方法分为三类：基于回归的算法，基于分类的算法和基于顺序回归的算法。

Pairwise方法将排序问题转化为二分类问题来处理，他输入成对的文档，根据一个排序函数输出成对文档的偏序关系，据此来学习排序模型.目前信息检索中很多排序算法都基于Pairwise算法，其中最具代表性的是：基于SVM 的Ranking SVM算法，基于Boosting的RankBoost算法和基于神经网络的RankNet算法。

參考文献：

[1]Cossock， D.， Zhang， T.： Subset ranking using regression. In： Proceedings of the 19th Annual Conference on Learning Theory （COLT 2006），2006：605-619.

[2]Nallapati， R.：Discriminative models for information retrieval.In： Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval （SIGIR 2004）， 2004： 64-71.

[3]Li， P.，Burges，C.，Wu， Q.：McRank： learning to rank using multiple classification and gradient boosting. In： Advances in Neural Information Processing Systems 20 （NIPS 2007）， 2008： 845-852.

[4]Crammer， K.， Singer， Y.： Pranking with ranking. In： Advances in Neural Information Processing Systems 14 （NIPS 2001）， 2002：641-647.

[5]Herbrich， R.， Obermayer， K.， Graepel， T.： Large margin rank boundaries for ordinal regression.In： Advances in Large Margin Classifiers， 2000： 115-132.

[6]Joachims， T.： Optimizing search engines using click through data.In： Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining （KDD2002）， 2002： 133-142.