xgboost理解(1) 从AdaBoost到GBDT的变迁

提到xgboost，大家都会说，xgboost是gbdt的一种高效实现。简而言之，它的指导思想和大的框架是gbdt(Gradient Boosting Decision Tree)，然后在各个步骤做了不同的优化，提升了训练的速度和精度。但是我看了论文后觉得，xgboost的改动还是很大的，因为修改了损失函数，并且使用了不同的角度去理解损失函数，不能完全看做是gbdt的一种实现，已经可以叫做另外一种算法了。

AdaBoost

首先说说提升算法。提升方法中最具代表性的是AdaBoost。所谓提升方法，思想就是综合多个弱分类器的结果，得到一个近似强分类器的结果。

举例来说，假设存在一组训练样本：

$$T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}$$

其中输入$x_i \in \mathcal{X} \subseteq \mathbf R^n$，输出$y_i \in \mathcal{Y}=\{-1,+1\}$。AdaBoost的做法是，训练$m$个轮次，每轮都训练出一个弱分类器$G_m(x)$，然后最终分类器$G(x)$是：

$$\\f(x)=\sum_{m=1}^{M}{\alpha_mG_m(x)} \\ \ \\G(x)={\rm sign} (f(x))$$

可以看见，最终分类器就是每一轮弱分类器的线性组合。然后AdaBoost告诉了我们如何去确定每一轮的$G_m(x)$和它对应的系数$\alpha_m$：通过每一轮的训练结果，将分错的样本赋予高的权重，在下一轮”重点”学习，相对的，分对的样本减小权重。然后根据本次的误差计算本次的系数。

因此，AdaBoost的思想是通过修改每轮次训练样本的权重来训练出不同的弱分类器，然后根据其错误率来确定每个弱分类器在最终分类器中的”话语权”。

Boosting Tree

提升树是以决策树为基函数的提升算法，和AdaBoost相似的地方是，它也是一个加法模型，但是省去了系数，并且提升树是用来解决回归问题的，因为分类问题也可以通过拟合一个线性边界去解决，所以提升树也可以在稍作转换后用于分类问题。

提升树类似AdaBoost，可以表示为一个加法模型：

$$f_M(x)=\sum_{m=1}^MT(x;\Theta_m)$$

其中$T(x;\Theta_m)$表示决策树，$\Theta_m$为决策树的参数，$M$为树的个数。在回归问题上，提升树与AdaBoost有微妙的不同，我举个具体的例子，假设一个样本是$(x_0=3,y_0=1.5)$，那么:

$$\begin{aligned} \\&f_0(x_0) =0 \\&f_1(x_0)=1 \\&f_2(x_0)=0.3 \\&f_3(x_0)=0.15 \\&f_M(x_0)=f_0+f_1+f_2+f_3=1.45 \end{aligned}$$

为什么后续的学习器呈现出越来越小的趋势呢，是因为提升树的训练算法的特点造成的。我们把公式变换一下：

$$\begin{aligned} \\&f_0(x)=0 \\&f_m(x)=f_{m-1}+T(x;\Theta_m)\ \ ,\ \ m=1,2,...,M \end{aligned}$$

在第m步，给定当前模型$f_{m-1}(x)$，要求解:

$$\Theta_m=\arg \min_{\Theta_m}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m))$$

然后得到第m棵树的参数$\Theta_m$。回归问题一般都采用平方差损失函数:

$$L(y,f(x))=(y-f(x))^2$$

然后带入到提升树的损失函数中：

$$\begin{aligned} \\L(y,f_{m-1}(x)+T(x;\Theta_m))&=[y-f_{m-1}(x)-T(x;\Theta_m)]^2 \\&=[r-T(x;\Theta_m)]^2 \end{aligned}$$

这里:

$$r=y-f_{m-1}(x)$$

也就是说，要最小化L，就要让待求的树模型$T(x;\Theta_m)$去拟合值r，而r实际上是当前给定总模型$f_{m-1}(x)$的残差，因此每一轮要求的单个树模型实际上是在拟合上一轮总模型的残差，残差当然是越拟合越小的，这时候就可以结合上面的例子理解整个提升树的思想了。

GBDT

对于提升树来说，它已经做得足够好了，但是让人觉得有瑕疵的地方是，只有损失函数是平方损失函数才能写成上面那种形式（虽然很多时候我们确实只用平方损失函数），如果能改进的更加通用一些，那么模型的适用性会更广泛。

Freidman针对这个问题提出了GBDT算法。提升树中，其实我们每一轮是拟合上一轮总模型的残差，从直观上来看，损失函数每一步都越来越低，这种迭代方式特别像梯度下降法。而梯度下降法与拟合残差不一样的是，梯度下降每一步都是沿着损失函数下降最快的方向进行的，只是一个速度快慢的问题。

我们把总模型$f_{m-1}(x)$整体看做是自变量，把$T(x;\Theta_m)$看做是自变量迭代的增量，将损失函数在$f_{m-1}$处用泰勒一阶展开:

$$\begin{aligned} L(f_m)&=L(f_{m-1}+T_m) \\ &\simeq L(f_{m-1})+L'(f_{m-1})T_m \end{aligned}$$

要使得$L(f_m)<L(f_{m-1})$，可以令$\ \ T_m=-\alpha L’(f_{m-1})$

那么迭代式可以写成：

$$\begin{aligned} f_{m}&=f_{m-1}+T_m\\ &=f_{m-1}+（-\alpha L'(f_{m-1})） \end{aligned}$$

这是标准的梯度下降法，那么总模型可以看成是从$f_0$开始的梯度下降迭代过程：

$$\begin{aligned} \\f_M(x)&=\sum_{m=1}^M T(x;\Theta_m) \\&=f_0+（-\alpha L'(f_0)）+（-\alpha L'(f_1)）+...+（-\alpha L'(f_{m-1})） \end{aligned}$$

因此我们每一步计算得到当前的$L’(f_{m-1})$，然后用当前待求的树模型$T(x;\Theta_m)$去拟合这个梯度的负数即可。

$$L'(f_{m-1}(x_i))=[\frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}]$$

当损失函数L为平方损失函数的时候，这个梯度恰好为残差$y_i-f_{m-1}(x_i)$。因此提升树是GBDT的一种特殊情况，这样一来，GBDT的适用范围就放的很大了，理论上可以解决所有具有一阶可导损失函数的有监督学习问题。

切分点、候选点、分箱

解决完算法核心思想问题，然后就要解决具体的操作问题了，如何去拟合每一个$T(x;\Theta_m)$。因为提升树和GBDT用的都CART树，因此每一轮拟合都可以看做是生成一棵CART树的过程。

李航老师在《统计学习方法》中给出的方法是，以每个$x_i$作为切分点，切分后该区域的最优值为该区域$y_i$的平均值，然后遍历计算切分后的平方差，选取平方差最低的作为本次的切分点。

详细见《统计学习方法》第二版 P81

然后GBDT在生成每一棵树的时候都要做这样大量的计算，当样本特别多的时候，给样本排序也很耗时，导致算法速度很慢，可以发现这一步也有很多可以优化的地方。分箱是一种减少计算量的离散化手段，一般是以分位点作为分箱的依据，这一步又可以做很多事情。

正则化

除了CART树自带的剪枝算法，其实在提升算法层面上，还可以有一系列的正则化方法可以使用。比如随机森林的列采样等等。

总结

XGBoost在GBDT的基础上做了进一步的细化和优化，包括从损失函数到CART树的生成策略都做了优化，尤其是在损失函数的定义上做了较大改动，下一章会详细探讨XGBoost的相关原理。

参考

李航《统计学习方法》

如有疑问和见解请留言~