排序算法介绍_八种排序算法效率比较「建议收藏」

1 Learing to Rank介绍

Learning to Rank (LTR)是一类技术方法，主要利用机器学习算法解决实际中的排序问题。传统的机器学习主要解决的问题是一个分类或者回归问题，比如对一个样本数据预测对应的类别或者预测一个数值分值。而LTR解决的是一个排序问题，对一个list的item进行一个排序，所以LTR并不太关注这个list的每个item具体得多少分值，更关注所有item的相对顺序。排序通常是信息检索的核心成分，所以LTR最常见的应用是搜索场景，对召回的document进行排序。对于排序算法从训练方式来看，主要分为三类：pointwise，pairwise和listwise方式，接下来对这三种方法进行介绍。

2 The Pointwise Approach

pointwise方法损失函数计算只与单个document有关，本质上是训练一个分类模型或者回归模型，判断这个document与当前的这个query相关程度，最后的排序结果就是从模型对这些document的预测的分值进行一个排序。对于pointwise方法，给定一个query的document list，对于每个document的预测与其它document是独立的。所以模型输入和对应的标签label形式如下：

• 输入: 单个document
• 标签label: document所属类型或者分值

pointwise方法将排序任务看做对单个文本的回归或者分类任务来做。若文档document的相关性等级有K种，则我们可以建模为一个有K个类别的 { 0 , 1 , 2 , . . . , K − 1 } \{0,1,2,…, K-1\} {
0,1,2,...,K−1}的Multi-class分类任务，则$y_i\in {\mathbb{R}}^k$是一个k维度的one-hot表示, 我们可以用交叉熵loss作为目标损失函数:
$$L=-（y_i\log (p_i)-(1-y_i)\log (1-p_i)]）$$

3 The Pairwise Approach

基于pairwise的方法，在计算目标损失函数的时候，每一次需要基于一个pair的document的预测结果进行损失函数的计算。比如给定一个pair对的document，优化器需要优化的是两个document的排序关系，与groud truth的排序顺序保持一致。目标是最小化与groud truth不一致的排序对。在实际应用中，pairwise方法比pointwise效果更好，因为预测相对的排序相比预测一个类别或者一个分值，更符合排序的性质。其中模型输入和对应的标签label形式如下：

• 输入: 一个pair对document (A,B)
• 输出标签: 相对顺序label (1, 0.5, 0)

其中1表示相关性等级A>B，0.5表示相关性等级A=B，0表示相关性等级A<B。目前使用较多的pairwise排序算法有RankNet，接下来对这种算法原理进行介绍。

3.1 RankNet

RankNet将排序问题转成对候选集所有document的pair对的分类问题，对query的document list分成两两pair对，并且根据每个文本的相关性等级，确定pair对的标签label， 如下图所示：

模型训练的任务是，判断两两pair之间的相关性相对大小。根据pair对的相关性等级大小，我们可以得到训练过程中每个pair对的标签label：
$$\overline{P_{ij}}=\{\begin{array}{l}1文本的相关性等级r_i>r_j\\ \frac{1}{2}文本的相关性等级r_i=r_j\\ 0文本的相关性等级r_i<r_j\end{array}$$
其中：
$$\overline{P_{ij}}=\frac{1}{2}(1+S_{ij})(1)$$
S i j ∈ { 0 , + 1 , − 1 } S_{ij} \in \{0, +1, -1\} Sij​∈{
0,+1,−1}，对于给定一个query，若文本$i$的相关性比文本$j$高，则$S_{ij}$=1, 若文本$i$的相关性比文本$j$高，则$S_{ij}$=-1,文本$i$的相关性与文本$j$相等，则$S_{ij}$=0。

而每个pair对模型预测的概率分值计算如下：
$$P_{ij}=\frac{1}{1+e^{-\sigma \cdot (s_i-s_j)}}(2)$$
参数$\sigma$决定了sigmoid函数的形状，其中$s_i$表示的是第$i$个document经过模型得到的预测分值。可以看出若$s_i-s_j$越大，则$P_{ij}$也越接近1，与pair对的标签$\overline{P_{ij}}=1$越符合。对于pair对，我们同样可以用交叉熵loss作为目标损失函数如下：
$$L=-\overline{P_{ij}}\log (P_{ij})-(1-\overline{P_{ij}})\log (1-P_{ij})(3)$$
通过Stochastic Gradient Descent随机梯度下降算法就可以优化求解模型参数权重了。在预测的阶段，对输入的是每个document得到模型预测分值$s_i$，根据document对应的分值就可进行排序结果。有人基于FRank对目标损失函数进行一个改进，试验效果取得了更好的结果，新定义的损失函数如下：
$$L=1-(\sqrt{\overline{P_{ij}}\cdot P_{ij}}+\sqrt{(1-\overline{P_{ij}})\cdot (1-P_{ij})})$$
如下是loss的函数图像对比情况：

基于pairwise的排序算法后面还有很多工作进行了改进，并取得了不错的效果，在这里就不一一介绍了。pairwise相对pointwise，不再假设绝对的相关性，而是有了相对的关系，但是排序的性质还没有完全在模型里得到体现。比如，如下两组排序，从pairwise来看，准确率是一致的，但是从整个排序效果来看，第二组是比第一组排序效果好的：

4 The Listwise Approach

Listwise方法是直接对整个list的document的排序进行优化，目标损失函数中优化整个list的document的排序结果。所以训练样本的输入和标签label输出结果如下：

• 输入: 整个list document
• 标签label: 排序好的document list

目前主要有两种方法来做listwise排序：

• 直接优化信息检索的测量指标：比如NDCG，这类型的算法主要由SoftRank, AdaRank等
• 最小化损失函数: 计算整个list的loss，最小化损失函数，比如ListNet，ListMLE等

4.1 直接优化评测指标

通过直接优化排序结果中的评测指标来优化排序任务，但是基于评测指标比如NDCG依赖排序结果，是不连续不可导的。所以优化这些不连续不可导的目标函数面临较大的挑战，目前多数优化技术都是基于函数可导的情况。那么如何解决这个问题？常见的有如下两种方法：

• 通过使用优化技术将目标函数转变成连续可导的函数，然后进行求解，比如SoftRank和 AdaRank等模型
• 通过使用优化技术对非连续的不可导目标函数就行求解，比如 LambdaRank

4.1.1 LambdaRank

LambadRank
上面介绍了RankNet的原理，RankNet优化目标是最小化pair对错误，但是在信息检索领域比如NDCG这样的评测指标，这样的优化目标并不能够最大化效果，通常在信息检索中我们更关注的是topN的排序结果，且相关性越大的文本最需要排在最前面。如下图所示：

给定一个query，上图为排序结果展示，其中蓝色的线表示的是相关的文档，灰色的线表示不相关的文档，那么在左图，有13个pair对错误，而在右图中，有11个pair对错误，在RankNet，右图的排序结果要比左图好，但是在信息检索指标中，比如NDCG指标，左图的效果比右边更好。
我们在上面介绍RankNet中，将上述(1)(2)公式代人到(3)公式中，我们可以得到损失函数如下：
$$C=\frac{1}{2}(1-S_{ij})\sigma (s_i-s_j)+log(1+e^{-\sigma (s_i-s_j)})(4)$$
从上面公式可以得出，当$S_{ij}=1$, 则损失函数变为如下：
$$C=log(1+e^{-\sigma (s_i-s_j)})(5)$$
要使得C变小，则$s_i$大于$s_j$且差距越大，C越小，与该pair对的相对相关性强度标签label $S_{ij}=1$(文本i比文本j更相关，也就是$s_i>s_j$）保持一致。
而当$S_{ij}=-1$，则代价函数如下：
$$C=log(1+e^{-\sigma (s_j-s_i)})(6)$$
同理，$s_j>s_i$差距越大，损失函数C越小，与该pair对的相对相关性强度标签label $S_{ij}=-1$(文本j比文本i更相关，也就是$s_j>s_i$）保持一致。
我们来计算下损失函数对$s_i$求导：
$$\frac{\partial C}{\partial s_i}=\sigma (\frac{1}{2}(1-S_{ij})-\frac{1}{1+e^{\sigma (s_i-s_j)}})=-\frac{\partial C}{\partial s_j}$$
那么损失函数对模型参数$w_k$的导数计算如下：
$$\frac{\partial C}{\partial w_k}=\frac{\partial C}{\partial s_i}\frac{\partial s_i}{\partial w_k}+\frac{\partial C}{\partial s_j}\frac{\partial s_j}{\partial w_k}$$
$$=\sigma (\frac{1}{2}(1-S_{ij})-\frac{1}{1+e^{\sigma (s_i-s_j)}})(\frac{\partial s_i}{\partial w_k}-\frac{\partial s_j}{\partial w_k})$$
我们定义：
$${\lambda }_{ij}=\frac{\partial C(s_i-s_j)}{\partial s_i}=\sigma (\frac{1}{2}(1-S_{ij})-\frac{1}{1+e^{\sigma (s_i-s_j)}})(7)$$
对于一个给定的query，我们定义$I$表示所有pair对的索引 { i , j } \{i,j\} {
i,j}，其中文本$U_i$的相关性大于$U_j$，也就是说$S_{ij}=1$，则上面的公式转变形式为：
$${\lambda }_{ij}=-\frac{\sigma }{1+e^{(s_i-s_j)}}<0(8)$$
因为${\lambda }_{ij}<0$，则由于这个pair对产生的梯度更新$s_i-{\lambda }_{ij}>s_i$，$s_i$是增加的，也就是若$U_i>U_j$，模型的每次调整需要调高$s_i$的预测值，但是对于另外一些pair对(j, i) ，$U_j>U_i$，对于这样的pair对，更新梯度后，需要调低$s_i$的分值。所以综合所有的pair对情况，对于文本$U_i$我们计算梯度${\lambda }_i$公式如下：
λ i = ∑ j : { i , j } ∈ I λ i j − ∑ j : { j , i } ∈ I λ i j    ( 9 ) \lambda_i = \sum_{j:\{i,j\} \in I} \lambda_{ij} – \sum_{j:\{j,i\}\in I} \lambda_{ij} \text{ }\text{ } (9) λi​=j:{
i,j}∈I∑​λij​−j:{
j,i}∈I∑​λij​  (9)
对于所有的pair对，那些 { i , j } ∈ I \{i,j\} \in I {
i,j}∈I需要调高$s_i$，而那些 { k , i } ∈ I \{k,i\} \in I {
k,i}∈I的则需要调低$s_i$，最后，综合所有pair对，由上述公式(8)决定梯度值${\lambda }_i$是小于0还是大于0，决定是调高$s_i$值还是调低$s_i$的值。RankNet就是由所有pair对错误情况去调整每个文本的$U_i$的排序位置，但是并不很适合信息检索类似NDCG这样的指标。
所以在LambdaRank算法里，定义的梯度${\lambda }_{ij}$公式如下：
$${\lambda }_{ij}=\frac{\partial C(s_i-s_j)}{\partial s_i}=\frac{-\sigma }{1+e^{{\sigma }^{(s_i-s_j)}}}|\Delta NDCG|(10)$$
在公式(8)的基础上再乘以$|\Delta NDCG|$，而$|\Delta NDCG|$表示的是交换$U_i$和$U_j$两个文本 (其它文本保持不变）后对应的NDCG分数的变化。
为什么要乘以这个变化后的$|\Delta NDCG|$?
${\lambda }_i$代表了文档$U_i$下一次优化是提升还是下降，对于RankNet，根据pair对的错误数量决定调整，但是lambdarank还要考虑pair对的重要性(用变化后的NDCG表示），pair对(i,j)交换位置后，对应的$|\Delta NDCG|$若变化很大，那说明$U_i$是个很重要的文本，这个pair对的${\lambda }_{ij}$起到的作用要增大，所以我们可以理解用$|\Delta NDCG|$代表这个${\lambda }_{ij}$权重，防止对重要文本下调。

4.1.2 LambdaMART

LambdaMART是Lambda和MART(Multiple Additive Regression Tree)组成，上面部分我们介绍了Lambda，根据导数公式(10)可知，损失函数C定义如下：
C = ∑ { i , j } ∣ Δ Z i j ∣ l o g ( 1 + e − σ ( s i − s j ) ) C=\sum_{\{i,j\}}|\Delta Z_{ij}|log(1+e^{-\sigma(s_i-s_j)}) C={
i,j}∑​∣ΔZij​∣log(1+e−σ(si​−sj​))
这里的$|\Delta Z_{ij}|$表示的信息检索指标，比如NDCG等。损失函数的一阶导数为：
∂ C ∂ s i = ∑ { i , j } − σ ∣ Δ Z i j ∣ 1 + e σ ( s i − s j ) = ∑ i , j − σ ∣ Δ Z i j ∣ p i j \frac{\partial C}{\partial s_i} = \sum_{\{i,j\}} \frac{-\sigma |\Delta Z_{ij}|}{1+e^{\sigma(s_i-s_j)}}=\sum_{i,j}-\sigma|\Delta Z_{ij}|p_{ij} ∂si​∂C​={
i,j}∑​1+eσ(si​−sj​)−σ∣ΔZij​∣​=i,j∑​−σ∣ΔZij​∣pij​
我们定义：
$$p_{ij}=\frac{1}{1+e^{\sigma (s_i-s_j)}}=\frac{-{\lambda }_{ij}}{\sigma |Z_{ij}|}$$
那么二阶导数为：
∂ 2 C ∂ s i 2 = ∑ { i , j } σ 2 ∣ Δ Z i j ∣ p i j ( 1 − p i j ) \frac{\partial^2C}{\partial s_i^2} = \sum_{\{i,j\}} \sigma^2|\Delta Z_{ij}|p_{ij}(1-p_{ij}) ∂si2​∂2C​={
i,j}∑​σ2∣ΔZij​∣pij​(1−pij​)
LambdaMART模型是由许多棵决策树，通过Boosting思想组成，每颗决策树拟合的是损失函数的梯度，其中叶子节点的权重$w$具体求解涉及一阶梯度和二阶梯度，大家可以先了解GBDT算法原理讲解，对一些基本原理进行熟悉。而在这里求解的梯度用lambda方式求解。LambdaMART算法求解步骤如下：
可以看出这里求解一阶和二阶导数用lambda替代，算法的逻辑和求解boosting算法逻辑一致。

4.2 定义Listwise损失函数

4.2.1 ListNet

ListNet与RankNet很相似，RankNet是用pair对文本排序顺序进行模型训练，而ListNet用的是整个list文本排序顺序进行模型训练。若训练样本中有m个query，假如对应需要排序的最多文本数量为n ，则RankNet的复杂度为$O(m\cdot n^2)$，而ListNet的复杂度为$O(m\cdot n)$，所以整体来说在训练过程中ListNet相比RankNet更高效。
假设对于query $q^i$对应排序的文本为：
$$d^i=(d_1^i,d_2^i,d_3^i,...,d_n^i)$$
其中对应的特征为：
$$x^i=(x_1^i,x_2^i,x_3^i,...,x_n^i)$$
假设我们用神经网络模型作为基础的分值预测，那么对每个样本的特征输入，模型都会给出预测分值：
$$z^i=(f(x_1^i),f(x_2^i),...,f(x_n^i))$$
对于每个文本的实际分值记录为：
$$y^i=(y_1^i,y_2^i,...,f_n^i)$$
则我们可以定义损失函数为：
$$\sum _{i=1}^{m}L(y^i,z^i)$$
这里的L我们可以用交叉熵损失函数定义，度量两个分布$y^i,z^i$之间的差异：
$$L(y^i,z^i(f_w))=-\sum _{j=1}^n{P}_{y^i}(x_j^i)log(P_{z^i(f_w)}(x_j^i))$$
其中$P_{y^i}(x_j^i)$表示的对于给定query $i$，对应第$j$个文本输入特征为$x_j^i$对应的概率值，这个概率值我们可以根据每个文档的等级分值，经过一个softmax函数求出概率值，比如，对应的文本相关性等级为：
y i = { 5 , 4 , 3 , 1 } y^i=\{5, 4, 3, 1\} yi={
5,4,3,1}
则第一个文本等级为5对应的概率分值为：
$$P(x_1^i)=\frac{e^5}{e^5+e^4+e^3+e^1}$$
而经过神经网络$f_w$，每个文本对应的概率分值也是经过一个softmax函数求得：
$$P_{z^i(f_w)(x_j^i)}=\frac{\exp (f_w(x_j^i))}{{\sum }_{k=1}^n\exp (f_w(x_k^i))}$$
这样我们就可以用交叉熵损失函数度量两个分布之间的差异，计算出loss，然后用梯度下降算法求解。

4.2.2 ListMLE

ListMLE也是基于list计算损失函数，论文对learning to rank算法从函数凸性，连续性，鲁棒性等多个维度进行了分析，提出了一种基于最大似然loss的listwise排序算法，取名为ListMLE。损失函数定义如下：
$$L(g(x),y)=-logP(y|x;g)$$
其中$P(y|x;g)$概率计算如下：
$$P(y|x;g)=\prod _{i=1}^n\frac{\exp (g(x_{y(i)}))}{{\sum }_{k=i}^n\exp (g(x_{y(k)}))}$$
我们用一个具体的例子来说明上述公式，假如对给定的query，其中对应的文本相关性等级为:
$$D=[3,5,1,2]$$
模型预测的logit分值对应为：
$$pred=[2.2,3.1,1.8]$$
按照D的相关性文本大小对应模型预测的分值顺序调整后为：
$$pre{d}^s=[3.1,2.2,1.8]$$
则对应的概率分值为：
$$P=\frac{3.1}{3.1+2.2+1.8}\times \frac{2.2}{2.2+1.8}\times \frac{1.8}{1.8}$$
对应的最大似然loss为：
$$loss=-\log (P)$$

5 排序评估指标

在排序任务中，模型对候选集进行打分，得到一个排序结果，再与真实的排序结果进行对比，通过一些指标来衡量排序模型的预测效果。而用的较广泛的评判标注主要分三部分：

• Binary judgment: 判断query与document相关与不相关，两种结果
• Multi-level ratings: 分perfect >excellent > good >fair > bad 5种相关性等级
• pairwise preferences: 给定一个query的两个document A, B，判断A与B谁相对query更相关

那么如何衡量排序模型的效果呢？接下来会对测评指标进行简单的介绍。

5.1 Mean Reciprocal Rank (MRR)

对于给定query $q$以及与该query相关的文本 D = { d 1 , d 2 , d 3 , d 4 , d 5 } D=\{d_1,d_2,d_3,d_4,d_5\} D={
d1​,d2​,d3​,d4​,d5​}，假设文本与query的相关性程度依次递减已经排好序，若排序模型预测的顺序是 r a n k = { d 2 , d 3 , d 1 , d 5 , d 4 } rank=\{d_2,d_3,d_1,d_5,d_4\} rank={
d2​,d3​,d1​,d5​,d4​}，则与该query第一相关的文本$d_1$所在的排序位置记为$r(q)=3$，则对于这个query的MRR指标计算结果为：
$$\text{MRR}=\frac{1}{r(q)}=\frac{1}{3}$$
该指标对应的值越大越好，且取值范围为$[\frac{1}{N},1]$，其中$N$表示的是排序的总文本数量。

5.2 Mean Average Precision (MAP)

MAP是排序模型效果评估的另外一个评价指标，首先我们定义在位置$k$的精确率记为：$P@k$，具体计算结果为：

P @ k ( q ) = # { relevant documents in the top k positions } k P@k(q) = \frac{\#\{\text{relevant documents in the top k positions}\}}{k} P@k(q)=k#{
relevant documents in the top k positions}​
则平均精确率AP定义如下：
A P ( q ) = ∑ k = 1 m P @ k ( q ) ⋅ l k # { relevant documents} AP(q) = \frac{\sum_{k=1}^m P@k(q) \cdot l_k}{\#\{\text{relevant documents\}}} AP(q)=#{
relevant documents}∑k=1m​P@k(q)⋅lk​​
其中$m$表示的是query $q$对应的所有文本数量，$l_k$取值为{0,1}，判断在第$k$个位置上的文本是否与query相关，相关为1，不相关为0。假设query对应排序的有5个document，其中红色代表不相关，绿色代表相关，则AP指标计算结果为：

$$AP=\frac{1}{3}\cdot (\frac{1}{1}+\frac{2}{3}+\frac{3}{5})$$

则最后的MAP指标表示所有query的平均AP值：
$$\text{MAP}=\frac{1}{m}\sum _i^{m}AP(q_i)$$

5.3 Normalized Discounted Cumulative Gain (NDCG)

前面的测量标准主要基于是否相关的0-1 binary决策，而DCG可以对包含多个相关性程度的类别进行测评，同时将位置衰减因子也定义到了计算公式里，假设对于query $q$，排序模型预测的相关性结果从高到低排序后记为$\pi$，则在位置k的DCG指标定义如下：
$$DCG@k(q)=\sum _{r=1}^{k}G(\pi (r))\eta (r)$$
其中$\pi (r)$表示的是排序$\pi$整个list在位置为$r$的原始文档相关性等级，$G(\cdot )$是对文档相关性计算出的新的等级分值，一般计算函数如下：
$$G(\pi (r))=2^{\pi (r)}-1$$
其中$\eta (r)$表示的是位置衰减因子，通常计算公式如下：
$$\eta (r)=\frac{1}{{\log }_2(r+1)}$$
所以从DCG公式可以看出，若相关性等级越高的文档排序越靠后，则由于$\eta (r)位置衰弱的越大，$DCG分值越低，且将位置信息融入到了计算公式里。则归一化的Normalized DCG (NDCG) 指标计算公式如下：
$$NDCG@k(q)=\frac{1}{Z_k}\sum _{r=1}^{k}G(\pi (r))\eta (r)=\frac{{\sum }_{r=1}^k(2^{\pi (r)}-1)\cdot (1/{\log }_2(r+1))}{Z_k}$$
其中$Z_k$是归一化因子，其计算值为DCG@k的最大值，也就是query对应的理想排序list (相关性等级越高，排在越靠前），可以看出NDCG@k(q)计算公式由4部分组成：归一化因子$Z_k$, 累积求和:${\sum }_{r=1}^k$，信息增益Gain: $(2^{\pi (r)}-1)$以及位置衰减: $1/{\log }_2(r+1))$, NDCG的取值范围为[0,1]。若根据Relevance Rating进行打标，则信息增益Gain值如下：

5.4 Rank Correlation (RC)

RC指标是衡量模型预测的一个排序list $\pi$与groudtruth标准排序list ${\pi }_l$之间的相关性。用带权重的Kendall等级相关系数作为评估准则，评估两个排序list中两两不一样的pairwise排序一致性情况，计算公式定义如下：
$$RC=\frac{{\sum }_{u<v}{w}_{u,v}(1+sgn((\pi (u)-\pi (v))({\pi }_l(u)-{\pi }_l(v))))}{2{\sum }_{u<v}{w}_{u,v}}$$
其中sgn是符合函数，定义如下：
$$sgn=\{\begin{array}{l}1x>0\\ 0x=0\\ -1x<0\end{array}$$
从上述公式可以看出，模型预测的排序list中两两pair对相对排序顺序与真实groudtruth中两个pair相对排序顺序一致的pair对越多，则RC计算的分值越大。

6 参考

Learning to Rank wikipedia
Learning to Rank for Information Retrieval
Learning to Rank: From Pairwise Approach to Listwise Approach
earning to rank using gradient descent
Listwise approach to learning to rank: theory and algorithm
Yahoo! Learning to Rank Challenge Overview
Metric Learning to Rank

今天的文章排序算法介绍_八种排序算法效率比较「建议收藏」分享到此就结束了，感谢您的阅读。