【机器学习】集成学习(三)----前向分步算法、提升树与GBDT

对于前一篇的AdaBoost算法我们其实可以这样理解，模型是加法模型、损失函数为指数函数、学习算法为前向分步算法时的二类分类学习方法。其实加法模型就是基分类器的线性组合啦，那么前向分步算法是什么呢？

【加法模型】

我们将f(x)=∑m=1Mβmb(x;γm)$f(x)=\sum _{m=1}^M{\beta }_{m}b(x;{\gamma }_m)$作为加法模型，其中b(x;γm)$b(x;{\gamma }_m)$为基函数，γm${\gamma }_m$为基函数的参数，βm${\beta }_m$为基函数的系数，βm${\beta }_m$表示着对应的基函数在加法模型f(x)$f(x)$中的重要性。

【前向分步算法】

基本思想：

一般来说：$一般来说：$
在给定训练数据和损失函数L(y,f(x))$L(y,f(x))$的条件下，学习加法模型f(x)$f(x)$成为经验风险极小化(即损失函数极小化问题)
　　　　minβm,γm∑i=1NL(yi,∑m=1Mβmb(xi;γm))$\underset{{\beta }_m,{\gamma }_m}{min}\sum _{i=1}^{N}L(y_i,\sum _{m=1}^M{\beta }_{m}b(x_i;{\gamma }_m))$
这里是要最小化每一步生成的基函数的损失函数之和$这里是要最小化每一步生成的基函数的损失函数之和$
但是！这通常是一个很复杂的问题，因此提出前向分步算法的思想：$但是！这通常是一个很复杂的问题，因此提出前向分步算法的思想：$
前向分步算法求解这一优化问题的想法是：由于学习的是加法模型，如果能从前向后每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，即minβm,γm∑i=1NL(yi,∑m=1Mβmb(xi;γm))$\underset{{\beta }_m,{\gamma }_m}{min}\sum _{i=1}^{N}L(y_i,\sum _{m=1}^M{\beta }_{m}b(x_i;{\gamma }_m))$，那么就可以简化优化的复杂度。因此每步我们只需要优化minβ,γ∑i=1NL(yi,βb(xi;γ))$\underset{\beta ,\gamma }{min}\sum _{i=1}^{N}L(y_i,\beta b(x_i;\gamma ))$即可。
也就是说我每次学习一个基函数(基分类器)，我只针对这个基分类器进行优化，$也就是说我每次学习一个基函数(基分类器)，我只针对这个基分类器进行优化，$
使其损失函数最小$使其损失函数最小$

算法过程：

输入:训练数据集T={(x1,y1),(x2,y2),...,(xN,yN)}$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$；损失函数L(y,f(x))$L(y,f(x))$；基函数集{b(x;γ)}$\{b(x;\gamma )\}$
输出:加法模型f(x)$f(x)$
(1)初始化f0(x)=0$f_0(x)=0$

(2)对m=1,2,...,M$m=1,2,...,M$
①极小化损失函数，得到参数βm${\beta }_m$和γm${\gamma }_m$
　　　　(βm,γm)=argminβ,γ∑i=1NL(yi,fm−1(xi)+βb(xi;γ))$({\beta }_m,{\gamma }_m)=arg\underset{\beta ,\gamma }{min}\sum _{i=1}^{N}L(y_i,f_{m-1}(x_i)+\beta b(x_i;\gamma ))$
②更新fm(x)$f_m(x)$
　　　　fm(x)=fm−1(x)+βmb(x;γm)$f_m(x)=f_{m-1}(x)+{\beta }_{m}b(x;{\gamma }_m)$
　　　　
(3)得到加法模型f(x)$f(x)$
　　　　f(x)=fM(x)=∑m=1Mβmb(x;γm)$f(x)=f_M(x)=\sum _{m=1}^M{\beta }_{m}b(x;{\gamma }_m)$
　　　　

这样我们就将同时求解从m=1$m=1$到M$M$所有参数βm${\beta }_m$和γm${\gamma }_m$的优化问题简化为逐次求解各个βm${\beta }_m$，γm${\gamma }_m$的优化问题。

【提升树】

提升树(Boosting Tree)其实就是采用加法模型与前向分步算法，以cart决策树为基函数的提升方法。对于分类问题决策树是二叉分类树，对于回归问题决策树是二叉回归树。

提升树的加法模型：

　　　　fM(x)=∑m=1MT(x;Θm)$f_M(x)=\sum _{m=1}^{M}T(x;{\Theta }_m)$
其中T(x;Θm)$T(x;{\Theta }_m)$表示决策树；Θm${\Theta }_m$表示决策树的参数；M$M$为树的个数

提升树的前向分步算法：

　　　　fm(x)=fm−1(x)+T(x;Θm)$f_m(x)=f_{m-1}(x)+T(x;{\Theta }_m)$
其中fm−1(x)$f_{m-1}(x)$为当前模型，通过经验风险极小化确定下一棵决策树的参数Θm${\Theta }_m$　　　　
　　　　Θ^m=argminΘm∑i=1NL(yi,fm−1(xi)+T(xi;Θm))${\hat{\Theta }}_m=arg\underset{{\Theta }_m}{min}\sum _{i=1}^{N}L(y_i,f_{m-1}(x_i)+T(x_i;{\Theta }_m))$

其实对于解决不同问题的提升树学习算法，它们的主要区别在于使用的损失函数的不同：

问题类型	损失函数	方法
分类问题	指数损失函数	极小化分类误差率
回归问题	平方误差损失函数	拟合当前模型的残差
一般决策问题	一般损失函数	梯度提升(最速下降法近似方法)

一、分类问题提升树算法

对于二类分类问题，提升树算法只需要将AdaBoost算法中的基分类器限制为二类分类树即可。

二、回归问题提升树算法

对于回归问题而言，提升树算法其实就是每次的训练数据都是上一次训练出来回归树的预测值与真实值的残差。回归问题提升树算法中，我们使用平方误差损失函数，即L(y,f(x))=(y−f(x))2$L(y,f(x))=(y-f(x){)}^2$
它的损失L(yi,fm−1(xi)+T(xi;Θm))$L(y_i,f_{m-1}(x_i)+T(x_i;{\Theta }_m))$则变为[yi−fm−1(xi)−T(xi;Θm)]2$[y_i-f_{m-1}(x_i)-T(x_i;{\Theta }_m){]}^2$
令rmi=yi−fm−1(xi)$r_{mi}=y_i-f_{m-1}(x_i)$即当前模型拟合数据的残差$即当前模型拟合数据的残差$
则等于[rmi−T(xi;Θm)]2$[r_{mi}-T(x_i;{\Theta }_m){]}^2$
也就是说，我们只需要简单的拟合当前模型的残差即可$也就是说，我们只需要简单的拟合当前模型的残差即可$
举个例子，比如我预测一个人的身高，真实身高是1.8m，我第一次拟合是1.7m，那么第二次拟合只需要对于我第一次拟合的残差1.8-1.7=0.1m进行拟合就可以了；假设第二次拟合了0.04，那么第二次拟合的残差就为1.8-1.74=0.06；这时第三次拟合只需要对0.06进行即可。通过这样的过程我们可以发现，拟合的误差会越来越小。

算法过程：

输入:训练数据集T={(x1,y1),(x2,y2),...,(xN,yN)}$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，xi∈X⊆Rn$x_i\in \mathcal{X}\subseteq R^n$，yi∈Y⊆R$y_i\in \mathcal{Y}\subseteq R$；损失函数L(y,f(x))$L(y,f(x))$；
输出:回归树f^(x)$\hat{f}(x)$
(1)初始化f0(x)$f_0(x)$
　　　　　　f0(x)=0$f_0(x)=0$
　　　　　　
(2)对m=1,2,...,M$m=1,2,...,M$
①计算残差rmi$r_{mi}$;
　　　　　　rmi=yi−fm−1(xi)$r_{mi}=y_i-f_{m-1}(x_i)$
②拟合残差rmi$r_{mi}$学习一个回归树，得到T(x;Θm)$T(x;{\Theta }_m)$;
③更新fm(x)$f_m(x)$;
　　　　　　fm(x)=fm−1(x)+T(x;Θm)$f_m(x)=f_{m-1}(x)+T(x;{\Theta }_m)$;

(3)得到回归问题提升树fM(x)$f_M(x)$
　　　　　　fM(x)=∑m=1MT(x;Θm)$f_M(x)=\sum _{m=1}^{M}T(x;{\Theta }_m)$

三、梯度提升树算法(GBDT)

如果我们的损失函数都是平方损失函数或是指数损失函数，那么每一步优化都是很简单的，但是对于一般损失函数而言，往往每一步优化并不容易，因此对于这个问题，提出了梯度提升算法。

算法过程:

输入:
输出:
(1)初始化f0(x)$f_0(x)$
　　　　f0(x)=argminc∑i=1NL(yi,c)$f_0(x)=arg\underset{c}{min}\sum _{i=1}^{N}L(y_i,c)$
估计使损失函数极小化的常数值c，将其赋值给f0(x)$估计使损失函数极小化的常数值c，将其赋值给f_0(x)$　　
　　
(2)对m=1,2,...,M$m=1,2,...,M$
①对i=1,2,...,N$i=1,2,...,N$计算
　　　　rmi=−[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)$r_{mi}=-[\frac{\mathrm{\partial }L(y,f(x_i))}{\mathrm{\partial }f(x_i)}{]}_{f(x)=f_{m-1}(x)}$
这里利用的是最速下降法的近似方法，利用损失函数的负梯度在当前模型的值，即$这里利用的是最速下降法的近似方法，利用损失函数的负梯度在当前模型的值，即$　　　　
−[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)$-[\frac{\mathrm{\partial }L(y,f(x_i))}{\mathrm{\partial }f(x_i)}{]}_{f(x)=f_{m-1}(x)}$
当做回归问题提升树中的残差rmi的近似值，拟合一个回归树$当做回归问题提升树中的残差r_{mi}的近似值，拟合一个回归树$
②对rmi$r_{mi}$拟合一个回归树，得到第m$m$棵树的叶节点区域Rmj,j=1,2,...,J$R_{mj},j=1,2,...,J$
J为叶节点个数$J为叶节点个数$
③对j=1,2,...,J$j=1,2,...,J$计算
　　　　cmj=argminc∑xi∈RmjL(yi,fm−1(xi)+c)$c_{mj}=arg\underset{c}{min}\sum _{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$
对于每个叶节点上的样本，我们求出使损失函数最小的输出值cmj$对于每个叶节点上的样本，我们求出使损失函数最小的输出值c_{mj}$
　　　　
④更新fm(x)$f_m(x)$
　　　　fm(x)=fm−1(x)+∑j=1JcmjI(x∈Rmj)$f_m(x)=f_{m-1}(x)+\sum _{j=1}^J{c}_{mj}I(x\in R_{mj})$
　　　　
(3)得到回归树
　　　　f^(x)=fM(x)=∑m=1M∑j=1JcmjI(x∈Rmj)$\hat{f}(x)=f_M(x)=\sum _{m=1}^M\sum _{j=1}^J{c}_{mj}I(x\in R_{mj})$

其实无论是分类问题还是回归问题的提升树，我们都可以用损失函数的负梯度来$其实无论是分类问题还是回归问题的提升树，我们都可以用损失函数的负梯度来$
近似残差，用作拟合数据，它们的区别只在于损失函数不同导致的负梯度的不同，$近似残差，用作拟合数据，它们的区别只在于损失函数不同导致的负梯度的不同，$
这就是GBDT算法。$这就是GBDT算法。$

GBDT和RF都是集成学习中很经典的算法，下一篇就来学习RF(随机森林)，看看它和GBDT的区别在哪

参考文献:《统计学习方法》