分裂查找算法：精确贪心

XGBoost利用正则化 (regularization)学习目标来构建构成其集成模型的决策树。分裂查找算法是这个树构建过程的一个主要组成部分。对于构建中的树中的每个候选节点，算法必须确定最佳特征以及该特征的最佳分裂点，以划分数据。“最佳”分裂被定义为使目标函数值减小量最大的分裂，这通常被称为增益。

XGBoost采用几种策略来查找分裂，最基本的一种是精确贪心算法。之所以称之为“精确”，是因为它详细评估了当前节点中实例的每个特征的每个可能分裂点。之所以称之为“贪心”，是因为它在每个节点上做出局部最优选择，选择增益最大的分裂，而不考虑对树中后续分裂的影响。

分裂质量的量化 (quantization)：增益计算

回顾步骤 $t$ 的XGBoost目标函数，它包含复杂度惩罚项：

$目标函数^{(t)} \approx \sum_{i=1}^{n} [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t)$

其中 $g_i$ 和 $h_i$ 是损失函数 (loss function)在步骤 $t-1$ 时关于实例 $i$ 预测值的一阶和二阶梯度。 $f_t(x_i)$ 是新树对实例 $i$ 的预测值，而 $\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2$ 是正则化 (regularization)项，其中 $T$ 是叶子数量，$w_j$ 是叶子 $j$ 的权重 (weight)。

对于固定的树结构，包含实例集 $I_j$ 的叶子 $j$ 的最佳权重 $w_j^*$ 为：

$w_j^* = - \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}$

且此树结构对应的最佳目标函数值为：

$目标函数^* = - \frac{1}{2} \sum_{j=1}^{T} \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma T$

我们定义 $G_j = \sum_{i \in I_j} g_i$ 和 $H_j = \sum_{i \in I_j} h_i$。目标函数变为：

$目标函数^* = - \frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T$

现在，考虑将包含实例 $I$ 的叶子（节点）分裂为两个子节点：一个包含实例 $I_L$ 的左子节点，和一个包含实例 $I_R$ 的右子节点，使得 $I = I_L \cup I_R$。这个分裂的增益是父节点（如果它保持为叶子）的目标函数值减去两个新子叶子的目标函数值之和。

如果节点 $I$ 不分裂（保持为单个叶子），则目标函数值为： $目标函数_{nosplit} = - \frac{1}{2} \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} + \gamma$

如果节点被分裂为 $I_L$ 和 $I_R$，则目标函数值为： $目标函数_{split} = - \frac{1}{2} \left( \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} \right) + 2\gamma$

增益定义为 $Gain = 目标函数_{nosplit} - 目标函数_{split}$。然而，XGBoost文献通常对增益的定义略有不同，它只关注目标函数第一部分的改进，并减去添加一个叶子的惩罚项 $\gamma$（因为分裂用两个叶子替换了一个叶子，增加了复杂度）：

$Gain = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} \right] - \gamma$

这个公式是精确贪心算法使用的主要计算。只有当结果增益为正（或大于最小阈值参数 (parameter) min_split_loss，在API中也称为 gamma）时，分裂才被认为是有效的。项 $\gamma$ 作为正则化参数，通过设定进行分裂所需的最小增益来控制复杂度。

精确贪心算法步骤

算法为每个节点执行以下操作：

1. 初始化 max_gain = 0。
2. 对于从 $1$ 到 $d$ 的每个特征 $k$（特征数量）： a. 令 $I$ 为当前节点中的实例集。 b. 计算总梯度 $G = \sum_{i \in I} g_i$ 和海森 $H = \sum_{i \in I} h_i$。 c. 根据特征 $k$ 的值对 $I$ 中的实例进行排序。 d. 初始化 $G_L = 0$， $H_L = 0$。 e. 从左到右遍历已排序的实例 $i$： i. 更新 $G_L = G_L + g_i$， $H_L = H_L + h_i$。 ii. 计算 $G_R = G - G_L$， $H_R = H - H_L$。 iii. 考虑当前实例 $i$ 和下一个实例之间的潜在分裂点（或者通常使用唯一的排序特征值作为潜在分裂点）。 iv. 使用以下公式计算此潜在分裂的增益： $Gain = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{G^2}{H + \lambda} \right] - \gamma$ v. 如果 $Gain > max\_gain$，则更新 $max\_gain = Gain$ 并存储当前特征 $k$ 和分裂点作为迄今为止找到的最佳分裂。
3. 如果 $max\_gain > 0$（或 max\_gain \ge \text{min_split_loss}），则使用找到的最佳特征和分裂点来分裂节点。否则，将节点声明为叶子。

下图说明了为单个特征找到最佳分裂点的过程：

单个特征的精确贪心算法的迭代过程。实例被排序，每个潜在分裂点根据增益计算进行评估。所有特征中的最佳分裂决定了节点的后续。

计算考量

精确贪心算法中主要的计算瓶颈是在每个节点上对特征值进行排序。如果有 $n$ 个实例到达一个节点，并且有 $d$ 个特征：

• 对于每个特征，排序需要 $O(n \log n)$ 时间。
• 排序后，扫描已排序的实例以找到最佳分裂点需要 $O(n)$ 时间。
• 对所有 $d$ 个特征执行此操作，每个节点的复杂度大约为 $O(d \times n \log n)$。

尽管很全面，但这种枚举在处理以下情况时可能会变得计算量大：

• 大量实例 ($n$)。
• 大量特征 ($d$)。
• 深度树（其中过程重复多次）。

这种计算成本促使了近似分裂查找算法的开发，我们将在下一节讨论这些算法。它们以牺牲找到绝对最佳分裂的一些准确性为代价，换取计算效率的显著提升，使XGBoost对非常大的数据集变得实用。

精确贪心算法是XGBoost中树构建的根本。它的优点在于对基于正则化 (regularization)目标函数的局部最优分裂进行详尽搜索。了解此过程对于理解XGBoost如何构建高效的树以及为什么有时需要近似算法等替代方法很重要。