Gradient Tree Boosting Algorithm

在机器学习各大算法中，决策树这种算法有着很多良好的特性，其现有的特点就有训练的时间复杂度$Omega$较低，对新样本预测的过程比较快，同时模型容易展示（容易将得到的决策树做成图片展示出来）等。但与此同时，单决策树又有一些不好的地方，比如说容易over-fitting。虽然目前有一些方法，比如剪枝可以减少这种over-fitting的程度，但结果还是不太理想。

与决策树相关的ensemble model（比如说有Boosting，Bagging等）算法比较多，比如RandomForest、Adaboost、GBRT等，这些算法最终的结果是生成$N$($N$的取值有可能成百上千）棵树，这样得到的最终模型可以大大减少单个决策树带来的缺陷。换言之，集成算法有点类似于“三个臭皮匠赛过一个诸葛亮”的做法。虽然这几百棵决策树中的每一棵都很简单（相对于C4.5这种单决策树而言），但将他们组合起来之后就能达到非常不错的模型。另外，值得注意的是，虽然这些算法都是由决策树演变而来，但不同的集成模型在训练的细节上伴有一些差异，在文章后面会对这些算法做一个本质的对比。下面先来讲解下本文的核心内容——Gradient Tree Boosting。

Introduction to Gradient Tree Boosting

Gradient Tree Boosting 算法最初是FreidMan在2000年提出来的，是一种集成算法（或是组合算法）。该算法的名字可以说是千奇百态，有叫GBRT（gradient boosting regression tree），也有说成GBM、GBDT的。它的base learners是决策树，既可以用来训练regression model，也可以用做classification。在分类性能上，能够和random forest媲美，甚至在有的dataset上表现的有过之而无不及。如今，Gradient Tree Boosting模型还广泛地运用在Web搜索排行榜以及生态学上，所以值得我们去花点时间认真学习。根据scikit-learn官网的介绍，GTB的优势有以下三大点：

自然而然地处理混合类型的数据；
预测能力强；
在输出空间对于异常值的鲁棒性强（通过强大的损失函数）。

然而，也存在一些劣势：

可扩展性方面，由于提升的时序性，不能进行并行处理。

尽管如此，由于gradient tree boosting algorithm的表现性能很好，所以受到广大业界人士的青睐。下面来介绍下梯度提升树的算法原理。

算法原理

gradient tree boosting 算法的核心在于，它的每棵树都是从上一次训练的所有树的残差中进行学习，进而拟合一棵回归（分类）树。
。在训练的时候，残差近似等于当前模型中损失函数的负梯度值，公式如下：

$r_{mi} = - \Bigg [ \frac {\partial L(y_i, f (x_i))}{\partial f (x_i)}\Bigg ] _{f (x) = f _{m-1}(x)}$

gradient boosting是boosting算法的一种，也可以说是Boosting算法的一种改进，原始的Boosting算法（Adaboost）是：在算法初始化阶段，为每一个样本赋予一个相等的weight，换言之，每个样本在开始都是一样重要的。接下来，每一次训练后得到的模型，对数据点的估计会有所差异，所以在每一步结束后，我们需要对weight进行处理，而处理的方式就是通过增加错分类的样本点的weight，同时减少分类正确的样本点的weight。这样能够确保，如果某些点经常被分错，那么就会被“严重关注”，也就会被赋予一个很高的weight。然后等进行了$N$次迭代（迭代次数由用户指定），将会得到$N$个简单的base learner，最后将它们组合起来，可以对它们进行加权（错误率越大的base learner 其权重值越小，错误率越小的基分类器权重值越大）、或者让它们进行投票等得到一个最终的模型。

gradient boosting与传统的boosting有着很大的区别，它的每一次计算都是为了减少上一次的 residual，而为了减少这些residual，它会在residual减少的gradient方向上建立一个新的 model。所以说，在gradient boosting algorithm中，新model建立的目的是为了使先前模型的残差往梯度方向减少，与传统的boosting算法对正错样本赋予不同加权的做法有着极大的区别。

gtb算法理论的核心包括三大点：

regression tree
gradient descent
boosting - Shrinkage

gradient tree boosting algorithm - Regression

对于给定的输入：训练数据集 $T={(x_1,y_1),(x_2,y_2),…,(x_n,y_n)},损失函数$L(y,f(x))$;
输出结果：一棵回归树$\tilde{f}(x)$

（1）首先初始化

$f_0(x)=\arg \ \min_c \sum_{i=1}^{N}L(y_i, c)$

建立一个model，估计一个使loss function 极小化的常数值，此时的model是一个只有一个节点的树；

（2）迭代的建立M棵boosting tree

$for m=1 to M:$（第一层循环开始）
$for i=1 to N:$（第二层循环1）计算loss function 的negative gradient在当前model的值，并将它作为residual的估计值。

$r_{mi} = - \Bigg [ \frac {\partial L(y_i, f (x_i))}{\partial f (x_i)}\Bigg ] _{f (x) = f _{m-1}(x)}$

接着，对于$r_{mi}$拟合一棵回归树，得到第$m$棵树的叶节点区域 $c_{mj} ,j=1,2,…,J$

$for j=1 to J:$（第二层循环2）,计算：

$c_{mj} = arg min_c \sum_{x_i\epsilon R_{mj}}L(y_i,f_{m-1}(x_i)+c)$

利用线性搜索估计叶节点区域的值，使损失函数极小化；

然后，更新

$f_{m}(x) = f_{m-1}(x) + \sum_{j=1}^Jc_{mj}I(x \epsilon R_{mj})$

（3）最后得到的$f_{m}(x)$就是我们最终的模型

$\tilde{f}(x)=f_M(x)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x \epsilon R_{mj})$

从式子中可以看出，gradient tree boosting algorithm 本质上是一个加和模型，并在推导中结合了前向分步算法。

scikit-learn中的GTB

在scikit-learn中对GTB算法有了很好的封装，对于分类可以选择的损失函数有逻辑回归和指数函数，对于回归的损失函数相对比较多，有最小二乘法、最小绝对偏差函数、huber以及分位数等。

下面是sklearn中的一个分类原例：

>>> from sklearn.datasets import make_hastie_10_2
>>> from sklearn.ensemble import GradientBoostingClassifier
>>> X, y = make_hastie_10_2(random_state=0)
>>> X_train, X_test = X[:2000], X[2000:]
>>> y_train, y_test = y[:2000], y[2000:]
>>> clf = GradientBoostingClassifier(n_estimators=100, learning_rate=1.0,
...     max_depth=1, random_state=0).fit(X_train, y_train)
>>> clf.score(X_test, y_test)                 
0.913...

其中$n_estimators$表示弱分类器的个数，$learning_rate$表示学习率，$max_depth$表示树的最大深度等。GTB的参数比较多，在实际应用中需要自己去调整合适的参数。

A comparison of ensemble algorithms

基于决策树的组合算法常用的有三个，分别是Adaboost、RandomFrest以及本文的GBRT。

Adaboost是通过迭代的学习每一个基分类器，每次迭代中，把上一次错分类的数据权值增大，正确分类的数据权值减小，然后将基分类器的线性组合作为一个强分类器，同时给分类误差率较小的基本分类器以大的权值，给分类误差率较大的基分类器以小的权重值。Adaboost使用的是自适应的方法，其中概率分布式变化的，关注的是难分类的样本。详细内容请参考之前的文章：机器学习算法-Adaboost。

Random Forest与adaboost有些区别，可以说一种改进的bagging算法。Random Forest不仅对样本进行sampling，还对feature进行sampling。它通过随机的方式建立一个森林，森林里面有许多棵决策树，并且每一棵树之间是没有联系的。在得到森林之后，当有一个新的input sample进来的时候，就让森林中的每一棵决策树分别对其进行判断，看这个样本应该属于哪一类（就分类算法而言），然后看看哪一类选择最多（随机森林使用到的是 vote方式），就预测这个样本为该class。在建立每一棵决策树的过程中，有两点需要注意，即采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行采样和列采样。对于行采样，是采用有放回的方式，即bootstrap sampling，也就是在采样得到的样本集合中，可能有重复的样本。举个例子，假设输入样本为$N$个，那么采样的样本也为$N$个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，从某种程度上讲，相对不容易出现over-fitting。其次就是列采样，这个过程是从$M$个feature中，选择$m$个($m << M$)。之后就是对采样之后的数据使用完全分裂的方式建立决策树模型。最后得到的决策树，它的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一类别。一般很多的决策树算法都一个重要的步骤-Pruning（剪枝），但是random forest并不这样干，由于之前的两个随机采样的过程保证了样本的随机性，所以替代了Pruning这个工作，也不太容易出现over-fitting。按照这种算法得到的random forest中的每一棵决策树都是非常弱的，但是当你把它们组合在一起的时候，就得对它刮目相看了。random forest可以这样来形容：每一棵决策树就是一个精通于某一领域的专家（因为我们从$M$个feature set中选择$m$个sub set让每一棵决策树进行学习），这样在random forest中就有了很多个精通不同领域的专家，对一个新的问题（input data），可以用不同的角度去看待它，最终由各个专家投票得到结果。random forest的分类准确率可以与adaboost媲美，但它对noise data更加鲁棒，运行速度比adaboost也快得多。

另外，random forest是可以实现并行化的，而adaboost无法并行。同时，random forest等bagging算法其本质是降variance的，而adaboost等boosting算法其实降的是bias。

最后，对于gradient tree boosting algorithm，它的每一次计算都是为了减少上一次训练模型的residual，而为了减少这些残差，可以在残差减少的梯度(Gradient)方向上建立一个新模型。这与adaboost和随机森林还是有很大区别的。

Introduction to Gradient Tree Boosting

算法原理

gradient tree boosting algorithm - Regression

scikit-learn中的GTB

A comparison of ensemble algorithms

References