Pairwise ranker
1.引言
排序学习（learning to rank）是目前比较热的研究领域。基于优先函数（pairwise方法）的排序学习是LTR的一个子方向，这一方向出现的原因在于团队在实际工程项目中发现，基于优先函数的排序学习方法在模型稳定性、泛化能力和可解释性上具有一定优势。
基于优先函数的排序学习算法包括两个阶段：
第一阶段使用机器学习算法训练优化函数
f
(
x
i
,
x
j
)
f(x_i,x_j)
f(xi,xj)。
f
(
x
i
,
x
j
)
f(x_i,x_j)
f(xi,xj)输出一个0-1的实数值表示样本
x
i
x_i
xi优先于
x
j
x_j
xj的概率，这个概率也记为
P
(
x
i
>
x
j
)
P(x_i>x_j)
P(xi>xj)。因此可以把
f
(
x
i
,
x
j
)
f(x_i,x_j)
f(xi,xj)的输出看做是对概率
P
(
x
i
>
x
j
)
P(x_i>x_j)
P(xi>xj)的估计值，训练的目标是提高
f
(
x
i
,
x
j
)
f(x_i,x_j)
f(xi,xj)的预测准确率，同时也是为了使
f
(
x
i
,
x
j
)
f(x_i,x_j)
f(xi,xj)满足实数比较符“
<
<
<”小于和“
>
>
>”大于的几大性质，包括自反性，反对称性和传递性。在理想情况下
f
(
x
i
,
x
j
)
f(x_i,x_j)
f(xi,xj)将满足与实数比较符相同的性质。
第二阶段基于测试集中两两样本间由算法
f
(
x
i
,
x
j
)
f(x_i,x_j)
f(xi,xj)预测得的优先关系，使用特定的排序算法来得到最终的排序结果。因为
f
(
x
i
,
x
j
)
f(x_i,x_j)
f(xi,xj)是学习得到的，因此它不满足实数比较符“
<
<
<”小于或“
>
>
>”大于那样的传递性。例如，
f
(
x
i
,
x
j
)
f(x_i,x_j)
f(xi,xj)有可能得到如下结果：
x
i
x_i
xi优先于
x
j
x_j
xj，
x
j
x_j
xj优先于
x
k
x_k
xk，而
x
k
x_k
xk优先于
x
i
x_i
xi。通常称这样的
f
(
x
i
,
x
j
)
f(x_i,x_j)
f(xi,xj)的输出结果不具有一致性。因此需设计特殊的排序算法来完成最终的排序。
2.优先函数的设计
通常将优先函数 f ( x i , x j ) f(x_i,x_j) f(xi,xj)的任务看是训练一个二分类器（Binary Classifier），因此可以照搬一些常用的机器学习算法来使用。下面介绍几种经典的基于pairwise的算法设计。
2.1 RankSVM
对于一个query-doc pair，可以将其用一个特征向量来表示：
x
x
x，而优先函数为
f
(
x
)
f(x)
f(x)，我们根据
f
(
x
)
f(x)
f(x)的大小来决定哪个doc排在前面，哪个doc排在后面。即如果
f
(
x
i
)
>
f
(
x
j
)
f(x_i)>f(x_j)
f(xi)>f(xj)，则
x
i
x_i
xi应该排在
x
j
x_j
xj前面，反之亦然。可以用下面的公式表示：
x
i
>
x
j
⇔
⟨
w
,
x
i
−
x
j
⟩
>
0
x_i >x_j \Leftrightarrow \langle w,x_i-x_j\ \rangle>0
xi>xj⇔⟨w,xi−xj ⟩>0
然后，便可以对
x
i
x_i
xi和
x
j
x_j
xj的差值向量考虑二元分类问题。特别地，我们可以对其赋值一个label：
f
(
n
)
=
{
+
1
,
if
x
i
−
x
j
>
0
−
1
,
if
x
i
−
x
j
<
0
f(n)= \begin{cases} +1, & \text {if $x_i-x_j>0$} \\ -1, & \text{if $x_i-x_j<0$} \end{cases}
f(n)={+1,−1,if xi−xj>0if xi−xj<0
则：
⟨
w
,
x
i
−
x
j
⟩
>
0
⇔
y
=
+
1
\langle w,x_i-x_j\ \rangle>0\Leftrightarrow y=+1
⟨w,xi−xj ⟩>0⇔y=+1
将排序问题转化为分类问题之后，就可以采用常用的分类模型来进行学习，选择Linear SVM或通过核函数的方法扩展的Nonlinear SVM。
2.2 IR SVM
RankSVM使用0-1分类损失函数实际使用hinge loss，这个函数与IR的常用指标是存在gap的，也就是只重视了doc之间的相对序关系，而忽视了doc之间相对序的量级关系。通过对SVM中的hinge loss进行改进得到IR SVM。
下图为IR SVM改进后的hinge loss：
IR SVM的优化问题可以表示如下：
min
w
∑
i
=
1
N
τ
k
(
i
)
μ
q
(
i
)
[
1
−
y
i
⟨
w
,
x
i
(
1
)
−
x
i
(
2
)
⟩
]
+
+
λ
∥
w
∥
2
\min_w \sum_{i=1}^N \tau_{k(i)}\mu_{q(i)}[1-y_i\langle w,{x_i}^{(1)}-{x_i}^{(2)} \rangle]_+ +\lambda{\lVert w\rVert}^2
wmini=1∑Nτk(i)μq(i)[1−yi⟨w,xi(1)−xi(2)⟩]++λ∥w∥2
τ
k
(
i
)
\tau_{k(i)}
τk(i)代表了隶属于第k档grade pair的instance的loss weight值，这个值的确定有一个经验式的方法：对隶属于这一档grade pair的两个doc，随机交换它们的排序位置，看NDCG@1的减少值，将所有的减少值求平均得到了这个loss weight。
μ
q
(
i
)
\mu_{q(i)}
μq(i)对应了query的归一化系数.可以表示为
1
n
q
\frac{1}{n_q}
nq1，即该query下的doc数目的倒数。
2.3 RankNet
是一种基于深度神经网络的pairwise方法，神经网络的输入是Q-D pair的特征，输出是相关性得分，可以用一个函数来表示：
s
=
f
(
q
,
d
o
c
)
s=f(q,doc)
s=f(q,doc)
RankNet巧妙地借用了Sigmoid函数来定义
d
o
c
i
doc_i
doci比
d
o
c
j
doc_j
docj更相关的概率为
P
i
j
=
P
(
d
o
c
i
>
d
o
c
j
)
=
1
1
+
e
−
σ
(
s
i
−
s
j
)
P_{ij}=P(doc_i>doc_j)=\frac {1}{1+e^{-\sigma(s_i-s_j)}}
Pij=P(doci>docj)=1+e−σ(si−sj)1
pairwise的真实概率标签是{-1，0，1}，在RankNet中我们继续沿用这套标签将其记为
S
i
j
∈
{
+
1
,
−
1
,
0
}
S_{ij}\in\lbrace+1,-1,0\rbrace
Sij∈{+1,−1,0}。由于是采用交叉熵作为损失函数因此将标签
S
i
j
S_{ij}
Sij与真实概率
P
ˉ
i
j
\bar{P}_{ij}
Pˉij进行一一映射，有：
P
ˉ
i
j
=
1
2
(
1
+
S
i
j
)
\bar{P}_{ij}=\frac{1}{2}(1+S_{ij})
Pˉij=21(1+Sij)
使用交叉熵作为损失函数，单个样本的交叉熵损失函数为：
C
i
j
=
−
P
ˉ
i
j
log
P
i
j
−
(
1
−
P
ˉ
i
j
)
log
(
1
−
P
i
j
)
C_{ij}=-\bar{P}_{ij}\log P_{ij}-(1-\bar{P}_{ij})\log(1-P_{ij})
Cij=−PˉijlogPij−(1−Pˉij)log(1−Pij)
RankNet还有一些特殊的加速方法。
2.4 LambdaRank
LambdaRank之于RankNet就相当于IRSVM之于RankSVM，是为了解决pairwise二分类解决方案与NDCG或者ERR等这些信息检索的评价指标之间的gap设计的。通过粗暴的在RankNet加速算法的梯度上在乘一项，以此定义了Lambda梯度。
λ
i
j
=
σ
[
1
2
(
1
−
S
i
j
)
−
1
1
+
e
−
σ
(
s
i
−
s
j
)
]
,
S
i
j
=
1
\lambda_{ij}=\sigma[\frac{1}{2}(1-S_{ij})-\frac{1}{1+e^{- \sigma (s_i-s_j)}}],S_{ij}=1
λij=σ[21(1−Sij)−1+e−σ(si−sj)1],Sij=1
λ
i
j
=
−
σ
1
+
e
−
σ
(
s
i
−
s
j
)
∣
△
Z
i
j
∣
\lambda_{ij}=-\frac{\sigma}{1+e^{-\sigma(s_i-s_j)}}\lvert\triangle Z_{ij}\rvert
λij=−1+e−σ(si−sj)σ∣△Zij∣
其中Z表示评价指标，可取NDCG、ERR等，把交换两个文档的位置引起的评价指标的变化作为其中一个因子，实验表明对模型效果有显著的提升。
2.5 FRank
FRank对RankNet的概率排序框架进行了进一步的研究，提出了名为Fidelity的新型损失函数来衡量排序损失，Fidelity不仅继承了RankNet中使用的损失函数的有效属性，它还拥有了几种有助于排序的新属性。
FRank和RankNet的区别仅在于损失函数的不同。FRank提出了RankNet的损失函数具有以下缺点：
- 当两个doc的相关程度相同时，即使模型精确学到了 f ( x i ) − f ( x v ) = 0 f(x_i)-f(x_v)=0 f(xi)−f(xv)=0仍然会带来损失。
- 损失没有上界，容易受到极端情况的影响。
Fidelity（保真度）最初是物理学中的一种距离度量，用于度量一个量子两种状态的差异。两个概率分布的Fidelity的定义如下：
F
(
p
x
,
q
x
)
=
∑
x
p
x
q
x
F(p_x,q_x)=\sum_x \sqrt{p_x q_x}
F(px,qx)=x∑pxqx
这里的
p
x
p_x
px和
q
x
q_x
qx是概率分布，当
p
x
p_x
px和
q
x
q_x
qx同分布时，
F
(
p
x
,
q
x
)
=
∑
x
p
x
=
1
F(p_x,q_x)=\sum_x p_x=1
F(px,qx)=∑xpx=1。
将Fidelity迁移至pairwise的loss funtion中可以得到FRank的损失函数：
F
i
j
=
F
(
o
i
j
)
=
1
−
(
P
ˉ
i
j
1
1
+
e
−
o
i
j
)
1
2
−
(
1
−
P
ˉ
i
j
)
(
1
1
+
e
o
i
j
)
1
2
F_ij=F(o_{ij})=1-(\bar{P}_{ij} \frac{1}{1+e^{-o_{ij}}})^{\frac{1}{2}}-(1-\bar{P}_{ij})(\frac{1}{1+e^{o_{ij}}})^{\frac{1}{2}}
Fij=F(oij)=1−(Pˉij1+e−oij1)21−(1−Pˉij)(1+eoij1)21
Fidelity loss和Binary cross entropy的对比如下：
由上图可见，Fidelity loss相比于BCE的良好性能：
- 损失函数在 o i j o_{ij} oij的定义域上是有界函数
- 当pairwise的两个样本相关性相等时，优化至 o i j = 0 o_{ij}=0 oij=0时会停止优化。
3.排序算法的设计
使用具有不一致性的优先函数对测试样本进行排序的问题称为“排列聚合（Rank Aggregation)”。排列聚合的目的是寻找对测试数据的一种排列，以使其中任意两两样本间的排列样本尽可能与优先函数吻合。
寻找排列聚合问题的最优解已经被证明是NPhard的。因此许多研究者都设计了相应的算法来解决排列聚合问题，下面我们会介绍其中一些非常有代表性的工作。
3.1 Greedy Ordering Algorithm
GOA（Greedy Ordering Algorithm）是该领域非常重要的一个算法。设 f ( x i , x j ) f(x_i,x_j) f(xi,xj)是事先训练好的优先函数，GOA中 f ( x i , x j ) f(x_i,x_j) f(xi,xj)的输出为1或-1：输出1表示样本 x i x_i xi优先于 x j x_j xj；输出-1表示样本 x j x_j xj优先于 x i x_i xi。因此这里的 f ( x i , x j ) f(x_i,x_j) f(xi,xj)不满足对称性。对于一个包含n个样本的待排数据集 X X X，GOA可描述如下：
- 对于样本集 X X X中的每一个样本 x i x_i xi,计算它的排序评分 π ( x i ) \pi(x_i) π(xi)： π ( x i ) = ∑ x j ∈ X , x i ≠ x j ( f ( x i , x j ) − f ( x j , x i ) ) . \pi(x_i)=\sum_{x_j\in X,x_i\neq x_j}(f(x_i,x_j)-f(x_j,x_i)). π(xi)=xj∈X,xi=xj∑(f(xi,xj)−f(xj,xi)).
- 从所有样本中选择排序评分最高的样本 x t x_t xt，将其加入到列表L中，然后将 x t x_t xt从集合 X X X中删除；
- 对X中剩余样本重复步骤1.和步骤2.，直到 X X X中没有样本。
GOA的作者证明了由GOA得到的排列结果与最优排列结果之间的关系。结论是：
如果最优排列结果中正确排序样本对的数量为 N N N，那么GOA得到的排列结果中正确排序样本对的数量一定大于或等于 N / 2 N/2 N/2。换言之，GOA能保证其精度下界为最优结果的一般。
GOA的缺点是它的时间复杂度较高，为 O ( n 2 ) O(n^2) O(n2)，因此当待排序样本数量较大时，GOA效率很低。
3.2 Gain
Gain与GOA只有一点区别，就是在GOA第一轮计算出所有样本的得票后，Gain直接用这个得票数量来对所有样本进行排序。
Gain在时间复杂度上也是
O
(
n
2
)
O(n^2)
O(n2)，其节约的时间仅仅是update分值时的减法操作。但在有限的实验结果来看，在时间复杂度少量增加的情况下，GOA略优于Gain。
3.3 Sum of Preferences
SOP（Sum of Preferences）在Gain的基础上，进行改进。
首先，SOP使用
P
(
x
i
>
x
j
)
=
f
(
x
i
,
x
j
)
f
(
x
i
,
x
j
)
+
f
(
x
j
,
x
i
)
P(x_i>x_j)= \frac{f(x_i,x_j)}{f(x_i,x_j)+f(x_j,x_i)}
P(xi>xj)=f(xi,xj)+f(xj,xi)f(xi,xj)来估计优先概率
P
(
x
i
>
x
j
)
P(x_i>x_j)
P(xi>xj)，而不像Gain和GOA一样仅使用输出优先函数的最终输出结果{-1,1}。
其次SOP以样本的优先概率之和作为他的ranking score，并使用该ranking score对样本进行排序。因此SOP仅仅是将Gain中的“优先函数投票累加”改成了“优先概率累加”。
3.4 QuickSort
直接利用实数排序中的经典算法”快速排序“来解决排列聚合问题。但定义在实数集上的排序算法都依赖与优先函数（即小于符号）的传递率，因此直接拿快速排序来解决排列聚合问题看起来有点奇怪。
方法是依据优先概率
P
(
x
i
,
x
j
)
P(x_i,x_j)
P(xi,xj)对样本集中的两个样本
x
i
x_i
xi和
x
j
x_j
xj换位，然后采用快速排序的方法进行排序。原论文中作者证明了这种方法应用于排列聚合问题的有效性，得出如下结论：
假设优先函数的错误率为e,QuickSort排序结果中的错误排序样本对的比率为r，那么r的期望不超过2e。
相比于GOA的结论，这个结论让人更加尴尬。因为他没有给出错误的上界，他给出的是错误率的期望上界，因此对于具体的问题无法准确得到r与e的关系是什么。虽然QuickSort的排序准确率效果很差，但效率却远高于上述三种方法。
3.5 Multi-QuickSort
Multi-QuickSort本质上是对待排序数据集独立多次使用3.4中的快速排序算法，然后将多次排序结果进行集成。
3.6 Fuzzy-Merge
结合归并排序和GOA的一种方法。简单理解为将归并过程替换为GOA的排序过程。该算法的实现还有一些细节，但由于利用传统排序算法的方法错误率的上界无法准确划定，因此不做深入研究。