XGBoost（Extreme Gradient Boosting），在kaggle中非常常用，还是很有必要学习一下的。
简单地说，XGBoost就是一个朴素地靠堆叠数量取胜的学习机，依赖的是简单的决策树模型，但是通过集成的神奇方式将多个“弱学习器”组合成一个“强学习器”。
1. 目标函数 (Objective Function)
对于给定的包含 $n$ 个样本的数据集，XGBoost 的预测输出是 $K$ 棵树的累加：
\[\hat{y}_i = \sum_{k=1}^K f_k(x_i) \quad ,\quad i=1,2...n\]每棵树都是在前面所有树的优化成果上进行进一步的修正，可以说本质上下一棵树是在拟合前面结果的残差。
用于优化的目标函数由两部分组成：损失函数（预测误差）和正则化项（复杂度惩罚）。
\[\text{Obj}(\Theta) = \sum_{i=1}^n L(y_i, \hat{y}_i) + \sum_{k=1}^K \Omega(f_k)\]2. 泰勒展开：目标函数的近似
在第 $t$ 轮迭代时，我们要在保留前 $t-1$ 轮预测结果 $\hat{y}_i^{(t-1)}$ 的基础上，寻找一个新的函数 $f_t$ 来最小化：
\[\text{Obj}^{(t)} = \sum_{i=1}^n L(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) + \text{constant}\]为了快速求得最优解，XGBoost 对损失函数 $L$ 进行 二阶泰勒展开：
\[L(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) \approx L(y_i, \hat{y}_i^{(t-1)}) + 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}_i^{(t-1)})$ 是一阶导数（梯度）。
- $h_i = \partial^2_{\hat{y}^{(t-1)}} L(y_i, \hat{y}_i^{(t-1)})$ 是二阶导数（海森矩阵/Hessian）。
移除常数项后，第 $t$ 步的简化目标函数为：
\[\tilde{\text{Obj}}^{(t)} = \sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t)\]为什么用二阶导？ 相比只用一阶导的 GBDT，二阶导提供了梯度的变化信息，能更准确地逼近真实损失，从而加快收敛速度。
3. 定义树的复杂度 (Regularization)
XGBoost的正则化项定义为：
\[\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2\]- $T$：叶子节点的数量。
- $w_j$：第 $j$ 个叶子的权重。
- $\gamma, \lambda$：惩罚系数（超参数）。
第一项用于限制节点数产生的过拟合，第二项用于限制树之间的贡献差，防止结果主要只由少数树贡献。同时也平滑单棵树的叶子权重差异，防止对某些局部特征过于敏感。
4. 最优叶子权重与得分计算
将树的结构代入目标函数，并将求和方式从样本遍历改为叶子遍历：
\[\tilde{\text{Obj}}^{(t)} = \sum_{j=1}^T [(\sum_{i \in I_j} g_i) w_j + \frac{1}{2} (\sum_{i \in I_j} h_i + \lambda) w_j^2] + \gamma T\]令 $G_j = \sum_{i \in I_j} g_i$（叶子 $j$ 内样本的一阶导和），$H_j = \sum_{i \in I_j} h_i$（二阶导和）。
对 $w_j$ 求导并令其为 0，得到最优权重 $w_j^*$：
\[w_j^* = -\frac{G_j}{H_j + \lambda}\]将 $w_j^*$ 代回目标函数，得到该树结构下的最小目标值（即结构分数）：
\[\text{Obj}^* = -\frac{1}{2} \sum_{j=1}^T \frac{G_j^2}{H_j + \lambda} + \gamma T\]5. 分裂准则 (Greedy Algorithm)
注意一下，会发现前面很多过程是和树本身的结构没有关系的，也就是说这个决策树究竟怎么决策的，无人在意，关注的只是叶子节点$\omega_j$的值。那么树的结构究竟在哪里体现？其实就是$G_j$和$H_j$，树的不同会影响叶子节点中最终包含的是哪个样本，从而影响到$G_j$和$H_j$。因此通过优化树结构来优化$G_j$和$H_j$是另一个优化点。
在实际建立树时，不可能遍历所有树结构。XGBoost 采用贪心算法。对于一个节点，XGBoost会遍历每一个特征，对每一个特征遍历一遍阈值，尝试将其分裂为左子树 $L$ 和右子树 $R$，计算分裂后的 增益（Gain）：
\[\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\]- $\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}$：不分裂时的分数。
- $\gamma$：引入新叶子节点的复杂度代价。
然后选取最大的$\text{Gain}$进行分裂，把对应的特征和阈值记录到这个节点上。
以上即为XGBoost的基本思想。
