树方法

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

精确解法

Exact 指的是 XGBoost 在树分裂时考虑所有数据中的候选分裂点，但其背后的目标函数仍然被解释为泰勒展开。

1. exact: 参考文献中描述的经典梯度提升树算法。在寻找分裂点时，它遍历输入数据的所有条目。它更准确（在其他贪心算法中），但计算速度比其他树方法慢。此外，它的功能集有限。不支持需要近似分位数的功能，如分布式训练和外部内存。将参数 tree_method 设置为 exact 即可使用此树方法。

近似解法

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

1. approx 树方法: 参考文献中描述的一种近似树方法。它在构建每棵树之前使用所有行（属于根节点的行）进行概要处理（sketching）。在概要处理期间，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，如下所示: {"process_type": "update", "updater": "prune"}。使用这组参数，在训练期间，XGBoost 将根据 min_split_loss (gamma) 和 max_depth 这两个参数对现有树进行剪枝。

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

   关于训练继续（添加新树）和使用更新过程的示例可以在 demo/guide-python 中找到。另请参阅 XGBoost Parameters 中的 process_type 参数。

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

已移除的更新器

开发期间由于维护性问题移除了3个更新器。我们在此描述它们仅为了文档的完整性。

1. Distributed colmaker，它是 exact 树方法的分布式版本。它需要针对基于列的分裂策略和不同的预测过程进行专门化处理。由于 exact 树方法本身就很慢且扩展效率更低，我们将其完全移除。

2. skmaker。由 grow_local_histmaker 使用的每个节点的加权概要处理（sketching）很慢，skmaker 没有维护，并且似乎是一个试图消除直方图创建步骤并在分裂评估期间直接使用概要处理值的变通方法。它从未经过测试并包含一些未知错误，我们决定将其移除，转而将资源集中在更有前景的算法上。为了精度，大多数情况下 approx 和 hist 经过一些参数调整就足够了，因此移除它们并没有实际影响。

3. grow_local_histmaker 更新器: 参考文献中描述的一种近似树方法。这种更新器在实践中很少使用，因此它仍然是一个更新器而不是树方法。在寻找分裂点时，它首先对属于当前节点的数据点进行加权GK概要处理（sketching）以找到候选分裂点，使用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 表示特殊处理。请注意，类别数据和外部内存都是实验性的。