XGBoost 二阶手推

XGBoost 是带正则化的二阶梯度提升。目标函数 $\mathcal{L} = \sum_{i=1}^{n} l\left(y_i, \hat{y}_i\right) + \sum_{k=1}^{K} \Omega(f_k)$, 树正则 $\Omega(f) = \gamma T + \frac{1}{2} \lambda \Vert w \Vert^2$($T$ 为叶子数, $w$ 为叶子权重向量, $\gamma$ 是每片叶子的复杂度惩罚, $\lambda$ 是叶子权重的 L2 收缩)。第 $t$ 轮增量 $f_t$: $\hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i)$, 对损失在 $\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(x_i)^2$, 其中一阶导 $g_i = \frac{\partial l\left(y_i, \hat{y}_i^{(t-1)}\right)}{\partial \hat{y}_i^{(t-1)}}$, 二阶导 $h_i = \frac{\partial^2 l\left(y_i, \hat{y}_i^{(t-1)}\right)}{\partial \left(\hat{y}_i^{(t-1)}\right)^2}$。丢掉常数项, 第 $t$ 步目标化为 $\sum_{i=1}^{n} \left[ g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2 \right] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2$, 其中 $q(x)$ 把样本映射到叶子。按叶子聚组: 令 $I_j = \{ i \mid q(x_i) = j \}$, $G_j = \sum_{i \in I_j} g_i$, $H_j = \sum_{i \in I_j} h_i$, 目标成为 $\sum_{j=1}^{T} \left[ G_j w_j + \frac{1}{2}\left(H_j + \lambda\right) w_j^2 \right] + \gamma T$ — 对每个 $w_j$ 是独立的二次函数, 求导置零得最优叶子权重 $w_j^* = -\frac{G_j}{H_j + \lambda}$, 代入得最优目标 $\mathcal{L}^* = -\frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T$。分裂时把节点 $I = I_L \cup I_R$ 拆成左右子节点, 结构增益 $\text{Gain} = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{\left(G_L + G_R\right)^2}{H_L + H_R + \lambda} \right] - \gamma$ — 当且仅当 $\text{Gain} > 0$ 才分裂 ($\gamma$ 即最小分裂增益门槛, 与后剪枝同效)。常见损失: 平方损失 $g_i = 2\left(\hat{y}_i - y_i\right)$, $h_i = 2$; 逻辑回归 log-loss 时 $\hat{p}_i = \sigma\left(\hat{y}_i\right)$, $g_i = \hat{p}_i - y_i$, $h_i = \hat{p}_i\left(1 - \hat{p}_i\right)$。

“白板手推 XGBoost”是 2026 大厂 ML 面试出现频率最高的手推题之一 — 要求写全 目标函数 → 二阶泰勒展开 → 叶子权重 → 结构增益 的完整链路; 工程上 XGBoost 是表格数据竞赛的事实标准之一。

相比一阶 GBDT, 二阶展开等价于函数空间上的牛顿步 — 用曲率 (Hessian) 信息, 收敛更快, 分裂准则更准 (一阶梯度相同但曲率不同的分裂能被区分); 显式正则 $\gamma T + \frac{1}{2} \lambda \Vert w \Vert^2$ 把叶子权重收缩 ($\lambda$) 与分裂惩罚 ($\gamma$) 直接并入目标, 端到端抗过拟合; 工程上列采样、近似分位数直方图 (候选分裂点从 $O(n)$ 降到 $O(\text{bins})$)、稀疏感知分裂 (缺失值自动学习默认方向) 使其在大规模稀疏数据上实用。

白板手推 XGBoost: 从目标 $\sum_i l(y_i, \hat{y}_i) + \sum_k \Omega(f_k)$ 出发, 二阶泰勒展开得到 $\sum_i [g_i w_{q(x_i)} + \frac{1}{2} h_i w^2] + \lambda \Vert w \Vert^2$, 再推导最优叶子权重 $w_j^* = -\frac{G_j}{H_j + \lambda}$

白板推导分裂结构增益 $\text{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$: 什么时候不分裂?

为什么用二阶导? 与一阶 GBDT 相比的收敛优势; $g_i$, $h_i$ 在平方损失与交叉熵下分别是多少?

$\gamma$ 与 $\lambda$ 的作用: 复杂度惩罚如何影响叶子数与叶子权重? 与决策树剪枝的关系?

工程机制: 精确贪心 vs 近似分位数直方图、稀疏感知分裂 (缺失值默认方向)、列采样; 与 LightGBM 的差异