决策树系列(二):GBDT-梯度提升决策树-算法原理以及步骤

时间:2024-03-26 09:11:43

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算法不是将若干个基学习器集成在一起吗?怎么集成的?就是简单地将多个基学习器相加,每一个基学习器有一个系数。就是这么简单。用一个数学公式表示就是:
决策树系列(二):GBDT-梯度提升决策树-算法原理以及步骤
什么是算法模型的学习/优化?

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

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

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

在给定训练数据集S={s1,s2,...,sN}S = {\{s_1, s_2, ..., s_N\}}和损失函数L(y,f(x))L(y, f(x))的情况下,以加法模型为例,学习加法模型f(x)f(x)就是让损失函数极小化:
决策树系列(二):GBDT-梯度提升决策树-算法原理以及步骤

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

什么是前向分步算法?

是一种优化方法。

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

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

优化问题一般都很复杂,加法模型算法涉及到若干个基学习器,每一个基学习器就是一个小算法,要优化若干个小算法,使其整体沿着整体损失函数最小化的方向前进,究竟该怎么做?基于加法模型的特点,发现如果能够从前向后,每一步只学习/优化一个基分类器及其系数,逐步逼近最终目标(8.14),就可以简化优化的复杂度。事情证明,此种方法确实可行,具体步骤如下:
决策树系列(二):GBDT-梯度提升决策树-算法原理以及步骤
那么怎么极小化每一个基学习器算法的损失函数,公式(8.16)怎么实现?这就由基学习器本身来决定了,如果基学习器是决策树,那么就用决策树的学习办法来学习优化;如果基学习器是KNN,就用KNN的学习办法来学习优化,具体情况具体定。

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

3 GBDT算法步骤

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

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

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

参考文献

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