排名算法简介
排名算法简介' can be condensed to 'Ranking Algorithm Introduction'.
了解用于排序搜索结果的主要排名算法
介绍
学习排序(LTR)是一类监督式机器学习算法,旨在根据其与查询的相关性对项目列表进行排序。在传统的机器学习中,例如分类和回归问题,目标是根据特征向量预测单个值。LTR算法操作一组特征向量,并预测项目的最佳顺序。
LTR具有许多不同的应用。以下是其中一些应用:
- 搜索引擎。用户在浏览器搜索栏中输入查询。搜索引擎应该以最相关的结果出现在前几个位置。
- 推荐系统。电影推荐系统根据输入查询选择应向用户推荐哪部电影。
让我们正式定义排名问题:
给定一个存储有关查询和文档信息的n维特征向量,排名的目标是找到这样一个函数f,它产生一个实数,表示查询与文档的相关性。另外,如果对象i的排名高于对象j(i ▷ j),则f(i)应大于f(j)。
注意。i ▷ j表示文档i的排名高于文档j。
数据
特征向量
特征向量由三种类型的特征组成:
- 仅从文档派生的特征(例如文档长度,文档中的链接数)。
- 仅从查询派生的特征(例如查询长度,查询的频率)。
- 从文档和查询的组合派生的特征(例如TF-IDF,BM25,BERT,在文档和查询中共同的单词数)
训练数据
为了训练模型,我们需要将训练数据输入模型。根据训练数据的收集方式,有两种可能的方法。
- 离线LTR。数据由人工进行手动注释。人员对不同查询和文档的(查询,文档)对的相关性进行评级。这种方法成本高且耗时,但提供高质量的注释。
- 在线LTR。数据是从用户与查询结果的交互中隐式收集的(例如,排名项目上的点击次数,停留在网页上的时间)。在这种情况下,获取训练数据很简单,但用户交互不易解释。
之后,我们有对应于它们的特征向量和标签。这就是训练模型所需的一切。下一步是选择最适合问题的机器学习算法。
排名类型
从高层次来看,大多数LTR算法使用随机梯度下降来找到最优排名。根据算法在每次迭代中如何选择和比较项目的排名,存在三种主要方法:
- 点对点排名。
- 成对排名。
- 列表排名。
所有这些方法都将排名任务转化为分类或回归问题。在接下来的章节中,我们将看到它们在幕后的运作方式。
点对点排名
在点对点方法中,为每个特征向量单独预测分数。最终,预测的分数被排序。对于预测,使用哪种类型的模型(决策树,神经网络等)并不重要。
这种类型的排名将排名问题转化为回归任务,其中回归模型尝试以选定的损失函数(例如MSE)预测正确的相关性。
另一种有效的方法是将真实排名转换为one-hot表示,并将这些数据馈送给模型。在这种情况下,可以使用回归模型或分类模型(使用交叉熵损失)。

尽管该方法非常简单,但存在以下一些问题。
类别不平衡
使用点对点方法时常见的问题是类别不平衡。如果在现实生活中随机选择一个查询,那么只有很小一部分文档与之相关。因此,在训练数据中,与查询相关和不相关的文档之间存在很大的不平衡。
虽然可以克服这个问题,但还有一个更严重的问题需要考虑。
优化指标不佳
点对点排序在其优化目标上存在一个主要的基本问题:
点对点排序独立地优化文档得分,不考虑不同文档之间的相对得分。因此,它不能直接优化排序质量。
考虑下面的例子,点对点算法对两组文档进行了预测。假设在训练过程中优化的是均方误差损失。


给定两个排序结果,我们可以看到从算法的角度来看,第二个排序更好,因为相应的均方误差值更低。然而,选择第二个排序意味着用户将首先看到所有不相关的结果。顺便说一句,在第一个例子中,相关结果首先显示,这在用户体验上要好得多。通常,用户对推荐内容后续的关注度不高。
这个例子表明,在现实生活中,我们更关心首先显示相关结果以及项目的相对顺序。点对点的文档独立处理并不能保证这些方面。较低的损失并不等同于更好的排序。
成对排序
成对模型在每次迭代中处理一对文档。根据输入格式,有两种类型的成对模型。
成对输入模型
模型的输入是两个特征向量。模型的输出是第一个文档排在第二个文档之前的概率。在训练过程中,对不同特征向量对计算这些概率。根据真实的排序调整模型的权重。

在推理过程中,该方法有两个主要缺点:
- 为了对给定查询的n个文档进行排序,需要将这些文档的每一对都通过模型处理以获取所有成对概率。成对的总数是二次的(恰好等于n * (n — 1) / 2),这非常低效。
- 即使有了所有文档的成对概率,如何最终对它们进行排序也不明显,特别是在存在类似恶性循环的矛盾情况下,例如存在三个文档(x, y, z),模型的排序方式为:x ▷ y,y ▷ z和z ▷ x。

因为这些缺点,配对输入模型在实践中很少使用,而单输入模型则优于它们。
单输入模型
该模型接受单个特征向量作为输入。在训练过程中,对于成对的每个文档,都会独立地输入模型以获取其自己的分数。然后比较两个分数,并根据真实排名使用梯度下降调整模型。

在推理过程中,每个文档通过模型传递以获得一个分数。然后对这些分数进行排序以获得最终的排序。
对于熟悉连体网络(FaceNet,SBERT等)的人来说,可以将单输入模型视为连体网络。
成对损失函数
在每个训练迭代中,模型预测一对文档的分数。因此,损失函数应该是成对的,并考虑到两个文档的分数。
通常,成对损失函数以其参数 z 为两个分数 s[i] — s[j] 的差乘以一个常数 σ。根据算法的不同,损失函数可以有以下形式之一:

有时,分数差异 z 可以乘以一个常数。
RankNet 是最流行的成对排序算法之一。我们将在下一节中详细介绍其实现细节。
RankNet
在获得文档 i 和 j 的分数后,RankNet 使用 softmax 函数对其进行归一化。这样,RankNet 获得了概率 P[i][j] = P(i ▷ j),即文档 i 被排在文档 j 之前的概率。相反,我们可以计算概率 P̃[j][i] = P(j ▷ i) = 1 — P(i ▷ j)。为简单起见,假设实际上 i 被排在 j 之前,因此 P̃[i][j] = 1 且 P̃[j][i] = 0。对于模型权重的更新,RankNet 使用交叉熵损失,其简化如下:

模型的权重通过梯度下降进行调整。下一次模型获取相同的文档 i 和 j 时,文档 i 的分数很可能会比以前更高,而文档 j 则可能会被推下去。
RankNet 分解
为简单起见,我们不会深入研究数学,但在原始论文中提出了一个有趣的研究结果,作者找到了一种简化训练过程的方法。这是通过引入变量 S[i][j] 来实现的,它可以取三个可能的值之一:
经过一些数学技巧,交叉熵损失的导数被因式分解为:
公式中的lambda值是一个常数,可以相对快速地计算出所有文档对的值。通过取正或负值,这些lambda作为推动文档向上或向下的力量。
我们可以对单个文档i的所有成对lambda进行求和。这个求和结果就是在排名中应用于文档i的总力量。

直接使用lambda进行工作可以加快训练时间并获得更好的结果解释。
尽管成对算法的性能优于点对算法,但它们有两个缺点。
无法解释的概率
模型的输出概率只是显示模型对某个对象i排名高于对象j的自信程度。然而,这些概率并不是真实的,有时可以通过模型粗略近似,因此在解释上不是一个好主意,尤其是在我们之前看到的混乱情况中。
倒置数量的最小化不是最优的
这个问题比前一个问题更加严重。大多数成对算法和尤其是RankNet的基本问题是,它们最小化了排名倒置的数量。尽管优化倒置的数量可能看起来很自然,但实际上,大多数最终用户并不需要这样做。考虑以下两个排名的例子。在您的意见中,哪个排名更好?


尽管第二个排名具有较少的倒置,这是算法的优先级,但正常用户仍然更喜欢第一个排名,因为至少有一个相关结果位于顶部。这意味着用户不需要滚动很多文档才能找到第一个相关结果。同样,使用以用户为导向的nDCG或ERR等指标会更好,这些指标更加强调顶部结果而不是倒置的数量。
因此,我们可以看到并非所有文档对都同等重要。算法需要进行调整,更加重视在顶部获得正确的排名,而不是在底部。
论文的研究人员提供了一个很好的例子,说明使用RankNet优化排名可能会导致不理想的结果:
我们可以看到,第一个位置的文档被推到了第四个位置,第15个文档被推到了第十个位置,因此倒置的总数减少了2。然而,从用户体验的角度来看,新的排名变得更差了。核心问题在于RankNet对处于较差位置的文档分配了更大的梯度。然而,为了优化面向用户的度量标准,应该相反地工作:在较好的位置上的文档应该被推得更高。这样,面向用户的度量标准如nDCG将会更高。
列表排序
列表排序算法明确地优化排序度量标准。要用梯度下降优化某个度量标准,需要计算该度量标准的导数。不幸的是,大多数排序度量标准如nDCG或精度都是不连续且不可微分的,因此发明了其他先进的技术。
与点对点或对点排序不同,列表方法一次将整个文档列表作为输入。有时这会导致大量计算,但也会提供更强的鲁棒性,因为算法在每次迭代时获得了更多的信息。

LambdaRank
根据实现的不同,LambdaRank可以被视为对点或列表方法。
当关注nDCG时,将较大的梯度分配给两个文档的位置交换导致更高nDCG的对。这个核心思想就是LambdaRank。
算法名称中的“lambda”暗示了LambdaRank也使用了RankNet中描述的lambda进行优化。
研究人员取得了令人惊讶的结果,并证明如果在RankNet中的损失值乘以|nDCG|,那么该算法倾向于直接优化nDCG!也就是说,LambdaRank算法与RankNet非常相似,只是这一次lambda乘以nDCG变化:

研究的另一个令人难以置信之处在于,这个技巧不仅适用于nDCG,还适用于其他信息检索指标!类似地,如果lambda乘以精确度变化,那么精确度将被优化。
最近,有理论证明LambdaRank优化了某些信息检索指标的下界。
其他方法
我们不会详细讨论其他列表方法的工作原理,但仍然提供两个值得称赞的算法实现背后的主要思想。
LambdaMart是使用从LambdaRank导出的损失函数的梯度提升树的著名列表方法实现。实际上,它的性能优于LambdaRank。
SoftRank解决了nDCG导数存在性的问题。它创建了一个称为“SoftNDCG”的新度量,平滑地表示和近似nDCG,从而可以找到相应的导数,并通过梯度下降更新模型的权重。实际上,这种方法同样适用于其他指标。
结论
我们已经涵盖了排序-一种在机器学习中对一组对象进行排序的重要任务。点对点和对点方法并不经常使用,而列表方法最为鲁棒。显然,我们只讨论了排序算法的一小部分,但这些信息对于理解更复杂的技术如ListNet或ListMLE至关重要。可以在这里找到一个详尽的列表列表方法。
<p 值得注意的是,LambdaRank目前是最先进的排名算法之一,可以为优化特定指标提供很大的灵活性。
如果您想了解更多关于排序指标的信息,我强烈推荐您阅读我在这个主题上的其他文章。
综合排序评估指标指南
探索丰富的指标选择,找到最适合您问题的指标
towardsdatascience.com
资源
- 从RankNet到LambdaRank到LambdaMART:概述
- 使用梯度下降进行排序
- 信息检索 | 学习排序 | Harrie Oosterhuis
- 学习排序 | 维基百科
- SoftRank:优化非平滑排序指标
除非另有说明,所有图像均为作者所有