排序学习

目录

概述

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

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

使用成对目标进行训练

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

QID	标签	功能
1	0	\(x_1\)
1	1	\(x_2\)
1	0	\(x_3\)
2	0	\(x_4\)
2	1	\(x_5\)
2	1	\(x_6\)
2	1	\(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)

请注意，截至撰写本文时，scikit-learn 中没有排序学习接口。因此，xgboost.XGBRanker 类不完全符合 scikit-learn 估算器指南，不能直接与其某些实用函数一起使用。例如，scikit-learn 中的 auc_score 和 ndcg_score 不考虑查询组信息或成对损失。大多数指标都作为 XGBoost 的一部分实现，但要使用 sklearn.model_selection.cross_validation() 等 scikit-learn 实用程序，我们需要进行一些调整，以便将 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]

位置偏差

2.0.0 版本新增。

注意

此功能被认为是实验性的。这是一个热门研究领域，非常感谢您的反馈！

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

损失函数

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

• NDCG

归一化折现累积增益 NDCG 可用于二元相关性和多级相关性。如果您不确定数据，此指标可用作默认值。此目标的名称是 rank:ndcg。

• MAP

平均平均精确率 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 接口的文档了解详情。

警告

现有分布式接口尚不支持位置去偏。

XGBoost 与集体操作协同工作，这意味着数据被分散到多个 worker。我们可以按查询组划分数据分区，并确保没有查询组在 worker 之间拆分。然而，这需要代价高昂的排序和分组操作，并且可能只在选定的用例中才需要。将查询组拆分并分散到多个 worker 在理论上是合理的，但可能会影响模型的准确性。如果只有少量组位于 worker 边界，那么小的差异不是问题，因为使用分布式训练时训练数据量通常很大。

更长的解释是，假设使用成对排序方法，我们通过在查询组中构建配对来计算基于相关度的梯度。如果一个单一查询组在 worker 之间拆分，并且我们使用 worker-local 数据进行梯度计算，那么我们只是从每个 worker 的较小组中采样配对来计算梯度和评估指标。配对之间的比较不会因为组被拆分为子组而改变，改变的是总配对和有效配对的数量以及诸如 IDCG 之类的归一化器。可以从一个大组生成比从两个较小子组生成更多的配对。因此，从理论角度来看，获得的梯度仍然有效，但可能不是最优的。只要 worker 中的每个数据分区都按查询 ID 正确排序，XGBoost 就可以相应地聚合样本梯度。而且 (Py)Spark 接口和 Dask 接口都可以根据查询 ID 排序数据，请参阅相应的教程了解更多信息。

然而，分布式框架可能会在 MapReduce 过程中打乱数据，并将每个查询组拆分到多个 worker。在这种情况下，性能将是灾难性的。因此，是否需要排序分组取决于数据和框架。

与 1.7 版本比较结果

排序学习的实现在 2.0 版本中进行了重大更新，增加了超参数和训练策略。为了获得与 1.7 版本 xgboost.XGBRanker 类似的结果，应使用以下参数

params = {
    # 1.7 only supports sampling, while 2.0 and later use top-k as the default.
    # See above sections for the trade-off.
    "lambdarank_pair_method": "mean",
    # 1.7 uses the ranknet loss while later versions use the NDCG weighted loss
    "objective": "rank:pairwise",
    # 1.7 doesn't have this normalization.
    "lambdarank_score_normalization": False,
    "base_score": 0.5,
    # The default tree method has been changed from approx to hist.
    "tree_method": "approx",
    # The default for `mean` pair method is one pair each sample, which is the default in 1.7 as well.
    # You can leave it as unset.
    "lambdarank_num_pair_per_sample": 1,
}

由于随机种子发生变化，结果仍然会有所不同。但 rank:pairwise 的整体训练策略将保持不变。

可重现的结果

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

[1]

minstd_rand 在 MSVC 上的实现不同。GCC 和 Thrust 的实现产生相同的输出。

参考文献

[1] Tie-Yan Liu. 2009. “信息检索的排序学习”. Found. Trends Inf. Retr. 3, 3 (2009 年 3 月), 225–331.

[2] Christopher J. C. Burges, Robert Ragno, 和 Quoc Viet Le. 2006. “使用非平滑成本函数进行排序学习”. 在第 19 届神经网络信息处理系统国际会议 (NIPS’06) 论文集。麻省理工学院出版社，马萨诸塞州剑桥，美国，193–200。

[3] Wu, Q., Burges, C.J.C., Svore, K.M. 等。“调整提升算法以适应信息检索度量”。信息检索 13，254–270 (2010)。

[4] Ziniu Hu, Yang Wang, Qu Peng, Hang Li. “无偏 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. “LambdaRank 的局部最优性”. 在第 32 届国际 ACM SIGIR 信息检索研究与开发会议 (SIGIR ‘09) 论文集。美国纽约 ACM 出版社，460–467。

[7] Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. 2005. “使用梯度下降进行排序学习”. 在第 22 届机器学习国际会议 (ICML ‘05) 论文集。美国纽约 ACM 出版社，89–96。

[8] Xuanhui Wang and Cheng Li and Nadav Golbandi and Mike Bendersky and Marc Najork. 2018. “用于排名指标优化的 LambdaLoss 框架”. 第 27 届 ACM 国际信息与知识管理会议 (CIKM ‘18) 论文集。