GBDT原理小结

快来打我* 2022-01-23 05:51 253阅读 0赞

最近在做文本分类的工作，使用到了XGBoost用于多分类。因此本文针对自己学习的XGBoost相关知识进行简单记录，并延伸了GBDT的相关理论知识。

## 一、监督学习算法 ##

监督学习算法主要有以下三个重要组成部分：

*  模型
 *  参数
 *  目标函数

#### 1、模型 ####

模型是指给定输入 x i x\_\{i\} xi如何去预测输出 y i y\_\{i\} yi，比较常见的模型有线性模型，采用线性叠加的方式进行预测：  
 y i ^ = ∑ j ω j x i j \\hat\{y\_\{i\}\}=\\sum\_\{j\}\\omega \_\{j\}x\_\{ij\} yi^=j∑ωjxij  
       这里的预测y可以有不同的解释，比如我们可以用它来作为回归目标的输出，或者进行sigmoid 变换得到概率，或者作为排序的指标等。 而一个线性模型根据y的解释不同（以及设计对应的目标函数）用到回归，分类或排序等场景。

#### 2、参数 ####

参数是指我们学习到的东西，在线性模型中，参数是指我们的线性系数 ω \\omega ω。

#### 3、目标函数 ####

模型和参数指定了在给定输入的情况下如何进行预测，但是没有告诉我们如何去寻找一个比较好的参数。目标函数就是为了确定最优参数而产生的，目标函数主要由损失函数和正则项两部分组成。**损失函数** L ( θ ) L\\left ( \\theta \\right ) L(θ)用于描述模型拟合数据的程度，**正则项** Ω ( θ ) \\Omega \\left ( \\theta \\right ) Ω(θ)用于控制模型的复杂度。  
 O b j ( θ ) = L ( θ ) + Ω ( θ ) Obj\\left ( \\theta \\right )=L\\left ( \\theta \\right )+\\Omega \\left ( \\theta \\right ) Obj(θ)=L(θ)\+Ω(θ)

## 二、GBDT ##

#### 1、GBDT简介 ####

DT（Decision Tree）是决策树，GB（Gradient Boosting）是一种学习策略，GBDT的含义就是用Gradient Boosting的策略训练出来的DT模型。GBDT是一种用于回归、分类和排序任务的机器学习技术，属于Boosting算法族的一部分。Boosting是一族可将弱学习器提升为强学习器的算法，属于集成学习（ensemble learning）的范畴。Boosting方法基于以下思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断要好。  
       GBDT是一个基于迭代累加的决策树算法，它通过构造一组弱的学习器（树），并把多棵决策树的结果累加起来作为最终的预测输出。  
       树模型也分为决策树和回归树，决策树常用来分类问题，回归树常用来预测问题。决策树常用于分类标签值，比如用户性别、网页是否是垃圾页面、用户是不是作弊；而回归树常用于预测真实数值，比如用户的年龄、用户点击的概率、网页相关程度等等。由于GBDT的核心在于累加所有树的结果作为最终结果，而分类结果对于预测分类并不是这么的容易叠加，所以GBDT中的树都是回归树（其实回归树也能用来做分类）。同样的我们经常会把RandomForest的思想引入到GBDT里面来，即每棵树建树的时候我们会对特征和样本同时进行采样，然后对采样的样本和特征进行建树。

#### 2、GBDT思路 ####

在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是 f t − 1 ( x ) f\_\{t-1\}\\left ( x \\right ) ft−1(x), 损失函数是 L ( y , f t − 1 ( x ) ) L\\left (y, f\_\{t-1\}\\left ( x \\right ) \\right ) L(y,ft−1(x)), 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器 h t ( x ) h\_\{t\}\\left ( x \\right ) ht(x)，让本轮的损失函数 L ( y , f t ( x ) ) = L ( y , f t − 1 ( x ) + h t ( x ) ) L\\left (y, f\_\{t\}\\left ( x \\right ) \\right )=L\\left (y, f\_\{t-1\}\\left ( x \\right ) +h\_\{t\}\\left ( x \\right )\\right) L(y,ft(x))=L(y,ft−1(x)\+ht(x))最小。也即是本轮迭代找到决策树，要让样本的损失尽量变得更小。  
       GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。

#### 3、GBDT的负梯度拟合 ####

上一节我们介绍了GBDT的思路，接下来我们解决损失函数拟合方法的问题。针对这个问题，大牛Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。第t轮的第i个样本的损失函数的负梯度表示为：  
 r t i = − \[ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) \] f ( x ) = f t − 1 ( x ) r\_\{ti\}=-\\left \[ \\frac\{\\partial L\\left (y\_\{i\}, f\\left ( x\_\{i\} \\right ) \\right )\}\{\\partial f\\left ( x\_\{i\} \\right )\} \\right \]\_\{f\\left ( x \\right )=f\_\{t-1\}\\left ( x \\right )\} rti=−\[∂f(xi)∂L(yi,f(xi))\]f(x)=ft−1(x)  
       利用 ( x i , r t i ) ( i = 1 , 2 , . . m ) (x\_\{i\},r\_\{ti\})(i=1,2,..m) (xi,rti)(i=1,2,..m)，我们可以拟合一颗CART回归树，得到了第t棵回归树，其对应的叶节点区域是 R t j , j = 1 , 2... J R\_\{tj\},j=1,2 ... J Rtj,j=1,2...J，其中J为第t棵树的叶子节点的个数。  
       针对每一个叶子节点里的样本，我们求出使损失函数最小，也就是拟合叶子节点最好的的输出值 c t j c\_\{tj\} ctj如下：  
 c t j = a r g m i n c ∑ x i ∈ R t j L ( y i , f t − 1 ( x i ) + c ) c\_\{tj\}=argmin\_\{c\}\\sum\_\{x\_\{i\}\\in R\_\{tj\}\} L(y\_\{i\}, f\_\{t-1\}( x\_\{i\} )+c) ctj=argmincxi∈Rtj∑L(yi,ft−1(xi)\+c)  
       这样我们就得到了本轮的决策树拟合函数如下，其中 I ( x ∈ R t j ) I(x\\in R\_\{tj\}) I(x∈Rtj)表示如果 x ∈ R t j x\\in R\_\{tj\} x∈Rtj，则 I ( x ∈ R t j ) = 1 I(x\\in R\_\{tj\})=1 I(x∈Rtj)=1，否则等于0：  
 h t ( x ) = ∑ j = 1 J c t j I ( x ∈ R t j ) h\_\{t\}(x)=\\sum\_\{j=1\}^\{J\}c\_\{tj\}I(x\\in R\_\{tj\}) ht(x)=j=1∑JctjI(x∈Rtj)  
       从而本轮最终得到的强学习器的表达式如下：  
 f t ( x ) = f t − 1 ( x ) + h t ( x ) = f t − 1 ( x ) + ∑ j = 1 J c t j I ( x ∈ R t j ) f\_\{t\}(x)=f\_\{t-1\}(x)+h\_\{t\}(x)\\\\=f\_\{t-1\}(x)+\\sum\_\{j=1\}^\{J\}c\_\{tj\}I(x\\in R\_\{tj\}) ft(x)=ft−1(x)\+ht(x)=ft−1(x)\+j=1∑JctjI(x∈Rtj)  
       通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。

#### 4、GBDT回归算法 ####

**输入**：训练集样本 T = ( x 1 , y 1 ) , ( x 2 , y 2 ) . . . ( x m , y m ) T=\{(x\_\{1\},y\_\{1\}),(x\_\{2\},y\_\{2\})...(x\_\{m\},y\_\{m\})\} T=(x1,y1),(x2,y2)...(xm,ym)， 最大迭代次数N, 损失函数L。  
**输出**：强学习器f(x)  
**过程**：  
（1） 初始化弱学习器：  
　　　　 f 0 ( x ) = a r g m i n c ∑ i = 1 m L ( y i , c ) f\_\{0\}(x)=argmin\_\{c\}\\sum\_\{i=1\}^\{m\} L(y\_\{i\},c) f0(x)=argminci=1∑mL(yi,c)  
（2）对迭代轮数 t = 1 , 2... N t=1,2 ... N t=1,2...N有：  
1）对样本 i = 1 , 2... m i=1,2 ... m i=1,2...m，计算负梯度  
 r t i = − \[ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) \] f ( x ) = f t − 1 ( x ) r\_\{ti\}=-\\left \[ \\frac\{\\partial L\\left (y\_\{i\}, f\\left ( x\_\{i\} \\right ) \\right )\}\{\\partial f\\left ( x\_\{i\} \\right )\} \\right \]\_\{f\\left ( x \\right )=f\_\{t-1\}\\left ( x \\right )\} rti=−\[∂f(xi)∂L(yi,f(xi))\]f(x)=ft−1(x)  
2）利用 ( x i , r t i ) ( i = 1 , 2 , . . m ) (x\_\{i\},r\_\{ti\})(i=1,2,..m) (xi,rti)(i=1,2,..m)，我们可以拟合一颗CART回归树，得到了第t棵回归树，其对应的叶节点区域是 R t j , j = 1 , 2... J R\_\{tj\},j=1,2 ... J Rtj,j=1,2...J，其中J为第t棵树的叶子节点的个数。  
3）对叶子区域 j = 1 , 2... J j =1,2 ... J j=1,2...J，计算最佳拟合值  
 c t j = a r g m i n c ∑ x i ∈ R t j L ( y i , f t − 1 ( x i ) + c ) c\_\{tj\}=argmin\_\{c\}\\sum\_\{x\_\{i\}\\in R\_\{tj\}\} L(y\_\{i\}, f\_\{t-1\}( x\_\{i\} )+c) ctj=argmincxi∈Rtj∑L(yi,ft−1(xi)\+c)  
4）更新强学习器  
 f t ( x ) = f t − 1 ( x ) + ∑ j = 1 J c t j I ( x ∈ R t j ) f\_\{t\}(x)=f\_\{t-1\}(x)+\\sum\_\{j=1\}^\{J\}c\_\{tj\}I(x\\in R\_\{tj\}) ft(x)=ft−1(x)\+j=1∑JctjI(x∈Rtj)  
（4）得到强学习器 f ( x ) f(x) f(x)的表达式  
 f ( x ) = f T ( x ) = f 0 ( x ) + ∑ t = 1 T ∑ j = 1 J c t j I ( x ∈ R t j ) f(x)=f\_\{T\}(x)=f\_\{0\}(x)+\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{J\}c\_\{tj\}I(x\\in R\_\{tj\}) f(x)=fT(x)=f0(x)\+t=1∑Tj=1∑JctjI(x∈Rtj)

#### 5、GBDT分类算法 ####

GBDT的分类算法从思想上和GBDT的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。  
       为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法；另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论用对数似然损失函数的GBDT分类。而对于对数似然损失函数，我们又有二元分类和多元分类的区别。

###### 5.1、二元GBDT分类算法 ######

对于二元GBDT分类算法，如果用类似于逻辑回归的对数似然损失函数，则损失函数为：  
　 L ( y , f ( x ) ) = l o g ( 1 + e x p ( − y f ( x ) ) ) L(y,f(x))=log(1+exp(-yf(x))) L(y,f(x))=log(1\+exp(−yf(x)))  
       其中 y ∈ \{ − 1 , + 1 \} y\\in \\left \\\{ -1,+1 \\right \\\} y∈\{ −1,\+1\}。则此时的负梯度误差为：  
 r t i = − \[ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) \] f ( x ) = f t − 1 ( x ) = y i 1 + e x p ( y i f ( x i ) ) r\_\{ti\}=-\\left \[ \\frac\{\\partial L\\left (y\_\{i\}, f\\left ( x\_\{i\} \\right ) \\right )\}\{\\partial f\\left ( x\_\{i\} \\right )\} \\right \]\_\{f\\left ( x \\right )=f\_\{t-1\}\\left ( x \\right )\}=\\frac\{y\_\{i\}\}\{1+exp(y\_\{i\}f(x\_\{i\}))\} rti=−\[∂f(xi)∂L(yi,f(xi))\]f(x)=ft−1(x)=1\+exp(yif(xi))yi  
       对于生成的决策树，我们各个叶子节点的最佳负梯度拟合值为：  
 c t j = a r g m i n c ∑ x i ∈ R t j l o g ( 1 + e x p ( − y i ( f t − 1 ( x i ) + c ) ) ) c\_\{tj\}=argmin\_\{c\}\\sum\_\{x\_\{i\}\\in R\_\{tj\}\} log(1+exp(-y\_\{i\}(f\_\{t-1\}(x\_\{i\})+c))) ctj=argmincxi∈Rtj∑log(1\+exp(−yi(ft−1(xi)\+c)))  
       由于上式比较难优化，我们一般使用近似值代替：  
 c t j = ∑ x i ∈ R t j r t i ∑ x i ∈ R t j ∣ r t i ∣ ( 1 − ∣ r t i ∣ ) c\_\{tj\}= \\frac\{\\sum\_\{x\_\{i\}\\in R\_\{tj\}\}r\_\{ti\}\}\{\\sum\_\{x\_\{i\}\\in R\_\{tj\}\} \\left | r\_\{ti\} \\right |(1-\\left | r\_\{ti\} \\right |)\} ctj=∑xi∈Rtj∣rti∣(1−∣rti∣)∑xi∈Rtjrti  
       除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，二元GBDT分类和GBDT回归算法过程相同。

###### 5.2、多元GBDT分类算法 ######

多元GBDT要比二元GBDT复杂一些，对应的是多元逻辑回归和二元逻辑回归的复杂度差别。假设类别数为K，则此时我们的对数似然损失函数为：  
 L ( y , f ( x ) ) = − ∑ k = 1 K y k l o g ( p k ( x ) ) L(y,f(x))=-\\sum\_\{k=1\}^\{K\}y\_\{k\}log(p\_\{k\}(x)) L(y,f(x))=−k=1∑Kyklog(pk(x))  
       其中如果样本输出类别为k，则 y k = 1 y\_\{k\}=1 yk=1。第k类的概率 p k ( x ) p\_\{k\}(x) pk(x)的表达式为：  
 p k ( x ) = e x p ( f k ( x ) ) ∑ l = 1 K e x p ( f l ( x ) ) p\_\{k\}(x)=\\frac\{exp(f\_\{k\}(x))\}\{\\sum\_\{l=1\}^\{K\}exp(f\_\{l\}(x))\} pk(x)=∑l=1Kexp(fl(x))exp(fk(x))  
       集合上两式，我们可以计算出第t轮的第i个样本对应类别l的负梯度误差为:  
 r t i l = − \[ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) \] f k ( x ) = f l , t − 1 ( x ) = y i l − p l , t − 1 ( x i ) r\_\{til\}=-\\left \[ \\frac\{\\partial L\\left (y\_\{i\}, f\\left ( x\_\{i\} \\right ) \\right )\}\{\\partial f\\left ( x\_\{i\} \\right )\} \\right \]\_\{f\_\{k\}\\left ( x \\right )=f\_\{l,t-1\}\\left ( x \\right )\}=y\_\{il\}-p\_\{l,t-1\}(x\_\{i\}) rtil=−\[∂f(xi)∂L(yi,f(xi))\]fk(x)=fl,t−1(x)=yil−pl,t−1(xi)  
       观察上式可以看出，其实这里的误差就是样本i对应类别l的真实概率和t−1轮预测概率的差值。  
       对于生成的决策树，我们各个叶子节点的最佳负梯度拟合值为  
 c t j l = a r g m i n c j l ∑ i = 0 m ∑ k = 1 K L ( y k , f t − 1 , l ( x ) + ∑ j = 0 J c j l I ( x i ∈ R t j l ) ) c\_\{tjl\}=argmin\_\{c\_\{jl\}\}\\sum\_\{i=0\}^\{m\}\\sum\_\{k=1\}^\{K\}L(y\_\{k\}, f\_\{t-1,l\}(x)+\\sum\_\{j=0\}^\{J\}c\_\{jl\}I(x\_\{i\}\\in R\_\{tjl\})) ctjl=argmincjli=0∑mk=1∑KL(yk,ft−1,l(x)\+j=0∑JcjlI(xi∈Rtjl))  
       由于上式比较难优化，我们一般使用近似值代替  
 c t j l = K − 1 K ∑ x i ∈ R t j l r t i l ∑ x i ∈ R t j l ∣ r t i l ∣ ( 1 − ∣ r t i l ∣ ) c\_\{tjl\}= \\frac\{K-1\}\{K\}\\frac\{\\sum\_\{x\_\{i\}\\in R\_\{tjl\}\}r\_\{til\}\}\{\\sum\_\{x\_\{i\}\\in R\_\{tjl\}\} \\left | r\_\{til\} \\right |(1-\\left | r\_\{til\} \\right |)\} ctjl=KK−1∑xi∈Rtjl∣rtil∣(1−∣rtil∣)∑xi∈Rtjlrtil  
       除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，多元GBDT分类和二元GBDT分类以及GBDT回归算法过程相同。

#### 6、GBDT优缺点 ####

GBDT主要**优点**：  
（1）可以灵活处理各种类型的数据，包括连续值和离散值。  
（2）在相对少的调参时间情况下，预测的准确率也可以比较高。这个是相对SVM来说的。  
（3）使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。  
GBDT的主要**缺点**：  
（1）由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

参考：[梯度提升树(GBDT)原理小结][GBDT]

[GBDT]: https://www.cnblogs.com/pinard/p/6140514.html#!comments