第二十三章 排序学习
互联网的蓬勃发展，尤其是社交网络的诞生，一改往日“信息匮乏”的局面，大数据时代已经
来临。搜索引擎是网络用户从海量数据中查找信息的主要入口，因此，如何根据用户的检索请求，
迅速地准确定位到相关信息源（如网页、文档、音频、视频、图片等），是搜索引擎能否为用户认
可，能否吸引用户的重要标准，而搜索核心环节就是排序：将搜索内容以列表的形式，按照相关程
度从高到低展现给用户。
传统的搜索排序主要基于手工构造的模型，计算文档与检索词之间的相关程度。传统的排序模
型大致可分为两种类型，基于链接分析的模型，如PageRank[12, 217]，HITS[20]，SALSA[218, 21]；
基于内容分析的模型，如向量空间模型[2]，BM25[4]。目前影响网页排名的因素有上千种，传统排
名算法面对这种复杂局面，存在以下几个方面的不足：（1）考虑的影响因素比较单一；（2）对多个
影响因素的融合能力较差；（3）使用时不够灵活；（5）对复杂模型的参数调整比较困难。
图 23.1: 排序学习框架
排序学习[219, 220]可以在一定程度上克服传统排序的缺点。它结合机器学习的方法，可以自
动地从训练数据集中学习排名函数。序列型排序学习方法是目前最直接，也是表现最好的一类排序
219
搜索与排名 Searching and Ranking
!"#
学习方法。排序学习是一种典型的监督学习方法，需要利用带有人工标记的标准数据集训练模型。
数据集一般包含多个检索词，每个检索词存在多个关联文档，每个文档由一个多维特征向量（每个
特征都可以单独作为一个排名函数，如PageRank，TF*IDF等）表示，相应地，每篇文档都有一个
人工标记的相关等级，反映文档同检索词的相关程度。
)!*+",$%"&'#(
23.1 背景介绍
排序学习方法是一种有效的排名技术，借鉴机器学习的监督学习方法，通过优化损失函数，从
训练数据集中学习一个排名函数。排序学习是一个较新的研究方向，在过去十年间发展迅速，已经
被成功地应用到网页搜索、机器翻译和系统推荐等领域[220]。
Liu[221]和Li[222]根据输入空间、输出空间、模型假设和损失函数的不同，将排序学习方法划
分为三类：逐点型（Pointwise）、序对型(Pairwise)、序列型(Listwise)。
逐点型排序学习方法将排名问题转化为传统的分类、（有序）回归问题，根据成熟的分类和回
归算法，使用分类错误率或者均方差构建损失函数，训练排名函数。比如，Crammer和Singer[223]
出的PRank算法，通过训练一个感知器模型，把训练样本映射到一个全序集。
序对型排序学习算法的训练数据是成对的样本，根据模型假设预测序对的偏好关系，结合真实
相关等级，构造序对损失函数，模型训练的目标即最小化序对损失函数。典型的序对型排序学习
算法有：Herbrich等人[224]将排序问题转化为序对型分类问题，基于支持向量机（Support Vector
Machine, SVM）出RankingSVM 算法；Freund等人[164]根据升（Boosting）技术，将用于分
类的经典算法AdaBoost应用到序对型排序学习问题，出了RankBoost算法；Burges等人[225]根
据神经网络（Artificial Neural Network, ANN）的进化学习理论，辅以梯度下降的优化方法调
整模型参数，训练排序模型，出RankNet 算法；由于标准评价指标是非平滑不可微的，无法
直接优化，Burges等人[226]分析交换序对文档名次引发的成本变化，直接定义损失函数的梯度
（Lambda），改进RankNet算法引入LambdaRank。
序列型排序学习方法直接将整个样本集合作为学习对象，根据模型的预测结果和真实排名列
表构建出序列型损失函数，通过优化序列型损失函数训练排序模型。比如，2007 年Xu和Li[165]基
于Boosting技术，以单个特征作为备选弱排名函数，出一种高效的学习算法――AdaRank。同
年，Cao等人[227]认为在训练过程中，RankNet算法使用的交叉熵损失函数降低的同时却无法保证
标准度量指标相应地升，于是出一种基于概率模型的排序模型ListNet。ListNet是RankNet的
一种序列型扩展。Qin等人[228]出的RankCosine算法是基于余弦损失函数，使用梯度下降
法在神经网络上训练模型。Xia等人[229]于2008年出的ListMLE算法同ListNet类似，都是基
于Plackett-Luce概率模型、神经网络技术和梯度下降法训练排名函数，但是ListMLE根据真实排名
$%"&'#(
220
)!*+",$
23.2. 研究团队
!"#
列表，假设列表中各个位置服从指数概率分布，并根据最大似然估计，定义似然损失函数。
由于衡量排序性能的标准评价指标需要考虑文档位置信息，因此是非平滑的不可微函数，
序列型排序学习方法“直 接”优 化 目 标 多 是 对 性 能 指 标 作 平 滑 近 似 或 者 通 过 寻 找 性 能 评 价
指标的平滑上界，间接地进行优化。如Taylor等人[230]出的SoftRank算法根据模型的预测结
果，使用SoftNDCG近似文档的排名分布，属于平滑近似方法。Yue等人[231]出的SVM
MAP
模型
和Chakrabarti等人[ 232]推出的SVM
NDCG
模型分别对标准评价指标MAP和NDCG估计出其平滑上
界，均属于确定平滑上界的方法。
序列型排序学习方法实际上是直接优化性能评价指标，相比逐点型、序对型排序学习方法而
言，训练过程较为直观，损失函数同性能评价指标之间的一致性更强，而且不易受检索词关联文档
数目差异的影响。序列型排序学习方法内在地要优于序对型排序学习方法。
23.2 研究团队
目前研究排序学习的主要团队有微软亚洲研究院（如Hang Li，Tie-Yan Liu等），微软Bing 搜
索已经使用RankNet算法，但更偏重于理论证明。俄罗斯的Yandex研究团队在2009年Yahoo!举办
的Learning to Rank Challenge中取得不错的名次，而且据说Yandex 搜索引擎已经开始使用排序学
习训练的模型改善搜索质量。据称，Yandex 从2009年开始使用一种新的机器学习模型MatrixNet，
融合了上千种搜索因素，极大地改善搜索的质量。Yandex还举办了Internet Mathematics 2009竞
赛。 2002年前后，AltaVista首先使用Boosted Tree Regression构建基于排序学习的排名系统，系统
上线后，排名第一的网页点击率有明显升。百度网页搜索于2011年左右引入机器排序学习，并发
布排序学习算法工程师的招聘通知。Google对排序学习的兴趣不高；Cuil的CEO认为由机器学习
的模型没有人工构造的模型健壮。
数学界对排序问题的兴趣逐渐增加。Belgian Mathematical Society & National Commit-
tee of Mathematics 联合组织了2008年10月15日的The Mathematics of Ranking；美国数学学会
（American Institute of Mathematics）于2010年8 月16日-20日承办的Workshop on the Mathemat-
ics of Ranking。
排序学习的研究团队主要包括：
• Soumen Chakrabarti’s group
• Olivier Chapelle’s group
• Thorsten Joachims’s group
• Dan Roth’s group
• Hongyuan Zha’s group
• Web Learning Group, Microsoft Research
$%"&'#(
221
)!*+",$
搜索与排名 Searching and Ranking
!"#
• Information Retrieval and Mining Group, Microsoft Research Asia
• Yandex’s lab, Yahoo! Research Center
• 大连理工大学信息检索研究室
• 南开大学智能信息处理实验室
23.3 PRank
2001年，Koby Crammer与Yoram Singer[223]出PRank（Perceptron Rank）排名方法，将
检索词-文档对作为训练样本，每个训练样本对应一个相关等级。PRank 的目标是训练多个平行的
分隔超平面（感知器）将样本正确的区分开，根据PRank 训练得到的排序模型可以表示为如下形
式的判定函数：
f(x )= min
r∈{1,2,...,k}
{ω
T
x − b
r
< 0} (23.1)
其中，参数ω表示分隔超平面的法向量，b
r
表示分隔超平面的截距，r =1, 2,...,k，并且满
足b
1
<b
2
< ···<b
k−1
<b
k
=+∞。
在训练过程，PRank同时调整法向量与截距组，从而减少预测排名的损失，并由模型的保序性
与误差有界性保证收敛性。
23.4 RankSVM
2002年，Thorsten Joachims[233]基于SVM技术，出RankSVM，它是一个经典的序对型排序
学习模型。RankSVM根据样本真实相关等级对样本序对重新标记，比如对样本空间X中任意关联
于相同检索词的样本x
i
与x
j
，构成序对z
ij
=(x
i
,x
j
)，如果y
i
>y
j
，则标记z
ij
的类标为+1，否则
就标记为−1。从本质上来看，RankSVM是将排序问题转化为二元分类问题，并使用成熟的SVM技
术予以解决。
假设排名函数是线性模型
f(x)=ω
T
x,
RankSVM根据偏好序对集合P = {(i, j)|y
i
>y
j
,x
i
,x
j
∈ X}，构建一个二次优化模型：
min
ω, ξ
1
2
ω
T
ω + C
(
(i,j)∈P
ξ
ij
s.t. ω
T
(x
i
− x
j
) > 1 − ξ
ij
ξ
ij
≥ 0, ∀(i, j) ∈ P
(23.2)
目标函数中，ω
T
ω反映了超平面的间隔，ξ
ij
表示松弛变量。
$%"&'#(
222
)!*+",$
23.5. IR-SVM
!"#
RankSVM模型能够利用复杂特征进行排序，并取得良好的排序效果，但是它存在一个致命的
缺陷：模型训练时间长。由于模型是序对型，对于大小为n的训练集，组成大约n
2
个样本序对，给
训练速度带来巨大的负面影响。对此，[87, 234]出改进，降低训练复杂度。
由于RankSVM采用单一的判别函数对所有检索词排序，不具有普遍适用性，对其排序
性能构成负面影响。为此，[235]基于RankSVM，对每个检索词训练一个基本排序模型，使
用前向分步加法模型集成基本排序模型。假设训练集包含m个检索词S = {(x
(i)
,y
(i)
)}
m
i=1
，其
中，x
(i)
= {x
(i)
1
,...,x
(i)
n
i
}表示第i个检索词的关联文档特征向量集合，n
i
表示关联文档的数目，
x
(i)
j
∈ R
d
表示第j个关联文档的特征向量，y
(i)
= {y
(i)
1
,...,y
(i)
n
i
}表示与x
(i)
对应的相关等级标记。验
证集是V = {(x
(k)
,y
(k)
)}
K
k=1
，其中K 表示验证集中包含的检索词总数。具体步骤如下：
（1） 选择(x
(i)
,y
(i)
),i =1,...,m作为独立的训练数据集，在每个独立训练集上应用RankSVM训
练排序模型，构成m个基本排序模型{f
(i)
}
m
i=1
。
（2） 对{f
(i)
}
m
i=1
基本模型重新排列，构成一个有序队列π，并选择第一个排序模型记为f，计
算f在验证集上的平均性能mp，将f添加至候选排序模型集合F = {f}。
（3） 从有序队列π中选取第二个模型f
′
，如果f + f
′
在验证集上的平均性能mp
′
≥ mp，则更
新f = f + f
′
, mp = mp
′
，将f
′
添加到排序模型集合F = {f,f
′
}；如果f + f
′
的平均性
能mp
′
< mp，则选择π下一个模型，直至遍历尽全部基本排序模型。
（4） 将候选排序模型集中所有候选排序模型加和，得到最终排序模型F，并计算F在验证集上的
平均性能mp
max
。
（5） 重复执行以上三个步骤T 次，将每次迭代获取的最终候选排序模型在验证集上的平均性能降
序排列，选择处于中间位置的mp
max
对应的排序模型作为学习得到的最终排序模型。
[235]出的模型时间复杂度为O((M/m)
2
×m)=O(M
2
/m)相比RankSVM 的O(M
2
) 升了m
倍，易于训练大规模数据，其中M表示训练数据集中样本总量。此外，由于每次选择模型时仅仅
保留对平均性能有贡献的基本模型，因此排序的平均精度有所升。
23.5 IR-SVM
[236]Adapting Ranking SVM to Document Retrieval
23.6 SVM-MAP
[231]A support vector method for optimizing average precision
$%"&'#(
223
)!*+",$
搜索与排名 Searching and Ranking
!"#
23.7 RankNet
2005年，微软研究院的Chris Burges等人[225]在第22届国际机器学习会议上出RankNet算
法。 它 是 一 种典 型 的序 对型 排 序学 习 方法， 以 神 经网 络 生成 模 型的 假 设空 间， 以 样本 序 对的 真 实
相关等级构建偏好概率模型和交叉熵损失函数，利用BP算法更新网络权值、优化调整模型参数。
RankNet算法是一种新颖有效的排序模型，据信已纳入微软Bing搜索引擎的核心搜索框架。
23.7.1. 交熵损失函数
给定任意一组文档对d
i
,d
j
，它们的真实相关等级分别是y
i
,y
j
，对两者的相关等级差值y
i
−y
j
应
用Logistic变换，表示“人们偏好d
i
甚至d
j
的概率”：
p(d
i
≻ d
j
)=p
ij
=
1
1+e
−(y
i
−y
j
)
(23.3)
文档d
i
的等级与d
j
的等级差值越大，则人们偏好d
i
甚于d
j
的可能性越大。偏好概率关于等级差值
呈S形分布，当y
i
= y
j
，两个文档相关等级相同时，偏好概率为p
ij
=0.5，表现出的不确定最强。
当y
i
>y
j
时，偏好概率大于0.5，断定“文档d
i
比文档d
j
更相关”的可信性更高；反之，偏好概率小
于0.5，断言“文档d
j
比文档d
i
更相关”更可信。
根据真实偏好概率的定义可以推知
y
i
− y
j
= log
p
ij
1 − p
ij
(23.4)
对任意的三个文档d
i
,d
j
,d
k
，由等式y
i
− y
k
=(y
i
− y
j
)+(y
j
− y
k
)，我们得到下面形式的关系式
p
ik
=
p
ij
p
jk
p
ij
p
jk
+(1− p
ij
)(1 − p
jk
)
(23.5)
可以证明：对于有限的训练样本，仅仅计算相邻样本对的偏好概率，便可唯一确定任意一个训练样
本对的偏好概率。
定理23. 1. 给定一组样本x
i
,i=1,...,n，自然数集合{1,...,m}的排列组合π。任取π两个相邻位
置(i, i + 1)，记k = π(i),j = π(i + 1)，利用Logistic 变换可以计算后验邻接概率p
kj
。给定任意一个
邻接概率集合，可以唯一确定任意一个样本对x
i
,x
j
的后验目标概率p
ij
，反之亦然。
当 p
ij
= p
jk
= p 时有关系式
p
ik
=
p
2
p
2
+(1− p)
2
=
p
2
2p
2
− 2p +1
,p∈ [0, 1] (23.6)
成立。根据组合概率p
ik
同p的关系（见图23.2）， 只 有 在 p = {0, 0.5, 1}时，才有组合概率p
ik
= p。
当p<0.5时，组合概率p
ik
<p；当p>0.5时，组合概率p
ik
> 0.5。由分析可知，偏好概率模型是
一致的。
$%"&'#(
224
)!*+",$
23.7. RankNet
!"#
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
图 23.2: 偏好概率模型
!4
!2
2
4
1
2
3
4
5
p"0 p"0.5 p"1
图 23.3: 交叉熵损失函数
假设排序模型是连续函数f : R
m
-→ R，对评分结果经过Logistic函数变换，可用于估计真实偏
好概率：
Op
ij
=
1
1+e
−o
ij
(23.7)
其中，o
ij
= f(θ,x
i
) − f(θ,x
j
)表示样本序对的预测差值。
排序模型预测结果同真实结果之间的差异可以使用概率分布的交叉熵距离表示，并直接用于度
量排序模型在样本序对(x
i
,x
j
)上的预测损失
L
ij
= −
#
p
ij
log Op
ij
+(1− p
ij
) log(1 − Op
ij
)
$
= p
ij
log(1 + e
−o
ij
)+(1− p
ij
) log(1 + e
o
ij
)
= log(1 + e
o
ij
) − p
ij
o
ij
(23.8)
交叉熵损失函数L
ij
与真实偏好概率p
ij
密切相关（见图23.3）， 偏 好 概 率 p
ij
取值不同，损失函数
随预测差值的变化趋势也不同。当p
ij
=0.5 时，表明样本序对的真实排名相同，损失函数关于样
本序对的预测差值o
ij
对称。当o
ij
=0时损失量最小L
ij
= log 2，仍大于零。
23.7.2. 训练
RankNet算法使用一个三层神经网络表示排序模型
f(θ,x)=ϕ
E
b +
h
"
l=1
υ
l
φ
l
*
b
l
+
m
"
k=1
ω
kl
x
k
+
F
(23.9)
其中，输入层有m个输入节点，隐藏层有h个节点，输出层只有一个输出节点。隐藏层的刺激函
数为φ
1
,...,φ
h
，输出层的刺激函数ϕ，均为Sigmoid函数。b
1
,...,b
h
与b都是偏置量。参数ω
kl
表示
第k个输入节点到第l个隐藏节点的连接权值，υ
l
则是第l个隐藏节点到输出节点的权值。x
k
表示输
入向量x的第k个元素。
RankNet算法使用样本训练集{x
i
,y
i
}
n
i=1
上的偏好序对
P = {(i, j) | y
i
≥ y
j
,i,j =1,...,n} (23.10)
$%"&'#(
225
)!*+",$
搜索与排名 Searching and Ranking
!"#
Algorithm 10 RankNet算法
Input: 训练集{(x
i
,x
j
),p
ij
, (i, j) ∈ P}，学习率η，迭代次数T ，初始网络参数θ
0
for t =1,...,T do
for 对任意的(i, j) ∈ P do
1. 前向传播：以(x
i
,x
j
)为输入，计算当前网络的输出值
f
i
= f(θ
t−1
,x
i
)
f
j
= f(θ
t−1
,x
j
)
2. 反向传播：使用梯度下降法更新网络参数
θ
t
= θ
t−1
− η∇L
ij
end for
end for
Output: 排序模型f(θ
T
,x)
作为网络模型训练样本的索引集，每次训练时从训练集中选取一对样本(x
i
,x
j
)作为输入，通过前
向传播（Forward Propagation）在整个网络扩散，产生一对网络输出(f(θ,x
i
),f(θ,x
j
))。
假设网络模型的刺激函数都是连续可微的，可以计算网络模型f(θ,x)交叉熵损失函数的梯度
∇
θ
L
ij
=
∂L
ij
∂o
ij
[∇
θ
f
i
−∇
θ
f
j
] (23.11)
其中，f
i
= f(θ,x
i
),f
j
= f(θ,x
j
)。根据f
i
关于b, υ
l
,b
l
, ω
kl
的一阶导数
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎩
∇
b
f
i
= ϕ
′
(θ,x
i
) ≡∇
(i)
1
∇
υ
l
f
i
= ϕ
′
(θ,x
i
)φ
l
(b
l
, ω,x
i
)=∇
(i)
1
φ
l
(b
l
, ω,x
i
)
∇
b
l
f
i
= ϕ
′
(θ,x
i
)υ
l
φ
′
l
(b
l
, ω,x
i
)=∇
(i)
1
υ
l
φ
′
l
(b
l
, ω,x
i
) ≡∇
(i)
2
∇
ω
kl
f
i
= ϕ
′
(θ,x
i
)υ
l
φ
′
l
(b
l
, ω,x
i
)x
ik
= ∇
(i)
2
x
ik
(23.12)
可以推导得到损失函数L
ij
的梯度：
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎩
∇
b
L
ij
= L
′
ij
#
∇
(i)
1
−∇
(j)
1
$
∇
υ
l
L
ij
= L
′
ij
#
∇
(i)
1
φ
l
(b
l
, ω,x
i
) −∇
(j)
1
φ
l
(b
l
, ω,x
j
)
$
∇
b
l
L
ij
= L
′
ij
#
∇
(i)
2
−∇
(j)
2
$
∇
ω
kl
L
ij
= L
′
ij
#
∇
(i)
2
x
ik
−∇
(j)
2
x
jk
$
(23.13)
观察可以发现，神经网络中参数更新的方向是从输出层开始逐层往后直至输入层，这种根据梯
度下降法更新参数的流程因此称作反向传播（Backward Propagation）：
θ ← θ −η∇L
ij
(23.14)
$%"&'#(
226
)!*+",$
23.7. RankNet
!"#
其中，η表示学习率。
在训练模型时，RankNet采用了一种简化的概率化规则
p
ij
=
⎧
⎨
⎩
1 y
i
>y
j
0.5 y
i
= y
j
(23.15)
23.7.3. 批量更新
原始的RankNet算法使用的是随机梯度下降法，每次更新网络模型参数的粒度都是单个样本
对，梯度计算的复杂度是O(N
2
)，其中N 表示平均每个检索词的关联文档数目。2007年，Burges等
人[226]在原始RankNet算法的基础上设计出一种高效的训练方法，他们出将梯度计算的中间结
果保存再利用，使用累加形式的梯度值对参数一次性更新，参数更新的粒度是检索词层面。这种方
法由此称为批量梯度下降法，计算复杂度仅为O(N)。
Algorithm 11 批量更新版RankNet算法
Input: 训练集Q, X, Y，学习率η，迭代次数T ，初始网络参数θ
0
for t =1,...,T do
for 任意的检索词q ∈ Q do
for 检索词q的任意关联文档x do
前向传播：以x为输入，计算并保存所有隐藏节点与输出节点的输出值
end for
反向传播：使用批量梯度下降法更新网络参数
θ
t
= θ
t−1
− η
"
i
E
λ
i
∂f
i
∂θ
F
6
6
6
θ
t−1
end for
end for
Output: 排序模型f(θ
T
,x)
网络模型在所有样本序对P上的预测损失可以表示成一种加和形式
L =
"
(i,j)∈P
L
ij
(23.16)
对于单个样本序对(x
i
,x
j
)，我们使用L
ij
关于函数值f
i
,f
j
的导数可以推知：
∂L
∂θ
=
"
(i,j)∈P
*
∂L
ij
∂f
i
∂f
i
∂θ
+
∂L
ij
∂f
j
∂f
j
∂θ
+
(23.17)
为方便记，我们定义两个指标集P
i∗
与P
∗i
：
P
i∗
= {j | (i, j) ∈ P } , P
∗i
= {j | (j, i) ∈ P } (23.18)
$%"&'#(
227
)!*+",$
搜索与排名 Searching and Ranking
!"#
索引集可以拆分如下：
"
(i,j)∈P
=
n
"
i=1
"
j∈P
i∗
=
n
"
j=1
"
i∈P
∗j
(23.19)
根据索引集的拆分形式，重新整理等式(23.17)可得
∂L
∂θ
=
(
i
(
j∈P
i∗
∂L
ij
∂f
i
∂f
i
∂θ
+
(
j
(
i∈P
∗j
∂L
ij
∂f
j
∂f
j
∂θ
=
(
i
∂f
i
∂θ
(
j∈P
i∗
∂L
ij
∂f
i
+
(
j
∂f
j
∂θ
(
i∈P
∗j
∂L
ij
∂f
j
=
(
i
∂f
i
∂θ
#
(
j∈P
i∗
∂L
ij
∂f
i
+
(
j∈P
∗i
∂L
ji
∂f
i
$
(23.20)
对于每个数据样本x
i
，经过网络模型的一次前向传播计算其输出分值f
i
，并且每个样本都涉及两个
加和形式的梯度运算
λ
i
=
"
j∈P
i∗
∂L
ij
∂f
i
+
"
j∈P
∗i
∂L
ji
∂f
i
,i=1,...,n (23.21)
两个加和项的计算量与数据样本相关等级数目、每个相关等级的文档数目有关，相对计算量较小。
每个数据样本最后都需要计算一个关于参数θ梯度值。
23.8 LambdaRank
排名标准度量指标通常是非平滑的，对直接优化形成阻碍。对此，在机器学习领域，有两种常
用的间接优化的方法：确定标准度量指标的平滑边界函数或者近似函数，通过优化边界函数或近似
函数，实现间接优化标准度量指标的目的。无论是界函数还是近似函数都与真实的标准度量指标存
在一定的差距，间接优化的结果与真实最优解不一致性。
2007年，Burges等人[226]分析排序性能、损失函数及样本序对排名间的关系，巧妙地避开非
平滑函数梯度的计算，直接构造具有期望性质的梯度函数（Lamda函数类），并将这种思想应用
到RankNet算法，基于非平滑的标准度量指标（NDCG）训练排序模型。他们直接定义了损失函数
关于预测结果的梯度，并使用希腊字母λ表示，所设计的算法由此称为LambdaRank。
23.9 LambdaMART
2010年，Burges[117, 237]使用梯度升决策树（Gradient Boost Decision Tree，也称MART），
训练排序模型，在LambdaRank 算法的基础上，发展成为高效的LambdaMART算法，并一举赢
得Yahoo!排序学习挑战赛（Learning To Rank Challenge）第一轮比赛。LambdaRank算法改进
于RankNet算法，都是基于神经网络构建的排序模型，而LambdaMART基于回归决策树，可视为
决策树版本的LambdaRank算法。
$%"&'#(
228
)!*+",$
23.10. GBRank
!"#
23.10 GBRank
[238]A Regression Framework for Learning Ranking Functions Using Relative Relevance
Judgments
23.11 GBlend
Learning to Blend by Relevance[239]
23.12 QBRank
A General Boosting Method and its Application to Learning Ranking Functions for Web
S e arch[116]
23.13 ListNet
2007年，Cao等人[227]出的ListNet是第一个序列型排序学习方法，比逐点型、序列型排序
学习方法性能优越。ListNet算法根据Plackett-Luce模型，从排序模型预测的分值列表中计算排列
概率分布（Permutation Probability Distribution）， 将 文 档 真 实 标 记 作 为 文 档 分 值 ， 据 此 计 算 真 实
概率分布。ListNet定义了排序模型预测的概率分布与真实概率分布之间的交叉熵损失函数，利用
梯度下降法最小化损失函数，达到优化排序模型的目的。
定义23.1 (排列概率). 假设Π[n]表示由n个对象所有可能排列构成的集合，由对象分值列表Y 生成排
列π ∈ Π
n
的概率定义如下：
P (π|Y )=
n
!
i=1
φ(y
π
−1
(i)
)
n
(
k=i
φ(y
π
−1
(k)
)
,
其中y
π
−1
(i)
表示π中排第i位的对象π
−1
(i)的分值，φ > 0是一个单调递增函数。这种模型称作Luce模模模
型型型，其复杂度是O(n!)，当n 增加，会产生巨大的计算开销。
文档排名问题主要目标是确保“排名越靠前越相关”，我们来看排名前K的对象排列分布。
定义23.2 (TopK概率). 对于给定的K<n，我们如果只关注排名前K的对象，由对象分值列表Y 生
成排列π ∈ Π[n]的概率定义如下：
P (π|Y ; K)=
K
!
i=1
φ(y
π
−1
(i)
)
n
(
k=i
φ(y
π
−1
(k)
)
.
其复杂度是O(n
K
)，只需要计算n!/(n − K)!次，远远小于n!。
$%"&'#(
229
)!*+",$
搜索与排名 Searching and Ranking
!"#
ListNet算法使用的是最简的Top-1概率，根据定义由对象分值列表Y 生成排列π的Top-1概率可
表示如下
P (π|Y ; 1) =
φ(y
π
−1
(1)
)
n
(
k=1
φ(y
π
−1
(k)
)
.
假设
ˆ
Y = f(X; Θ)是模型f对训练样本的相关性预测评分列表，Y 是训练样本的真实相关性评分列
表，ListNet算法使用P(π|
ˆ
Y ; 1)近似表示P (π|
ˆ
Y )，使用P (π|Y ; 1) 近似表示P (π|Y )，通过最小化交
叉熵损失函数
L(X, Y ; Θ)=−
n
"
π
−1
(1)=1
P (π|Y ; 1) log P (π|
ˆ
Y ; 1)
训练预测模型参数Θ。
23.14 ListMLE
2008年，Xia等人[229]从损失函数的一致性出发，出一个新的序列型排序学习算法ListMLE。
它是ListNet的一个拓展，也是通过神经网络，应用梯度下降法最小化损失函数，训练出最优排名
函数。两者都是建立在Plackett-Luce概率模型之上的序列型排序学习方法，但是使用的损失函数不
同，ListNet使用的是交叉熵损失函数，而ListMLE使用的则是似然损失函数。
假设Y 是训练样本的真实相关性评分列表，根据真实相关性评分从高到低排序，可以生成一个
排列π。ListMLE方法利用TopK概率模型，定义损失函数为对数似然函数
L(X, Y ; Θ)=−log P (
ˆ
Y |X; Θ)=−log
K
!
i=1
φ(f(x
π
−1
(i)
; Θ))
n
(
k=i
φ(f(x
π
−1
(k)
; Θ))
.
23.15 FRank
FRank: A Ranking Method with Fidelity Loss[240]
23.16 BoltzRank
BoltzRank: Learning to maximize expected ranking gain[241]
23.17 SortNet
SortNet: learning to rank by a neural-based sorting algorithm[242]
$%"&'#(
230
)!*+",$
23.18. RankBoost
!"#
23.18 RankBoost
2003年，Freund等人出了RankBoost方法[164]，其基本思想源于AdaBoost[160, 161]。它根
据排序模型在样本序对上的预测误差，训练多个弱排名函数h
t
，并加权形成组合排序模型
f
T
=
T
"
t=1
α
t
h
t
,
α
t
表示弱排名模型h
t
的权重。
RankBoost使用反馈函数以真实地反映文档序关系，根据样本的原始分值对样本序对重新标
记，作为序对型训练样本的真实标记，并定义一种分类误差最小化的排名损失函数，期望训练得
到的模型的预测结果与反馈结果尽可能地一致。RankBoost是首个Boosting框架下用于排序问题
的学习算法，属于序对型排序学习方法，可应用于元搜索引擎排名聚合、协同过滤推荐系统等。
RankBoost算法可以概括如下：
Algorithm 12 RankBoost学习算法
Input: 训练集S = {q
i
,x
i
,y
i
}
m
i=1
，迭代次数T ，特征集合Φ
• 在训练集上对每个检索词构建一组序对集P
i
= {(x
1
,x
2
) | y
1
>y
2
}，初始化序对样
本X × X上的概率分布D
1
for t =1,...,T do
1. 基于样本序对的概率分布D训练弱排序模型h
t
: X -→ R
2. 给弱排序模型赋权值α
t
∈ R
3. 更新概率分布
D
t+1
(x
1
,x
2
)=D
t
(x
1
,x
2
)
exp
,
− α
t
#
h
t
(x
1
) − h
t
(x
2
)
$-
Z
t
(23.22)
其中，Z
t
是标准化因子。
end for
Output: 最终排名函数f
T
=
T
(
t=1
α
t
h
t
根据RankBoost的概率分布更新方式可知，如果h
t
能够对P中的文档序对给出正确的排名，也
就是说当h
t
(x
1
) − h
t
(x
2
) > 0，由于α
t
> 0，相应地需要降低该序对在下轮迭代中的权重；否则，
增大权重。这个特征与Boosting技术精神是吻合的。
23.18.1. 排名误差
对于RankBoost的排名误差，可以证明“最终排名函数f
T
在初始概率分布D
1
下的排名误差有
$%"&'#(
231
)!*+",$
搜索与排名 Searching and Ranking
!"#
上界”：
L
D
1
(f
T
) ≤
T
!
t=1
Z
t
(23.23)
我们下面给出简要证明。
证明： 根据排名误差的定义：
L
D
1
(f
T
)=
"
(x
1
,x
2
)∈P
D
1
(x
1
,x
2
)I(f
T
(x
1
) ≤ f
T
(x
2
)) ≤
"
(x
1
,x
2
)∈P
D
1
(x
1
,x
2
)exp(−[f
T
(x
1
) − f
T
(x
2
)])
(23.24)
由概率分布更新策略可知：
D
t+1
(x
1
,x
2
)=D
t
(x
1
,x
2
)
exp
,
− α
t
#
h
t
(x
1
) − h
t
(x
2
)
$-
Z
t
(23.25)
将其在T +1处展开可得：
D
T +1
(x
1
,x
2
)=D
1
(x
1
,x
2
)
T
9
t=1
exp
,
− α
t
#
h
t
(x
1
) − h
t
(x
2
)
$-
/
T
9
t=1
Z
t
= D
1
(x
1
,x
2
)exp
,
T
(
t=1
−α
t
#
h
t
(x
1
) − h
t
(x
2
)
$-
/
T
9
t=1
Z
t
= D
1
(x
1
,x
2
)exp(−[f
T
(x
1
) − f
T
(x
2
)])/
T
9
t=1
Z
t
(23.26)
根据展开式，则
L
D
1
(f
T
) ≤
"
(x
1
,x
2
)∈P
D
T +1
T
!
t=1
Z
t
=
T
!
t=1
Z
t
, (23.27)
证毕。
根据排名误差上界可以推断，如果在每轮迭代过程通过选择合适的弱学习器，并给其赋予恰当
的权值，最小化标准化因子
Z
t
=
"
(x
1
,x
2
)∈P
D
t
(x
1
,x
2
)exp
,
− α
t
#
h
t
(x
1
) − h
t
(x
2
)
$-
(23.28)
则可以保证训练得到一个低排名误差的组合模型f
T
。
23.18.2. 弱学习器选择和赋权
根据上一小节的结论，弱学习器的选择与赋权的目标是最小化标准化因子：
(α
t
,h
t
) = arg min
α,h
"
(x
1
,x
2
)∈P
D
t
(x
1
,x
2
)exp
,
− α
#
h(x
1
) − h(x
2
)
$-
(23.29)
下面我们将重点介绍弱学习器选择与加权的基本思路。为方便记，在不引起混淆的情况，我们
将省略掉变量下标t。
给定弱学习器h，标准化因子是单变量α的函数，使用简单的搜索算法即可确定其唯一的最小
值点。对于特殊的弱学习器，比如二元函数h ∈ {0, 1} ，定义
W
b
=
"
(x
1
,x
2
)∈P
D(x
1
,x
2
)I(h(x
1
) − h(x
2
)=b) (23.30)
$%"&'#(
232
)!*+",$
23.18. RankBoost
!"#
则b ∈ {−1, 0, 1}，根据定义，W
+1
表示能够被h正确排序的文档序对权重，类似地，W
−1
则等于
被h错误排列的文档序对权重。
利用W
b
改写标准化因子：
Z(α)=
"
(x
1
,x
2
)∈P
D(x
1
,x
2
)exp
,
− α
#
h(x
1
) − h(x
2
)
$-
= W
−1
e
α
+ W
0
+ W
+1
e
−α
(23.31)
根据极值条件可以推得
dZ
dα
= W
−1
e
α
− W
+1
e
−α
=0 (23.32)
成立，Z(α)的最小值点为
ˆα =
1
2
log(
W
+1
W
−1
) (23.33)
如果W
+1
≥ W
−1
，则ˆα ≥ 0；否则， ˆα < 0。
将最小值点ˆα带入标准化因子
Z(ˆα)=W
0
+2
)
W
−1
W
+1
(23.34)
使用二元弱学习器h ∈ {0, 1}对文档排名，实际上是将排序问题转化为二元分类问题，直接使
用成熟的分类理论处理排名问题，适用范围受到极大的限制。我们下面将介绍另外一种常见的形
式：h ∈ [0, 1]。
给定弱学习器h ∈ [0, 1]，我们利用Z的近似（界）确定h的最优权值α。根据e
αx
的凸性可知，
如果x ∈ [0, 1]，则有下式
e
αx
≤
1+x
2
e
α
+
1 − x
2
e
−α
(23.35)
成立。对于Z(α)
Z(α)=
(
(x
1
,x
2
)∈P
D(x
1
,x
2
)exp
,
− α
#
h(x
1
) − h(x
2
)
$-
≤
(
(x
1
,x
2
)∈P
7
D(x
1
,x
2
)
1−
#
h(x
1
)−h(x
2
)
$
2
e
α
+
1+
#
h(x
1
)−h(x
2
)
$
2
e
−α
8
=(
1−ϕ
2
)e
α
+(
1+ϕ
2
)e
−α
!
O
Z(α)
(23.36)
其中，
ϕ =
"
(x
1
,x
2
)∈P
D(x
1
,x
2
)
#
h(x
1
) − h(x
2
)
$
(23.37)
表示弱学习器对x
1
与x
2
预测结果的期望间隔。
我们通过最小化Z(α)的上界函数
O
Z(α)，达到间接优化Z(α)的目的。根据极值条件
d
O
Z(α)
dα
=(
1 − ϕ
2
)e
α
− (
1+ϕ
2
)e
−α
=0 (23.38)
可以求得最小值点
ˆα =
1
2
ln
1+ϕ
1 − ϕ
(23.39)
$%"&'#(
233
)!*+",$
搜索与排名 Searching and Ranking
!"#
从而可得最优标准化因子
Z(ˆα) ≤
)
1 − ϕ
2
(23.40)
为了实现近似最小化Z，根据以上推导过程，我们选择能够最大化|ϕ|的弱学习器，即：
ˆ
h = arg max
h
|ϕ| = arg max
h
6
6
6
6
"
(x
1
,x
2
)∈P
D(x
1
,x
2
)
#
h(x
1
) − h(x
2
)
$
6
6
6
6
(23.41)
这正是RankBoost所采用的弱学习器选择与赋权方案：通过最大化期望间隔选择弱学习器，实现近
似最小化标准化因子进而最小化排序损失给弱学习器赋权。
23.18.3. 弱学习器的构造
无论是弱学习选择还是赋权都是基于指定类型的弱学习器，必然会涉及到弱学习器的构造问
题。本节主要讨论弱学习器之弱排序模型的构造方法。
构造弱排名函数h最简单也是最明了的方法是使用样本的单个排名特征f
i
作为排名函数，然而
此法的薄弱之处在排名特征对真实分值的过分依赖[164]，在诸如排名聚合之类的应用中，我们无
从得知各自的真实分值，并且不同搜索引擎所采用的评分算法不同，纵然知晓具体分值，也不能直
接使用。对于任意类型的搜索引擎，从搜索结果中我们能够获得的最具价值、最宜标准化的信息是
关联文档的相对序关系，而且更易推广，适用性也更强。鉴于此，我们主要关注基于相对序关系信
息构造弱排名函数。
[164]声称在构造弱排名函数时，忽略排名特征的具体分值，仅使用排名特征供的排序信息。
实际上，弱排名函数是依赖于具体分值f
i
(x)同一个阈值θ比较结果：
h(x)=
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
1 f
i
(x) > θ
0 f
i
(x) ≤ θ
qf
i
(x)=⊥
(23.42)
其中，θ，q ∈ {0, 1}是优化选择的参数，而f
i
(x)=⊥表示排名特征为获取x的任何信息。
根据弱排名函数的选择与赋权分析流程，如果通过优化(23.34)选择弱排名函数时间复杂度
是O(n|Φ||χ
Φ
|)。如果通过优化(23.41)选择弱排名函数，可以通过变换合并ϕ各项，从而减少时间复
$%"&'#(
234
)!*+",$
23.18. RankBoost
!"#
杂度至O(|Φ|)：
ϕ =
(
(x
1
,x
2
)∈P
D(x
1
,x
2
)
#
h(x
1
) − h(x
2
)
$
=
(
(x
1
,x
2
)∈P
D(x
1
,x
2
)h(x
1
) −
(
(x
1
,x
2
)∈P
D(x
1
,x
2
)h(x
2
)
=
(
x
1
h(x
1
)
(
x
2
∈P
1∗
D(x
1
,x
2
) −
(
x
2
h(x
2
)
(
x
1
∈P
∗2
D(x
1
,x
2
)
=
(
x
1
h(x
1
)
(
x
2
∈P
1∗
D(x
1
,x
2
) −
(
x
1
h(x
1
)
(
x
2
∈P
∗1
D(x
2
,x
1
)
=
(
x
1
h(x
1
)
#
(
x
2
∈P
1∗
D(x
1
,x
2
) −
(
x
1
∈P
∗2
D(x
2
,x
1
)
$
=
(
x
h(x)
#
(
x≻x
′
D(x, x
′
) −
(
x
′
≻x
D(x
′
,x)
$
=
(
x
h(x)π(x)
(23.43)
其中，π(x)=
(
x≻x
′
D(x, x
′
) −
(
x
′
≻x
D(x
′
,x)。对于排名特征f
i
，如果将h(x)的表达式带入ϕ，可得：
ϕ =
"
x:f
i
(x)>θ
π(x)+q
"
x:f
i
(x)=⊥
π(x) (23.44)
根据π(x)的定义可知
(
x
π(x)=
(
x
(
x≻x
′
D(x, x
′
) −
(
x
′
≻x
D(x
′
,x)=0，故而：
"
x:f
i
(x)=⊥
π(x)=−
"
x:f
i
(x)̸=⊥
π(x) (23.45)
ϕ可以进一步化简得：
ϕ =
"
x:f
i
(x)>θ
π(x) − q
"
x:f
i
(x)̸=⊥
π(x)=L − qR (23.46)
在学习弱排名函数时，遍历特征集f ∈ {f
i
}
n
i=1
，阈值列表θ ∈ {θ
j
}
J
j=1
，计算L, R，选择一个局部最
优的q ∈ {0, 1}，计算ϕ，从而优选出全局最优的参数组合。
23.18.4. 二分反馈
本小节主要考察一种特殊的反馈函数――二分反馈（Bipartite Feedback）： 在 X上存在两个不
相交的子集X
1
,X
2
，如果对于任意的x
1
∈ X, x
2
∈ X，反馈函数定义成下面的形式：
Φ(x
1
,x
2
)=
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
−1,x
1
∈ X
2
,x
2
∈ X
1
,
1,x
1
∈ X
1
,x
2
∈ X
2
,
0,x
1
∋ X
1
|x
2
∋ X
2
,
(23.47)
则用于表达偏好关系的反馈函数Φ是二分反馈。二分反馈可以很容易的推广到一般类型的反馈。
如果令Z
t
= Z
1
t
· Z
2
2
，可以推导它等价于一般形式的标准化因子：
D
t+1
(x
1
,x
2
)=D
t
(x
1
,x
2
)
exp
,
−α
t
#
h
t
(x
1
)−h
t
(x
2
)
$-
Z
t
= ω
t
(x
1
)
exp(α
t
h
t
(x
1
))
Z
1
t
· ω
t
(x
2
)
exp(α
t
h
t
(x
2
))
Z
2
t
= ω
t+1
(x
1
)ω
t+1
(x
2
)
(23.51)
$%"&'#(
235
)!*+",$
搜索与排名 Searching and Ranking
!"#
Algorithm 13 RankBoost二分反馈学习算法
Input: 训练集X上不相交的子集X
1
,X
2
，迭代次数T
• 初始化样本分布
ω
1
(x)=
⎧
⎨
⎩
1/|X
1
| ,x∈ X
1
1/|X
2
| ,x∈ X
2
(23.48)
• 根据样本权值概率分布，初始化样本序对分布D
1
(x
1
,x
2
)=ω
1
(x
1
)ω
1
(x
2
)
for t =1,...,T do
1. 基于样本序对的概率分布D
t
(x
1
,x
2
)=ω
t
(x
1
)ω
t
(x
2
)训练弱排序模型h
t
: X -→ R
2. 给弱排序模型赋权α
t
∈ R
3. 更新概率分布
ω
t+1
(x)=
⎧
⎪
⎪
⎨
⎪
⎪
⎩
ω
t
(x)
exp(α
t
h
t
(x))
Z
1
t
,x∈ X
1
ω
t
(x)
exp(−α
t
h
t
(x))
Z
2
t
,x∈ X
2
(23.49)
其中，Z
i
t
是X
i
上的标准化因子（i =1, 2）：
⎧
⎪
⎨
⎪
⎩
Z
1
t
=
(
x∈X
1
ω
t
exp(α
t
h
t
(x))
Z
2
t
=
(
x∈X
2
ω
t
exp(−α
t
h
t
(x))
(23.50)
end for
Output: 最终排名函数f
T
=
T
(
t=1
α
t
h
t
$%"&'#(
236
)!*+",$
23.18. RankBoost
!"#
在二分反馈形式的RankBoost算法中，若选择最佳的弱学习器，需要最大化ϕ，我们充分利用
二分反馈的特点，重新改写ϕ：
ϕ =
(
(x
1
,x
2
)∈P
D(x
1
,x
2
)
#
h(x
1
) − h(x
2
)
$
=
(
(x
1
,x
2
)∈P
ω(x
1
)ω(x
2
)
#
h(x
1
) − h(x
2
)
$
=
(
(x
1
,x
2
)∈P
ω(x
1
)ω(x
2
)h(x
1
) −
(
(x
1
,x
2
)∈P
ω(x
1
)ω(x
2
)h(x
2
)
=
(
x
1
∈X
1
ω(x
1
)h(x
1
)
(
x
2
∈X
2
ω(x
2
) −
(
x
2
∈X
2
ω(x
2
)h(x
2
)
(
x
1
∈X
1
ω(x
1
)
(23.52)
为方便记，我们引入新的变量：
s(x)=
⎧
⎨
⎩
+1,x∈ X
1
−1,x∈ X
2
(23.53)
故而：
ϕ =
(
x
1
∈X
1
s(x
1
)ω(x
1
)h(x
1
)
(
x
2
∈X
2
ω(x
2
)+
(
x
2
∈X
2
s(x
2
)ω(x
2
)h(x
2
)
(
x
1
∈X
1
ω(x
1
)
=
(
x
7
s(x)ω(x)h(x)
(
x
′
:s(x
′
)=−s(x)
ω(x
′
)
8
(23.54)
二分反馈的计算优势是明显的，可以将计算复杂度从O(|X
1
|·|X
2
|)降低至O(|X
1
| + |X
2
|)。
23.18.5. 泛化误差
这一小节，我们基于二元排序模型h ∈ {0, 1}与二分反馈函数Φ确立组合排序模型的泛化界。
假设Φ将样本空间X分成两个互不相交的部分X,Z，使得对任意的x ∈ X, z ∈ Z，都有Φ(x, z) > 0，
即X中样本排名高于Z。
在机器学习理论中，通常假设在样本空间X存在个未知的分布，训练数据与测试数据均
是独立同分布的样本集合。对于二分反馈排序模型，最容易想到的是假设样本序对独立同分布
于X × X上的个分布D。 实际上，训练集中样本序对独立性都得不到满足，因此需要另辟新径：
假设在集合X,Z 上各存在一个样本分布D
1
,D
2
，则原始训练集就是分别服从D
1
,D
2
的样本集合的
并。
由RankBoost算法所确定的组合排序模型f
T
(x)=
T
(
t=1
α
t
h
t
(x)，通过分值对文档排名。为分析
模型对样本序对的预测精度，我们定义
H(x, z) = sgn
.
T
"
t=1
α
t
h
t
(x) −
T
"
t=1
α
t
h
t
(z)
/
(23.55)
其中，h
t
∈ H，H ∈ C。H是二元函数类，C是函数集。
如果H(x, z) ̸=1，则表明H在(x, z) ∈ X × Z上产生预测误差，结合排序问题的概率模型，由
此我们可定义H的泛化误差：
ε(H)=
"
(x,z)∈X× Z
p(x, z)I(H(x, z) ̸= 1) = E
7
I(H(x, z) ̸= 1)
8
(23.56)
$%"&'#(
237
)!*+",$
搜索与排名 Searching and Ranking
!"#
可以证明泛化误差的定义与测试误差是一致的。对于测试样本集合T
X
× T
Z
，T
X
= {x
1
,...,x
p
}，
T
Z
= {z
1
,...,z
p
}，则H的期望测试误差如下：
E
7
1
pq
p
(
i=1
q
(
j=1
I(H(x
i
,z
j
) ̸= 1)
8
=
1
pq
p
(
i=1
q
(
j=1
E
7
I(H(x
i
,z
j
) ̸= 1)
8
=
1
pq
p
(
i=1
q
(
j=1
(
(x
i
,z
j
)∈T
X
×T
Z
p(x
i
,z
j
)
7
I(H(x
i
,z
j
) ̸= 1)
8
=
1
pq
p
(
i=1
q
(
j=1
ε(H)
= ε(H)
(23.57)
假设训练样本是S
X
× S
Z
，S
X
= {x
1
,...,x
m
}，S
Z
= {z
1
,...,z
n
}，类似地可以给出H的训练
误差：
ˆε(H)=
1
mn
m
"
i=1
n
"
j=1
I(H(x
i
,z
j
) ̸= 1) (23.58)
我们的目标是证明：训练误差ˆε(H)以很高的概率逼近于泛化误差ε(H)，意味着组合排序模型
在训练集上的表现具有足够的代表性，无论学习算法选择何种组合排序模型，模型的训练误差都能
够精确地估计其泛化误差。换言之，对任意η > 0，都存在一个小量ϵ > 0使得：
p
*
∃H ∈ C : |ˆε (H) − ε(H)| > ϵ
+
= p
.
∃H ∈ C :
6
6
6
6
1
mn
m
(
i=1
n
(
j=1
I(H(x
i
,z
j
) ̸= 1) −
(
(x,z)∈X×Z
p(x, z)I(H(x, z) ̸= 1)
6
6
6
6
> ϵ
/
≤ η
(23.59)
整理绝对值内的量可得：
1
mn
m
(
i=1
n
(
j=1
I(H(x
i
,z
j
) ̸= 1) −
(
(x,z)∈X×Z
p(x, z)I(H(x, z) ̸= 1)
=
1
mn
m
(
i=1
n
(
j=1
I(H(x
i
,z
j
) ̸= 1) −
(
x∈X
(
z∈Z
p(x)p(z)I(H(x, z) ̸= 1)
=
7
1
mn
m
(
i=1
n
(
j=1
I(H(x
i
,z
j
) ̸= 1) −
1
m
m
(
i=1
(
z∈Z
p(z)I(H(x
i
,z) ̸= 1)
8
+
7
1
m
m
(
i=1
(
z∈Z
p(z)I(H(x
i
,z) ̸= 1) −
(
x∈X
(
z∈Z
p(x)p(z)I(H(x, z) ̸= 1)
8
=
1
m
m
(
i=1
7
1
n
n
(
j=1
I(H(x
i
,z
j
) ̸= 1) −
(
z∈Z
p(z)I(H(x
i
,z) ̸= 1)
8
+
(
z∈Z
p(z)
7
1
m
m
(
i=1
I(H(x
i
,z) ̸= 1) −
(
x∈X
p(x)I(H(x, z) ̸= 1)
8
(23.60)
为了使用分类泛化误差的结果，我们定义F : X × Z → {0, 1}，表示函数H给(x, z)的排序是否
正确，即F (x, z)=I(H(x, z) ̸= 1)，则我们可以重写上面的等式为：
1
m
m
"
i=1
7
1
n
n
"
j=1
F (x
i
,z
j
) −
"
z∈Z
p(z)F (x
i
,z)
8
+
"
z∈Z
p(z)
7
1
m
m
"
i=1
F (x
i
,z) −
"
x∈X
p(x)F (x, z)
8
(23.61)
给定z ∈ Z，则F (x, z)可以看做是一个单变量二元函数，假设F
z
表示所有给定z的二元函数类，
则(23.61)第二部分中F 取自
P
z
F
z
。根据Vapnik[72]，对于任意η > 0，存在个与训练集S
X
大小m、
$%"&'#(
238
)!*+",$
23.18. RankBoost
!"#
错误概率η和函数类
P
z
F
z
的VC维d
1
有关的ε
1
(m, η,d
1
)，使得
p
.
∃F ∈
B
z
F
z
:
6
6
6
6
1
m
m
"
i=1
F (x
i
,z) −
"
x∈X
p(x)F (x, z)
6
6
6
6
> ε
1
(m, η,d
1
)
/
< η (23.62)
成立，其中：
ε
1
(m, η,d
1
)=2
'
d
1
(ln(2m/d
1
) + 1) − ln(η/9)
m
(23.63)
对于(23.61)第一部分，我们可以得到类似的结论：对于任意η > 0，存在ε
2
(n, η,d
2
)，使得
p
.
∃F ∈
m
B
i=1
F
x
i
:
6
6
6
6
1
n
n
"
j=1
F (x
i
,z
j
) −
"
z∈Z
p(z)F (x
i
,z)
6
6
6
6
> ε
2
(n, η,d
2
)
/
< η (23.64)
成立，其中：
ε
2
(n, η,d
2
)=2
'
d
2
(ln(2n/d
2
) + 1) − ln(η/9)
n
(23.65)
对于给定的z ∈ Z：
F (x, z)=I(H(x, z) ̸= 1)
= I
.
T
(
t=1
α
t
h
t
(x) ≤
T
(
t=1
α
t
h
t
(z)
/
= I
.
T
(
t=1
α
t
h
t
(x) − b ≤ 0
/
(23.66)
其中，b =
T
(
t=1
α
t
h
t
(z)是关于z的常数。Freund与Schapire[160]基于T、弱排名函数类H的VC维d ≥
2 给出此函数类
P
z
F
z
的VC维上界：
d
1
≤ 2(d + 1)(T + 1) log
2
(e(T + 1)) (23.67)
类似地，我们可以推断：
d
2
≤ 2(d + 1)(T + 1) log
2
(e(T + 1)) (23.68)
由此，我们可以得到下面的定理：
定理23.2. 假设C是形如
H(x, z) = sgn
.
T
"
t=1
α
t
h
t
(x) −
T
"
t=1
α
t
h
t
(z)
/
的函数集，其中h
t
∈ H，并且其VC维V
H
= d。假设S
X
,S
Z
分别是大小为m, n的训练样本样本，
H ∈ C，对任意的η > 0，概率不等式
p
.
|ˆε(H) − ε(H)| > 2
'
d
′
(ln(2m/d
′
) + 1) − ln(η/18)
m
+2
'
d
′
(ln(2n/d
′
) + 1) − ln(η/18)
n
/
≤ η
(23.69)
成立，其中
d
′
= 2(d + 1)(T + 1) log
2
(e(T + 1)). (23.70)
$%"&'#(
239
)!*+",$
搜索与排名 Searching and Ranking
!"#
23.19 SSRankBoost
[243]A Boosting Algorithm for Learning Bipartite Ranking Functions with Partially Labeled
Data
23.20 AdaRank
2007年，Xu等人[165]使用Boosting技术，发明了AdaRank排名算法。AdaRank根据弱排名函
数备选集合（比如特征集合，每个特征都可以作为独立的排名函数）中的备选排名函数在训练数据
集上的平均性能，选取一组弱排名函数，并根据其平均性能确定入选的弱排名函数的权值。一般
地，如果排名函数平均性能越高，则相应的权值越大，反之亦反。
AdaRank算法是一种迭代学习算法，每次迭代选取一个弱排名函数（弱学习），最终以线性加
权的方式组合各个弱排名函数，形成最终排序模型。在训练过程中，需要根据组合形式的弱排名函
数在各个检索词上的表现，调整各个检索词的概率权值。如果组合形式的弱排名函数在检索词上
的表现越好，则降低该检索词的概率权值，反之则升其权值，从而总能在下轮迭代中实现重点
突破。AdaRank算法承袭了Boosting技术弱学习能力，能够将一组弱排名函数集成一个强学习器
（排序模型）。
由于NDCG、MAP等排名精度评价标准非平滑性，我们无法基于标准升技术直接推导弱
排名函数最优权值的解析形式。传统的优化算法，如梯度下降法、坐标下降法，均以迭代方式逐
步优化目标函数，只是在每次更新参数时确保目标（损失函数）保持下降趋势[165]。从这个意义
上来说，任何能够使总体损失持续减少的参数更新策略都是合适的（在收敛速度上有所区别）。
AdaRank从AdaBoost算法获得启发，使用了一种形式相似的弱排名函数权值公式，采用先猜测再
证明的方式，从理论上证明，在一定条件下，可以保证训练过程损失持续减少，从而实现优化损失
函数的目的。
下面我们证明AdaRank算法的一个重要性质：只要满足
e
−δ
t
min
)
1 − ϕ
2
t
< 1 (23.75)
其中，
⎧
⎨
⎩
δ
t
i
= E(x
i
,y
i
,f
t−1
+ α
t
h
t
) − E(x
i
,y
i
,f
t−1
) − α
t
E(x
i
,y
i
,h
t
)
δ
t
min
=min
i∈{1,...,m}
δ
t
i
则模型的排序性能可以持续改善。
证明： 根据α
t
, ϕ
t
的定义可知：
e
α
t
=
'
1+ϕ
t
1 − ϕ
t
(23.76)
最终排序模型f
T
在训练集上的平均性能
1
m
m
(
i=1
E(x
i
,y
i
,f
T
)是衡量AdaRank算法的重要标准，
$%"&'#(
240
)!*+",$
23.20. AdaRank
!"#
Algorithm 14 AdaRank算法
Input: 训练集S = {q
i
,x
i
,y
i
}
m
i=1
，迭代次数T ，标准评价指标E，检索词概率分布P
1
(i)=1/m，
特征集合Φ
for t =1,...,T do
1. 根据训练集S上的检索词概率分布P
t
，从特征集合中选择出弱排名函数h
t
：
h
t
= arg max
h
t
∈Φ
ϕ
t
(23.71)
其中，
ϕ
t
=
m
"
i=1
P
t
(i)E(x
i
,y
i
,h
t
)
2. 给弱排名函数h
t
赋最优权值α
t
：
α
t
=
1
2
log
1+ϕ
t
1 − ϕ
t
(23.72)
表示平均性能。
3. 组合弱排名函数f
t−1
与h
t
：
f
t
= f
t−1
+ α
t
h
t
(23.73)
4. 根据f
t−1
在各个检索词上的表现，更新检索词的分布P
t+1
:
P
t+1
(i)=
1
Z
t
exp{−E(x
i
,y
i
,f
t
)} (23.74)
其中，
Z
t
=
m
"
i=1
exp{−E(x
i
,y
i
,f
t
)}
end for
Output: 最终排名函数f
T
=
T
(
t=1
α
t
h
t
$%"&'#(
241
)!*+",$
搜索与排名 Searching and Ranking
!"#
可以用于说明AdaRank算法持续改善模型性能。下面我们从模型的平均性能指标的下界出发进行
深入分析。
由于模型中用于衡量排序性能的指标E ∈ [0, 1]，所以e
−E
≥ 1 − E，从而有：
1
m
m
(
i=1
E(x
i
,y
i
,f
T
) ≥
1
m
m
(
i=1
?
1 − exp{−E(x
i
,y
i
,f
T
)}
@
=1−
1
m
m
(
i=1
exp{−E(x
i
,y
i
,f
T
)}
=1−
1
m
Z
T
(23.77)
建立了模型平均性能指标同Z
T
的关系，进而转向对Z
T
上界的分析。
由于
−E(x
i
,y
i
,f
T
)=
#
− E(x
i
,y
i
,f
T
)+α
T
E(x
i
,y
i
,h
T
)+E(x
i
,y
i
,f
T −1
)
$
+
#
− α
T
E(x
i
,y
i
,h
T
) − E(x
i
,y
i
,f
T −1
)
$
可得：
Z
T
=
m
(
i=1
exp{−E(x
i
,y
i
,f
T
)}
=
m
(
i=1
7
e
−δ
T
i
exp{−α
T
E(x
i
,y
i
,h
T
)}exp{−E(x
i
,y
i
,f
T −1
)}
8
≤ e
−δ
T
min
Z
T −1
m
(
i=1
7
exp{−E(x
i
,y
i
,f
T −1
)}
Z
T −1
exp{−α
T
E(x
i
,y
i
,h
T
)}
8
= e
−δ
T
min
Z
T −1
m
(
i=1
P
T
(i)exp{−α
T
E(x
i
,y
i
,h
T
)}
! e
−δ
T
min
Z
T −1
W
T
(23.78)
由于
−α
T
E(x
i
,y
i
,h
T
)=λ(−α
T
)+(1− λ)α
T
其中，
λ =
1+E(x
i
,y
i
,h
T
)
2
根据函数e
x
的凸性可得：
e
−α
T
E(x
i
,y
i
,h
T
)
≤
1+E(x
i
,y
i
,h
T
)
2
e
−α
T
+
1 − E(x
i
,y
i
,h
T
)
2
e
α
T
(23.79)
那么：
W
T
=
m
(
i=1
P
T
(i)exp{−α
T
E(x
i
,y
i
,h
T
)}
≤
m
(
i=1
P
T
(i)
?
1+E(x
i
,y
i
,h
T
)
2
e
−α
T
+
1−E(x
i
,y
i
,h
T
)
2
e
α
T
@
=
m
(
i=1
7
P
T
(i)
1+E(x
i
,y
i
,h
T
)
2
8
e
−α
T
+
m
(
i=1
7
P
T
(i)
1−E(x
i
,y
i
,h
T
)
2
8
e
α
T
=
1+ϕ
T
2
e
−α
T
+
1−ϕ
T
2
e
α
T
=
)
1 − ϕ
2
T
(23.80)
$%"&'#(
242
)!*+",$
23.20. AdaRank
!"#
从而可推知：
Z
T
≤ e
−δ
T
min
Z
T −1
)
1 − ϕ
2
t
= Z
T −2
T
9
t=T −1
e
−δ
t
min
)
1 − ϕ
2
t
= Z
1
T
9
t=2
e
−δ
t
min
)
1 − ϕ
2
t
(23.81)
由于
Z
1
=
m
(
i=1
exp{−E(x
i
,y
i
, α
1
h
1
)}
≤ e
−δ
1
min
m
(
i=1
exp{−α
1
E(x
i
,y
i
,h
1
)}
= m · e
−δ
1
min
m
(
i=1
P
1
(i)exp{−α
1
E(x
i
,y
i
,h
1
)}
≤ m · e
−δ
1
min
)
1 − ϕ
2
1
(23.82)
通过上面推导结果可知：
Z
T
≤ m
T
!
t=1
e
−δ
t
min
)
1 − ϕ
2
t
(23.83)
因而可得：
1
m
m
"
i=1
E(x
i
,y
i
,f
T
) ≥ 1 −
T
!
t=1
e
−δ
t
min
)
1 − ϕ
2
t
(23.84)
根据不等式(23.84)可知，只要在每步迭代保证：
e
−δ
t
min
)
1 − ϕ
2
t
< 1 (23.85)
成立，则排序模型的平均性能下界趋于上升，由此表明AdaRank算法使用的排名函数加权、检索
词分布更新策略可以持续改善模型性能。
弱排名函数的选取（见(23.71)）与赋权（见(23.72)）、检索词分布更新（见(23.74)）、 前 向 分 步
加法模型的使用（见(23.73)）同AdaRank算法的基本性质（见(23.85)）是紧密相连的，目标一致：
确保算法能够持续地改善排序性能。
23.20.1. AdaRank算法的缺陷
AdaRank属于一种启发式方法，将标准度量指标嵌入到弱排名函数权值的计算与检索词概率
分布更新过程，以迭代的方式，依据平均性能指标选择弱排名函数。AdaBoost算法为实现有的放
矢地训练模型，使用基于单个样本的概率分布，适应性地调整各个样本的权值。如果样本在上一轮
模型评估中表现突出，在下轮迭代中则会降低其权值，否则，升其权值。AdaRank则不同，它
基于检索词概率分布进行适应性调整，但调整的颗粒度要大得多，对排名精度的估计因此略显粗
糙。此外，AdaRank模型是在“一定条件下”收敛，如果条件无法满足，模型则可能无法收敛。事
实证明，这种忧虑确实存在[244, 245]。
$%"&'#(
243
)!*+",$
搜索与排名 Searching and Ranking
!"#
23.20.2. 改进的AdaRank算法
对于实时搜索环境，排名效果（Effectiveness）与排名效率（Efficiency）同等重要，然而目前
绝大多数排名算法均以排名效果为中心，对于排名效率则不甚关心。Wang等人[246, 247]尝试以最
短的时间供最相关的文档集合，兼顾排名效果与效率。为此，他们出一种新颖的排序学习方法
――级联排名模型（Cascade Ranking Model, CRM）， 在 Boosting技术框架下，学习一组弱排名函
数。 为 了 减 少 在大 量 不相 关 文 档 集 上 的评 分 成 本， CRM在每一个阶段，使用剪枝函数（Pruning
Function）， 亦 称 剪 枝 准 则 ， 剔 除 部 分 不 相 关 文 档 ， 将 主 要 精 力 用 于 训 练 相 关 性 较 高 的 文 档 集 合 上 ，
以期在训练结束时取得的文档集都是最相关的，由此实现同时最大化排名精度、最小化时间成本的
目的。
排序学习任务属于监督学习的范畴，因此需要对每个样本确定一个“标准答案”。一般而言，
样本都是人工标记，需要大量的人力支持。为了减少人工标记的成本，Ren 等人[248]将Kullback-
Leibler重要性估计流程（Importance Estimation Procedure，KLIEP）应用于实现自动标记，
把AdaRank改造成一个直推型模型（Transductive Model）， OHSUMED数据集上的表现良好。
Kao与Fahn[249]将AdaRank应用于面部表情（Facial Expression）分类，分类效果很好。
23.21 NDCGBoost
Learning to Rank by Optimizing NDCG Measure[245]
23.22 MPBoost
A General Magnitude-Preserving Boosting Algorithm for Search Ranking[250]
23
.
23 Ranking Refinement
Ranking Refinement and Its Application for Information Retrieval[251]
23.24 RankCosine
逐点型、序对型排序学习方法所使用的损失函数是建立在单个文档、文档序对层面的，用于衡
量排序模型性能的标准评价指标，如MAP、NDCG均是建立在文档列表层面，它们具有明显的不
一致性，通过最小化逐点型、序对型损失函数很难实现改善标准评价指标的目的。
$%"&'#(
244
)!*+",$
23.24. RankCosine
!"#
23.24.1. 余弦损失函数
2008年，Qin等人[228]对排序模型预测的文档分值、文档真实相关等级，使用夹角余弦距离度
量排序模型在文档列表层面上的性能。假设预测模型为f，它在给定检索词q关联文档集合下的余
弦损失函数定义如下：
L(f | q)=
1
2
E
1 −
δ(q)
T
f(q)
∥δ(q)∥∥f (q)∥
F
(23.86)
其中，δ是一个单调函数，δ(q)是检索词q下所有关联文档真实相关等级的δ变换结果，是一个向量；
f(q)是排序模型对所有关联文档的预测结果，也是一个向量。
如果预先对训练集下每个检索词的关联文档的真实相关等级做标准化处理
δ(q) ←
δ(q)
∥δ(q)∥
(23.87)
则余弦损失函数可以重新写作
L(f | q)=
1
2
E
1 −
δ(q)
T
f(q)
∥f(q)∥
F
(23.88)
23.24.2. 基排名函数的赋权
RankCosine算法[228]是一种序列性排名学习算法，建立在Boosting框架下，排序模型为广义
加法模型（Generalized Additive Model, GAM），每次迭代均从基排名函数（弱学习器）类中选
择一个当前最佳的基排名函数，组合到当前模型中，并通过不断更新检索词权值概率分布，实现由
易到难的学习目标，逐渐“理解”不易学习的检索词样本，最终训练出一个性能优良的排序模型
（强学习器）。
假设当前排序模型是f
t−1
，则在下次迭代时学习一个基排名函数h
t
，添加至当前加法模型
f
t
= f
t−1
+ α
t
h
t
(23.89)
其中，基排名函数h
t
及其权值α
t
是能够最小化f
t
在训练集上经验损失的最优参数组
(h
t
, α
t
) = arg min
h∈H,α
"
q
L(f
t−1
+ αh | q) (23.90)
RankCosine算法的基排名函数类是有限集合，每次选择基函数时，通过遍历整个假设空间，
选择一个最优的权值，通过比较选择经验损失最小的基函数，添加到当前加法模型，其加权权值就
是对应的最优权值。给定基函数h，经验损失函数就是参数α的函数，可以写作
L(α)=
"
q
L(f
t−1
+ αh | q)=
"
q
1
2
−
1
2
"
q
δ(q)
T
#
f
t−1
(q)+αh(q)
$
∥f
t−1
(q)+αh(q)∥
≡
"
q
1
2
−
1
2
A (23.91)
下文分析A的梯度计算，为方便起见，至此略去q：
A =
"
δ
T
#
f
t−1
+ αh
$#*
f
t−1
+ αh
+
T
*
f
t−1
+ αh
+$
−1/2
(23.92)
$%"&'#(
245
)!*+",$
搜索与排名 Searching and Ranking
!"#
我们的目标是最小化损失函数，根据极值必要性条件
∇A =
(
β
E
δ
T
h ·
*
f
t−1
+ αh
+
T
*
f
t−1
+ αh
+
− δ
T
(f
t−1
+ αh) · (f
t−1
+ αh)
T
h
F
=
(
β
E
(f
T
t−1
f
t−1
· δ − δ
T
f
t−1
· f
t−1
)
T
h + α(δ
T
h · h − h
T
h · δ)
T
f
t−1
F
=0
(23.93)
有关系式
α =
(
β · (f
T
t−1
f
t−1
· δ − δ
T
f
t−1
· f
t−1
)
T
h
(
β · (δ
T
h · h − h
T
h · δ)
T
f
t−1
(23.94)
成立，而关联因子
β =
#*
f
t−1
+ αh
+
T
*
f
t−1
+ αh
+$
−3/2
(23.95)
假设加法模型每次添加的基排名函数h对预测结果产生微弱的影响，不足改变模型的整体预
测，关联因子β可以做如下近似
β ≈ (f
T
t−1
f
t−1
)
−3/2
(23.96)
由此可以计算α的近似最优解形式。
23.25 PermuRank
[252]首次研究了AdaRank与SVM
MAP
在直接优化评测指标行为中的关系。
23.26 IntervalRank
2010年，Moon等人[253]出了IntervalRank学习算法，在保序回归的基础上，添加序对型、
序列型约束条件，使用共轭梯度下降法与GBDT训练模型。
给定检索词集合Q，对于任意的检索词q ∈ Q，存在n个关联文档X
q
= {x
i
}
n
i=1
,x
i
∈ R
m
，文
档x
i
与检索词的相关等级r
i
∈ G，其中，G = {r
i
}
k
i=1
表示文档与检索词的相关程度设有k个等级。
对于预测模型f，IntervalRank根据最大化等级不同的文档序对预测差值，最小化等级相同的文档
序对预测差值的原则，建立下面形式的优化问题
min
δ,ϵ,ξ
1
2
∥δ∥
2
2
+
λ
1
2
∥ϵ∥
2
2
+
λ
2
2
∥ξ∥
2
2
s.t. (f
i
+ δ
i
) − (f
j
+ δ
j
) ≥ (r
i
− r
j
) − ϵ
i
, ∀(i, j) ∈ O
q
|(f
i
+ δ
i
) − (f
j
+ δ
j
)| ≤ ξ
i
, ∀(i, j) ∈ T
q
(23.97)
其中，第一个约束条件要求等级不同的文档序对预测差值以文档等级差值为下界，允许波动的
范围是ϵ ∈ R
k−1
，第二个约束条件要求等级相同的文档序对预测差值尽可能为零，允许波动的范
围是ξ ∈ R
k
。符号δ ∈ R
n
表示文档预测分值的偏置量，一个文档对应一个偏置量。文档序对集
合O
q
, T
q
定义为：
⎧
⎨
⎩
O
q
! {(i, j) | r
i
>r
j
,i,j=1,...,n}
T
q
! {(i, j) | r
i
= r
j
,i,j=1,...,n}
(23.98)
$%"&'#(
246
)!*+",$
23.27. CRR
!"#
可以证明，δ是损失函数L(f, q)=∥δ∥
2
2
/2关于f的梯度。若取
δ
i
= f
i
− max(l
i
, min(u
i
,f
i
)),i=1,...,n (23.99)
则优化模型(23.97)可以转化成一个等价的优化问题
min
l,u,ϵ,ξ
1
2
(
r
i
∈G
(
j∈S
i
[(l
i
− f
j
)
2
+
+(f
j
− u
i
)
2
+
]+
λ
1
2
∥ϵ∥
2
2
+
λ
2
2
∥ξ∥
2
2
s.t. l
i
≤ u
i
≤ l
i
+ ξ
i
, ∀r
i
∈ G
l
i+1
− u
i
≥ (r
i+1
− r
i
) − ϵ
i
, ∀r
i
∈ G\{r
k
}
(23.100)
其中，(x)
+
! max(0,x)，l ∈ R
k
，u ∈ R
k
。S
k
表示相关等级为r
k
的文档集合
S
k
! {i | r
i
= r
k
,i=1,...,n} (23.101)
Algorithm 15 IntervalRank算法
Input: 训练数据集{x
i
,r
i
}
n
i=1
，迭代次数T ，学习率η，初始参数f = f
0
∈ H
for t =1,...,T do
1. 根据对数障碍函数法-共轭梯度下降法(16)优化问题(23.102)，确定最优权值l
∗
,u
∗
2. 根据公式(23.99)，作为损失函数梯度，重新为响应变量r
i
赋值
r
i
← f
i
− max(l
∗
i
, min(u
∗
i
,f
i
))
3. 使用决策树模型h ∈ H拟合数据{x
i
,r
i
}
n
i=1
4. 添加基本模型h到集成模型：f ← f − ηh
end for
Output: 集成模型f
模型(23.100)相比原始等价模型(23.97)，变量个数从n +2k − 1降至4k − 1。通过引入对数障碍
函数，可将其转化为下面形式的无约束优化问题：
min
l,u,ϵ,ξ
1
2
(
r
i
∈G
(
j∈S
i
[(l
i
− f
j
)
2
+
+(f
j
− u
i
)
2
+
]+
λ
1
2
∥ϵ∥
2
2
+
λ
2
2
∥ξ∥
2
2
−µ
−1
(
r
i
∈G
[log(u
i
− l
i
) + log(l
i
+ ξ
i
− u
i
)]
−µ
−1
(
r
i
∈G\{r
k
}
log(l
i+1
− u
i
− r
i+1
+ r
i
+ ϵ
i
)
(23.102)
23.27 CRR
2010年，D. Sculley[254]（Google公司）出了一种组合回归与排名算法（Combined Regres-
sion and Ranking，CRR ）， 能 够 兼 顾 预 测 模 型 的 回 归 拟 合 效 果 与 排 名 精 度 ， 是 一 种 混 合 型 的 排 序
学习算法（Pointwise-Pairwise）。
$%"&'#(
247
)!*+",$
搜索与排名 Searching and Ranking
!"#
Algorithm 16 对数障碍函数法-共轭梯度下降法
Input: 训练数据集{x
i
,r
i
}
n
i=1
，惩罚因子µ =1，初始化可行参数l, u,ϵ, ξ
for t =1,...,5 do
1. 根据共轭梯度下降法优化问题(23.102)
2. 更新障碍函数惩罚因子：µ ← 2
t
end for
Output: 最优解l
∗
,u
∗
, ϵ
∗
, ξ
∗
给定训练集S = {x
i
,y
i
,q
i
}
n
i=1
与预测模型f(ω,x)，CRR算法定义了一种组合形式的损失函数
min
ω
αL(ω,S)+(1− α )L (ω, P)+
λ
2
∥ω∥
2
2
(23.103)
包括三项，第一项是回归预测损失
L(ω,S)=
1
n
"
(x,y,q)∈S
L(y, f(ω,x)) (23.104)
第二项是序对型排名损失
L(ω, P)=
1
|P|
"
(i,j)∈P
L(φ(y
i
− y
j
),f(ω,x
i
− x
j
)) (23.105)
最后一项是规则化项。其中，P 表示样本序对集合，由相关等级相异的关联文档序对构成：
P =
,
(i, j) | y
i
̸= y
j
,q
i
= q
j
,i,j=1,...,n
-
符号ω表示模型参数，φ表示样本标记的一种变换，λ > 0是规则化因子，α ∈ [0, 1]是一个权衡因子
（Tradeoff），取值越大则对回归拟合损失惩罚力度大，反之对排名损失给予更多惩罚。
23.28 SoftRank
SoftRank: Optimising Non-Smooth Rank Metrics[230]
23.29 BayesRank
Learning to Rank from Bayesian Decision Inference[255]
23.30 RankRLS
An efficient algorithm for lear ning to rank from preference graphs[256]
$%"&'#(
248
)!*+",$
23.31. RankGP
!"#
Algorithm 17 CRR算法
Input: 训练数据集S，迭代次数T ，权衡因子α，规则化因子λ，初始参数ω
0
=0
for t =1,...,T do
1. 随机抽取z ∈ [0, 1]，若z<α，随机抽样(x, y, q) ∈ S；否则，随机抽取有序对(i, j) ∈ P，
记
x ← (x
i
− x
j
)
y ← φ(y
i
− y
j
)
2. 根据Pecasos算法[79]采用的学习率调整规则，设置可变的学习率：η
t
←
1
tλ
3. 根据随机梯度下降法更新参数：ω
t
← (1 − λη
t
)ω
t−1
+ η
t
x(y − f(ω
t−1
,x))，适用于
(a) 线性预测模型f(ω,x)=ω
T
x，平方损失函数L(y, y
′
)=
1
2
(y − y
′
)
2
(b) Logistic预测模型f( ω,x)=1/(1 + e
−ω
T
x
)，负的交叉熵损失函数L(y, y
′
)=y log y
′
+
(1 − y) log (1 − y
′
)
end for
Output: 最终排名函数f(ω
T
,x)
23.31 RankGP
Learning to Rank for Information Retrieval Using Genetic Programming[257]
23.32 SLR
Probabilistic retrieval based on staged logistic regression[258]
23.33 McRank
2007年，Li等人[259]将排序看做一个多元分类问题，出McRank方法，根据多个分类器综合
确定最终排名。在McRank 方法中，首先对训练样本分类，然后按照类别对样本排列。对于类别
相同的训练样本，McRank并未具体区分，允许任意排序，导致排序结果不稳定。为了避免这一问
题，可以对每一个训练样本软分类（Soft Classify）， 根 据 训 练 样 本 的 类 别 分 布 ， 计 算 期 望 相 关 性 ，
利用相关性分值降序排列。
$%"&'#(
249
)!*+",$
搜索与排名 Searching and Ranking
!"#
23.34 系数排序学习
稀疏排序学习是一个崭新的研究方向，研究稀疏排序学习肇始于机器学习中的稀疏模型
（Sparse Model）， 稀 疏 模 型 是 指 训 练 得 到 的 模 型 包 含 少 量 的 关 于 输 入 特 征 的 非 零 因 子 ， 同 时 又 保
持许多优良的性质：易于解释、泛化能力强、 计算开销低，在计算机视觉与生物信息学应用广
泛[260]。[261]与[260]一脉相承，都是研究稀疏排序学习（Sparse Learning to Rank），不同的是前
者使用梯度下降法，而后者则基于Fenchel对偶理论[262]优化损失函数。
给定训练数据集S = {(X
i
,Y
i
)}
n
i=1
，其中X
i
= {x
i1
,...,x
in
i
}表示检索词q
i
的关联文档集合，
x
ij
∈ R
d
表示与检索词q
i
关联的第j个文档特征向量，包含d个检索词-文档特征；Y
i
表示文档的相
关等级标记，且Y
i
= {y
i1
,...,y
in
i
}，y
ij
∈ {0,...,k}，k是最高相关等级。
对于同一个检索词，根据其关联文档集合构造序对集P = {(i, j, k)|y
ij
̸= y
ik
,x
ij
,x
ik
∈
X
i
,i =1,...,n}，设p表示P的大小，即P中序对个数。根据P中序对可以构造序对比较误差
矩阵（Pairwise Comparison Error Matrix）K ∈ R
p×d
，K的一行对应P的一个序对，比如对
于(i, j, k) ∈ P，则该序对对应K中的行I(y
ij
,y
ik
)(x
ij
− x
ik
)，其中I(x)=1，如果x>0，否
则I(x)=−1。由此可见K ∈ R
p×d
。
多数SVM模型，比如RankSVM-Struct模型[87]与RankSVM-Primal模型[263]，都是通过优化
下面形式的规则化的序对型损失函数学习排序模型：
min
ω
1
2
||ω||
2
2
+ C
"
(i,j,k)∈P
ℓ(I(y
ij
,y
ik
)ω
T
(x
ij
− x
ik
)) (23.106)
其中，ℓ是铰链损失函数（Hinge Loss），存 在 两 种常 见 的 形式：一 阶 铰 链ℓ(x) = max(0, 1 −
x)与二阶铰链ℓ(x) = max(0, 1 − x)
2
。当取一阶铰链损失函数时，则上述损失函数优化问题就
是RankSVM的目标函数。当取二阶铰链损失函数时，就是RankSVM-Primal模型的目标函数。
FenchelRank模型将ℓ
2
范数替换为ℓ
1
范数，
➊
使用二阶铰链损失函数，得到下面的优化目标函
数：
min
ω
||ω||
1
+
C
p
"
(i,j,k)∈P
max(0, 1 − I(y
ij
,y
ik
)ω
T
(x
ij
− x
ik
))
2
(23.107)
可以证明，对于每一个C，都存在一个r>0，使得(23.107)等价于下面形式的优化问题：
min
||ω ||
1
≤r
1
p
"
(i,j,k)∈P
max(0, 1 − I(y
ij
,y
ik
)ω
T
(x
ij
− x
ik
))
2
=min
||ω ||
1
≤r
1
p
p
"
i=1
max(0, 1 − (Kω)
i
)
2
(23.108)
为方便分析，可基于标准化的ω进行优化：
min
||ω ||
1
≤1
r
2
p
p
"
i=1
max(0,
1
r
− (Kω)
i
)
2
(23.109)
[260]基于遗传算法框架与Fenchel对偶理论，优化序对型排序模型FenchelRank。模型经过T 次
迭代，能够确保优化误差达到ϵ =O(
1
T
)，相比流行的次梯度下降法（Sub-gradient Descent）收
➊ ℓ
1
−惩罚项是基于ℓ
1
−范数（元素绝对值的和），而ℓ
0
−惩罚项是基于ℓ
0
− 范数（非零元的个数）
$%"&'#(
250
)!*+",$
23.35. 联级排序模型
!"#
敛速度快。[260]模型使用的参数r通过交叉验证从集合2
i
(i =0,...,8) 中选取，迭代次数最大
为T = 1000，优化精度设为ϵ =0.001，当精度或者迭代次数达到阈值时，停止迭代。
为了衡量模型的稀疏性，本文使用如下形式的稀疏率（Sparsity Ratio）定义：对于线性
模型ω ∈ R
d
，其 稀 疏 率 定 义 为：1 − |ω|
0
/d，其中|ω|
0
表示ω 中非零元素的个数。实验显示，
FenchelRank 训练的模型稀疏率远远低于其他模型，精度较为突出。
23.35 联级排序模型
对于实时搜索环境，排名效果（Effectiveness）与排名效率（Efficiency）同等重要，然而目前
绝大多数排名算法均以排名效果为中心，对于排名效率则不甚关心。Wang等人[246, 247]尝试以最
短的时间供最相关的文档集合，兼顾排名效果与效率。为此，他们出一种新颖的排序学习方
法――级联排序模型（Cascade Ranking Model, CRM）， 在 Boosting技术框架下，学习一组弱排名
函数。为了减少在大量不相关文档集上的评分成本，级联排序模型在每一个阶段，使用剪枝函数
（Pruning Function）， 亦 称 剪 枝 准 则 ， 剔 除 部 分 不 相 关 文 档 ， 将 主 要 精 力 用 于 训 练 相 关 性 较 高 的 文
档集合上，以期在训练结束时取得的文档集都是最相关的，由此实现同时最大化排名精度、最小化
时间成本的目的。
级联排序模型的训练是分阶段进行的，后续阶段的训练是基于前一阶段的输出文档集，参与训
练的文档集逐阶减少。在每个级联阶段（首个阶段除外），都会训练一个弱排名函数和一个含参的
剪枝准则，依次对输入文档剪枝、评分，并进入下一阶段。
级联模型（Cascade Model）包括多个相互串联的工作流程，如图23.4所示。级联模型包括多
个级联阶段，每一个阶段，譬如第t个阶段，参与的主体包括剪枝函数J
t
(β
t
)与弱排名函数H
t
。
图 23.4: 级联模型
级联模型可以使用一组前后相继的阶段模型{⟨J
t
(β
t
),H
t
, α
t
⟩}
T
t=1
来表示，每个阶段产生一个完
整的阶段模型，包括含参的剪枝模型J
t
(β
t
)、弱排名函数H
t
及其权值α
t
。为方便，记阶段t完整的阶
段模型S
t
：
S
t
= ⟨J
t
(β
t
),H
t
, α
t
⟩ (23.110)
在阶段t之前（包括阶段t）的所有阶段模型集合记为G
t
=
t
P
i=0
S
i
。
级联排序问题属于多目标规划问题，为了兼顾模型效果与效率，级联模型定义了基于模型性能
$%"&'#(
251
)!*+",$
搜索与排名 Searching and Ranking
!"#
Algorithm 18 级联排序算法
Input: 训练集{q
i
,x
i
,y
i
}
m
i=1
，级联阶数T ，检索词概率分布P
1
(i)=1/m，初始级联模型G
0
= ∅
for t =1,...,T do
1. 根据训练集检索词概率分布P
t
，确定最佳的阶段模型S
t
=<J
t
(β
t
),H
t
, · >：
S
t
= arg min
S
t
#
η
2
t
− ϕ
2
t
$
(23.111)
其中，
⎧
⎪
⎨
⎪
⎩
η
t
=
m
(
i=1
P
t
(i)
1−γC(x
i
,S
t
)
ϕ
t
=
m
(
i=1
P
t
(i)
1−γC(x
i
,S
t
)
E(x
i
,y
i
,S
t
)
(23.112)
2. 给弱排名函数H
t
赋最优权值α
t
：
α
t
=
1
2
log
η
t
+ ϕ
t
η
t
− ϕ
t
(23.113)
3. 将完整的阶段模型⟨J
t
(β
t
),H
t
, α
t
⟩添加到G
t
：
G
t
= G
t−1
∪ {⟨J
t
(β
t
),H
t
, α
t
⟩} (23.114)
4. 根据级联模型在各个检索词上的表现，更新检索词的分布P
t+1
：
P
t+1
(i)=
exp{−E(x
i
,y
i
,f
t
)+γC(x
i
,G
t
)}
Z
t
(23.115)
其中，
⎧
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎩
f
t
=
t
(
k=1
α
k
H
k
E(x
i
,y
i
,f
t
)=E(x
i
,y
i
,G
t
)
Z
t
=
m
(
i=1
exp{−E(x
i
,y
i
,f
t
)+γC(x
i
,G
t
)}
(23.116)
end for
Output: 最终排名函数f
T
=
T
(
t=1
α
t
H
t
$%"&'#(
252
)!*+",$
23.35. 联级排序模型
!"#
与计算开销的线性组合形式的平衡度量指标（Tradeoff Metric）：
TM
ti
= E(x
i
,y
i
,G
t
) − γC(x
i
,G
t
) (23.117)
其中，E(x
i
,y
i
,G
t
)表示直至阶段t的级联模型在检索词q
i
上的排名效果，C(x
i
,G
t
)表示直至阶段t的
级联模型的计算成本，γ ∈ [0, 1]平衡两种指标对平衡度量指标的贡献，文中选择γ =0.1。当γ =0
时，级联排序模型就简化成AdaRank模型，因此级联排序模型可以看做是AdaRank模型的推广。
成本函数C(x
i
,G
t
)一般可以使用下面的加和形式表示：
C(x
i
,G
t
)=
t
"
k=1
C(x
i
,S
t
) (23.118)
对于每个级联阶段，影响计算成本的因素包括排名模型H
t
的复杂度，参与评估的文档数目，需要
一种合适的成本估计方法。
通过对每个弱排名函数H
t
（类似AdaRank，选择特征空间中的单个特征作为备选的弱排名函
数）评估训练集中所有的检索词，并记录相应的时间开销，基于平均时间开销U
t
估计计算成本：
C(x
i
,S
t
)=U
t
|R
i{·,J
t
}
| (23.119)
其中，|R
i{·,J
t
}
|表示参与评估的文档数目。为计算方便，作者选择衰减的指数函数e
−δ C(x
i
,G
t
)
，将
计算成本映射到[0, 1]区间，其中，δ =0.01。
由此，可以定义下面形式的损失函数：
L =
1
m
m
"
i=1
ℓ
i
=
1
m
m
"
i=1
exp{−E(x
i
,y
i
,G
t
)+γC(x
i
,G
t
)}) (23.120)
剪枝函数的作用是约减待评价的文档集，因为在实际应用中，多数文档属于不相关文档，那么
预先将其从文档集中剔除，在高文档整体质量的同时也升了排名的效率。通常，剪枝函数都是
含参β
t
的评价准则，常用的剪枝函数有三种：
1. 基于排名的剪枝函数（Rank-based）：
J
t
(β
t
):θ
t
=(1− β
t
) × |R
{·,H
t−1
}
|
其中，|R
{·,H
t−1
}
|表示在第t阶段输入的文档数目。这种剪枝函数要求对于排名低于θ
t
的文档剪
枝。参数β
t
越大，则剔除的文档越多（数值越小，名次越高）。
2. 基于分值的剪枝函数（Score-based）：
J
t
(β
t
):θ
t
= β
t
× [max(R
{·,H
t−1
}
) − min(R
{·,H
t−1
}
)] + min(R
{·,H
t−1
}
)
其中，max(R
{·,H
t−1
}
)，min(R
{·,H
t−1
}
)表示R
{·,H
t−1
}
中最大、最小的分值。如果文档的分值
低于θ
t
，则从集合中剪除。
$%"&'#(
253
)!*+",$
搜索与排名 Searching and Ranking
!"#
3. 均值-最大值阈值准则（Mean-Max Threshold）：
J
t
(β
t
):θ
t
= β
t
× max(R
{·,H
t−1
}
)+(1− β
t
) × mean(R
{·,H
t−1
}
)
其中，mean(R
{·,H
t−1
}
)表示R
{·,H
t−1
}
中文档的平均分值。如果待测文档分值低于θ
t
，则从集合
中剪除。
级联排序模型使用剪枝函数逐阶削减输入文档的数目，将相关性低的文档前从输入集合中剔
除，在升训练效率的同时有助于改善文档集合的综合质量：
|R
{·,J
t
}
| ≤ |R
{·,J
t−1
}
| ≤ ···≤ |R
{·,J
1
}
|
E(R
{·,H
t
}
) ≥ E(R
{·,H
t−1
}
) ≥ ···≥ E(R
{·,H
0
}
)
(23.121)
下面我们来证明级联排序模型具有持续改善排名性能的作用，证明步骤类似于AdaRank。
证明： 根据ϕ
t
, η
t
, α
t
的定义可知：
e
α
t
=
'
η
t
+ ϕ
t
η
t
− ϕ
t
(23.122)
由于模型中用于衡量排序性能的指标E ∈ [0, 1]，所以e
−E
≥ 1 − E，从而有：
1
m
m
(
i=1
7
E(x
i
,y
i
,f
T
) − γC(x
i
,G
T
)
8
≥
1
m
m
(
i=1
?
1 − exp{−E(x
i
,y
i
,f
T
)+γC(x
i
,G
T
)}
@
=1−
1
m
m
(
i=1
exp{−E(x
i
,y
i
,f
T
)+γC(x
i
,G
T
)}
=1−
1
m
Z
T
(23.123)
建立了模型平均性能指标同Z
T
的关系，进而转向对Z
T
上界的分析。
由于
−E(x
i
,y
i
,f
T
)+γC(x
i
,G
T
)=
#
− E(x
i
,y
i
,f
T
)+α
T
E(x
i
,y
i
,H
T
)+E(x
i
,y
i
,f
T −1
)
$
+
#
− E(x
i
,y
i
,f
T −1
)+γC(x
i
,G
T −1
)
$
+
#
γC(x
i
,S
T
) − α
T
E(x
i
,y
i
,H
T
)
$
所以有：
Z
T
=
m
(
i=1
exp{−E(x
i
,y
i
,f
T
)+γC(x
i
,G
T
)
$
}
=
m
(
i=1
7
e
−δ
T
i
exp{−E(x
i
,y
i
,f
T −1
)+γC(x
i
,G
T −1
}exp{γC(x
i
,S
T
) − α
T
E(x
i
,y
i
,H
T
)}
8
≤ e
−δ
T
min
Z
T −1
m
(
i=1
7
exp{−E(x
i
,y
i
,f
T −1
)+γC(x
i
,G
T −1
}
Z
T −1
exp{γC(x
i
,S
T
) − α
T
E(x
i
,y
i
,H
T
)}
8
= e
−δ
T
min
Z
T −1
m
(
i=1
P
T
(i)exp{γC(x
i
,S
T
) − α
T
E(x
i
,y
i
,H
T
)}
! e
−δ
T
min
Z
T −1
W
T
(23.124)
由于当x>0时，有e
x
≤
1
1−x
，所以：
e
γC(x
i
,S
T
)
≤
1
1 − γC(x
i
,S
T
)
(23.125)
$%"&'#(
254
)!*+",$
23.35. 联级排序模型
!"#
因为：
−α
T
E(x
i
,y
i
,H
T
)=λ(−α
T
)+(1− λ)α
T
其中，
λ =
1+E(x
i
,y
i
,H
T
)
2
根据函数f( x)=e
x
的凸性可知：
e
−α
T
E(x
i
,y
i
,H
T
)
≤
1+E(x
i
,y
i
,H
T
)
2
e
−α
T
+
1 − E(x
i
,y
i
,H
T
)
2
e
α
T
(23.126)
那么：
W
T
=
m
(
i=1
P
T
(i)exp{γC(x
i
,S
T
) − α
T
E(x
i
,y
i
,H
T
)}
≤
m
(
i=1
P
T
(i)
1−γC(x
i
,S
T
)
e
−α
T
E(x
i
,y
i
,H
T
)
≤
m
(
i=1
P
T
(i)
1−γC(x
i
,S
T
)
?
1+E(x
i
,y
i
,H
T
)
2
e
−α
T
+
1−E(x
i
,y
i
,H
T
)
2
e
α
T
@
=
m
(
i=1
P
T
(i)
1−γC(x
i
,S
T
)
7
1+E(x
i
,y
i
,H
T
)
2
8
e
−α
T
+
m
(
i=1
P
T
(i)
1−γC(x
i
,S
T
)
7
1−E(x
i
,y
i
,H
T
)
2
8
e
α
T
=
η
T
+ϕ
T
2
e
−α
T
+
η
T
−ϕ
T
2
e
α
T
=
)
η
2
T
− ϕ
2
T
(23.127)
从而可推知：
Z
T
≤ e
−δ
T
min
Z
T −1
)
η
2
T
− ϕ
2
T
= Z
T −2
T
9
t=T −1
e
−δ
t
min
)
η
2
t
− ϕ
2
t
= Z
1
T
9
t=2
e
−δ
t
min
)
η
2
t
− ϕ
2
t
(23.128)
由于
Z
1
= exp{−E(x
i
,y
i
, α
1
H
1
)+γC(x
i
,G
1
)}
≤ e
−δ
1
min
m
(
i=1
exp{−α
1
E(x
i
,y
i
,H
1
)+γC(x
i
,S
1
)}
≤ e
−δ
1
min
m
(
i=1
exp{−α
1
E(x
i
,y
i
,H
1
)}
1−γC(x
i
,S
1
)
= m · e
−δ
1
min
#
e
−α
1
m
(
i=1
P
1
(i)
1−γC(x
i
,S
1
)
1+E(x
i
,y
i
,H
1
)
2
+ e
α
1
m
(
i=1
P
1
(i)
1−γC(x
i
,S
1
)
1−E(x
i
,y
i
,H
1
)
2
$
= m · e
−δ
1
min
)
η
2
1
− ϕ
2
1
(23.129)
通过上面推导结果可知：
Z
T
≤ m
T
!
t=1
e
−δ
t
min
)
η
2
t
− ϕ
2
t
(23.130)
因而可得：
1
m
m
"
i=1
7
E(x
i
,y
i
,f
T
) − γC(x
i
,G
T
)
8
≥ 1 −
T
!
t=1
e
−δ
T
min
)
η
2
t
− ϕ
2
t
, (23.131)
证毕。
$%"&'#(
255
)!*+",$
搜索与排名 Searching and Ranking
!"#
根据不等式(23.131)可知，只要在每步迭代保证：
e
−δ
t
min
)
η
2
t
− ϕ
2
t
< 1
成立，则排序模型的平均性能下界趋于上升，由此表明级联排名算法可以持续改善模型性能。
23.36 排序逻辑回归模型
2006年，Yan与Hauptmann [264]出一种基于间隔（Margin-based）的广义排名学习框架，
通过近似优化序对型风险函数估计模型参数，使用不同形式的损失函数与规则化项，可以推演
出不同形式的排序模型，比如使用Logit 损失函数，他们出了排序逻辑回归（Ranking Logistic
Regression，RLR）模型，实验表明基于间隔的排序框架性能显著。
序对型排序学习方法将排名问题转化为二元分类问题，在分类框架下通过优化下面形式的正则
化经验风险训练排序模型：
min
f
R
0
(f)=
"
q ∈ Q
n
q
"
i=1
L(y
i
f(d
i
,q)) + CΩ(∥f ∥
H
) (23.132)
其中，第一部分是一般的经验风险，第二部分是正则化项。Q是检索词集合，n
q
是同检索词q关联
的文档数目，y
i
f(d
i
,q)是分类模型的“间隔” [63]，L表示损失函数，一般地是关于间隔的递减函
数，Ω表示单调递增的规则化函数，C>0代表正则化系数。
分类框架下学习排序模型存在两个主要弊端，一方面模型预测精度对数据分布敏感，即种类
型的数据分布越多，则相应的预测结果就越倾向于此类型。另一方面，分类精度与排名精度不一
致，模型分类精度很高，但是相应的排名性能未必尽如人意。 为此，我们可以通过最大化同序对
（Concordant Pairs）克服这些问题：
max
f
"
q ∈ Q
"
d
i
∈D
+
q
"
d
j
∈D
−
q
I(f (d
i
,q) >f(d
j
,q)) (23.133)
分析同序对可以发现，直接优化是行不通的，如果使用一个连续的、凸的、单调递减的损失函
数替换它，势必可以方便模型优化工作。通过引入正则化项，本文给出下面统一形式的基于间隔的
排序学习框架：
min
f
R
1
(f)=
(
q ∈ Q
(
d
i
∈D
+
q
(
d
j
∈D
−
q
L(f(d
i
,q) − f(d
j
,q)) + CΩ(∥f ∥
H
)
=
(
q ∈ Q
(
d
i
∈D
+
q
(
d
j
∈D
−
q
L(
n
(
k=1
ω
k
[f
k
(d
i
,q) − f
k
(d
j
,q)]) + CΩ(∥f ∥
H
)
(23.134)
排序模型选择最简单的线性模型f(d, q)=
n
(
k=1
ω
k
f
k
(d, q)，通过选择不同的损失函数与正则化项，就
可以导出一系列排序模型。
$%"&'#(
256
)!*+",$
23.36. 排序逻辑回归模型
!"#
定义23.3 (排名一致性). 风险最小估计模型因子ω ∈ R
n
，对任意的d
i
∈ D
+
q
,d
j
∈ D
−
q
，排名特征f
k
如
果满足ω
k
(f
k
(d
i
,q) −f
k
(d
j
,q)) ≥ 0，则称风险最小估计特征权值ω
k
与真实排名一致，我们称模型满
足排名一致性（Rank Consistency）。
定理23.3. 基于间隔的排序框架学习到的风险最小估计量ω
k
与真实排名一致。
证明： 如果存在排名特征f
k
满足f
k
(d
i
,q) ≥ f
k
(d
j
,q), ∀q ∈ Q, d
i
∈ D
+
q
,d
j
∈ D
−
q
，我们用反证法证
明ω
k
≥ 0。假设ω
k
< 0，若记ω
′
k
= −ω
k
，基于间隔的排序框架使用的损失函数是单调递减的，由
于
ω
k
(f
k
(d
i
,q) − f
k
(d
j
,q)) ≤ ω
′
k
(f
k
(d
i
,q) − f
k
(d
j
,q)) (23.135)
记∆
k
=
(
l̸=k
ω
l
(f
l
(d
i
,q) − f
l
(d
j
,q))，则有
L(ω
′
k
(f
k
(d
i
,q) − f
k
(d
j
,q)) + ∆
k
) ≤ L(ω
k
(f
k
(d
i
,q) − f
k
(d
j
,q)) + ∆
k
) (23.136)
这与ω
k
是风险最小估计量矛盾，故而ω
k
≥ 0。
定理23.4. 若损失函数L是凸的，并且满足2L( x/2) ≥ L (x)，则不等式成立：
1
2
#
R
2
(f) − R
2
(−f)
$
≤ R
1
(f) ≤ R
2
(f) (23.137)
其中，R
1
(f)不含正则项，R
2
(f)是一个基于有偏置的排名函数f
b
(d, q)近似风险函数：
R
2
(f)=
"
q∈Q
?
"
d
i
∈D
+
q
|D
−
q
|L(f
b
(d
i
,q)) +
"
d
j
∈D
−
q
|D
+
q
|L(−f
b
(d
j
,q))
@
(23.138)
其中，|·|表示集合大小，f
b
(d, q)=
n
(
k=1
ω
k
(f
k
(d, q) − b
k
)。
证明： 由于损失函数是凸的并且2L(x/2) ≥ L(x)，则对任意的A, B ∈ R，都有
L(A)+L(B) ≥ 2L(
A + B
2
) ≥ L(A + B)
类似地可得
L(A + B)+L(−B) ≥ 2L(
A
2
) ≥ L(A),L(A + B)+L(−A) ≥ L(B)
将两个不等式相加有：
2L(A + B)+L(−B)+L(−A) ≥ L(A)+L(B)
整理可得L(A + B) ≥
1
2
#
L(A)+L(B) − L(−A) − L(− B)
$
，综上：
L(A)+L(B) ≥ L(A + B) ≥
1
2
#
L(A)+L(B) − L(−A) − L(− B)
$
(23.139)
令A = f
b
(d
i
,q),B = −f
b
(d
j
,q)，我们有
L(f
b
(d
i
,q)) + L(−f
b
(d
j
,q)) ≥ L(f
b
(d
i
,q) − f
b
(d
j
,q)) = L ( f (d
i
,q) − f(d
j
,q))
≥
1
2
#
L(f
b
(d
i
,q)) + L(−f
b
(d
j
,q)) − L(−f
b
(d
i
,q)) − L(f
b
(d
j
,q))
$
(23.140)
$%"&'#(
257
)!*+",$
搜索与排名 Searching and Ranking
!"#
两边同时加和
(
q ∈ Q
(
d
i
∈D
+
q
(
d
j
∈D
−
q
#
L(f
b
(d
i
,q)) + L(−f
b
(d
j
,q))
$
≥
(
q ∈ Q
(
d
i
∈D
+
q
(
d
j
∈D
−
q
L(f(d
i
,q) − f(d
j
,q))
≥
1
2
(
q ∈ Q
(
d
i
∈D
+
q
(
d
j
∈D
−
q
#
L(f
b
(d
i
,q)) + L(−f
b
(d
j
,q)) − L(−f
b
(d
i
,q)) − L(f
b
(d
j
,q))
$
(23.141)
由于第一个不等式
(
q ∈ Q
(
d
i
∈D
+
q
(
d
j
∈D
−
q
#
L(f
b
(d
i
,q)) + L(−f
b
(d
j
,q))
$
=
(
q ∈ Q
,
(
d
i
∈D
+
q
|D
−
q
|L(f
b
(d
i
,q)) +
(
d
j
∈D
−
q
|D
+
q
|L(−f
b
(d
j
,q))
-
= R
2
(f)
(23.142)
因此可得第二个不等式
1
2
(
q ∈ Q
(
d
i
∈D
+
q
(
d
j
∈D
−
q
#
L(f
b
(d
i
,q)) + L(−f
b
(d
j
,q)) − L(−f
b
(d
i
,q)) − L(f
b
(d
j
,q))
$
=
1
2
#
R
2
(f) − R
2
(−f)
$
(23.143)
综上有
1
2
#
R
2
(f) − R
2
(−f)
$
≤ R
1
(f) ≤ R
2
(f)。特别地，如果L是线性的，则等式成立。
近似风险函数R
2
(f)的计算复杂度是O(|D
+
q
| + |D
−
q
|)远低于R
1
(f)的复杂度O(|D
+
q
||D
−
q
|)，此外
通过系数|D
+
q
|, |D
−
q
| 抵消两类数据分布不平衡的影响，最大化两类数据的预测间隔。
如果取Logit损失函数
L(x) = log(1 + e
−x
) (23.144)
那么有
L(x)+L(−x) = log(1 + e
−x
) + log(1 + e
x
) ≤ 2+|x|
在模型训练之前，必须首先确定偏置向量b，为此，可通过最小化上下界之差
b
∗
= arg min
b
1
2
#
R
2
(f)+R
2
(−f)
$
(23.145)
使近似风险函数R
2
更贴近于R
1
的准确值，由于
1
2
#
R
2
(f)+R
2
(−f)
$
≤ 2|Q||D
+
q
||D
−
q
| +
1
2
"
q ∈ Q
?
"
d
i
∈D
+
q
|D
−
q
||f
b
(d
i
,q)| +
"
d
j
∈D
−
q
|D
+
q
||f
b
(d
j
,q)|
@
(23.146)
偏置向量的优化等价于下面的优化问题
min
b
"
q ∈ Q
?
"
d
i
∈D
+
q
|D
−
q
||f
b
(d
i
,q)| +
"
d
j
∈D
−
q
|D
+
q
||f
b
(d
j
,q)|
@
(23.147)
直接优化难以实现，为此，使用一组优化模型逐个优选偏置量，达到近似优化的目的：
min
b
k
"
q∈Q
?
"
d
i
∈D
+
q
|D
−
q
||f
k
(d
i
,q) − b
k
| +
"
d
j
∈D
−
q
|D
+
q
||f
k
(d
j
,q) − b
k
|
@
(23.148)
$%"&'#(
258
)!*+",$
23.37. 序对协调排名方法
!"#
最优的偏置量是同一个排名特征下，所有检索词关联文档特征值的中值：
ω
∗
k
= median
?
B
q∈Q
.
B
d
i
∈D
+
q
,
f
k
(d
i
,q)
-
|D
−
q
|
BB
d
j
∈D
−
q
,
f
k
(d
j
,q)
-
|D
+
q
|
/@
(23.149)
其中，{x}
n
表示n个数值都等于x的集合，等价于将每个排名特征中值都转化为0。
将最优的偏置向量代入至R
2
(f)中，使用Logit损失函数与ℓ
2
规则化项，我们可以利用梯度下降
法进行优化。
23.37 序对协调排名方法
假设检索词q的关联文档集合是{x
i
,r
i
}
n
i=1
，利用训练集学习线性模型f(ω,x)=ω
T
x，我们要
求模型在单个文档、文档序对及文档序列层面具有下面三条性质：
1. 逐点型：预测结果与真实相关等级之间的误差尽可能小
arg min
ω
n
"
i=1
∥ω
T
x
i
− r
i
∥
2. 序对型：对于检索词q的任意两个关联文档x
i
,x
j
，基于预测分值的排名结果与真实排名一致
(ω
T
x
i
− ω
T
x
j
)(r
i
− r
j
)=ω
T
(x
i
− x
j
)(r
i
− r
j
) ≥ 0
3. 序列型：在检索词q上的排名精度尽可能高
arg max
ω
E(q, f)
其中，E表示衡量排序性能的标准指标，如MAP、NDCG等。
序对型约束条件要求预测模型能够最大化序对间隔，由此建立下面形式的优化问题
max
ω
"
(i,j)
ω
T
(x
i
− x
j
)(r
i
− r
j
)
由于
(x
i
− x
j
)(r
i
− r
j
)=(x
j
− x
i
)(r
j
− r
i
)
则原始问题等价于下面形式的优化问题
max
ω
"
(i,j)∈P
ω
T
(x
i
− x
j
)(r
i
− r
j
) (23.150)
其中，集合P表示文档偏好序对集，定义为
P = {(i, j) | r
i
>r
j
,i,j =1,...,n}
$%"&'#(
259
)!*+",$
搜索与排名 Searching and Ranking
!"#
对同序对间隔项进行整理，可得：
(
(i,j)∈P
(x
i
− x
j
)(r
i
− r
j
)
=
(
(i,j)∈P
7
x
i
(r
i
− r
j
) − x
j
(r
i
− r
j
)
8
=
n
(
i=1
x
i
(
j∈P
i∗
(r
i
− r
j
)+
n
(
j=1
x
i
(
i∈P
∗j
(r
i
− r
j
)
=
n
(
i=1
x
i
(
j∈P
i∗
!
P
∗i
(r
i
− r
j
)
≡
n
(
i=1
x
i
α
i
(23.151)
其中，集合
P
i∗
= {j | (i, j) ∈ P , ∀j =1,...,n}, P
∗i
= {j | (j, i) ∈ P , ∀j =1,...,n}
是根据样本i的相关等级对样本集合做出的一种，前者是所有等级低于i的样本集合，后者是所有等
级高于i的样本集合。此外，还有一部分样本，它们的等级与样本i的相同，记为S
r
：
S
r
= {i | r
i
= r, ∀i =1,...,n}, ∀r ∈ G (23.152)
其中，样本i的相关等级等于r，G表示数据集上所有相关等级的集合。
序对协调排名方法（Pairwise Concordant Ranking Method，PCRank）在优化问题(23.150)之
上添加一个规则化项：
L(ω, λ)=ω
T
n
"
i=1
x
i
α
i
−
λ
2
∥ω∥
2
(23.153)
若取ℓ
2
−范数，由极值必要性条件可知
ω
∗
=
1
λ
n
"
i=1
x
i
α
i
(23.154)
其中，ω
∗
是最优解，在不产生混淆的情况下，我们略去上标星号。由于λ > 0，不会影响预测的排
名结果，等价于
ω =
n
"
i=1
x
i
α
i
(23.155)
其中，X ∈ R
n×m
表示训练数据集，每行表示一个数据样本特征向量。
我们利用等价关系
P
i∗
∪ P
∗i
= {1,...,n}\S
r
$%"&'#(
260
)!*+",$
23.37. 序对协调排名方法
!"#
进一步化简等式(23.151)，可得
ω =
n
(
i=1
x
i
α
i
=
n
(
i=1
x
i
(
j∈P
i∗
∪P
∗i
(r
i
− r
j
)
=
(
r∈G
(
j/∈S
r
(r − r
j
)
(
i∈S
r
x
i
=
(
r∈G
[(n − |S
r
|)r −
(
j/∈S
r
r
j
]
(
i∈S
r
x
i
=
(
r∈G
[nr −
(
r
0
∈G
r
0
|S
r
0
|]
(
i∈S
r
x
i
≡
(
r∈G
(β
r
(
i∈S
r
x
i
)
(23.156)
当r是最小的相关等级，则必然有β
r
≤ 0；反之，当r是最大的相关等级，则必然有β
r
> 0。如果训
练数据只包含一种相关等级，则ω =0。
若数据集线性不可分，引入核函数K则有：
ω
T
φ(x)=
(
r∈G
[nr −
(
r
0
∈G
r
0
|S
r
0
|]
(
i∈S
r
φ(x
i
)
T
φ(x)
=
(
r∈G
[nr −
(
r
0
∈G
r
0
|S
r
0
|]
(
i∈S
r
K(x
i
,x)
(23.157)
其中，φ是映射函数，将输入变量映射到再生核Hilbert特征空间。基于核函数的PCRank存在一个
严重的问题，在模型预测时所有的训练样本输入特征都要参与计算，无疑是不可行的。我们可以根
据每个相关等级（或类别）下的输入特征，确定输入特征向量各个维度的区间范围，使用特征边界
建立预测模型。
利用相关等级可将关联文档集合划分成多个等价类，统计各个等价类下样本个数|S
r
0
|，只需复
杂度为O(n)的时间就可以迅速确定对应与检索词q的最佳线性模型。我们使用此办法，对不同检索
词构建不同的线性模型，作为基本排名函数，使用AdaRank算法，基于Boosting技术集成为强排
名函数。
在确定最佳基本线性模型时，模型参数（特征权值）可能存在负值，并且对各个等级相关文档
分布十分敏感。对于同一组数据集，相关等级经过保序变换，本质上并不会影响预测模型的排名精
度。本模型可能会受到相关等级保序变换的影响，我们下面考察保序变换对线性模型的影响（假设
相关等级保序变换函数为ψ）：
β
r
(
i∈S
r
x
i
= nr −
(
r
0
∈G
r
0
|S
r
0
|
(
i∈S
r
x
i
=
(
r
0
∈G
|S
r
0
|(r − r
0
)
(
i∈S
r
x
i
=
(
r
0
∈G
|S
r
||S
r
0
|(r − r
0
)
(
i∈S
r
x
i
/|S
r
|
=¯x
r
(
r
0
∈G
|S
r
||S
r
0
|(r − r
0
)
(23.158)
因此，β可以看做是每个相关等级所有文档特征向量加权平均值权重。
$%"&'#(
261
)!*+",$
搜索与排名 Searching and Ranking
!"#
相关等级进行线性变换ψ(r)=a ∗ r + b
β
′
r
"
i∈S
r
x
i
=¯x
r
"
r
0
∈G
|S
r
||S
r
0
|[ψ(r) − ψ(r
0
)] = aβ
r
"
i∈S
r
x
i
(23.159)
对关联文档的排名不会产生任何影响。
在PCRank模型中，相同等级的文档序对Pairwise Concordance间隔无任何贡献。分析模型的
预测精度可以发现，相同等级的文档预测结果越接近则模型预测精度越高
min
ω
"
r∈G
"
i,j∈S
r
|ω
T
x
i
− ω
T
x
j
| (23.160)
并且对于等级越高的文档序对，它们的预测接近程度更有利于升模型整体的预测精度，为此可以
添加权重因子
max
ω
"
r∈G
"
i,j∈S
r
ϕ(r)|ω
T
x
i
− ω
T
x
j
| (23.161)
由于在文档标记中，相关等级数值越小则等级越高，则ϕ(r)是关于相关等级的单调递减函数，比
如ϕ(r)=e
−r
。
将相同等级的文档序对预测结果接近程度添加到PCRank模型中，建立下面形式的模型（统一
称为PCRank模型）
max
ω
"
(i,j)∈P
(ω
T
x
i
− ω
T
x
j
)[ψ(r
i
) − ψ(r
j
)] − γ
"
r∈G
"
i,j∈S
r
ϕ(r)|ω
T
x
i
− ω
T
x
j
| −
1
2
λ∥ω∥
2
(23.162)
其中，λ > 0，函数ψ是关于相关等级r的单调递增函数，升模型在高相关等级文档上的预测精度，
γ > 0可以融入到单调递减函数ϕ 中。
假设预测函数为f，一般性的PCRank模型可以表示如下
max
f∈H
J(θ, λ)=
"
(i,j)∈P
#
f( x
i
) − f(x
j
)
$
[ψ(r
i
) − ψ(r
j
)] −
"
r∈G
"
i,j∈S
r
ϕ(r)
6
6
f( x
i
) − f(x
j
)
6
6
−
1
2
λ∥f∥
2
H
(23.163)
模型反映了聚类的部分思想：使不同类别的样本数据尽量分散，相同类别的样本数据尽量聚集，
并保证预测结果与真实相关等级的一致性。PCRank模型可以应用到多元分类问题
PCRank模型可以应用到分类问题：选择最优的阈值b（每个分类一个阈值），确保分类误差最
小：
arg max
b
"
r∈G
"
i∈S
r
I(g(ω
T
x
i
+ b
r
)=y
i
) (23.164)
23.38 公开数据集：排序学习
排序学习是典型的监督学习方法，使用包含人工标记的数据作为训练数据集训练模型。目
前，支持排序学习训练、检测的数据集很多，比如微软亚洲研究院供的LETOR[265]、Microsoft
Learning to Rank、Yahoo! Learning to Rank Challenge、Yandex Internet Mathematics等。
$%"&'#(
262
)!*+",$
23.38. 公开数据集：排序学习
!"#
23.38.1. LETOR
目前，LETOR
➊
公开数据集是排序学习研究人员使用最多的标准数据集，并且还供多种经
典排序学习算法的实验结果。LETOR是LEarning TO Rank的缩写，由微软亚洲研究院（Microsoft
Research Asia，MSRA）发布。从2007年4月至2009年7月，MSRA已经发布了四个版本，本文实验
使用的数据集是LETOR 3.0与LETOR 4.0两个版本。本节主要介绍实验中使用的LETOR数据集基本
信息。
LETOR数据集包含的数据信息有三个主要部分：检索词集合、文档集合（也称“语料库”）、
文档与检索词的相关等级。检索词集合与文档集合来源不同，前者统一标记赋予唯一的ID号，后
者源自于网络采集程序从互联网上抓取的网页数据，并且以数值型的文档特征向量形式存储。文档
与检索词的相关等级是监督学习的“标准答案”，部分来自于人工标记，还有是根据Bing搜索引擎
的搜索日志生成。在LETOR 3.0数据包中含有七个数据集：HP2003、HP2004、NP2003、NP2004、
TD2003、TD2004 和OHSUMED，LETOR 4.0 则含有两个数据集：MQ2007与MQ2008。
LETOR 3.0使用的文档集合是OHSUMED和Gov语料库。OHSUMED语料库[266]属于医学文
献数据库MEDLINE的一个数据集，由1987年至1991年刊发的、出自270 个医学期刊的348,566篇医
学文献构成。OHSUMED数据集由106个检索词，大约16,140篇文档构成，每篇文档取45个特征，
并根据文档与检索词的相关程度标记为三个等级：高度相关、部分相关、不相关。 Gov语料库包
含大约1,053,110篇网页，是2002年初从域名后缀为.gov的政府网站上爬取下来的。2003年，Gov语
料库开始用于文本检索会议（Text REtrieval Conference，TREC）Web检索项目[267]下的主题
取（Topic Distillation，TD）、 主 页 发 现 （ Home Page Finding，HP）和命名网页发现（Named
Page Finding，NP）三类检索任务，语料库中每篇网页取64个特征，文档与检索词的相关性标
记为两个等级：相关与不相关。 2003年、 2004年文本检索会议Web 检索项目使用的数据集有六组：
TD2003，TD2004，HP2003，HP2004，NP2003，NP2004。 LETOR 4.0使用的文档集合是Gov2语
料库、使用的检索词集合源自2007 年、 2008 年文本检索会议Million Query（MQ）项目，分别记
为MQ2007与MQ2008。 Gov2语料库源自2004年初从政府网站上爬取下来的25,000,000篇网页，达
到426G。语料库中每篇网页取46个特征。MQ2007、 MQ2008分别包含1700条、 800条检索词。
每个检索词文档，所有训练数据标记为三个等级：高度相关、相关、不相关。
23.38.2. Microsoft Lear ning to Rank
数据集采自Bing的标签集合，相关等级有5个级别：0（不相关）∼ 4（完全相关）。 它包含两
组数据集：MSLR-WEB30k、MSLR-WEB10k，前者包含30,000个检索词，后者只有10,000检索词。
每对query-doc包含136个特征。
➊ LETOR: http://research.microsoft.com/
$%"&'#(
263
)!*+",$
搜索与排名 Searching and Ranking
!"#
23.38.3. Yahoo! Learning to Rank Challenge
Yahoo! 实验室于2010年初举办了一次Learning to Rank 挑战赛
➊
，使用的数据源自Yahoo!自
己用作训练排名函数的子数据集。它包含两组数据集，一大一小，分别被分割成三个子数据集：
训练集、验证集、测试集。数据包含700个特征，评价分5个等级：0（不相关）∼ 4（高度相关）。
[268]总结了竞赛的结果，并对胜出模型做出评价。
23.38.4. Yandex Internet Mathematics
Yandex是俄罗斯目前最大的搜索引擎公司，于2009年组织了一场互联网数学竞赛（Internet
Mathematics Challenge）
➋
，竞 赛 使 用 的 数 据 分 成 两 部 分：训 练 集 与 测 试 集。 训 练 集 中 包
含9,124条检索词，97,290篇文档。测试集总共包含115,643篇文档，取出21,103篇文档作为公开测试
数据，其他用作最终测试。每篇文档取245个特征，训练数据由人工标记为5个等级（0∼4）。
23.39 排序学习算法汇总表
➊ Yahoo! Learning to Rank Challenge
➋ Internet Mathematics Challenge: 2009, 2011
$%"&'#(
264
)!*+",$
23.39. 排序学习算法汇总表
!"#
类型 名称 时间 损失函数 优化方法 数据集 对比算法
SVM RankSVM[233] 2002
SVM IR-SVM[236] 2006
SVM SVM
MAP
[231] 2007
ANN PRank[223] 2001
ANN RankNet[225] 2005
ANN LambdaRank[226] 2007
ANN LambdaMART[117] 2010
ANN ListNet[227] 2007
ANN ListMLE[229] 2008
ANN QBRank[116] 2007
ANN FRank[240] 2007
ANN SortRank[242] 2008
ANN BoltzRank[241] 2009
Boosting RankBoost[164] 2003
Boosting AdaRank[165] 2007
Boosting RankCosine[228] 2008
Boosting SRankBoost[243] 2008
Boosting NDCGBoost[245]
Boosting GBRank[238] 2007
Boosting RankRefine[251]
Boosting MPBoost[250]
Boosting GBlend[239] 2010
Regression SLR[258] 1992
Regression RankLR[269] 2009
Regression CRR[254] 2010 Combined SGD
Regression IntervalRank[253] 2010
– RankGP[257] 2007 GA
– McRank[259] 2007
– SoftRank[230] 2008
– RankRLS[256] 2009
Bayes BayesRank[255] 2009
– PermuRank[252] 2008
$%"&'#(
265
)!*+",$
