2021人工智能领域新星创作者，带你从入门到精通，该博客每天更新，逐渐完善机器学习各个知识体系的文章，帮助大家更高效学习。

一、引言

之前我们使用Boosting模型讲解了AdaBoost算法模型的原理，采用加法模型和向前分步算法，它是采用了很多个基学习器按照一定权重进行线性组合。

f M ( x ) = ∑ m = 1 M a m f m ( x ) f_M(x)=\sum_{m=1}^Ma_mf_m(x)fM(x)=m=1∑Mamfm(x)

Boosting算法的思想就是将多个基学习器串行训练，它会改变样本的权重，将每次训练失败的样本的权重增加，使之后的学习器更加关注上次错误分类的样本。

这里说明一下为什么要改变权重，一是上面说到的，为了使后面的学习器更加前面分错的样本，另外就是我们使用集成学习的目的就是能够使内部每个基学习器应该有各自的特点，如果使用同样的数据进行拟合，那么我们获得的基学习器几乎是差不多的，集成参数相似的模型没有什么意思，所以我们希望内部的基学习器应为不同的模型，要达到这样，我们就使用了一种方法就是每轮更改样本的权重，这样基学习器每次学习的样本就会不同。

AdaBoost就是按照这个思想，通过改变样本的权重，Boosting还有一种方式就是不改变样本的权重，采用拟合残差的方式，它的一种典型算法就是提升树。

二、提升树

提升树算法

我们上面说Boosting一般两种方式，一是更改样本权重，另外一种是拟合参数，我们的提升树就是使用了第二种拟合残差的方式，提升树可以理解为是AdaBoost+决策树的模型。

提升树的模型定义如下：

f M ( x ) = ∑ m = 1 M T ( x ; θ m ) f_M(x)=\sum_{m=1}^MT(x;\theta_m)fM(x)=m=1∑MT(x;θm)

注意这里和AdaBoost不同的地方是这里只是所有树模型最终输出值相加，没有权重。

前向分步算法

由于提升树是AdaBoost的一种特例，所以它的求解也是使用了前向分步算法。

所以我们把上面的定义换一种写法：

f m ( x ) = f m − 1 ( x ) + T ( x ; θ m ) f_m(x)=f_{m-1}(x)+T(x;\theta_m)fm(x)=fm−1(x)+T(x;θm)

它的意思就是当前的集成模型等于前m-1个模型+当前训练的模型 T ( x ; θ m ) T(x;\theta_m)T(x;θm) ,为了与上述等式一致，我们设定 f 0 ( x ) = 0 f_0(x)=0f0(x)=0 ，这样当 m = 1 m=1m=1 时，f 1 ( x ) = f 0 ( x ) + T ( x ; θ 1 ) = T ( x ; θ 1 ) f_1(x)=f_0(x)+T(x;\theta_1)=T(x;\theta_1)f1(x)=f0(x)+T(x;θ1)=T(x;θ1) 就等于第一个基学习器。

为了求解模型参数，我们需要构建损失函数：

L ( y , f ( x ) ) = L ( y , f m ( x ) ) = L ( y , y m − 1 ( x ) + T ( x ; θ m ) ) L(y,f(x))=L(y,f_m(x))=L(y,y_{m-1}(x)+T(x;\theta_m))L(y,f(x))=L(y,fm(x))=L(y,ym−1(x)+T(x;θm))

上述三种写法都是损失函数，等价，其中 f m ( x ) f_m(x)fm(x) 代表m个基学习器的集成模型，T ( x ; θ m ) T(x;\theta_m)T(x;θm) 代表第m个基学习器，我们的目的就是最小化损失函数，求取每个基学习器的参数 θ m \theta_mθm 。

为了叙述方便，我们定义我们的损失为回归损失，所以损失函数为：

L ( y , f m ( x ) ) = ( y − f m ( x ) ) 2 L(y,f_m(x))=(y-f_m(x))^2L(y,fm(x))=(y−fm(x))2

又因为 f m ( x ) = f m − 1 ( x ) + T ( x ; θ m ) f_m(x)=f_{m-1}(x)+T(x;\theta_m)fm(x)=fm−1(x)+T(x;θm) ，所以损失函数变为：

L ( y , f m − 1 ( x ) + T ( x ; θ m ) ) = ( y − f m − 1 ( x ) − T ( x ; θ m ) ) 2 = ( r − T ( x ; θ m ) ) 2 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))^2L(y,fm−1(x)+T(x;θm))=(y−fm−1(x)−T(x;θm))2=(r−T(x;θm))2

其中 r = y − f m − 1 ( x ) r=y-f_{m-1}(x)r=y−fm−1(x)

为了求解最优模型，所以我们希望损失函数很小，越趋于0越好，所以我们希望 r − T ( x ; θ m ) ∼ 0 r-T(x;\theta_m) \sim 0r−T(x;θm)∼0 ，也就是我们第m个基学习器的预测值越接近残差越好。

那么什么是残差呢？残差就是预测值和真实值的差值，就是 y ∗ − y y^*-yy∗−y ，可以看到我们定义的残差 r = y − f m − 1 ( x ) r=y-f_{m-1}(x)r=y−fm−1(x) ，其中y就是真实值标签，f m − 1 ( x ) f_{m-1}(x)fm−1(x) 就是 m-1个基学习器集成模型的预测值，或者说是训练上个基学习器的时候的预测值。

重点：

我们的AdaBoost的基学习器是希望每个基学习器拟合原数据越精准越好，都是拟合同样的y，然是我们提升树的基学习器不一样，它不拟合数据y，它是拟合参数，什么意思呢？就是每个基学习器学习的数据的标签不是原数据y，而是相对应的残差r，这就是二者不一样的地方，提升树是希望每个基学习器能够更好的拟合残差，这个可以从上面的式子看出：

( r − T ( x ; θ m ) ) ∼ 0 (r-T(x;\theta_m)) \sim 0(r−T(x;θm))∼0

每个基学习器的输出值越接近残差越好，这就是提升树原理，尽可能让每个基学习器拟合上一轮的残差。

提升树算法流程

1.初始化 f 0 ( x ) = 0 f_0(x)=0f0(x)=0 ，这是为了不影响结果，f 1 ( x ) = f 0 ( x ) + T ( x ; θ 1 ) f_1(x)=f_0(x)+T(x;\theta_1)f1(x)=f0(x)+T(x;θ1)

2.迭代训练M个基学习器

（a）更新样本标签，将原标签y换成相应的残差，为什么换成残差上面我们说过了

r m i = y i − f m − 1 ( x i ) r_{mi}=y_i-f_{m-1}(x_i)rmi=yi−fm−1(xi)

（b）训练新数据 ( x 1 , r m 1 ) , ( x 2 , r m 2 ) , . . . , ( x n , r m n ) (x_1,r_{m1}),(x_2,r_{m2}),...,(x_n,r_{mn})(x1,rm1),(x2,rm2),...,(xn,rmn) ，用第m个基学习器 T ( x ; θ m ) T(x;\theta_m)T(x;θm) 去拟合新数据集

（c）更新集成模型

f m ( x ) = f m − 1 ( x ) + T ( x ; θ m ) f_m(x)=f_{m-1}(x)+T(x;\theta_m)fm(x)=fm−1(x)+T(x;θm)

3.获得最终集成模型

f m ( x ) = ∑ m = 1 M T ( x ; θ m ) f_m(x)=\sum_{m=1}^MT(x;\theta_m)fm(x)=m=1∑MT(x;θm)

三、梯度提升树

提升树利用加法模型与前向分步算法实现学习的优化过程，当损失函数为平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不容易，所以为了应对这一问题，Freidman提出了梯度提升算法，将其应用到我们的提升树中就成为了很出名的梯度提升树即GDBT。

损失函数和上面的一样都为：

L ( y , f m − 1 ( x ) + T ( x ; θ m ) ) = ( y − f m − 1 ( x ) − T ( x ; θ m ) ) 2 = ( r − T ( x ; θ m ) ) 2 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))^2L(y,fm−1(x)+T(x;θm))=(y−fm−1(x)−T(x;θm))2=(r−T(x;θm))2

然后模型也是同样：

f m ( x ) = f m − 1 ( x ) + T ( x ; θ m ) f_m(x)=f_{m-1}(x)+T(x;\theta_m)fm(x)=fm−1(x)+T(x;θm)

但是这里我们不用 y − f m − 1 ( x ) y-f_{m-1}(x)y−fm−1(x) 代替残差，而是换一种方式，采用负梯度的形式，其实梯度提升树和普通提升树就差在残差这里。

普通提升树的残差为：

r m i = y i − f m − 1 ( x i ) r_{mi}=y_i-f_{m-1}(x_i)rmi=yi−fm−1(xi)

但是我们梯度提升树的残差用下面的式子进行代替：

r m i = − ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) r_{mi}=-\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}rmi=−∂f(xi)∂L(yi,f(xi))

其中这里 f ( x ) = f m − 1 ( x ) f(x)=f_{m-1}(x)f(x)=fm−1(x)

GBDT算法流程

1.初始化

f 0 ( x ) = a r g m i n c   ∑ i = 1 N L ( y i , c ) f_0(x)=argmin_c\ \sum_{i=1}^NL(y_i,c)f0(x)=argminci=1∑NL(yi,c)

2.训练M个基学习器

（a）更新样本数据，将标签换成残差

r m i = − ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) r_{mi}=-\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}rmi=−∂f(xi)∂L(yi,f(xi))

（b）使用第m个基学习器拟合新的样本数据，得到 T ( x ; θ m ) T(x;\theta_m)T(x;θm) 回归树

（c）更新模型

f m ( x ) = f m − 1 ( x ) + T ( x ; θ m ) f_m(x)=f_{m-1}(x)+T(x;\theta_m)fm(x)=fm−1(x)+T(x;θm)

3.获得最终的集成模型

f m ( x ) = ∑ m = 1 M T ( x ; θ m ) = ∑ m = 1 M ∑ j = 1 J c m j I ( x ∈ R m j ) f_m(x)=\sum_{m=1}^MT(x;\theta_m)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj})fm(x)=m=1∑MT(x;θm)=m=1∑Mj=1∑JcmjI(x∈Rmj)

泰勒一阶展开

这里证明一下为什么使用 r m i = − ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) r_{mi}=-\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}rmi=−∂f(xi)∂L(yi,f(xi)) 代替原来的残差。

我们现在存在两个模型，分别为 f m ( x ) f_m(x)fm(x) 和 f m − 1 ( x ) f_{m-1}(x)fm−1(x) ，可以看出 f m ( x ) = f m − 1 ( x ) + T ( x ; θ m ) f_m(x)=f_{m-1}(x)+T(x;\theta_m)fm(x)=fm−1(x)+T(x;θm) ，可以看出 f m ( x ) f_m(x)fm(x) 为 f m − 1 ( x ) f_{m-1}(x)fm−1(x) 的升级版，因为又加入了一个基学习器，我们希望集成学习中没加入一个基学习器，模型的效果越高，那也就是说模型的损失函数降低，即：

L ( y , f m ( x ) ) < L ( y , f m − 1 ( x ) ) L(y,f_m(x))<L(y,f_{m-1}(x))L(y,fm(x))<L(y,fm−1(x))

因为 f m ( x ) = f m − 1 ( x ) + T ( x ; θ m ) f_m(x)=f_{m-1}(x)+T(x;\theta_m)fm(x)=fm−1(x)+T(x;θm) ，所以上式可写为：

L ( y , f m − 1 ( x ) + T ( x ; θ m ) ) < L ( y , f m − 1 ( x ) ) L(y,f_{m-1}(x)+T(x;\theta_m))<L(y,f_{m-1}(x))L(y,fm−1(x)+T(x;θm))<L(y,fm−1(x))

这里我们使用了泰勒一阶展开进行函数逼近，我们将 L ( y , f m − 1 ( x ) + T ( x ; θ m ) ) L(y,f_{m-1}(x)+T(x;\theta_m))L(y,fm−1(x)+T(x;θm)) 在点 f m − 1 ( x ) f_{m-1}(x)fm−1(x) 处进行泰勒一阶展开。

泰勒展开式一般为：

f ( x ) = f ( x 0 ) + f ′ ( x 0 ) ( x − x 0 ) f(x)=f(x_0)+f'(x_0)(x-x_0)f(x)=f(x0)+f′(x0)(x−x0)

所以上式的展开式为：

L ( y , f m − 1 ( x ) + T ( x ; θ m ) ) = L ( y , f m − 1 ( x ) ) + ∂ L ( y , f m − 1 ( x ) ) ∂ f m − 1 ( x ) T ( x ; θ m ) L(y,f_{m-1}(x)+T(x;\theta_m))=L(y,f_{m-1}(x))+\frac{\partial L(y,f_{m-1}(x))}{\partial f_{m-1}(x)}T(x;\theta_m)L(y,fm−1(x)+T(x;θm))=L(y,fm−1(x))+∂fm−1(x)∂L(y,fm−1(x))T(x;θm)

这里有些人可能没看明白，解释一下：

• f ( x 0 ) f(x_0)f(x0) ：L ( y , f m − 1 ( x ) ) L(y,f_{m-1}(x))L(y,fm−1(x))
• f ′ ( x 0 ) f'(x_0)f′(x0) ：∂ L ( y , f ( x ) ) ∂ f ( x ) \frac{\partial L(y,f(x))}{\partial f(x)}∂f(x)∂L(y,f(x))
• x − x 0 x-x_0x−x0 ：T ( x ; θ m ) T(x;\theta_m)T(x;θm)
• x 0 x_0x0 ：f m − 1 ( x ) f_{m-1}(x)fm−1(x)

为了方便观看计算，我们另 f m − 1 ( x ) + T ( x ; θ m ) = x f_{m-1}(x)+T(x;\theta_m)=xfm−1(x)+T(x;θm)=x ，所以原式就变为了：

L ( y , f m − 1 ( x ) + T ( x ; θ m ) ) = L ( y , x ) L(y,f_{m-1}(x)+T(x;\theta_m))=L(y,x)L(y,fm−1(x)+T(x;θm))=L(y,x)

所以当 x = x 0 x=x_0x=x0 时，f ( x 0 ) = L ( y , f m − 1 ( x ) ) f(x_0)=L(y,f_{m-1}(x))f(x0)=L(y,fm−1(x)) ，其它同理。

L ( y , f m − 1 ( x ) + T ( x ; θ m ) ) < L ( y , f m − 1 ( x ) ) L(y,f_{m-1}(x)+T(x;\theta_m))<L(y,f_{m-1}(x))L(y,fm−1(x)+T(x;θm))<L(y,fm−1(x))

所以这个式子就变成了：

L ( y , f m − 1 ( x ) ) + ∂ L ( y , f m − 1 ( x ) ) ∂ f m − 1 ( x ) T ( x ; θ m ) < L ( y , f m − 1 ( x ) ) L(y,f_{m-1}(x))+\frac{\partial L(y,f_{m-1}(x))}{\partial f_{m-1}(x)}T(x;\theta_m)<L(y,f_{m-1}(x))L(y,fm−1(x))+∂fm−1(x)∂L(y,fm−1(x))T(x;θm)<L(y,fm−1(x))

化简后得：

∂ L ( y , f m − 1 ( x ) ) ∂ f m − 1 ( x ) T ( x ; θ m ) < 0 \frac{\partial L(y,f_{m-1}(x))}{\partial f_{m-1}(x)}T(x;\theta_m)<0∂fm−1(x)∂L(y,fm−1(x))T(x;θm)<0

所以 T ( x ; θ m ) T(x;\theta_m)T(x;θm) 和 ∂ L ( y , f m − 1 ( x ) ) ∂ f m − 1 ( x ) \frac{\partial L(y,f_{m-1}(x))}{\partial f_{m-1}(x)}∂fm−1(x)∂L(y,fm−1(x)) 异号，所以我们另：

T ( x ; θ m ) = − ∂ L ( y , f m − 1 ( x ) ) ∂ f m − 1 ( x ) T(x;\theta_m)=-\frac{\partial L(y,f_{m-1}(x))}{\partial f_{m-1}(x)}T(x;θm)=−∂fm−1(x)∂L(y,fm−1(x))

这样就可以保证两者乘积异号，我们希望当前模型 T ( x ; θ m ) T(x;\theta_m)T(x;θm) 的值为负梯度方向，这样我们的模型的损失函数才能够下降，所以我们每次更新模型就变成了：

f m ( x ) = f m − 1 ( x ) + T ( x ; θ m ) = f m − 1 ( x ) − ∂ L ( y , f m − 1 ( x ) ) ∂ f m − 1 ( x ) f_m(x)=f_{m-1}(x)+T(x;\theta_m)=f_{m-1}(x)-\frac{\partial L(y,f_{m-1}(x))}{\partial f_{m-1}(x)}fm(x)=fm−1(x)+T(x;θm)=fm−1(x)−∂fm−1(x)∂L(y,fm−1(x))

其实这个就和普通提升树差不多了，普通提升树是用每轮的残差代替 T ( x ; θ m ) T(x;\theta_m)T(x;θm) ，而我们的梯度提升树就是使用了负梯度进行近似拟合。