排序学习

概述

在信息检索的背景下，学习排序旨在训练一个模型，将一组查询结果排列成有序列表 [1]。对于监督学习排序，预测器是编码为特征矩阵的样本文档，标签是每个样本的相关性程度。相关性程度可以是多级的（分级）或二元的（相关或不相关）。训练样本通常按其查询索引分组，每个查询组包含多个查询结果。

XGBoost 通过一组目标函数和性能指标实现学习排序。默认目标是基于 LambdaMART [2] 算法的 rank:ndcg，这是对 LambdaRank [3] 框架在梯度提升树上的适应。有关该算法的背景和总结，请参阅 [5]。XGBoost 中的实现具有确定性的 GPU 计算、分布式训练、位置去偏和两种不同的配对构建策略。

使用成对目标进行训练

LambdaMART 是一个成对排序模型，这意味着它比较查询组中每对样本的相关性程度，并为每对样本计算一个代理梯度。默认目标 rank:ndcg 使用从 ndcg 指标派生的代理梯度。要训练一个 XGBoost 模型，我们需要一个额外的排序数组，称为 qid，用于指定输入样本的查询组。一个示例输入如下所示：

QID	标签	特性
`toctree` 是一个 reStructuredText 指令，这是一个非常多功能的标记。指令可以有参数、选项和内容。	0	\(x_1\)
`toctree` 是一个 reStructuredText 指令，这是一个非常多功能的标记。指令可以有参数、选项和内容。	`toctree` 是一个 reStructuredText 指令，这是一个非常多功能的标记。指令可以有参数、选项和内容。	\(x_2\)
`toctree` 是一个 reStructuredText 指令，这是一个非常多功能的标记。指令可以有参数、选项和内容。	0	\(x_3\)
2	0	\(x_4\)
2	`toctree` 是一个 reStructuredText 指令，这是一个非常多功能的标记。指令可以有参数、选项和内容。	\(x_5\)
2	`toctree` 是一个 reStructuredText 指令，这是一个非常多功能的标记。指令可以有参数、选项和内容。	\(x_6\)
2	`toctree` 是一个 reStructuredText 指令，这是一个非常多功能的标记。指令可以有参数、选项和内容。	\(x_7\)

请注意，样本是根据它们的查询索引按非递减顺序排序的。在上面的例子中，前三个样本属于第一个查询，接下来的四个样本属于第二个查询。为了简单起见，我们将在下面的代码片段中使用一个合成二进制学习排序数据集，二进制标签表示结果是否相关，并随机分配查询组索引给每个样本。有关使用真实世界数据集的示例，请参见开始学习排序。

from sklearn.datasets import make_classification
import numpy as np

import xgboost as xgb

# Make a synthetic ranking dataset for demonstration
seed = 1994
X, y = make_classification(random_state=seed)
rng = np.random.default_rng(seed)
n_query_groups = 3
qid = rng.integers(0, n_query_groups, size=X.shape[0])

# Sort the inputs based on query index
sorted_idx = np.argsort(qid)
X = X[sorted_idx, :]
y = y[sorted_idx]
qid = qid[sorted_idx]

训练排序模型的最简单方法是使用 scikit-learn 估计器接口。继续前面的代码片段，我们可以训练一个简单的排序模型而不进行调优：

ranker = xgb.XGBRanker(tree_method="hist", lambdarank_num_pair_per_sample=8, objective="rank:ndcg", lambdarank_pair_method="topk")
ranker.fit(X, y, qid=qid[sorted_idx])

请注意，截至撰写本文时，scikit-learn 中没有学习排序接口。因此，xgboost.XGBRanker 类不完全符合 scikit-learn 估计器指南，并且不能直接与某些实用函数一起使用。例如，scikit-learn 中的 auc_score 和 ndcg_score 不考虑查询组信息或成对损失。大多数指标作为 XGBoost 的一部分实现，但要使用 scikit-learn 的实用函数，如 sklearn.model_selection.cross_validation()，我们需要进行一些调整，以便将 qid 作为附加参数传递给 xgboost.XGBRanker.score()。给定一个数据框 X``（可以是 pandas 或 cuDF），按如下方式添加 ``qid 列：

import pandas as pd

# `X`, `qid`, and `y` are from the previous snippet, they are all sorted by the `sorted_idx`.
df = pd.DataFrame(X, columns=[str(i) for i in range(X.shape[1])])
df["qid"] = qid

ranker.fit(df, y)  # No need to pass qid as a separate argument

from sklearn.model_selection import StratifiedGroupKFold, cross_val_score
# Works with cv in scikit-learn, along with HPO utilities like GridSearchCV
kfold = StratifiedGroupKFold(shuffle=False)
cross_val_score(ranker, df, y, cv=kfold, groups=df.qid)

上述代码片段使用 LambdaMART 和 NDCG@8 指标构建了一个模型。排序器的输出是相关性分数：

scores = ranker.predict(X)
sorted_idx = np.argsort(scores)[::-1]
# Sort the relevance scores from most relevant to least relevant
scores = scores[sorted_idx]

位置偏差

Added in version 2.0.0.

备注

该功能被视为实验性的。这是一个热门的研究领域，您的输入非常受欢迎！

获取查询结果的真实相关性程度是一个昂贵且费力的过程，需要人工标注者逐一标注所有结果。当这种标注任务不可行时，我们可能希望在用户点击数据上训练学习排序模型，因为收集这些数据相对容易。直接使用点击数据的另一个优势是它可以反映最新的用户偏好 [1] 。然而，用户点击通常是有偏的，因为用户倾向于选择显示在更高位置的结果。用户点击也可能是噪声，用户可能会意外点击不相关的文档。为了改善这些问题，XGBoost 实现了 Unbiased LambdaMART [4] 算法来去偏位置依赖的点击数据。该功能可以通过 lambdarank_unbiased 参数启用；有关相关选项，请参阅学习排序的参数 (rank:ndcg, rank:map, rank:pairwise)，有关模拟用户点击的工作示例，请参阅开始学习排序。

损失

XGBoost 实现了基于不同度量的不同 LambdaMART 目标。我们在这里列出它们作为参考。除了用作目标函数的那些之外，XGBoost 还实现了诸如 ``pre``（用于精度）等用于评估的度量。有关可用选项，请参阅参数，以及以下部分，了解如何根据有效对的数量选择这些目标。

NDCG

Normalized Discounted Cumulative Gain NDCG 可以用于二元相关性和多级相关性。如果你不确定你的数据，这个指标可以作为默认使用。目标的名称是 rank:ndcg。

地图

平均精度均值 MAP 是一个二元度量。当相关性标签为0或1时可以使用。目标的名称为 rank:map。

成对

LambdaMART 算法通过学习排序指标（如 NDCG）来缩放逻辑损失，以期将排序信息纳入损失函数中。rank:pairwise 损失是成对损失的原始版本，也称为 RankNet 损失 [7] 或成对逻辑损失。与 rank:map 和 rank:ndcg 不同，没有应用缩放（\(|\Delta Z_{ij}| = 1\)）。

是否使用LTR指标进行扩展实际上更有效，这仍然有待商榷；[8] 为一般的lambda损失函数提供了理论基础，并对该框架提供了一些见解。

构建对

有两种实现策略用于构建 \(\lambda\)-梯度计算的文档对。第一种是 mean 方法，另一种是 topk 方法。首选策略可以通过 lambdarank_pair_method 参数指定。

对于 mean 策略，XGBoost 为查询列表中的每个文档采样 lambdarank_num_pair_per_sample 对。例如，给定一个包含 3 个文档的列表，并且 lambdarank_num_pair_per_sample 设置为 2，XGBoost 将随机采样 6 对，假设这些文档的标签不同。另一方面，如果对方法设置为 topk，XGBoost 构建大约 \(k \times |query|\) 对，其中每个样本在顶部 \(k = lambdarank\_num\_pair\) 位置有 \(|query|\) 对。这里计算的对数是一个近似值，因为我们跳过了具有相同标签的对。

获得良好结果

排序学习是一个复杂的任务，也是一个活跃的研究领域。训练一个泛化能力强的模型并非易事。XGBoost 提供了多种损失函数以及一组超参数。本节包含了一些如何选择超参数作为起点的提示。通过调整这些超参数，可以进一步优化模型。

第一个问题是如何选择一个与当前任务匹配的目标。如果你的输入数据具有多层次的相关性程度，那么应该使用 rank:ndcg 或 rank:pairwise。然而，当输入数据是二元标签时，我们有多重选择，这取决于目标指标。[6] 提供了一些关于此主题的指导，并鼓励用户查看他们在该工作中的分析。选择应基于有效对的数量，这指的是能够生成非零梯度并有助于训练的对数。LambdaMART 使用 MRR 时，有效对的数量最少，因为 \(\lambda\)-梯度仅在包含一个排名高于最高相关文档的非相关文档的对中才为非零。因此，它没有在 XGBoost 中实现。由于 NDCG 是一个多层次的指标，它通常比 MAP 生成更多的有效对。

然而，当存在足够多的有效对时，[6] 表明，将目标指标与目标匹配具有重要意义。当目标指标是 MAP 并且你使用的是一个可以提供足够多有效对的大型数据集时，理论上 rank:map 可以比 rank:ndcg 产生更高的 MAP 值。

对有效对的考虑也适用于配对方法的选择（lambdarank_pair_method）和每个样本的配对数量（lambdarank_num_pair_per_sample）。例如，平均-NDCG 考虑的对比 NDCG@10 更多，因此前者生成的有效对更多，提供的粒度也比后者更细。此外，使用 mean 策略可以帮助模型通过随机采样进行泛化。然而，有些人可能希望将训练重点放在前 \(k\) 个文档上，而不是使用所有对，以更好地适应他们的实际应用。

在使用均值策略生成对时，目标指标（如 NDCG）是基于整个查询列表计算的，用户可以通过设置 lambdarank_num_pair_per_sample 来指定每个文档应生成多少对。XGBoost 将为查询组中的每个元素随机采样 lambdarank_num_pair_per_sample 对（\(|pairs| = |query| \times num\_pairsample\)）。通常，将其设置为 1 可以产生合理的结果。在由于生成的有效对数量不足而导致性能不佳的情况下，可以将 lambdarank_num_pair_per_sample 设置为更高的值。随着生成更多的文档对，也会生成更多的有效对。

另一方面，如果你优先考虑排名前 \(k\) 的文档，lambdarank_num_pair_per_sample 应该设置得比 \(k\) 稍高（多几个文档）以获得良好的训练结果。最后，XGBoost 为排序学习目标采用了额外的正则化，这可以通过将 lambdarank_normalization 设置为 False 来禁用。

总结如果你有大量的训练数据：

使用目标匹配目标。
选择 topk 策略来生成文档对（如果这适合你的应用）。

另一方面，如果你有相对较少的训练数据：

选择 NDCG 或 RankNet 损失 (rank:pairwise)。
选择 mean 策略来生成文档对，以获得更有效的对。

对于任何选择的方法，您可以通过修改 lambdarank_num_pair_per_sample 来控制生成的对数。

分布式训练

XGBoost 实现了分布式学习排序，集成了多个框架，包括 Dask、Spark 和 PySpark。接口与单节点版本类似。请参阅相应 XGBoost 接口的文档以获取详细信息。将查询组分散到多个工作节点在理论上是合理的，但可能会影响模型精度。对于大多数用例，由于在使用分布式训练时通常训练数据量很大，因此这种小的差异不是问题。因此，用户不需要根据查询组来划分数据。只要每个数据分区都按查询 ID 正确排序，XGBoost 就可以相应地聚合样本梯度。

可重复结果

与其他任何任务一样，给定相同的硬件和软件环境（以及数据分区，如果使用分布式接口），XGBoost 应该生成可重复的结果。即使底层环境发生变化，结果也应保持一致。然而，当 lambdarank_pair_method 设置为 mean 时，XGBoost 使用随机采样，结果可能会因使用的平台而异。Windows（Microsoft Visual C++）上使用的随机数生成器与 Linux（GCC、Clang）等其他平台上使用的生成器不同 [1]，因此这些平台之间的输出差异显著。

参考文献

[1] 刘铁岩. 2009. “Learning to Rank for Information Retrieval”. Found. Trends Inf. Retr. 3, 3 (March 2009), 225–331.

[2] Christopher J. C. Burges, Robert Ragno, 和 Quoc Viet Le. 2006. “Learning to rank with nonsmooth cost functions”. 在第19届国际神经信息处理系统会议 (NIPS’06) 的论文集中。MIT Press, Cambridge, MA, USA, 193–200.

[3] Wu, Q., Burges, C.J.C., Svore, K.M. 等. “Adapting boosting for information retrieval measures”. Inf Retrieval 13, 254–270 (2010).

[4] 胡子牛, 王洋, 彭泉, 李航. “无偏LambdaMART: 一种无偏的成对学习排序算法”. 2019年世界万维网大会论文集.

[5] Burges, Chris J.C. “从RankNet到LambdaRank再到LambdaMART：概述”。MSR-TR-2010-82

[6] Pinar Donmez, Krysta M. Svore, 和 Christopher J.C. Burges. 2009. “On the local optimality of LambdaRank”. 在第32届国际ACM SIGIR会议关于信息检索研究和开发的论文集 (SIGIR ‘09). 美国纽约州纽约市计算机协会, 460–467.

[7] Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, 和 Greg Hullender. 2005. “Learning to rank using gradient descent”. 在第22届国际机器学习会议(ICML ‘05)的会议录中。美国纽约州纽约市，计算机协会，89–96。

[8] Xuanhui Wang 和 Cheng Li 和 Nadav Golbandi 和 Mike Bendersky 和 Marc Najork. 2018. “The LambdaLoss Framework for Ranking Metric Optimization”. Proceedings of The 27th ACM International Conference on Information and Knowledge Management (CIKM ‘18).