排序算法是信息检索里面很重要的一环，例如用户提交了一个查询 q，搜索引擎会返回很多相关的文档，然后需要采用排序算法根据文档与 q 的相关性对文档进行排序。可以采用机器学习的方法解决排序的问题，称为 Learning To Rank (LTR) 。LTR 主要分三类 PointWise，PairWise，ListWise，本文主要介绍一种 PairWise 的算法 RankNet。

1.信息检索排序

在信息检索时，系统需要根据用户的查询 q，对文档进行相关性排序。信息检索中有很多经典的排序算法。

布尔模型(Boolean Model)

将查询表示成关键词的布尔组合，用 "与"，"或"，"非" 将查询组合起来，然后计算文档和查询的匹配程度。但是布尔模型通常只能检索出符合条件的文档，不能进行排序，例如我们有如下三个文档：

文档1: a b c d e f
文档2: a x b y y z
文档3: a c d e f g

根据文档和单词可以构造出一个单词-文档矩阵，表示单词是否出现在文档中。

布尔模型

如果用户要查询有 a 或者 b，但是一定有 z 的文档。首先从上述矩阵中找出 a，b，z 对应的向量 a(1, 1, 1)，b(1, 1, 0)，z(0, 1, 0)，然后按照查询所描述的布尔组合将向量组合在一起。如下所示，只有文档 2 符合条件。

布尔模型检索

向量空间模型 Vectos Space Model

将文档和查询转成向量空间中的向量，然后计算查询向量和文档向量的内积得到相似度，按相似度进行排序。向量可以用 TF-IDF 向量表示。

PageRank

给定一个网页 u，其影响力等于所有链接到 u 的网页加权影响力之和，如下所示。

PageRank

v 表示所有能够跳转到网页 u 的页面，L(v) 表示网页 v 所有跳转链接个数。另外用户也有可能通过输入网址访问页面而不是通过跳转链接，因此 PageRank 算法还加上了一个因子 d，表示用户按照跳转链接上网的概率。

PageRank

2.Learning To Rank

Learning To Rank 主要是使用机器学习的方法学习出文档的排序，主要分为三类：

PointWise：给定查询 q，PointWise 模型的输入是单个文档，直接计算出 q 和该文档的相关性，再根据相关性进行排序。这一类方法没有考虑文档之间的相互依赖关系，而且损失函数是不知道排序后文档的相对位置的。

PairWise：给定查询 q，PairWise 模型的输入是文档对 (即两个文档)，然后计算 q 更偏向于哪个文档。因此模型可以知道文档之间的相对顺序。

ListWise：输入的是查询 q 以及一组文档，输出为所有文档的排序结果。

本文主要介绍一种 PairWise 的 LTR 算法，RankNet 是微软研究院 2005 年提出的，用在搜索引擎 Bing 中，对应的论文是《Learning to Rank Using Gradient Descent》。RankNet 提出了一种概率损失函数，然后使用神经网络学习排名函数 (ranking function)，最后用使用梯度下降的方法训练模型。

3.RankNet

RankNet 使用神经网络对文档进行打分，f(x1) 表示样本 x1 的分数，如果 f(x1) > f(x2)，则表示 x1 排名高于 x2 (用 x1->x2 表示)。

我们可以利用函数 f 计算得到样本 xi 比样本 xj 排名更高的概率，如下所示。

Pij

另外还需要 xi 比 xj 排名更高 (即 xi 比 xj 更加相关) 的真实概率，在数据集中有参数 Sij。如果 xi 相关性比 xj 更高，则 Sij = 1；如果 xi 相关性比 xj 低，则 Sij = -1；如果 xi 相关性和 xj 一样，则 Sij = 0。我们可以通过下面的公式计算 xi 比 xj 排名更高的真实概率。

真实概率

RankNet 的损失函数采用了 cross entrophy，根据 损失函数进行梯度下降，优化神经网络的参数 (即函数 f)，损失函数如下所示。

损失函数

下图是不同真实概率下，损失函数取值和 (oi-oj) 的关系。

4.参考文献

《Learning to Rank using Gradient Descent》