XGBoost算法的原理与构建过程
题目描述
XGBoost（eXtreme Gradient Boosting）是一种基于梯度提升框架的机器学习算法，广泛应用于分类、回归和排序任务。其核心思想是通过迭代地训练多个弱学习器（通常是决策树），并将它们组合成一个强学习器。要求详细解释XGBoost的目标函数设计、正则化策略、分裂节点的方法，以及如何通过加权分位数草图等技术优化计算效率。
解题过程
- 目标函数设计
- XGBoost的目标函数包括损失函数和正则化项。对于包含 \(n\) 个样本的数据集，第 \(t\) 次迭代的目标函数为：
\[ \text{Obj}^{(t)} = \sum_{i=1}^n L\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \Omega(f_t) \]
其中 $ L $ 是损失函数（如均方误差或交叉熵），$ \hat{y}_i^{(t-1)} $ 是前 $ t-1 $ 棵树的预测值，$ f_t $ 是第 $ t $ 棵树，$ \Omega(f_t) $ 是正则化项。
- 通过二阶泰勒展开近似目标函数：
\[ \text{Obj}^{(t)} \approx \sum_{i=1}^n \left[ L(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t) \]
其中 $ 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)}) $ 分别为损失函数的一阶和二阶梯度。
- 正则化与树结构定义
- 正则化项 \(\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2\)，其中 \(T\) 是叶子节点数，\(w_j\) 是第 \(j\) 个叶子节点的权重，\(\gamma\) 和 \(\lambda\) 是超参数，用于控制树结构的复杂度和权重幅度。
- 将样本按叶子节点分组，定义 \(I_j = \{ i \mid f_t(x_i) \in \text{叶子节点} j \}\)，目标函数可重写为：
\[ \text{Obj}^{(t)} = \sum_{j=1}^T \left[ \left(\sum_{i \in I_j} g_i\right) w_j + \frac{1}{2} \left(\sum_{i \in I_j} h_i + \lambda\right) w_j^2 \right] + \gamma T \]
- 对 \(w_j\) 求导，得到最优叶子权重：
\[ w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} \]
代入目标函数后，得到最小化目标：
\[ \text{Obj}^* = -\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 \]
- 分裂节点算法
- 使用贪心策略选择分裂特征和阈值：遍历所有特征的可能分裂点，计算分裂后的增益：
\[ \text{Gain} = \frac{1}{2} \left[ \frac{(\sum_{i \in I_L} g_i)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{(\sum_{i \in I_R} g_i)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{(\sum_{i \in I} g_i)^2}{\sum_{i \in I} h_i + \lambda} \right] - \gamma \]
其中 $ I_L $ 和 $ I_R $ 是分裂后的左右子节点样本集。选择增益最大的分裂点，但仅当增益为正时才分裂。
- 优化技巧：
- 预排序算法：提前对特征值排序，遍历时直接计算梯度统计量（\(\sum g_i, \sum h_i\)）的累积值。
- 加权分位数草图：根据二阶梯度 \(h_i\) 分布近似选择候选分裂点，减少计算量。
- 工程优化与扩展功能
- 稀疏感知分裂：自动处理缺失值，在分裂时学习缺失值的默认方向（左子树或右子树）。
- 并行化：在特征选择阶段并行计算不同特征的分裂增益。
- 交叉验证：支持每轮迭代后使用验证集早停（early stopping）。
总结
XGBoost通过二阶梯度提升和正则化控制过拟合，结合高效的节点分裂算法与工程优化，实现了高精度与可扩展性。其核心在于目标函数的分解与贪心分裂策略的联合优化。