排名算法简介

排名算法简介' 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表示,并将这些数据馈送给模型。在这种情况下,可以使用回归模型或分类模型(使用交叉熵损失)。

点对点模型架构。模型接受查询和特征向量作为输入。

尽管该方法非常简单,但存在以下一些问题。

类别不平衡

使用点对点方法时常见的问题是类别不平衡。如果在现实生活中随机选择一个查询,那么只有很小一部分文档与之相关。因此,在训练数据中,与查询相关和不相关的文档之间存在很大的不平衡。

虽然可以克服这个问题,但还有一个更严重的问题需要考虑。

优化指标不佳

点对点排序在其优化目标上存在一个主要的基本问题:

点对点排序独立地优化文档得分,不考虑不同文档之间的相对得分。因此,它不能直接优化排序质量。

考虑下面的例子,点对点算法对两组文档进行了预测。假设在训练过程中优化的是均方误差损失。

集合包含5个文档,其中1个文档相关,其他4个文档不相关。对于相关文档,预测的相关性为0.7,对于其他文档为0.5。
集合包含5个文档,其中1个文档相关,其他4个文档不相关。对于相关文档,预测的相关性为0.1,对于其他文档为0.2。

给定两个排序结果,我们可以看到从算法的角度来看,第二个排序更好,因为相应的均方误差值更低。然而,选择第二个排序意味着用户将首先看到所有不相关的结果。顺便说一句,在第一个例子中,相关结果首先显示,这在用户体验上要好得多。通常,用户对推荐内容后续的关注度不高。

这个例子表明,在现实生活中,我们更关心首先显示相关结果以及项目的相对顺序。点对点的文档独立处理并不能保证这些方面。较低的损失并不等同于更好的排序。

成对排序

成对模型在每次迭代中处理一对文档。根据输入格式,有两种类型的成对模型。

成对输入模型

模型的输入是两个特征向量。模型的输出是第一个文档排在第二个文档之前的概率。在训练过程中,对不同特征向量对计算这些概率。根据真实的排序调整模型的权重。

成对输入模型架构。作为输入,模型接受一个查询和两个连接的特征向量。

在推理过程中,该方法有两个主要缺点:

  • 为了对给定查询的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 使用交叉熵损失,其简化如下:

RankNet 损失函数

模型的权重通过梯度下降进行调整。下一次模型获取相同的文档 i 和 j 时,文档 i 的分数很可能会比以前更高,而文档 j 则可能会被推下去。

RankNet 分解

为简单起见,我们不会深入研究数学,但在原始论文中提出了一个有趣的研究结果,作者找到了一种简化训练过程的方法。这是通过引入变量 S[i][j] 来实现的,它可以取三个可能的值之一:

经过一些数学技巧,交叉熵损失的导数被因式分解为:

公式中的lambda值是一个常数,可以相对快速地计算出所有文档对的值。通过取正或负值,这些lambda作为推动文档向上或向下的力量。

我们可以对单个文档i的所有成对lambda进行求和。这个求和结果就是在排名中应用于文档i的总力量。

对文档应用的总力量进行lambda求和

直接使用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优化公式

研究的另一个令人难以置信之处在于,这个技巧不仅适用于nDCG,还适用于其他信息检索指标!类似地,如果lambda乘以精确度变化,那么精确度将被优化。

最近,有理论证明LambdaRank优化了某些信息检索指标的下界。

其他方法

我们不会详细讨论其他列表方法的工作原理,但仍然提供两个值得称赞的算法实现背后的主要思想。

LambdaMart是使用从LambdaRank导出的损失函数的梯度提升树的著名列表方法实现。实际上,它的性能优于LambdaRank。

SoftRank解决了nDCG导数存在性的问题。它创建了一个称为“SoftNDCG”的新度量,平滑地表示和近似nDCG,从而可以找到相应的导数,并通过梯度下降更新模型的权重。实际上,这种方法同样适用于其他指标。

结论

我们已经涵盖了排序-一种在机器学习中对一组对象进行排序的重要任务。点对点和对点方法并不经常使用,而列表方法最为鲁棒。显然,我们只讨论了排序算法的一小部分,但这些信息对于理解更复杂的技术如ListNet或ListMLE至关重要。可以在这里找到一个详尽的列表列表方法。

<p 值得注意的是,LambdaRank目前是最先进的排名算法之一,可以为优化特定指标提供很大的灵活性。

如果您想了解更多关于排序指标的信息,我强烈推荐您阅读我在这个主题上的其他文章。

综合排序评估指标指南

探索丰富的指标选择,找到最适合您问题的指标

towardsdatascience.com

资源

  • 从RankNet到LambdaRank到LambdaMART:概述
  • 使用梯度下降进行排序
  • 信息检索 | 学习排序 | Harrie Oosterhuis
  • 学习排序 | 维基百科
  • SoftRank:优化非平滑排序指标

除非另有说明,所有图像均为作者所有