树方法

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

精确解

精确意味着 XGBoost 考虑所有来自数据用于树分裂的候选，但其潜在目标仍然被解释为泰勒展开。

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

近似解

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

approx 树方法：参考文献中描述的一种近似树方法。它在构建每棵树之前使用所有行（属于根节点的行）进行草图绘制。在草图绘制期间，Hessian 被用作权重。该算法可以通过将 tree_method 设置为 approx 来访问。
hist 树方法：LightGBM 中使用的一种近似树方法，在实现上略有不同。它在训练前仅使用用户提供的权重而不是 Hessian 进行草图绘制。随后的每节点直方图是基于这个全局草图构建的。这是最快的算法，因为它只运行一次草图绘制。该算法可以通过将 tree_method 设置为 hist 来访问。

影响

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

其他更新器

Prune：它修剪现有树。prune 通常作为其他树方法的一部分使用。要独立使用修剪器，需要通过设置处理类型为更新：{"process_type": "update", "updater": "prune"}。使用这组参数，在训练期间，XGBoost 将根据两个参数 min_split_loss (gamma) 和 max_depth 修剪现有树。
Refresh：在新训练数据集上刷新已构建树的统计数据。与修剪器类似，要独立使用刷新器，需要将处理类型设置为更新：{"process_type": "update", "updater": "refresh"}。在训练期间，更新器将根据新的训练数据集更改诸如 cover 和 weight 等统计数据。当 refresh_leaf 也设置为 true（默认）时，XGBoost 将根据新的叶子权重更新叶子值，但树结构（分裂条件）本身不会改变。

demo/guide-python 中有关于训练延续（添加新树）和使用更新过程的示例。另请查看 XGBoost 参数中的 process_type 参数。
Sync：在分布式训练时，同步工作节点之间的树。

已移除的更新器

在开发过程中，由于可维护性问题，有 3 个更新器被移除。我们在此仅为文档的目的描述它们。

分布式 colmaker，它是精确树方法的分布式版本。它需要专门用于基于列的分裂策略和不同的预测过程。由于精确树方法本身就很慢，并且扩展效率更低，我们完全将其移除。
skmaker。grow_local_histmaker 使用的每节点加权草图绘制很慢，skmaker 未维护，似乎是一种试图消除直方图创建步骤并在分裂评估期间直接使用草图值的方法。它从未经过测试，并且包含一些未知错误，我们决定将其移除，并将资源集中于更有前途的算法。为了提高准确性，大多数情况下，approx 和 hist 足以通过一些参数调整，因此移除它们没有任何实际影响。
grow_local_histmaker 更新器：参考文献中描述的一种近似树方法。此更新器在实践中很少使用，因此它仍然是一个更新器而不是树方法。在寻找分裂时，它首先对属于当前节点的数据点运行加权 GK 草图绘制以找到分裂候选，使用 Hessian 作为权重。直方图是基于此每节点草图构建的。它在某些应用中比 exact 快，但计算仍然很慢。它被移除是因为它依赖于 Rabit 的自定义归约函数，该函数处理所有可以序列化/反序列化为固定大小缓冲区的数据结构，而 NCCL 或联邦学习 gRPC 不直接支持该功能，这使得将其重构为通用 allreducer 接口变得困难。

功能矩阵

下表总结了 4 种树方法在支持功能方面的一些差异，T 表示支持，F 表示不支持。

	Exact	Approx	Approx (GPU)	Hist	Hist (GPU)
grow_policy	深度优先	深度优先/损失引导	深度优先/损失引导	深度优先/损失引导	深度优先/损失引导
max_leaves	F	T	T	T	T
采样方法	均匀	均匀	基于梯度/均匀	均匀	基于梯度/均匀
分类数据	F	T	T	T	T
外部存储	F	T	P	T	P
分布式	F	T	T	T	T

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