https://blog.csdn.net/kunlong0909/article/details/16805889

Table of Contents

1 前言

Web Search 的历史经历了

传统的 “text retrieval” 到 “基于link analysis的搜索引擎”，目前，由于机器学习和数据挖掘

的技术不断成熟，利用统计模型来解决rank问题已经成为一个hot topic： Learning to Rank

 

2 LTR的流程

• Collect Training Data (Queries and their labeled documents) 
• Feature Extraction for Query-document Pairs
• Learning the Ranking Model by Minimizing a Loss Function on the Training Data
• Use the Model to Answer Online Queries

3 训练数据的获取

有2种获取训练数据的来源:1）人工标注；2）搜索日志。

3.1 人工标注

从搜索日志中随机选取一部分Query，让受过专业训练的数据评估员对”Query-Url对”给出

相关性判断。常见的是5档的评分:差、一般、好、优秀、完美。以此作为训练数据。人工标

注是标注者的主观判断，会受标注者背景知识等因素的影响。

3.2 搜索日志

使用点击日志的偏多。比如，结果ABC分别位于123位，B比A位置低，但却得到了更多的点击，

那么B的相关性可能好于A。点击数据隐式反映了同Query下搜索结果之间相关性的相对好坏。

在搜索结果中，高位置的结果被点击的概率会大于低位置的结果，这叫做”点击偏见”（Click Bias）。

但采取以上的方式，就绕过了这个问题。因为我们只记录发生了”点击倒置”的高低位结果，使用这

样的”偏好对”作为训练数据。关于点击数据的使用，后续再单独开帖记录，这里不展开。

在实际应用中，除了点击数据，往往还会使用更多的数据。比如通过session日志，挖掘诸如页面停

留时间等维度。在实际场景中，搜索日志往往含有很多噪音。且只有Top Query（被搜索次数较多

的Query）才能产生足够数量能说明问题的搜索日志。

3.3 公共数据集

现存一批公开的数据集可以使用

1. LETOR, 
2. Microsoft Learning to Rank Dataset, 
3. Yahoo Learning to Rank Challenge, 

4 特征抽取

搜索引擎会使用一系列特征来决定结果的排序。一个特征称之为一个“feature”。按照我的理解，

feature可以分为3大类：

1. Doc本身的特征：Pagerank、内容丰富度、是否是spam等
2. Query-Doc的特征：文本相关性、Query term在文档中出现的次数等

此阶段就是要抽取出所有的特征，供后续训练使用。

5 模型训练

5.1 训练方法

LTR的学习方法分为Pointwise、Pairwise和Listwise三类。Pointwise和Pairwise把排序问题转换成 

回归 、 分类 或 有序分类 问题。Lisewise把Query下整个搜索结果作为一个训练的实例。3种方法

的区别主要体现在损失函数（Loss Function）上：

• Regression: treat relevance degree as real values
• Classification: treat relevance degree as categories
• Pairwise classification: reduce ranking to classifying the order between each pair of documents.

 

5.1.1 Pointwise

        Pointwis方法的主要思想是将排序问题转化为多类分类问题或者回归问题。以多类分类为例

进行说明：假设对于查询query，与其相关的文档集合为：{d1, d2, …, dn}。那么首先对这n个pair：

(query, di)抽取特征并表示成特征向量。

• Regression-based：

将query与di之间的相关度作为value，利用regression model来得到一个query与document之间相关

度的预测。

• Classification-based：

将query与di之间的相关度的程度作为label，一般的label等级划分方式为：｛Perfect, Excellent,

Good, Fair, Bad｝，一共五个类别。于是，对于一个查询及其文档集，可以形成n个训练实例。有了

训练实例，我们可以使用任一种多类分类器进行学习，比如最大熵，SVM。下面是一个例子：

 

 

5.1.2 Pairwise

 Pairwise方法是目前比较流行的方法，效果也非常不错。它的主要思想是将Ranking问题形式化为二元

分类问题。

        下面这张图很直观地表达了pairwise方法的思想，同时也给出了构造训练实例的方法。

        对于同一条query，在它的所有相关文档集里，对任两个不同label的文档，都可以得到一个训练实例

（pair），比如图中的（）分别对应label为5和3，那么对于这个pair实例，给它赋予类别+1（5>3），

反之则赋予类别-1。于是，按照这种方式，我们就得到了二元分类器训练所需的样本了。预测时，只需要对

所有pair进行分类，便可以得到文档集的一个偏序关系，从而实现排序。

 Pairwise方法有很多的实现，比如SVM Rank（开源）, 还有RankNet(C. Burges, et al. ICML 2005)， FRank

(M.Tsai, T.Liu, et al. SIGIR 2007)，RankBoost(Y. Freund, et al. JMLR 2003)等等。下面是SVM Rank的例子：

 

 

        相比于Pointwise方法，Pairwise方法不再对相关度作独立假设，因为它只对同一个query里的文档集生成

训练样本。然而，Pairwise模型也有一些缺点：1.它对不同级别之间的区分度是一致对待的。在信息检索领域，

尤其对于搜索引擎而言，人们更倾向于只点击搜索引擎返回的前几页结果，甚至只是前几条。所以我们对相关

度高（Perfect）的文档应该作更好的区分。2.相关文档集大小带来的模型偏置。假设query1对应的相关文档

集大小为5，query2的相关文档集大小为1000，那么从后者构造的训练样本数远远大于前者，从而使得分类器

对相关文档集小的query所产生的训练实例区分不好，甚至视若无睹。

        还有一个重要的因素也会影响Pairwise方法的排序性能。以Ranking SVM为例，它优化的目标是使得正负

样本之间的Margin最大，而并非以排序性能为优化目标。就像BP神经网络以训练误差为目标优化函数，从而使

得它很容易过拟合。优化目标本身的差异将导致模型本身的功能偏置。于是，基于这个特性，人们提出了Listwise

的方法。

5.1.3 Listwise

        Listwise方法相比于前两种（Pointwise，Pairwise）而言，不再将Ranking问题直接形式化为一个分类或者

回归问题，而是直接对文档的排序结果（list）进行优化。目前主要有两种优化方法：

• 直接针对Ranking评价指标进行优化。比如常用的MAP, NDCG（下面介绍）。这个想法非常自然，但是往往

 难以实现，因为NDCG这样的评价指标通常是非平滑（连续）的，而通用的目标函数优化方法针对的都是连续函数。

• 优化损失函数

        损失函数的构造有很多种方式。RankCosine(T. Qin, T. Liu, et al. IP&M 2007)使用正确排序与预测排序的分值向量

之间的Cosine相似度（夹角）来表示损失函数。 ListNet(Z. Cao, T. Qin, T. Liu, et al. ICML 2007)使用正确排序与预测排

序的排列概率分布之间的KL距离（交叉熵）作为损失函数，等等。

        以ListNet为例，其损失函数如下：

        和分别表示正确的排序以及预测的排序。其中，概率分布由以下公式定义：

        其中为第j个特征向量的Score。当然这个概率分布需要满足一些性质，比如，对于更佳排序，其概率值应该更高。

那么，最终损失函数就可以表示为以下形式：

        从式中可以看出，ListNet对特征向量进行简单的线性加权来对Score进行预测。此时，任务转化为对权矢量w的学习。

这显然是一个老生常谈的问题，梯度下降是最常用的方法。这里就不再赘述了。

        我觉得Listwise的方法是最优美的，因为它专注于自己的目标和任务。相比之下，Pairwise有点儿歪门邪道的感觉：）

当然，这种方法也并非完美，还是有一些缺点的。比如Score()如何构造？能直接使用Label么？事实上，这也是制约性能

的一大原因。还有，求解KL距离时，需要对所有排列计算其概率，算法复杂度趋于。针对这几个问题，都有相应的

Solution。

        对于ListNet，据我目前所知，有两个开源的Java版本实现，一是Minorthird，这是CMU的教授带领他的

学生们做的，类似于Weka，是一个实现了大量机器学习、数据挖掘算法的开源工具，它在Sorceforge上的主页在。另一个

是罗磊同学近期做的，使用的是单层神经网络模型来调整权值。目前已经在Google code上开源，地址在。欢迎大家使用并给

出意见。

 

6 效果评估

对于搜索结果，有多种量化搜索得分的计算方法，这里介绍NDCG和MAP。

6.1 NDCG（Normalized Discounted Cumulative Gain）

6.1.1 定义

• 计算前k条结果的相关性得分
• i：第i次搜索
• j：第j条结果
• y_i,j：第j条结果的相关性标注得分，5档制
• π_i(j)：这条结果在排序中的位置

6.1.2 描述

• 顾名思义，NDCG的公式由 N、D、C、G 4部分组成。将公式改写成
• 先看G部分。G是增益函数（Gain）,表示第j条结果在被给予评分y_i,j之后所贡献的分值增益。定义如下
• 再看D部分。D是位置折算函数（Discounted）。因为不同位置的增益应该是不同的，D函数给结果按照位置赋予一个权重。定于如下C部分就是累加（Cumulative），将k条结果的得分加在一起。
• N是归一化因子（Normalized），取值是该位置上G函数理论上取得的最大值的倒数。目的是缩放不同位置上的得分到统一区间。

6.2 MAP（Mean Average Precision）

6.2.1 定义

• MAP中，相关性评分y_i,j只有2档：0和1

6.2.2 描述

• P表示结果j的权重，从位置j开始，相关（标记为1）的结果所在的比例
• AP表示单query下，相关的结果的平均的加权得分
• AP中，只有标记为相关的结果才会参与加权的累加
• AP是单query下的得分，多query的平均AP，就成了MAP

7 参考

信息检索初学者's Learning to Rank 小结：

jiangfeng's 漫谈Learning to Rank：

1: Adapting Ranking SVM to Document Retrieval. (Liu Tie Yan. et al. MSRA) 【】

2: Learning to rank for Information Retrieval– tutorial. (Liu Tie Yan. et al. MSRA) 【】

3: Learning to rank: From Pairwise Approach to Listwise Approace. (Liu Tie Yan. et al. MSRA)【】

4: Learning to rank for  Information Retrieval - book. (Liu Tie Yan. MSRA)【】

5：Learning to Rank Report @ CIIR 2011 【】