GBDT 梯度提升树的基本原理

什么是GBDT?

GBDT (Gradient Boosting Decision Tree) 是一种基于boosting集成学习(ensemble method)的算法,但相对于传统的Adaboost又有很大不同。在Adaboost,我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重。尽管GBDT也是迭代并且使用了前向分布算法,但是弱学习器限定了只能使用CART回归树模型,同时迭代思路和Adaboost也有所不同。GBDT选用的弱分类器一般是低方差高偏差,因为Boosting主要关注降低偏差,因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。GBDT的训练过程如下[1]

Fig 1. GBDT 的训练过程

Boost

Boost是一个加法模型,它是由若干个基函数及其权值乘积之和的累加。

Gradient Boosting

GBDT把所有树的结论进行累加,从而获得最终结论,所以每棵树的结论并不是年龄本身,而是年龄的一个累加量。GBDT的核心就在于,每一棵树学习的是之前所有树结论和的残差,这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁,但第一棵树的预测年龄是12岁,差了6岁,即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习,如果第二棵树真的能把A分到6岁的叶子节点,那累加两棵树的结论就是A的真实年龄;如果第二棵树的结论是5岁,则A仍然存在1岁的残差,第三棵树里A的年龄就变成1岁,继续学。这就是Gradient Boosting在GBDT中的意义[2]

根据上面那个简单的例子,我们知道假设损失函数为平方损失(square loss)时,我们使用残差来进行下一轮的训练,即GBDT算法的每一步在生成决策树时只需要拟合前面的模型的残差,从而使得损失函数最小。那如何使损失函数最小呢?Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值,进而拟合一个CART回归树,这就是GBDT的负梯度拟合。损失函数的负梯度在当前模型的值为:

$$ -[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]{f(x)=f{m-1}(x)} \tag1 $$

Boosting的最大好处在于,每一步的残差计算其实变相地增大了分错样本的权重,而已经分对的样本则都趋向于0。因为对于已经分对的样本,其残差为0,在下一轮中几乎不起作用。

GBDT算法

知道了怎么解决损失函数拟合的问题,即GBDT的负梯度拟合之后,需要使用这些负梯度进行训练。假设$r_{mi}$表示第$m$轮的第$i$个样本的损失函数的负梯度:

$$ r_{mi} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = f_{m-1} (x)}\tag2 $$

利用$(x_i,r_{mi})\quad(i=1,2,..n)$,我们可以拟合第$m$棵CART回归树,其对应的叶节点区域$R_{mj}, j =1,2,..., J$,其中$J$为叶子节点的个数。

针对每个叶子节点里的样本,我们求出损失函数最小,也就是拟合叶子节点最好的的输出值$c_{mj}$如下:

$$ c_{mj} = \underbrace{arg; min}_{c}\sum\limits_{x_i \in R_{mj}} L(y_i,f_{m-1}(x_i) +c)\tag3 $$

从而可以获得本轮的CART回归树的拟合函数:

$$ h_m(x) = \sum\limits_{j=1}^{J}c_{mj}I(x \in R_{mj})\tag4 $$

最后获得强学习器的表达式:

$$ f_{m}(x) = f_{m-1}(x) + \sum\limits_{j=1}^{J}c_{mj}I(x \in R_{mj})\tag5 $$

请结合上面的例子,理解每一轮更新强学习器都需要加上前面所有轮的输出!

GBDT回归算法

Freidman提出的梯度提升(Gradient Boosting)算法:利用最速下降的近似方法,即利用损失函数的负梯度在当前模型的值,作为回归问题中提升树算法的残差的近似值,拟合一个回归树。算法如下[3]

算法步骤解释:

1、初始化,估计使损失函数极小化的常数值,它是只有一个根节点的树,即$\gamma$是一个常数值;

2、对于每轮CART回归树:

(a)计算损失函数的负梯度在当前模型的值,将它作为残差的估计
(b)估计回归树叶节点区域,以拟合残差的近似值
(c)利用线性搜索估计叶节点区域的值,使损失函数极小化
(d)更新回归树

3、得到输出的最终模型 $f(x)$。

GBDT分类算法

这里我们再看看GBDT分类算法,GBDT的分类算法从思想上和GBDT的回归算法没有区别,但是由于样本输出不是连续的值,而是离散的类别,导致我们无法直接从输出类别去拟合类别输出的误差[4]

为了解决这个问题,主要有两个方法,一个是用指数损失函数,此时GBDT退化为AdaBoost算法。另一种方法是用类似于逻辑回归的对数似然损失函数。也就是说,我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论用对数似然损失函数的GBDT分类。而对于对数似然损失函数,我们又有二元分类和多元分类的区别。

二元GBDT分类算法

对于二元GBDT,如果用类似于逻辑回归的对数似然损失函数,则损失函数为:

$$ (y, f(x)) = log(1+ exp(-yf(x)))\tag6 $$

其中$y \in{-1, +1}$。此时的负梯度误差为:

$$ r_{mi} = -\bigg[\frac{\partial L(y, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = f_{m-1};; (x)} = y_i/(1+exp(y_if(x_i)))\tag7 $$

对于生成的CART回归树,我们各个叶子节点的最佳残差拟合值为:

$$ c_{mj} = \underbrace{arg; min}_{c}\sum\limits_{x_i \in R_{mj}} log(1+exp(-y_i(f_{m-1}(x_i) +c)))\tag8 $$

由于上面的式子比较难优化,一般使用近似值代替:

$$ c_{mj} = \sum\limits_{x_i \in R_{mj}}r_{mi}\bigg / \sum\limits_{x_i \in R_{mj}}|r_{mi}|(1-|r_{mi}|)\tag9 $$

除了负梯度计算和叶子节点的最佳残差拟合的线性搜索,二元GBDT分类和GBDT回归算法过程相同。

多元GBDT分类算法

多元GBDT要比二元GBDT复杂一些,对应的是多元逻辑回归和二元逻辑回归的复杂度差别。假设类别数为K,则此时我们的对数似然损失函数为:

$$ L(y, f(x)) = - \sum\limits_{k=1}^{K}y_klog;p_k(x)\tag{10} $$

其中如果样本输出类别为$k$,则$y_{k}=1$。第$k$类的概率$p_{k}(x)$的表达式为:

$$ p_k(x) = exp(f_k(x)) \bigg / \sum\limits_{l=1}^{K} exp(f_l(x))\tag{11} $$

集合上两式,我们可以计算出第$t$轮的第$i$个样本对应类别$l$的负梯度误差为:

$$ r_{mil} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f_k(x) = f_{l, m-1} (x)} = y_{il} - p_{l, m-1}(x_i)\tag{12} $$

观察上式可以看出,其实这里的误差就是样本$i$对应类别$l$的真实概率和$m−1$轮预测概率的差值。

对于生成的决策树,我们各个叶子节点的最佳残差拟合值为:

$$ c_{mjl} = \underbrace{arg; min}_{c_{jl}}\sum\limits_{i=0}^{m}\sum\limits_{k=1}^{K} L(y_k, f_{m-1, l}(x) + \sum\limits_{j=0}^{J}c_{jl} I(x_i \in R_{mj}))\tag{13} $$

由于上式比较难优化,我们一般使用近似值代替:

$$ c_{mjl} = \frac{K-1}{K} \frac{\sum\limits_{x_i \in R_{mjl}}r_{mil}}{\sum\limits_{x_i \in R_{mil}}|r_{mil}|(1-|r_{mil}|)}\tag{14} $$

除了负梯度计算和叶子节点的最佳残差拟合的线性搜索,多元GBDT分类和二元GBDT分类以及GBDT回归算法过程相同。


  1. 机器学习算法GBDT 

  2. GBDT之原理、所解决的问题、应用场景 

  3. The Elements of Statistical Learning 

  4. 梯度提升树 (GBDT) 原理小结 

updatedupdated2021-07-192021-07-19