排序学习

目录

概述

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

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

使用 Pairwise 目标函数进行训练

LambdaMART 是一种 pairwise 排序模型，这意味着它会比较查询组中每一对样本的相关度，并为每对样本计算一个代理梯度。默认目标函数 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 不考虑查询组信息或 pairwise 损失。大多数指标作为 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]

位置偏差

2.0.0 版本新增。

注意

该功能被认为是实验性的。这是一个热门的研究领域，非常感谢您的意见和建议！

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

损失函数

XGBoost 根据不同的指标实现了不同的 LambdaMART 目标函数。我们在此列出作为参考。除了用作目标函数的指标外，XGBoost 还实现了用于评估的指标，如 pre（用于精确率）。有关可用选项，请参阅 parameters；有关如何根据有效 pair 数量选择这些目标函数，请参阅以下章节。

• NDCG

Normalized Discounted Cumulative Gain (标准化折损累积增益) NDCG 可用于二元相关度和多级相关度。如果您不确定自己的数据，此指标可用作默认值。此目标函数的名称为 rank:ndcg。

• MAP

Mean average precision (平均准确率) MAP 是一种二元度量。当相关性标签为 0 或 1 时可以使用它。此目标函数的名称为 rank:map。

• Pairwise

LambdaMART 算法将 logistic loss 与排序学习指标（如 NDCG）进行缩放，希望将排序信息纳入损失函数。 rank:pairwise 损失是 pairwise 损失的原始版本，也称为 RankNet loss [7] 或 pairwise logistic loss。与 rank:map 和 rank:ndcg 不同，它不进行缩放（\(|\Delta Z_{ij}| = 1\)）。

使用 LTR 指标进行缩放是否更有效仍然存在争议；[8] 为一般的 lambda 损失函数提供了理论基础，并对该框架提供了一些见解。

构建 Pair

对于 \(\lambda\) 梯度计算，有两种已实现的文档 pair 构建策略。第一种是 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] 提供了关于此主题的一些指导方针，建议用户查阅其工作中的分析。选择应基于有效 pair的数量，有效 pair 指的是可以产生非零梯度并有助于训练的 pair 数量。使用 MRR 的 LambdaMART 具有最少的有效 pair，因为当 pair 包含排名高于最相关文档的非相关文档时，\(\lambda\) 梯度才为非零。因此，它未在 XGBoost 中实现。由于 NDCG 是一个多级指标，它通常比 MAP 生成更多有效 pair。

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

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

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

另一方面，如果您优先考虑前 \(k\) 个文档，则应将 lambdarank_num_pair_per_sample 设置为略高于 \(k\) 的值（包含少量额外文档），以获得良好的训练结果。最后，XGBoost 为排序学习目标函数使用了额外的正则化，可以通过将 lambdarank_normalization 设置为 False 来禁用它。

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

• 使用与目标匹配的目标函数。

• 选择 topk 策略生成文档 pair（如果适用于您的应用）。

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

• 选择 NDCG 或 RankNet 损失 (rank:pairwise)。

• 选择 mean 策略生成文档 pair，以获得更多有效 pair。

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

分布式训练

XGBoost 实现了分布式排序学习，并集成了多种框架，包括 Dask、Spark 和 PySpark。接口与单节点版本类似。详情请参阅相应 XGBoost 接口的文档。

警告

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

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

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

然而，分布式框架可能在 map reduce 过程中对数据进行洗牌，并将每个查询组拆分到多个 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 (March 2009), 225–331。

[2] Christopher J. C. Burges, Robert Ragno, and Quoc Viet Le. 2006. “使用非光滑成本函数进行排序学习”. 载于 Proceedings of the 19th International Conference on Neural Information Processing Systems (NIPS’06)。MIT Press, Cambridge, MA, USA, 193–200。

[3] Wu, Q., Burges, C.J.C., Svore, K.M. 等人. “信息检索度量的 boosting 自适应”. Inf Retrieval 13, 254–270 (2010)。

[4] Ziniu Hu, Yang Wang, Qu Peng, Hang Li. “无偏 LambdaMART：一种无偏的 pairwise 排序学习算法”. Proceedings of the 2019 World Wide Web Conference。

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

[6] Pinar Donmez, Krysta M. Svore, and Christopher J.C. Burges. 2009. “关于 LambdaRank 的局部最优性”. 载于 Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval (SIGIR ‘09)。Association for Computing Machinery, New York, NY, USA, 460–467。

[7] Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. 2005. “使用梯度下降进行排序学习”. 载于 Proceedings of the 22nd international conference on Machine learning (ICML ‘05)。Association for Computing Machinery, New York, NY, USA, 89–96。

[8] Xuanhui Wang and Cheng Li and Nadav Golbandi and Mike Bendersky and Marc Najork. 2018. “用于排序指标优化的 LambdaLoss 框架”. Proceedings of The 27th ACM International Conference on Information and Knowledge Management (CIKM ‘18)。