XGBoost算法的数学推导与二阶泰勒展开优化过程
题目描述：
XGBoost（eXtreme Gradient Boosting）是一种基于梯度提升决策树的集成学习算法，通过二阶泰勒展开优化损失函数，并引入正则化项控制模型复杂度。本题要求详细解释其数学推导过程，包括目标函数的构建、泰勒展开的应用、最优权重的计算以及分裂节点的评估方法。
解题过程：
- 目标函数的定义
- 假设有 \(n\) 个样本和 \(K\) 棵树，模型的预测值为所有树的输出之和：
\[ \hat{y}_i = \sum_{k=1}^K f_k(x_i), \quad f_k \in \mathcal{F} \]
其中 $ f_k $ 是第 $ k $ 棵树，$ \mathcal{F} $ 为所有可能的决策树空间。
- 目标函数包括损失函数和正则化项：
\[ \text{Obj} = \sum_{i=1}^n L(y_i, \hat{y}_i) + \sum_{k=1}^K \Omega(f_k) \]
正则化项 $ \Omega(f_k) = \gamma T + \frac{1}{2} \lambda \|w\|^2 $，$ T $ 为叶子节点数，$ w $ 为叶子权重。
- 加法训练与泰勒展开
- 采用前向分步算法，第 \(t\) 次迭代时，模型预测为：
\[ \hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i) \]
- 目标函数重写为：
\[ \text{Obj}^{(t)} = \sum_{i=1}^n L\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \Omega(f_t) \]
- 对损失函数进行二阶泰勒展开（以 \(\hat{y}_i^{(t-1)}\) 为展开点）：
\[ \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)}) $ 分别为一阶和二阶梯度。
- 叶子权重的优化
- 定义叶子节点集合 \(I_j = \{ i \mid x_i \in \text{叶子} j \}\)，每个叶子节点赋予权重 \(w_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 $ 为分裂后的左右节点样本集合。
- 选择增益最大的分裂方案，若增益为负则停止分裂（预剪枝）。
- 算法流程总结
- 初始化模型预测值（如均值）。
- 迭代训练每棵树：
- 计算每个样本的一阶梯度 \(g_i\) 和二阶梯度 \(h_i\)。
- 根据增益公式贪婪地分裂节点，构建树结构。
- 计算叶子权重 \(w_j^*\) 并更新模型。
- 输出最终模型 \(\hat{y}_i = \sum_{k=1}^K f_k(x_i)\)。
关键点：XGBoost通过二阶泰勒展开更精确地逼近损失函数，并利用正则化防止过拟合，同时通过加权分位数草图等技术优化计算效率。