树方法

在训练提升树模型时，有两个参数用于选择算法，即 updater 和 tree_method。XGBoost 有三种内置的树方法，分别是 exact、approx 和 hist。除了这些树方法外，还有一些独立的更新器，包括 refresh、prune 和 sync。参数 updater 比 tree_method 更原始，因为后者只是前者的预配置。这种差异主要是由于历史原因，每个更新器需要一些特定的配置，并且可能缺少某些功能。随着我们不断前进，它们之间的差距变得越来越不相关。我们将它们统一归档在树方法下。

精确解

精确意味着 XGBoost 在树分裂时考虑数据中的所有候选者，但其底层目标仍被解释为泰勒展开。

1. exact: 在 参考论文 中描述的原始梯度提升树算法。在寻找分割点时，它会遍历输入数据的所有条目。与其他贪婪方法相比，它的准确性更高，但计算速度较慢。此外，它的功能集有限。不支持需要近似分位数的分布式训练和外部内存等功能。此树方法可以通过将参数 tree_method 设置为 exact 来使用。

近似解

由于 exact 树方法在计算性能上较慢且难以扩展，我们通常采用近似训练算法。这些算法为每个节点构建梯度直方图，并通过直方图进行迭代，而不是通过实际数据集。这里我们介绍 XGBoost 中的实现。

1. approx 树方法：一种近似树方法，描述在 参考论文 中。它在构建每棵树之前使用所有行（属于根的行）进行草图绘制。在草图绘制过程中使用Hessian作为权重。可以通过将 tree_method 设置为 approx 来访问该算法。

2. hist 树方法：在 LightGBM 中使用的一种近似树方法，其实现略有不同。它在训练前仅使用用户提供的权重而不是 Hessian 进行草图绘制。后续的每个节点的直方图是基于这个全局草图构建的。这是最快的算法，因为它只运行一次草图绘制。可以通过将 tree_method 设置为 hist 来访问该算法。

影响

一些目标如 reg:squarederror 具有恒定的 Hessian。在这种情况下，应优先选择 hist，因为加权草图在恒定权重下没有意义。在使用非恒定 Hessian 目标时，有时 approx 可以提供更好的准确性，但计算性能较慢。大多数情况下，使用 hist 并提高 max_bin 可以在保持良好性能的同时达到相似甚至更高的准确性。然而，由于 xgboost 主要由社区驱动，实际实现与纯数学描述存在一些差异。结果可能与预期略有不同，这是我们目前正在努力克服的问题。

其他更新器

1. Prune: 它修剪现有的树。prune 通常作为其他树方法的一部分使用。要独立使用修剪器，需要将处理类型设置为更新，方法如下：{"process_type": "update", "updater": "prune"}。通过这组参数，在训练过程中，XGBoost 将根据两个参数 min_split_loss (gamma) 和 max_depth 修剪现有的树。

2. Refresh: 在新训练数据集上刷新构建树的统计信息。与剪枝器类似，要独立使用刷新功能，需要将处理类型设置为更新：{"process_type": "update", "updater": "refresh"}。在训练过程中，更新器将根据新的训练数据集更改 cover 和 weight 等统计信息。当 refresh_leaf 也设置为 true（默认）时，XGBoost 将根据新的叶子权重更新叶子值，但树结构（分裂条件）本身不会改变。

   在 demo/guide-python 上，既有训练继续（添加新树）的示例，也有使用更新过程的示例。同时，请查看 参数 中的 process_type 参数。

3. Sync: 在运行分布式训练时，同步工作节点之间的树。

移除的更新器

3 个更新器在开发过程中因可维护性问题被移除。我们在这里描述它们仅出于文档的兴趣。

1. 分布式 colmaker，这是精确树方法的分布式版本。它需要针对基于列的分割策略进行专门化，并采用不同的预测过程。由于精确树方法本身就很慢，扩展性更差，我们完全移除了它。

2. skmaker。 grow_local_histmaker 使用的按节点加权草图绘制速度较慢，skmaker 未维护，似乎是一种尝试消除直方图创建步骤并在分割评估期间直接使用草图值的权宜之计。它从未经过测试，包含一些未知的错误，我们决定移除它，并将资源集中在更有前途的算法上。为了准确性，大多数情况下 approx 和 hist 通过一些参数调整就足够了，因此移除它们没有任何实际的实际影响。

3. grow_local_histmaker 更新器：一种在 参考论文 中描述的近似树方法。这个更新器在实践中很少使用，因此它仍然是一个更新器而不是树方法。在寻找分割时，它首先对属于当前节点的数据点运行加权GK草图以找到分割候选，使用hessian作为权重。直方图是基于这个每个节点的草图构建的。它在某些应用中比``exact``更快，但在计算上仍然较慢。它被移除是因为它依赖于Rabit的自定义归约函数，该函数处理所有可以序列化/反序列化为固定大小缓冲区的数据结构，这在NCCL或联邦学习gRPC中没有直接支持，使得它很难重构为一个通用的allreducer接口。

功能矩阵

下表总结了四种树方法之间在支持功能上的某些差异，T 表示支持，而 F 表示不支持。

	精确	大约	近似 (GPU)	历史	Hist (GPU)
grow_policy	深度方向	depthwise/lossguide	depthwise/lossguide	depthwise/lossguide	depthwise/lossguide
max_leaves	F	T	T	T	T
采样方法	uniform	uniform	基于梯度的/均匀的	uniform	基于梯度的/均匀的
分类数据	F	T	T	T	T
外部存储器	F	T	P	T	P
分布式	F	T	T	T	T

此处未提及的功能/参数在所有3种树方法中都是普遍支持的（例如，列采样和约束）。外部内存中的`P`表示特殊处理。请注意，分类数据和外部内存均为实验性功能。