[toc]

XGBoost

  XGBoost也是一种 Boosting 方法，是陈天奇大佬提出的，广泛应用于各大数据挖掘比赛，它几乎就是在GBDT的基础之上做了很多细节的优化，这些细节的优化使得XGBoost在很多数据集上拥有比GBDT更强的泛化性能。回归树在做节点分裂的时候需要遍历所有的特征，以确定最佳的特征进行分裂，这一算法在工程实现时，对特征选择进行了并行化处理，使得其在多核计算机上拥有更快的训练速度。

算法推导

目标函数

  上一篇讲解过GBDT，与GBDT类似，XGBoost也是基于前向分步加法模型进行迭代地求解每一个基学习器。在建立目标函数方面，XGBoost从两个发面出发，一方面目标函数包含一个用来衡量学习器对数据集拟合情况的损失函数；另一方面目标函数还包括了当前学习器模型复杂程度的度量，也即正则项，这一点是在目标函数方面对GBDT的一个改进。结合损失函数和正则项两方面，在第$m$次迭代的时候，得到如下目标函数：
\begin{equation}
\begin{array}{r l}
obj = & \min_w \sum_{i=1}^n L \left( y_i,f_{m-1}(x_i)+T(x_i;w) \right) + \gamma J +\frac{1}{2} \lambda| w |_2^2 \
= & \min_w \sum_{i=1}^n L\left( y_i,f_{m-1}(x_i)+\sum_{j=1}^J w_j I \left( x_i \in R_j\right) \right) + \gamma J +\frac{1}{2} \lambda\sum_{j=1}^J w_j^2 \
= & \min_w \sum_{j=1}^J \sum_{x_i \in R_j} L\left(y_i,f_{m-1}(x_i) + w_j \right) +\frac{1}{2}\lambda w_j^2 + \gamma,
\end{array}
\end{equation}
上式中的$J$为一棵树的叶子节点个数，$R_j$为第$j$个叶子节点或者叫做划分空间，$w_j$为叶子节点的取值，也就是要求解的参数。目标函数的第二项 $\gamma J +\frac{1}{2} | w |_2^2$ 就是正则项，它使得在优化目标更倾向于叶子节点相对较少，权重相对较小的参数。那么对于每个节点而言，最优的取值由下式得到：
$$w_j^{\ast} = \arg\min_{w_j} \sum_{x_i \in R_j} L\left(y_i,f_{m-1}(x_i) + w_j \right) +\frac{1}{2}\lambda w_j^2 + \gamma,$$
对目标函数进行二阶泰勒展开
$$
w_j^{\ast} = \arg\min_{w_j} \sum_{x_i \in R_j} L\left(y_i,f_{m-1}(x_i)\right) + g_iw_j+\frac{1}{2}h_iw_j^2 + \frac{1}{2}\lambda w_j^2 + \gamma,
$$
去掉常数项，得到目标函数
$$
w_j^{\ast} = \arg\min_{w_j} \sum_{x_i \in R_j} \left( g_iw_j+\frac{1}{2}h_iw_j^2\right) + \lambda w_j^2 + \gamma,
$$
其中$g_i = \frac{\partial L(f(x))}{\partial f(x)} \Big|_ {f(x) = f_ {m-1}(x_i)}, h_i = \frac{\partial^2 L(f(x))}{\partial f^2(x)} \Big|_ {f(x) = f_ {m-1}(x_i)}.$
方便起见，令$G_j = \sum_{x_i \in R_j} g_i, H_j = \sum_{x_i \in R_j} h_i,$求解上面的 一元二次非程得到最优解：
$$w_j^{\ast} = -\frac{G_j}{H_j+\lambda},$$
将最优解代入目标函数得到最优值为
$$
\text{opt_j} = -\frac{1}{2}\frac{G_j^2}{H_j+\lambda} + \gamma.
$$

节点分裂

  由上面推导出在每个叶子节点的最优取值，那么节点分裂前后目标函数最优值的下降量为：
\begin{equation}
\begin{array}{r l}
& -\frac{1}{2}\frac{G_j^2}{H_j+\lambda} + \gamma - \left( -\frac{1}{2}\frac{G_{jL}^2}{H_{jL}+\lambda} + \gamma-\frac{1}{2}\frac{G_{jR}^2}{H_{jR}+\lambda} + \gamma\right) \
= & \frac{1}{2}\left(\frac{G_{jL}^2}{H_{jL}+\lambda} + \frac{G_{jR}^2}{H_{jR}+\lambda} - \frac{G_j^2}{H_j+\lambda} \right) - \gamma
\end{array}
\end{equation}
故我们可以遍历所有的特征和特征划分以选择最优的分裂。

算法

XGBoost 算法
:

1. $f_0(x) = \arg\min_w \sum_{i=1}^nL(y_i,w)$
2. $m = 1,\cdots,M:$
   a. $g_i = -\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\Big|_ { f(x) = f_ {m-1}(x)}, \
   h_i = \frac{\partial^2 L(y_i,f(x))}{\partial f^2(x)} \Big|_ {f(x) = f_ {m-1}(x_i)}, i=1,\cdots,n$
   b. 使用上面描述的节点分裂的方法生成$T(x;w) = \sum_{j}^J w_j I(x\in R_j)$
   c. $f_m(x) = f_{m-1}(x) + \sum_{j}^J w_j I(x\in R_j)$

缺失值处理

  XGBoost 可以自动的学习出缺失值的分裂方向，具体来说，当一个特征在某些样本缺失时，分裂算法在查找这个特征最佳分裂点时做两次遍历，一次遍历把所有包含缺失值的样本分裂到左边，第二次分裂到右边，从两次遍历中找到该特征的最佳分裂点和缺失值分裂方向。

正则化

  在防止过拟合方面，XGBoost引入了很多的正则化手段，具体来说包括：

1. 目标函数引入了权重的$L1,L2$正则项，有利于减少每个树模型的复杂度，降低方差
2. 学习率，每次迭代生成一个树都要乘上学习率
3. 样本和特征的下采样，借鉴了随机森林

XGBoost与GBDT的区别和联系

1. 在目标函数方面： XGBoost引入了正则项，而GBDT没有，由于XGBoost需要用到目标函数的二阶泰勒展开，所以XGBoost的目标函数必须是二阶可微的。
2. 正则化方面： gbdt中引入学习率和样本的下采样，而XGBoost还引入了特征维度的下采样，XGBoost还可以设置提前终止。
3. 在学习树的结构方面： GBDT每一步是拟合一个CART，拟合的目标就是负梯度方向，分裂节点时用的是平方误差损失，因为回归树的损失函数就是平方误差损失；XGBoost虽然也是一个回归树，但是它分裂节点时直接对损失函数做优化，叶子节点的权重和分裂都是直接在损失函数的基础上优化的。
4. 缺失值处理方面： GBDT所采用的CART可以对有缺失值的数据进行训练，它对缺失值处理的方式是忽略掉特征在那些样本缺失的数据，只用无缺失的数据进行训练，预测的时候，若存在缺失值则使用替代变量进行分割（在sklearn实现的GBDT好像并不能处理缺失值）；而XGBoost通过学习出缺失值的的默认分裂方向来处理缺失值。

   References

   [1] Tianqi Chen, XGBoost: A Scalable Tree Boosting System
   [2] Hastie, The Elements of Statistical Learning
   [3] 机器之心，为什么XGBoost在机器学习竞赛中表现如此卓越？