决策树系列（二）：GBDT-梯度提升决策树-算法原理以及步骤

1 GBDT简介

GBDT，英文全称是Gradient Boosting Decision Tree，梯度提升决策树，顾名思义，与梯度、boosting算法、决策树有关。是一种迭代的决策树算法，由多棵决策树组成，每一颗决策树也叫做基学习器，GBDT最后的结果就是将所有基学习器的结果相加。

2 boosting算法

GBDT既然跟boosting算法有关，就先来讲讲boosting算法。如果不想看，直接跳到GBDT章节，再回过头来看也可以。

2.1 集成学习算法
Boosting，是集成学习算法的一种。什么是集成学习算法？是一种提高弱分类算法准确度的方法，就是将多个弱分类算法(基学习器)以一定的方式集合在一起，然后再以一定的方式集结多个弱学习算法的结果，作为最终的结果。集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。

(1) 根据集成基学习器方式的不同，会细分为不同的算法，大致分为以下2种：
a 各个基学习器之间相互独立，不存在依赖关系，典型算法有bagging、随机森林；
b 各个基学习器之间存在强依赖关系，每一个基学习器都是在前一个基学习器的基础上才能生成，典型算法有boosting。
(2) 集成学习算法的结果集合策略也有很多种：
a 平均法
b 加权平均法
c 投票法
d 学习法

所以简单来说，boosting算法，是一个集成算法，集成若干个基学习器，再集合他们的结果作为最终结果：
(1) 集成基学习器的方式是：每一个基学习器都是在前一个基学习器的基础之上生成；
(2) 集合结果的策略是：将所有基学习器的结果相加。

那么boosting算法的基学习器究竟都是怎么学习，得到最终结果的呢？

2.2 boosting算法详解

怎么将boosting算法的原理数学化，将实际问题变成可以求解的数学公式？？
将【boosting算法，是一个集成算法，集成若干个基学习器，再集合他们的结果作为最终结果】这句话，数学化就是：boosting算法，是利用加法模型与前向分布算法实现学习，得到最终结果的。

什么是加法模型？

就是基学习器的线性组合。boosting算法不是将若干个基学习器集成在一起吗？怎么集成的？就是简单地将多个基学习器相加，每一个基学习器有一个系数。就是这么简单。用一个数学公式表示就是：

什么是算法模型的学习/优化？

用一个算法去预测样本的目标值，我们怎么知道这个算法模型好不好用呢？看该算法对样本的预测值与样本真实值之间的差异，差异越小，说明该模型算法越好用。

一个算法模型，在最初的参数下，不能保证是好用的，用此时的模型对样本进行预测，预测值与样本真实值之间的差异，不能保证是最小的。所以我们就需要让该算法进行学习，学习的目标就是让样本预测值与真实值之间的差异最小，学习的过程就是不断调整模型参数，以缩小这个差异，直到缩小到足够小。我们平时说的模型算法的学习过程，就指的是这个过程。

样本预测值与其真实值之间的差异，总得有一个数学公式来表示，这个数学公式就叫做损失函数，损失函数的值就是样本预测值与真实值之间的差异。损失函数有很多种定义方式，各有优缺点，这里先不展开。

在给定训练数据集$S = {\{s_1, s_2, ..., s_N\}}$S={s1​,s2​,...,sN​}和损失函数$L(y, f(x))$L(y,f(x))的情况下，以加法模型为例，学习加法模型$f(x)$f(x)就是让损失函数极小化：

总结几种说法，以下几种说法代表的是同一种意思：
优化一个算法模型 
= 学习一个算法模型 
= 不断调整该算法模型的参数，使得该算法对样本的预测值与样本真实值之间的差异越来越小，直到达到足够小 
= 不断调整该算法模型的参数，使得该算法朝着损失函数最小化的方向前进，直到满足条件

什么是前向分步算法？

是一种优化方法。

既然算法要进行学习，那么怎么来调整算法模型的参数，才能使得损失函数最小呢？总得有一个方法来指导，不能瞎调。这个方法就是我们说的优化方法。

加法模型朝着损失函数最小化的方向进行优化，所使用的优化方法就叫做前向分步算法。

优化问题一般都很复杂，加法模型算法涉及到若干个基学习器，每一个基学习器就是一个小算法，要优化若干个小算法，使其整体沿着整体损失函数最小化的方向前进，究竟该怎么做？基于加法模型的特点，发现如果能够从前向后，每一步只学习/优化一个基分类器及其系数，逐步逼近最终目标(8.14)，就可以简化优化的复杂度。事情证明，此种方法确实可行，具体步骤如下：

那么怎么极小化每一个基学习器算法的损失函数，公式(8.16)怎么实现？这就由基学习器本身来决定了，如果基学习器是决策树，那么就用决策树的学习办法来学习优化；如果基学习器是KNN，就用KNN的学习办法来学习优化，具体情况具体定。

上面的过程就是boosting算法的学习/优化步骤。

3 GBDT算法步骤

将上面的内容总结一下：
集成算法： 就是将多个弱分类算法(基学习器)以一定的方式集合在一起，然后再以一定的方式集结多个弱学习算法的结果，作为最终的结果。有2种基学习器集成方法：1、 各个基学习器之间相互独立；2、 各个基学习器之间存在强依赖关系。数学化说法就是，集成算法是一个加法模型，需要用前向优化算法来进行优化学习，得到最终结果；
boosting算法： 是集成算法的一种，属于各个基学习器之间存在强依赖关系的那一种集成算法，每一个基学习器都是依赖于前一个基学习器生成。也是使用前向优化算法进行优化学习；

GBDT： 梯度提升决策树，就是梯度+boosting算法+回归树 = 是一种集成算法，以回归树为基学习器，每一颗回归树都是在前一颗回归树的基础之上生成的，整个算法也是根据前向优化算法进行学习优化。回归树是什么，可以看这个决策树系列（一）：CART-分类回归树-建模步骤以及代码

GBDT，究竟是怎么进行学习的？究竟每一颗回归树是怎么依赖前一颗回归树生成的呢？GBDT中的每一颗回归树拟合的都是上一个回归树的负梯度值，也是残差的近似值。当每一颗回归树的损失函数是平方损失函数时，每一棵决策树（除了第一棵决策树）拟合的是上一棵树的残差；当每一颗回归树的损失函数是一般的损失函数时，每一棵决策树拟合的是上一棵树残差的近似值：损失函数的负梯度。

参考文献

【1】Boosting（Adboost、GBDT、Xgboost）
【2】李航《统计学习》