Question

红色石头的个人网站： redstonewill.com

上节课我们主要介绍了 Random Forest 算法模型。Random Forest 就是通过 bagging 的方式将许多不同的 decision tree 组合起来。除此之外，在 decision tree 中加入了各种随机性和多样性，比如不同特征的线性组合等。RF 还可以使用 OOB 样本进行 self-validation，而且可以通过 permutation test 进行 feature selection。本节课将使用 Adaptive Boosting 的方法来研究 decision tree 的一些算法和模型。

Adaptive Boosted Decision Tree

Random Forest 的算法流程我们上节课也详细介绍过，就是先通过 bootstrapping“复制”原样本集 D，得到新的样本集 D’；然后对每个 D’进行训练得到不同的 decision tree 和对应的；最后再将所有的通过 uniform 的形式组合起来，即以投票的方式得到 G。这里采用的 Bagging 的方式，也就是把每个的预测值直接相加。现在，如果将 Bagging 替换成 AdaBoost，处理方式有些不同。首先每轮 bootstrap 得到的 D’中每个样本会赋予不同的权重；然后在每个 decision tree 中，利用这些权重训练得到最好的；最后得出每个所占的权重，线性组合得到 G。这种模型称为 AdaBoost-D Tree。

但是在 AdaBoost-DTree 中需要注意的一点是每个样本的权重。我们知道，在 Adaptive Boosting 中进行了 bootstrap 操作，表示 D 中每个样本在 D’中出现的次数。但是在决策树模型中，例如 C&RT 算法中并没有引入。那么，如何在决策树中引入这些权重来得到不同的而又不改变原来的决策树算法呢？

在 Adaptive Boosting 中，我们使用了 weighted algorithm，形如：

每个犯错误的样本点乘以相应的权重，求和再平均，最终得到了。如果在决策树中使用这种方法，将当前分支下犯错误的点赋予权重，每层分支都这样做，会比较复杂，不易求解。为了简化运算，保持决策树算法本身的稳定性和封闭性，我们可以把决策树算法当成一个黑盒子，即不改变其结构，不对算法本身进行修改，而从数据来源 D’上做一些处理。按照这种思想，我们来看权重 u 实际上表示该样本在 bootstrap 中出现的次数，反映了它出现的概率。那么可以根据 u 值，对原样本集 D 进行一次重新的随机 sampling，也就是带权重的随机抽样。sampling 之后，会得到一个新的 D’，D’中每个样本出现的几率与它权重 u 所占的比例应该是差不多接近的。因此，使用带权重的 sampling 操作，得到了新的样本数据集 D’，可以直接代入决策树进行训练，从而无需改变决策树算法结构。sampling 可看成是 bootstrap 的反操作，这种对数据本身进行修改而不更改算法结构的方法非常重要！

所以，AdaBoost-DTree 结合了 AdaBoost 和 DTree，但是做了一点小小的改变，就是使用 sampling 替代权重，效果是相同的。

上面我们通过使用 sampling，将不同的样本集代入决策树中，得到不同的。除此之外，我们还要确定每个所占的权重。之前我们在 AdaBoost 中已经介绍过，首先算出每个的错误率，然后计算权重：

如果现在有一棵完全长成的树（fully grown tree），由所有的样本训练得到。若每个样本都不相同的话，一刀刀切割分支，直到所有的都被完全分开。这时候，，加权的而且也为 0，从而得到权重。表示该所占的权重无限大，相当于它一个就决定了 G 结构，是一种 autocracy，而其它的对 G 没有影响。

显然不是我们想看到的，因为 autocracy 总是不好的，我们希望使用 aggregation 将不同的结合起来，发挥集体智慧来得到最好的模型 G。首先，我们来看一下什么原因造成了。有两个原因：一个是使用了所有的样本进行训练；一个是树的分支过多，fully grown。针对这两个原因，我们可以对树做一些修剪（pruned），比如只使用一部分样本，这在 sampling 的操作中已经起到这类作用，因为必然有些样本没有被采样到。除此之外，我们还可以限制树的高度，让分支不要那么多，从而避免树 fully grown。

因此，AdaBoost-DTree 使用的是 pruned DTree，也就是说将这些预测效果较弱的树结合起来，得到最好的 G，避免出现 autocracy。

刚才我们说了可以限制树的高度，那索性将树的高度限制到最低，即只有 1 层高的时候，有什么特性呢？当树高为 1 的时候，整棵树只有两个分支，切割一次即可。如果 impurity 是 binary classification error 的话，那么此时的 AdaBoost-DTree 就跟 AdaBoost-Stump 没什么两样。也就是说 AdaBoost-Stump 是 AdaBoost-DTree 的一种特殊情况。

值得一提是，如果树高为 1 时，通常较难遇到的情况，且一般不采用 sampling 的操作，而是直接将权重 u 代入到算法中。这是因为此时的 AdaBoost-DTree 就相当于是 AdaBoost-Stump，而 AdaBoost-Stump 就是直接使用 u 来优化模型的。

Optimization View of AdaBoost

接下来，我们继续将继续探讨 AdaBoost 算法的一些奥妙之处。我们知道 AdaBoost 中的权重的迭代计算如下所示：

之前对于 incorrect 样本和 correct 样本，的表达式不同。现在，把两种情况结合起来，将写成一种简化的形式：

其中，对于 incorrect 样本，，对于 correct 样本，。从上式可以看出，由与某个常数相乘得到。所以，最后一轮更新的可以写成的级联形式，我们之前令，则有如下推导：

上式中被称为 voting score，最终的模型。可以看出，在 AdaBoost 中，与成正比。

接下来我们继续看一下 voting score 中蕴含了哪些内容。如下图所示，voting score 由许多乘以各自的系数线性组合而成。从另外一个角度来看，我们可以把看成是对的特征转换，就是线性模型中的权重。看到这里，我们回忆起之前 SVM 中，w 与的乘积再除以 w 的长度就是 margin，即点到边界的距离。另外，乘积项再与相乘，表示点的位置是在正确的那一侧还是错误的那一侧。所以，回过头来，这里的 voting score 实际上可以看成是没有正规化（没有除以 w 的长度）的距离，即可以看成是该点到分类边界距离的一种衡量。从效果上说，距离越大越好，也就是说 voting score 要尽可能大一些。

我们再来看，若 voting score 与相乘，则表示一个有对错之分的距离。也就是说，如果二者相乘是负数，则表示该点在错误的一边，分类错误；如果二者相乘是正数，则表示该点在正确的一边，分类正确。所以，我们算法的目的就是让与 voting score 的乘积是正的，而且越大越好。那么在刚刚推导的中，得到越小越好，从而得到越小越好。也就是说，如果 voting score 表现不错，与的乘积越大的话，那么相应的应该是最小的。

那么在 AdaBoost 中，随着每轮学习的进行，每个样本的是逐渐减小的，直到最小。以上是从单个样本点来看的。总体来看，所有样本的之和应该也是最小的。我们的目标就是在最后一轮（T+1）学习后，让所有样本的之和尽可能地小。之和表示为如下形式：

上式中，被称为 linear score，用 s 表示。对于 0/1 error：若 ys<0，则；若 ys>=0，则。如下图右边黑色折线所示。对于上式中提到的指数 error，即，随着 ys 的增加，error 单调下降，且始终落在 0/1 error 折线的上面。如下图右边蓝色曲线所示。很明显，可以看成是 0/1 error 的上界。所以，我们可以使用来替代 0/1 error，能达到同样的效果。从这点来说，可以看成是一种 error measure，而我们的目标就是让其最小化，求出最小值时对应的各个和。

下面我们来研究如何让取得最小值，思考是否能用梯度下降（gradient descent）的方法来进行求解。我们之前介绍过 gradient descent 的核心是在某点处做一阶泰勒展开：

其中，是泰勒展开的位置，v 是所要求的下降的最好方向，它是梯度的反方向，而是每次前进的步长。则每次沿着当前梯度的反方向走一小步，就会不断逼近谷底（最小值）。这就是梯度下降算法所做的事情。

现在，我们对做梯度下降算法处理，区别是这里的方向是一个函数，而不是一个向量。其实，函数和向量的唯一区别就是一个下标是连续的，另一个下标是离散的，二者在梯度下降算法应用上并没有大的区别。因此，按照梯度下降算法的展开式，做出如下推导：

上式中，表示当前的方向，它是一个矩，是沿着当前方向前进的步长。我们要求出这样的和，使得是在不断减小的。当取得最小值的时候，那么所有的方向即最佳的和就都解出来了。上述推导使用了在处的一阶泰勒展开近似。这样经过推导之后，被分解为两个部分，一个是前 N 个 u 之和，也就是当前所有的之和；另外一个是包含下一步前进的方向和步进长度的项。的这种形式与 gradient descent 的形式基本是一致的。

那么接下来，如果要最小化的话，就要让第二项越小越好。则我们的目标就是找到一个好的（即好的方向）来最小化，此时先忽略步进长度。

对于 binary classification，和均限定取值-1 或+1 两种。我们对做一些推导和平移运算：

最终化简为两项组成，一项是；另一项是。则最小化就转化为最小化。要让最小化，正是由 AdaBoost 中的 base algorithm 所做的事情。所以说，AdaBoost 中的 base algorithm 正好帮我们找到了梯度下降中下一步最好的函数方向。

以上就是从数学上，从 gradient descent 角度验证了 AdaBoost 中使用 base algorithm 得到的就是让减小的方向，只不过这个方向是一个函数而不是向量。

在解决了方向问题后，我们需要考虑步进长度如何选取。方法是在确定方向后，选取合适的，使取得最小值。也就是说，把看成是步进长度的函数，目标是找到最小化时对应的值。

目的是找到在最佳方向上的最大步进长度，也就是 steepest decent。我们先把表达式写下来：

上式中，有两种情况需要考虑：

• ： correct
• ： incorrect

经过推导，可得：

然后对求导，令，得：

由此看出，最大的步进长度就是，即 AdaBoost 中计算所占的权重。所以，AdaBoost 算法所做的其实是在 gradient descent 上找到下降最快的方向和最大的步进长度。这里的方向就是，它是一个函数，而步进长度就是。也就是说，在 AdaBoost 中确定和的过程就相当于在 gradient descent 上寻找最快的下降方向和最大的步进长度。

Gradient Boosting

前面我们从 gradient descent 的角度来重新介绍了 AdaBoost 的最优化求解方法。整个过程可以概括为：

以上是针对 binary classification 问题。如果往更一般的情况进行推广，对于不同的 error function，比如 logistic error function 或者 regression 中的 squared error function，那么这种做法是否仍然有效呢？这种情况下的 GradientBoost 可以写成如下形式：

仍然按照 gradient descent 的思想，上式中，是下一步前进的方向，是步进长度。此时的 error function 不是前面所讲的 exp 了，而是任意的一种 error function。因此，对应的 hypothesis 也不再是 binary classification，最常用的是实数输出的 hypothesis，例如 regression。最终的目标也是求解最佳的前进方向和最快的步进长度。

接下来，我们就来看看如何求解 regression 的 GradientBoost 问题。它的表达式如下所示：

利用梯度下降的思想，我们把上式进行一阶泰勒展开，写成梯度的形式：

上式中，由于 regression 的 error function 是 squared 的，所以，对 s 的导数就是。其中标注灰色的部分表示常数，对最小化求解并没有影响，所以可以忽略。很明显，要使上式最小化，只要令是梯度的反方向就行了，即。但是直接这样赋值，并没有对的大小进行限制，一般不直接利用这个关系求出。

实际上的大小并不重要，因为有步进长度。那么，我们上面的最小化问题中需要对的大小做些限制。限制的一种简单做法是把的大小当成一个惩罚项（）添加到上面的最小化问题中，这种做法与 regularization 类似。如下图所示，经过推导和整理，忽略常数项，我们得到最关心的式子是：

上式是一个完全平方项之和，表示当前第 n 个样本真实值和预测值的差，称之为余数。余数表示当前预测能够做到的效果与真实值的差值是多少。那么，如果我们想要让上式最小化，求出对应的的话，只要让尽可能地接近余数即可。在平方误差上尽可能接近其实很简单，就是使用 regression 的方法，对所有 N 个点做 squared-error 的 regression，得到的回归方程就是我们要求的。

以上就是使用 GradientBoost 的思想来解决 regression 问题的方法，其中应用了一个非常重要的概念，就是余数。根据这些余数做 regression，得到好的矩，方向函数也就是由余数决定的。

在求出最好的方向函数之后，就要来求相应的步进长度。表达式如下：

同样，对上式进行推导和化简，得到如下表达式：

上式中也包含了余数，其中可以看成是的特征转换，是已知量。那么，如果我们想要让上式最小化，求出对应的的话，只要让尽可能地接近余数即可。显然，这也是一个 regression 问题，而且是一个很简单的形如 y=ax 的线性回归，只有一个未知数。只要对所有 N 个点做 squared-error 的 linear regression，利用梯度下降算法就能得到最佳的。

将上述这些概念合并到一起，我们就得到了一个最终的演算法 Gradient Boosted Decision Tree(GBDT)。可能有人会问，我们刚才一直没有说到 Decison Tree，只是讲到了 GradientBoost 啊？下面我们来看看 Decison Tree 究竟是在哪出现并使用的。其实刚刚我们在计算方向函数的时候，是对所有 N 个点做 squared-error 的 regression。那么这个回归算法就可以是决策树 C&RT 模型（决策树也可以用来做 regression）。这样，就引入了 Decision Tree，并将 GradientBoost 和 Decision Tree 结合起来，构成了真正的 GBDT 算法。GBDT 算法的基本流程图如下所示：

值得注意的是，的初始值一般均设为 0，即。每轮迭代中，方向函数通过 C&RT 算法做 regression，进行求解；步进长度通过简单的单参数线性回归进行求解；然后每轮更新的值，即。T 轮迭代结束后，最终得到。

值得一提的是，本节课第一部分介绍的 AdaBoost-DTree 是解决 binary classification 问题，而此处介绍的 GBDT 是解决 regression 问题。二者具有一定的相似性，可以说 GBDT 就是 AdaBoost-DTree 的 regression 版本。

Summary of Aggregation Models

从机器学习技法课程的第 7 节课笔记到现在的第 11 节课笔记，我们已经介绍完所有的 aggregation 模型了。接下来，我们将对这些内容进行一个简单的总结和概括。

首先，我们介绍了 blending。blending 就是将所有已知的 aggregate 结合起来，发挥集体的智慧得到 G。值得注意的一点是这里的都是已知的。blending 通常有三种形式：

• uniform：简单地计算所有的平均值
• non-uniform：所有的线性组合
• conditional：所有的非线性组合

其中，uniform 采用投票、求平均的形式更注重稳定性；而 non-uniform 和 conditional 追求的更复杂准确的模型，但存在过拟合的危险。

刚才讲的 blending 是建立在所有已知的情况。那如果所有未知的情况，对应的就是 learning 模型，做法就是一边学，一边将它们结合起来。learning 通常也有三种形式（与 blending 的三种形式一一对应）：

• Bagging：通过 bootstrap 方法，得到不同，计算所有的平均值
• AdaBoost：通过 bootstrap 方法，得到不同，所有的线性组合
• Decision Tree：通过数据分割的形式得到不同的，所有的非线性组合

然后，本节课我们将 AdaBoost 延伸到另一个模型 GradientBoost。对于 regression 问题，GradientBoost 通过 residual fitting 的方式得到最佳的方向函数和步进长度。

除了这些基本的 aggregation 模型之外，我们还可以把某些模型结合起来得到新的 aggregation 模型。例如，Bagging 与 Decision Tree 结合起来组成了 Random Forest。Random Forest 中的 Decision Tree 是比较“茂盛”的树，即每个树的都比较强一些。AdaBoost 与 Decision Tree 结合组成了 AdaBoost-DTree。AdaBoost-DTree 的 Decision Tree 是比较“矮弱”的树，即每个树的都比较弱一些，由 AdaBoost 将所有弱弱的树结合起来，让综合能力更强。同样，GradientBoost 与 Decision Tree 结合就构成了经典的算法 GBDT。

Aggregation 的核心是将所有的结合起来，融合到一起，即集体智慧的思想。这种做法之所以能得到很好的模型 G，是因为 aggregation 具有两个方面的优点：cure underfitting 和 cure overfitting。

第一，aggregation models 有助于防止欠拟合（underfitting）。它把所有比较弱的结合起来，利用集体智慧来获得比较好的模型 G。aggregation 就相当于是 feature transform，来获得复杂的学习模型。

第二，aggregation models 有助于防止过拟合（overfitting）。它把所有进行组合，容易得到一个比较中庸的模型，类似于 SVM 的 large margin 一样的效果，从而避免一些极端情况包括过拟合的发生。从这个角度来说，aggregation 起到了 regularization 的效果。

由于 aggregation 具有这两个方面的优点，所以在实际应用中 aggregation models 都有很好的表现。

总结

本节课主要介绍了 Gradient Boosted Decision Tree。首先讲如何将 AdaBoost 与 Decision Tree 结合起来，即通过 sampling 和 pruning 的方法得到 AdaBoost-D Tree 模型。然后，我们从 optimization 的角度来看 AdaBoost，找到好的 hypothesis 也就是找到一个好的方向，找到权重也就是找到合适的步进长度。接着，我们从 binary classification 的 0/1 error 推广到其它的 error function，从 Gradient Boosting 角度推导了 regression 的 squared error 形式。Gradient Boosting 其实就是不断迭代，做 residual fitting。并将其与 Decision Tree 算法结合，得到了经典的 GBDT 算法。最后，我们将所有的 aggregation models 做了总结和概括，这些模型有的能防止欠拟合有的能防止过拟合，应用十分广泛。

注明：

文章中所有的图片均来自台湾大学林轩田《机器学习技法》课程

更多 AI 资源请关注公众号：红色石头的机器学习之路（ID：redstonewill）