GBDT：全方面讲解提升树及问题思考 - 统计学习基础

本是古典何须时尚 2022-01-05 08:33 155阅读 0赞

### 前言 ###

提升树是以分类树或者回归树作为基本分类器的提升方法，提升树被认为是统计学习性能中最好的方法之一

### 提升树模型 ###

提升方法采用决策树为弱分类器、学习算法为前向分布学习算法称为提升树，针对分类问题，采用二叉分类树，针对回归问题采用二叉回归树，提升树模型可以表示为决策树的加法模型：  
 f m ( x ) = ∑ m = 1 m T ( x , Θ m ) f\_m(x)=\\sum\_\{m=1\}^\{m\}T(x,\\Theta\_\{m\}) fm(x)=m=1∑mT(x,Θm)  
 T ( x , Θ m ) T(x,\\Theta\_\{m\}) T(x,Θm)为决策树， m m m为分类器的个数， Θ m \\Theta\_\{m\} Θm为决策树的参数。

### 提升树算法 ###

提升树算法，与AdaBoost算法流程相似，第m+1步的决策树模型是：  
 f m + 1 ( x ) = f m ( x ) + T ( x , Θ m + 1 ) f\_\{m+1\}(x)=f\_\{m\}(x)+T(x,\\Theta\_\{m+1\}) fm\+1(x)=fm(x)\+T(x,Θm\+1)  
通过经验风险极小化可以得到：  
 Θ ^ m + 1 = a r g min ⁡ ∑ i = 1 n L ( y i , f m + 1 ( x i ) ) = a r g min ⁡ ∑ i = 1 n L ( y i , f m ( x i ) + T ( x , Θ m + 1 ) \\begin\{aligned\} \\widehat\{\\Theta\}\_\{m+1\} &= arg\\min\\sum\_\{i=1\}^\{n\}L(y\_i,f\_\{m+1\}(x\_i))\\\\ &= arg\\min\\sum\_\{i=1\}^\{n\}L(y\_i,f\_\{m\}(x\_i)+T(x,\\Theta\_\{m+1\}) \\end\{aligned\} Θm\+1=argmini=1∑nL(yi,fm\+1(xi))=argmini=1∑nL(yi,fm(xi)\+T(x,Θm\+1)  
这是求最小化损失函数情况下的提升树的参数，参数得到之后就确定了第m+1轮的提升树，这里要区分一下AdaBoost算法，在AdaBoost算法中，很明显的区别有两个：

*  1、AdaBoost算法中对样本有一个权重 w i w\_i wi，这个权重可以让下一轮的弱分类器专注这些权重比较大的样本，在提升树中没有这个要求，特别是回归树中，每一轮都是上一轮的训练误差。
 *  2、AdaBoost算法中每个分类器都有一个权重 a i a\_i ai，在提升树中就不需要这个，因为每个分类器不需要权重区分，把每个回归树的结果详解就是最终的回归结果。

### 提升树 回归算法 ###

我们来看下提升树在回归问题的算法步骤：  
输入： T = ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x n , y n ) T=\{(x\_1,y\_1),(x\_2,y\_2),...,(x\_n,y\_n)\} T=(x1,y1),(x2,y2),...,(xn,yn)， x i ∈ X ⊆ R n x\_i \\in X \\subseteq R^n xi∈X⊆Rn, y i ∈ Y ⊆ R n y\_i \\in Y \\subseteq R^n yi∈Y⊆Rn  
输出：提升树 f m ( x ) f\_m(x) fm(x)

*  1、初始化 f ( x 0 ) = 0 f(x\_0)=0 f(x0)=0
 *  2、m=1,2,…,m  
    (1) 计算误差： r m i = y i − f m − 1 ( x i ) r\_\{mi\} = y\_\{i\}-f\_\{m-1\}(x\_i) rmi=yi−fm−1(xi)  
    (2) 用误差学习生成回归树 T m ( x , Θ m ) T\_\{m\}(x,\\Theta\_\{m\}) Tm(x,Θm)  
    (3)更新提升树： f m ( x ) = f m − 1 ( x ) + T m ( x , Θ m ) f\_\{m\}(x) = f\_\{m-1\}(x)+T\_\{m\}(x,\\Theta\_\{m\}) fm(x)=fm−1(x)\+Tm(x,Θm)
 *  3、得到最终的提升树：  
     f m ( x ) = ∑ i = 1 m T i ( x , Θ i ) f\_\{m\}(x) = \\sum\_\{i=1\}^\{m\} T\_\{i\}(x,\\Theta\_\{i\}) fm(x)=i=1∑mTi(x,Θi)

#### 回归树例子 ####

以上是提升树的数学表达形式，但其实不够详细，我们先看一个例子来了解一下整体流程，你会发现还有几个问题需要解决。训练集如下所示：

我们假设采用平方损失函数，则我们的损失函数形式如下：  
 min ⁡ s \[ min ⁡ c 1 ∑ x i ∈ R 1 ( y i − c 1 ) 2 + min ⁡ c 2 ∑ x i ∈ R 2 ( y i − c 2 ) \] \\min\_\{s\}\\big\[\\min\_\{c\_1\}\\sum\_\{x\_i \\in R\_1\}(y\_i-c\_1)^2+\\min\_\{c\_2\}\\sum\_\{x\_i\\in R\_2\}(y\_i-c\_2)\\big\] smin\[c1minxi∈R1∑(yi−c1)2\+c2minxi∈R2∑(yi−c2)\]  
其中s表示对数据集的切割， R 1 = \{ x ∣ x ≤ s \} , R 2 = \{ x ∣ x > s \} R\_1=\\\{x|x\\le s\\\},R\_2=\\\{x|x>s\\\} R1=\{ x∣x≤s\},R2=\{ x∣x>s\}， c 1 c\_1 c1和 c 2 c\_2 c2表示对y的输出，表示一个节点把数据集上分隔成两份后各自的输出。

当s=6.5时， R 1 = \{ 1 , 2 , 3 , 4 , 5 , 6 \} R\_1=\\\{1,2,3,4,5,6\\\} R1=\{ 1,2,3,4,5,6\}， R 2 = \{ 7 , 8 , 9 , 10 \} R\_2=\\\{7,8,9,10\\\} R2=\{ 7,8,9,10\}， c 1 = 6.24 c\_1=6.24 c1=6.24， c 2 = 8.91 c\_2=8.91 c2=8.91，所以回归树 T 1 ( x ) T\_1(x) T1(x)表示：  
 T 1 ( x ) = \{ 6.24 x<6.5 8.91 x> 6.5 T\_1(x) = \\begin\{cases\} 6.24& \\text\{x<6.5\}\\\\ 8.91& \\text\{x> 6.5\} \\end\{cases\} T1(x)=\{ 6.248.91x<6.5x> 6.5  
 f 1 ( x ) = T 1 ( x ) f\_1(x)=T\_1(x) f1(x)=T1(x)，用 f 1 ( x ) f\_1(x) f1(x)来拟合这些数据，得到实际的误差 r 2 f = y i − f 1 ( x i ) r\_\{2f\}=y\_i-f\_1(x\_i) r2f=yi−f1(xi) 如下：

所有误差项的平方相加累计得到 L ( y , f 1 ( x ) ) L(y,f\_1(x)) L(y,f1(x))：  
 L ( y , f 1 ( x ) ) = ∑ i = 1 10 ( y i − f 1 ( x i ) ) 2 = 1.93 L(y,f\_1(x))=\\sum\_\{i=1\}^\{10\}(y\_i-f\_1(x\_i))^2=1.93 L(y,f1(x))=i=1∑10(yi−f1(xi))2=1.93  
接下来进行第二轮，第二轮的训练集变成了上图的 x i x\_i xi和 r 2 f r\_\{2f\} r2f，训练集特征数据没变，但是输出数据变成了误差 r 2 f r\_\{2f\} r2f，也就是说我们第二轮需要拟合的数据是误差 r 2 f r\_\{2f\} r2f，流程如上述一样，结果就是经过6轮后，最终的误差为0.17，符合我们的误差期望，得到的分类函数为：  
 f ( x ) = T 1 ( x ) + T 2 ( x ) + . . . + T 6 ( x ) f ( x ) = \{ 5.63 x < 2.5 5.82 2.5 ≤ x < 3.5 6.56 3.5 ≤ x < 4.5 6.83 4.5 ≤ x < 6.5 8.95 x ≥ 6.5 f(x)=T\_1(x)+T\_2(x)+...+T\_6(x) \\\\ f(x) = \\begin\{cases\} 5.63& x<2.5\\\\ 5.82& 2.5\\le x<3.5\\\\ 6.56& 3.5\\le x<4.5\\\\ 6.83& 4.5\\le x<6.5\\\\ 8.95& x\\ge6.5 \\end\{cases\} f(x)=T1(x)\+T2(x)\+...\+T6(x)f(x)=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧5.635.826.566.838.95x<2.52.5≤x<3.53.5≤x<4.54.5≤x<6.5x≥6.5

L ( y , f 6 ( x ) ) = ∑ 1 10 ( y i − f 6 ( x i ) ) 2 = 0.17 L(y,f\_6(x))=\\sum\_\{1\}^\{10\}(y\_i-f\_6(x\_i))^2 = 0.17 L(y,f6(x))=1∑10(yi−f6(xi))2=0.17  
最终的分类函数这么多区间都是不同决策树切割样本后将决策树输出叠加在一起后的结果。总结一下几个问题：

*  1、这里似乎生成回归树值有两层树结构，第一层是没有切分的样本数据，第二层是切割一层之后的样本数据，不会有第三层树结构，这可能不是完全意义上的树算法，更像是一个二分结构，只不过正好跟二叉树有点类似。
 *  2、这里如何确定切割点 s s s？因为每一轮生成一颗提升树都要一个切割点，而且本文样本只有一个特征，只需要对这一个特征确定切割点，如果样本有多个特征，这个切割是怎么回事？
 *  3、如何确定二叉树的每个分支的预测值，本文采取平方最小化来实现，但很明显，用其他计算方式也应该同样可以用来表示。

### 梯度提升 ###

提升树为加法模型和前向分步算法实现学习优化过程，当损失函数是平方损失和指数损失函数时，每一步优化都很简单，但对一般损失函数来说，每一步的优化并不容易，同样可以采用梯度下降法来求解，接下来我们分析梯度提升算法：  
输入： T = ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x n , y n ) T=\{(x\_1,y\_1),(x\_2,y\_2),...,(x\_n,y\_n)\} T=(x1,y1),(x2,y2),...,(xn,yn)， x i ∈ X ⊆ R n x\_i \\in X \\subseteq R^n xi∈X⊆Rn, y i ∈ Y ⊆ R n y\_i \\in Y \\subseteq R^n yi∈Y⊆Rn  
输出：提升树 f m ( x ) f\_m(x) fm(x)

*  1、初始化  
     f 0 ( x ) = a r g min ⁡ c ∑ i = 1 n L ( y i , c ) f\_0(x)=arg\\min\_\{c\} \\sum^\{n\}\_\{i=1\}L(y\_i,c) f0(x)=argcmini=1∑nL(yi,c)  
     a r g min ⁡ arg \\min argmin就是使后面这个式子达到最小值时的变量c的取值，这里c是什么值呢？就是第一个颗树的输出值。当然这个c就是为了第二步骤的梯度计算，这里 f 0 ( x ) = c f\_0(x)=c f0(x)=c，在第二步骤就是用 f 0 ( x ) f\_0(x) f0(x)来计算梯度。
 *  2、对 m = 1 , 2 , 3 , . . . , M m=1,2,3,...,M m=1,2,3,...,M， i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N，计算  
     r m i = − \[ ∂ L ( y i , f m ( x i ) ) ∂ f m ( x i ) \] f m ( x ) = f m − 1 ( x ) r\_\{mi\}=-\\bigg\[\\frac\{\\partial L(y\_i,f\_m(x\_i))\}\{\\partial f\_m(x\_i)\}\\bigg\]\_\{f\_m(x)=f\_\{m-1\}(x)\} rmi=−\[∂fm(xi)∂L(yi,fm(xi))\]fm(x)=fm−1(x)  
    其中， L ( y i , f m ( x i ) ) L(y\_i,f\_m(x\_i)) L(yi,fm(xi))是我们定义的一般性的损失函数，上述公式是对提升树函数的求一阶导，并计算导数得到误差项 r m i r\_\{mi\} rmi，用一个提升树来对 r m i r\_\{mi\} rmi进行拟合。  
    这里最大的区别是用梯度值来模拟一颗树，之前都是计算误差，这里样本的点就变为了 ( x i , r m i ) (x\_i,r\_\{mi\}) (xi,rmi)，之前误差是 y i − ∑ i = 1 m − 1 T ( x i , Θ m ) y\_i-\\sum\_\{i=1\}^\{m-1\}T(x\_i,\\Theta\_\{m\}) yi−∑i=1m−1T(xi,Θm)。
 *  3、拟合之后，得到第m课树的叶结点区域 R m j R\_\{mj\} Rmj， j = 1 , 2 , . . . , J j=1,2,...,J j=1,2,...,J，就是切割之后的分支，计算每个树分支的输出值，也就是预测值 c m j c\_\{mj\} cmj：  
     c m j = a r g min ⁡ c ∑ x i ∈ R m j L ( y i , f m − 1 ( x i ) + c ) c\_\{mj\}=arg \\min\_\{c\}\\sum\_\{x\_i \\in R\_\{mj\}\}L(y\_i,f\_\{m-1\}(x\_i)+c) cmj=argcminxi∈Rmj∑L(yi,fm−1(xi)\+c)  
    这里 c m j c\_\{mj\} cmj就是我们说的树的每个分支的预测值，利用 c m j c\_\{mj\} cmj更新提升树：  
     f m x = f m − 1 ( x ) + ∑ j = 1 J c m j I ( x ∈ R m j ) f\_m\{x\}=f\_\{m-1\}(x)+\\sum\_\{j=1\}^\{J\}c\_\{mj\}I(x \\in R\_\{mj\}) fmx=fm−1(x)\+j=1∑JcmjI(x∈Rmj)
 *  4、得到最终的提升树，累计相加：  
     f ( x ) = f M ( x ) = ∑ m = 1 M ∑ j = 1 J c m j I ( x ∈ R m j ) f(x)=f\_\{M\}(x)=\\sum\_\{m=1\}^\{M\}\\sum\_\{j=1\}^\{J\}c\_\{mj\}I(x \\in R\_\{mj\}) f(x)=fM(x)=m=1∑Mj=1∑JcmjI(x∈Rmj)  
    计算损失函数的负梯度在当前模型的值，将它作为残差的估计，对于平方损失函数，它就是通常所说的残差，对于一般损失来说，它就是残差的近似值。

同样总结一下流程，有几点疑问：

*  为什么梯度提升树中就有很多树分支？不想上一节那样，只切分成两个树分支，如果切割成多个树分支，那为啥不一个样本一个分支，这样在测试集上的准确率就100%了，哈哈，不过鲁棒性很差，在测试集上肯定过拟合，所以这个树分支数目如何确定？还是说本流程只是一个数学形式化表示？
 *  上面那个问题同样涉及到如何切割分割点的问题，1个切割点就会有2个树分支，2个数分支就会有3个树分支，这两者有关联。

### 关于梯度提升 ###

上一节内容里我很奇怪，为什么可以拿负梯度作为近似值？如果回归问题是可以这么做的，如果是分类问题，如何求的误差？对于分类问题，你得到的误差是无意义的，所以用损失函数的负梯度可以兼容分类、回归问题，只不过是，不同任务选择不同的损失函数，同时也是一种近似值。我们看下关乎近似值的问题。  
找了一些关于梯度提升的资料，我们总结分析一下，误差函数为 L ( y , f ( x ) ) = L ( y , y t − 1 + f t ( x ) ) L(y,f(x))=L(y,y^\{t-1\}+f\_\{t\}(x)) L(y,f(x))=L(y,yt−1\+ft(x))， f t ( x ) f\_\{t\}(x) ft(x)为树函数，对误差公式做二阶泰勒展开式有：  
 L ( y , y t − 1 + f t ( x ) ) = L ( y , y t − 1 ) + g f t ( x ) + 1 2 h f t 2 ( x ) L(y,y^\{t-1\}+f\_\{t\}(x))=L(y,y^\{t-1\})+gf\_\{t\}(x)+\\frac\{1\}\{2\}hf\_\{t\}^\{2\}(x) L(y,yt−1\+ft(x))=L(y,yt−1)\+gft(x)\+21hft2(x)  
其中 g g g是 L L L的一阶导数， h h h是 L L L的二阶导数，对泰勒展开式求极值，对 f ( x ) f(x) f(x)求一阶导数得到：  
 L ′ = g + h f t ( x ) L'=g+hf\_\{t\}(x) L′=g\+hft(x)  
让上式等于0，得到 f t ( x ) = − g h f\_t(x)=-\\frac\{g\}\{h\} ft(x)=−hg，对于平方损失函数，以及 g = y t − 1 − y , h = 1 g=y^\{t-1\}-y,h=1 g=yt−1−y,h=1，所以 f t ( x ) = − g = y − y t − 1 f\_t(x)=-g=y-y^\{t-1\} ft(x)=−g=y−yt−1，也就是残差等于负梯度，也就利用负梯度来拟合新的决策树，对于其他的损失函数，我们假设 h = 1 h=1 h=1，舍弃高阶项，相当于拟合残差的近似值，如果加上正则项，变为：  
 f t ( x ) = − g h + λ f\_t(x)=-\\frac\{g\}\{h+\\lambda\} ft(x)=−h\+λg  
这里有一个比较令人思考的问题：残差=真值-预测值，明明可以直接计算，为啥要用负梯度？  
我们知道当我们确定了一颗树之后，我们就可以求得残差，利用残差去拟合下一课树，第一课树的残差就是真实值，我们利用损失函数来确定一棵树，他们之间的关系就是：  
残差 - - > 损失函数 - - > 确定一课决策树 - - > 计算下一轮的残差  
这同时又一个问题？残差必须要算出实际值吗？我觉得是不需要的，因为：  
 f m + 1 ( x ) = f m ( x ) + T ( x , Θ m + 1 ) f\_\{m+1\}(x)=f\_\{m\}(x)+T(x,\\Theta\_\{m+1\}) fm\+1(x)=fm(x)\+T(x,Θm\+1)

所以第m+1论的决策树的 残 差 = y i − f m ( x ) 残差=y\_i-f\_\{m\}(x) 残差=yi−fm(x)，我们可以直接用公式来做处理，带入到损失函数中，为了求解第m+1轮的决策树，我们要使得损失函数最小，结果发现残差等于 f t ( x ) = − g = y − y m f\_t(x)=-g=y-y^\{m\} ft(x)=−g=y−ym，残差也等于 y − y m y-y^\{m\} y−ym，所以正好利用负梯度来做残差。 f t ( x ) = − g = y − y m f\_t(x)=-g=y-y^\{m\} ft(x)=−g=y−ym这个公式是上述泰勒展开式得到的结果。

### 与AdaBoost对比 ###

AdaBoost是通过直接改变样本权重分布来让下个基学习器关注错误样本，尽可能的预测对权重更大的错误样本。而梯度提升树是通过负梯度值来让下个基学习器关注错误样本，尽可能的预测对负梯度值更大的错误样本。

某个样本，如果他是正类，预测也是正类， 那么 r = 1 1 + e r=\\frac\{1\}\{1+e\} r=1\+e1，如果他是正类，预测是负类， 那么 r = 1 1 + e − 1 r=\\frac\{1\}\{1+e^\{-1\}\} r=1\+e−11，明显误分类的时候要拟合的负梯度大。而且在求每颗树的叶子节点的时候其实是没有参考该颗树的输入标签的值，而是通过之前所有树的输出和原始标签值对比，来求得一个误差最小的值作为该叶子区域的样本输出。

### 损失函数选择 ###

比如回归基本就是均方误差。分类多点，常见的有对数损失函数，指数损失函数，交叉熵损失函数等。损失函数的选择和对问题的建模方法有关。这个要在实际中去摸索经验。

### 总结 ###

一句话提升树被认为是统计学习中最有效的方法之一，本文依旧会有一些问题，我想再写一篇文章中来探讨这些问题，算是系列二吧。

### 参考博客 ###

统计学习方法  
[梯度提升树中为什么说目标函数关于当前模型的负梯度是残差的近似值？][Link 1]

[Link 1]: https://www.zhihu.com/question/60625492