前言
本文主要介绍XGBoost这一超快集成训练模型。该算法思想就是不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数去预测一个样本的分数，最后将每棵树对应的分数加起来就是该样本的预测值。
推导
目标函数定义
\[ L(\phi)=\sum_i l(y_i,\hat{y}_i)+\sum_k \Omega(f_k) \\ \Omega(f_k)=\gamma T+\frac{1}{2}\lambda \|w\|^2 \]
其中 \(\sum_i l(y_i,\hat{y}_i)\) 代表损失函数，\(\sum_k \Omega(f_k)\) 代表正则化项。\(\hat{y}_i\) 代表预测输出， \(y_i\) 代表真实值，\(f_k\) 代表第 k 棵树， \(T\) 为树叶子节点数，\(\omega\) 为叶子权重值，\(\gamma\) 为正则化系数。
\[ \hat{y}_i=\phi(x_i)=\sum_{k=1}^Kf_k(x_i) \\ where F=\{f(x)=w_{q(x)}\} (q:R^m \rightarrow T,w \in R^T) \]
其中，\(w_{q(x)}\) 是叶子节点 \(q\) 的分数，函数 \(q(x)\) 将样本 \(x\) 映射到树上的某一叶子节点。\(f(x)\) 是一颗回归树。对于任一样本 \(x\)，其分值为 \(w_{q(x)}\)。
目标函数可以重写为
\[ Obj^{(t)}=\sum_{i=1}^{n} l(y_i,\hat{y}^{(t-1)}+f_t(x_i))+\Omega(f_t)+constant \]
接下来就是最小化目标函数。XGBoost 利用其泰勒二阶展开来近似。
\[ Obj^{(t)} \simeq \sum_{i=1}^n [l(y_i,\hat{y}^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t) + constant \\ g_i=\frac{\partial l(y_i,\hat{y}^{(t-1)})}{\partial \hat{y}^{(t-1)}}, h_i =\frac{\partial^2 l(y_i,\hat{y}^{(t-1)})}{\partial {\hat{y}^{(t-1)}}^2} \]
此处为什么使用二阶偏导数呢？
首先我们需要明确 boosting 每一轮迭代都是在优化什么。换言之，我们都在用损失函数 \(l\) 干什么。我们看 Boosting 的框架，无论是 GBDT 还是 Adaboost，其在每一轮的迭代过程中并没有理会损失函数具体是什么，仅仅用到了损失函数的一阶导数。仅仅用一阶导数的问题就是我们无法保证我们找到的是全局最优。除非问题本身 \(f(x)\) 是强凸的。每次迭代相当于最优化负梯度。即下式中的 \(\nabla f(x^{(i)})\)，因为梯度为负所以加负号， \(c\) 代表学习率。
\[ x_c^{(i+1)}=x^{(i)}-c\nabla f(x^{(i)}) \]
大家都能看出这就是一般长假的呢 Linear Regression 的 Stochastic Gradient Descend 梯度更新公式。既然 GBDT 用的是 SGD，那还有其他的梯度更新方式吗？所以我们想到了牛顿法。或许可以说，XGBoost 是利用了牛顿法进行的梯度更新。
首先看泰勒展开式：
\[ \sum_{n=0}^\infty \frac{1}{n!}\frac{\partial ^nf(x)}{\partial x^n}\nabla x^n = f(x)+\frac{\partial f(x)}{\partial x}\nabla x + \frac{1}{2!}\frac{\partial^2f(x)}{\partial x^2}\nabla x^2 + ... \]
对于上式，其与 \(f(x+\nabla x)\) 之间的误差，可以用下式表示:
\[ f(x+\nabla x)-\sum_{n=0}^\infty \frac{1}{n!}\frac{\partial ^nf(x)}{\partial x^n}\nabla x^n=h_k(x)a^k \]
保留二阶泰勒展开:
\[ f(x+\nabla x) \simeq f(x) + f'(x)\nabla x+\frac{1}{2}f''(x)\nabla x^2 \]
这个式子是成立的，当且仅当 \(\nabla x\)趋近于 0，我们对上式求导（对 \(\nabla x\) 求导）并令导数为 0。
\[ f'(x)+f''(x)\nabla x = 0 \]
即得到:
\[ \nabla x = -\frac{f'(x)}{f''(x)} \]
得出迭代公式
\[ x_{n+1} = x_n - \frac{f'(x)}{f''(x)} \]
将损失函数与 \(f(x)\) 对应起来:
\[ \begin{aligned} f(x)&=l(y_i, \hat{y}_i^{(t-1)} ) \\ &=(y_i - \hat{y}_i^{(t-1)})^2 \\ f(x+\Delta x)&=l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) \\ &=(y_i - (\ \hat{y}_i^{(t-1)} + f_t(x_i)\ )\ )^2 \end{aligned} \]
所以实际上 \(x\) 即为 \(\hat{y}_i^{t-1}\)，而 \(\nabla x\) 即为 \(f_t(x_i)\)。故对 \(f(x)\) 求导数时即对 \(\hat{y}_i^{t-1}\) 求偏导，故根据二阶泰勒展开，\(f(x+\nabla x\) 可以表示为:
\[ f(x+\nabla x)=(y_i-\hat{y}_i^{(t-1)})^2 + [(y_i-\hat{y}_i^{(t-1)})^2]'*f_t(x_i) + \frac{1}{2}[(y_i-\hat{y}_i^{(t-1)})^2]''*f_t^2(x_i) \]
用 \(g_i\) 和 \(h_i\) 替代上式中的 \(f'(x)\) 和 \(f''(x)\)，即可得到
\[ \begin{aligned} \text{obj}^{(t)} = \sum_{i=1}^n [l(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t) + constant \end{aligned} \]
理解了一二阶偏导之后再来看正则化项:
\[ \Omega(f_t)=\gamma T + \frac{1}{2}\lambda \|w\|^2 \]
我们为了使目标函数最小，自然正则化项要小，正则化项要小，叶子节点个数 T 要小（叶子越少，树越简单）。
由于前 t-1 棵树的预测分数与 y 的残差对目标函数优化没有影响可以直接去掉，所以有:
\[ 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) \]
上式是将每个样本的损失函数值加起来，我们知道，每个样本最终都会落到一个叶子节点上，所以我们可以将所有同一叶子节点的样本重组起来，过程如下:
\[ \begin{aligned} 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) \\ &=\sum_{i=1}^n[g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2 \\ &=\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 \\ &=\frac{1}{2} \sum_{j=1}^T(H_j+\lambda)(w_j + \frac{G_j}{H_j+\lambda})^2 + \gamma T - \frac{1}{2}\sum_{j=1}^T \frac{G_j^2}{H_j+\lambda} \\ &=\sum_{j=1}^T[G_jw_j + \frac{1}{2}(H_j + \lambda) w_j^2] + \gamma T \end{aligned} \]
其中 \(G_i = \sum_{i\in I_j} g_i\) 为落入叶子 \(i\) 的所有样本一阶梯度统计值综合，\(H_i=\sum_{i\in I_j} h_i\) 为落入叶子 \(i\) 所有样本二阶梯度统计值总和。
对 \(w_j\) 求导可得
\[ w_j^*=-\frac{G_j}{H_j+\lambda} \]
代入 \(w_j^*\) 有
\[ Obj=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda} + \gamma T \]
\(Obj\) 代表当我们指定一个树结构后，在目标上最多减少多少。因此叫做结构分数。
目前为止，我们一直在围绕目标函数进行分析。主要也是为了寻找 \(f_k(x)\)，也就是建树的过程。回忆决策树算法，建树的时候最关键的一步就是选择一个分裂的准则，也就是如何评价分裂的质量。比如在 GBDT 里，我们可以选择 MSE、MAE 来评价我们分裂的质量。但是我们所选择的分裂准则并不总是和我们的损失函数有关，因为这种选择是启发式的。比如在分类任务里，损失函数可以选择 log loss，分裂准则选择 MSE，这样看来，似乎分裂的好坏和我们的损失并没有直接挂钩。
但是在 XGBoost 里面，我们的分裂准则是直接与损失函数挂钩的准则。这个也是 XGBoost 与 GBDT 很不一样的地方。
具体来说，XGBoost 选择这个准则计算增益 Gain
\[ Gain=\frac{1}{2}[\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 \]
其中 \(G_L\) 代表分裂的话左叶子节点中样本点的集合的一阶梯度和，\(G_R\) 代表右边边界的。
当所有样本都存在于未分类的节点中，此时该节点中一阶导的和就相当于 \(G_L+G_R\)，未分裂节点上的二阶导数为 \(H_L+H_R\)，将其带入结构分数中，我们得到不分裂的情况下的结构分数。
\[ \frac{(G_L + G_R)^2}{H_L+H_R+\lambda} \]
假设这个接点分裂，分类之后左右叶子节点的结构分数分别为:
\[\frac{G_L^2}{H_L+\lambda}\]
\[\frac{G_R^2}{H_R+\lambda}\]
分裂的时候我们选择分裂之后损失减少最多的，也就是找到一种分裂有着
\[ \max (\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\) 的作用即为控制树的复杂度。进一步说，利用 \(\gamma\) 作为阈值，只有当大于 \(\gamma\) 时才选择分裂，也起到预剪枝的作用。
所以总结一下，XGBoost 主要做了以下几件事。
- 在损失函数中加入了正则化项。
- 对目标函数进行二阶泰勒展开。
- 利用推导得到的表达式作为分裂准则构建每一棵树。
总结：XGBoost 与 GBDT 的区别与联系
区别:
- xgboost和GBDT的一个区别在于目标函数上。在xgboost中，损失函数+正则项。 GBDT中一般只有损失函数。
- xgboost中利用二阶导数的信息，而GBDT只利用了一阶导数, 即在GBDT回归中利用了残差的概念。
- xgboost在建树的时候利用的准则来源于目标函数推导，即可以理解为牛顿法。而GBDT建树利用的是启发式准则。
- xgboost中可以自动处理空缺值，自动学习空缺值的分裂方向，GBDT(sklearn版本)不允许包含空缺值。
相似:
- xgboost和GBDT的学习过程都是一样的，都是基于Boosting的思想，先学习前n-1个学习器，然后基于前n-1个学习器学习第n个学习器。而且其都是将损失函数和分裂点评估函数分开了。
- 建树过程都利用了损失函数的导数信息。
- 都使用了学习率来进行Shrinkage，从前面我们能看到不管是GBDT还是xgboost，我们都会利用学习率对拟合结果做缩减以减少过拟合的风险。