XGBoost的二阶泰勒展开目标函数与正则化项设计

核心推导：从目标函数到分裂规则

XGBoost 的精华在于它如何优化一棵决策树。传统梯度提升树（GBDT）也使用梯度下降，但 XGBoost 走得更远。它引入了二阶导数和显式正则化项，这使得训练过程更精确，同时抑制过拟合。

本文将拆解 XGBoost 的目标函数，教你一步步理解其数学推导，最终掌握其核心分裂增益的计算公式。

第一阶段：构建带正则化的目标函数

XGBoost 的目标函数包含两部分：损失项（衡量预测值与真实值的差距）和正则化项（控制模型复杂度，防止过拟合）。目标是最小化这两项之和。

1. 写出基础目标函数 如下：
   $$ Obj = \sum_{i=1}^{n} L(y_i, \hat{y}_i) + \sum_{k=1}^{K} \Omega(f_k) $$
   其中，$L$ 是损失函数，$y_i$ 是真实值，$\hat{y}_i$ 是预测值。$\Omega(f_k)$ 是第 $k$ 棵树的正则化项，$K$ 是树的总数。

2. 拆解正则化项 $\Omega(f_k)$ 的设计如下：
   $$ \Omega(f_k) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2 $$
   这里，$T$ 是树的叶子节点数，$w_j$ 是第 $j$ 个叶子节点的权重（即该叶子的预测分值）。$\gamma$ 和 $\lambda$ 是超参数，控制惩罚力度。

3. 代入并简化。为清晰起见，将正则化项带入目标函数：
   $$ Obj = \sum_{i=1}^{n} L(y_i, \hat{y}_i) + \sum_{k=1}^{K} \left( \gamma T_k + \frac{1}{2} \lambda \sum_{j=1}^{T_k} w_{kj}^2 \right) $$
   这个公式看起来仍很复杂，因为要对所有树的叶子权重求和。下一步，我们将通过加法训练和泰勒展开对其进行简化。

第二阶段：应用二阶泰勒展开推导

XGBoost 采用加法训练（Additive Training）：在每一步，只优化一棵新增的树 $f_t(x)$，并且假设之前的 $t-1$ 棵树已经确定。核心思想是对当前的目标函数进行二阶泰勒展开，从而得到一个关于新树叶子权重的二次函数。

1. 定义当前预测值 和 新树贡献。设第 $t$ 轮迭代前，前 $t-1$ 棵树的预测值为 $\hat{y}_i^{(t-1)}$。则加入新树 $f_t(x_i)$ 后的新预测值为：
   $$ \hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i) $$

2. 重新定义第 $t$ 轮的目标函数（仅针对第 $t$ 棵树的参数）：
   $$ Obj^{(t)} = \sum_{i=1}^{n} L\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \Omega(f_t) + \text{constant} $$
   其中 constant 代表前 $t-1$ 棵树的正则化项，在当前优化时是常数，可以忽略。

3. 进行二阶泰勒展开。将 $L\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right)$ 在点 $\hat{y}_i^{(t-1)}$ 处展开：
   $$ L\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) \approx L\left(y_i, \hat{y}_i^{(t-1)}\right) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) $$
   这里，$g_i = \partial_{\hat{y}^{(t-1)}} L(y_i, \hat{y}^{(t-1)})$ 是一阶导数（梯度），$h_i = \partial_{\hat{y}^{(t-1)}}^2 L(y_i, \hat{y}^{(t-1)})$ 是二阶导数（海森矩阵，即Hessian矩阵）。在XGBoost中，$h_i$ 必须是正数。

4. 移除常数项。由于 $L\left(y_i, \hat{y}_i^{(t-1)}\right)$ 在当前优化中是常数，可以忽略。因此，简化后的目标函数为：
   $$ Obj^{(t)} \approx \sum_{i=1}^{n} \left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t) $$

第三阶段：从叶子权重到最终的增益公式

现在，我们将注意力集中在正在优化的这棵新树 $f_t$ 上。树的结构决定了一个样本 $x_i$ 被分到哪个叶子节点，而该叶子节点有一个权重 $w_{q(x_i)}$（$q(x_i)$ 表示 $x_i$ 所在的叶子索引）。因此，$f_t(x_i) = w_{q(x_i)}$。

1. 重新组织求和。所有落在叶子 $j$ 上的样本，它们的梯度和海森矩阵分别求和。定义叶子 $j$ 上的总梯度和总海森矩阵为：
   $$ G_j = \sum_{i \in I_j} g_i, \quad H_j = \sum_{i \in I_j} h_i $$
   其中 $I_j$ 是落在叶子 $j$ 上的样本索引集。

2. 将目标函数转化为关于叶子权重的二次函数。代入 $f_t(x_i) = w_j$ 和正则化项 $\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2$，目标函数变为：
   $$ Obj^{(t)} = \sum_{j=1}^{T} \left[ G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2 \right] + \gamma T $$

3. 求解最优叶子权重 $w_j^*$。对 $w_j$ 求导并令导数为0，得到：
   $$ w_j^* = - \frac{G_j}{H_j + \lambda} $$

4. 计算最终的目标函数值（损失值）。将 $w_j^*$ 代入目标函数表达式，得到在一棵给定结构树上的最小损失（也称为结构分数）：
   $$ Obj^* = - \frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T $$

5. 导出分裂增益。这是决策树分裂决策的核心依据。假设在某个节点，根据某个特征和分裂值，我们将样本分成左右两个集合（叶子 $L$ 和 $R$）。分裂前的损失是节点作为一个整体时的结构分数；分裂后的损失是两个子节点结构分数之和。增益 $Gain$ 为分裂前后损失的减少量：
   $$ 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 $$
   XGBoost 通过计算所有可能分裂的增益，并选择 $Gain > 0$ 且最大的分裂点来构建树。这里 $\gamma$ 起到了分支惩罚的作用 – 如果增益不足以抵消增加叶子节点的代价，则不会进行分裂。