GBDT&Xgboost

提升方法

在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,他通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,特高分类性能

对于提升方法,有两个问题需要回答:一是在每一轮如何改变训练数据的权值或概率分布;而是如何将弱分类器组合成一个强分类器。

​ -《统计学习方法》

Adaboost

$Adaboost$算法的特点是通过迭代每次学习一个基本分类器,每次迭代中,提高那些被前一轮分类器错误分类数据的权值,而降低那些被正确分类的数据的权值。最后$Adaboost$将基本分类器的线性组合作为强分类器,其中给分类误差率小的基本分类器大的权值,给分类误差率大的基本分类器小的权值

提升树

提升树正是一种前向分步的加法模型,但是其基分类器是树模型(二叉树),分为二叉分类树和二叉回归树,提升树往往在实践中表现非常好。提升树的模型如下:

其中$T(x;\Theta)$表示决策树,$M$为树的个数,$\Theta$表示树的参数。

首先确定初始提升树$f_0(x)=0$,第$m$步的模型是

其中,$f_{m-1}(x)$为当前模型,通过经验风险极小化确定下一棵决策树的参数$\Theta_m$,第$m$步的模型是

GBDT

为什么拟合负梯度

为什么要拟合负梯度(注意这里的梯度是对$\hat y_i^{t-1}$求导)呢?

跟梯度下降类似,我们不断减去$\partial f(x)\over \partial x$可以得到$\min_x f(x)$,同理不断减去$\partial L\over\partial \hat y^{t-1}_i$就能得到$\min_{\hat y}L(\hat y)$。所以其实GBDT就是在函数空间的梯度下降。

传统GBDT算法

算法流程:

乍一看,GBDT算法跟梯度下降算法很像,其实GBDT就是在函数空间的梯度下降,我们不断减去$\partial f(x)\over \partial x$可以得到$\min_x f(x)$,同理不断减去$\partial L\over\partial F_{K-1}$就能得到$\min_FL(F)$,注意这里是对$F_{K-1}$求导。

基于残差的GBDT

推导

$GBDT$全称$Gradient Boosting Decision Tree$, 其中$gradient$被称为梯度,更一般的理解,可以认为是一阶导,这里残差与梯度是什么关系呢。我们看平方损失函数${1\over 2}\sum^n_0(y_i-F(x_i))^2$,这个算是函数主要是针对回归类型的。

$ {1\over 2}\sum^n_{i=1}(y_i-F(x_i))^2$

$= {1\over 2}\sum^n_{i=1}(y_i-\hat y_i^t)^2$

$= {1\over 2}\sum^n_{i=1}(y_i-\hat y_i^{t-1}-f_t(x_i))^2$

令其对$\hat y_i^{t-1}$求导为0 得:

则:

所以基于残差的gbdt是一种特殊的gbdt模型,它的损失函数是平方损失函数,只能处理回归类的问题。

为什么基于残差的gbdt不是一个好的选择

首先基于残差的gbdt只能处理回归类的问题,不能处理分类问题,这是损失函数所限制的,所以更一般化的gbdt是基于梯度的算法,这也就意味着只要我给出的损失函数是可导的,那么我就能用gbdt的思想去解决问题。具体解决的问题就不会仅仅限于回归了。

另外,基于残差的gbdt在解决回归问题上也不算是一个好的选择,一个比较明显的缺点就是对异常值过于敏感。

Boosting的加法模型

gbdt模型可以认为是是由k个基模型组成的一个加法运算式:

其中F是指所有基模型组成的函数空,以回归任务为例,回归树可以看作为一个把特征向量映射为某个score的函数。该模型的参数为:$\Theta=\{f_1,f_2,…,f_K\}$。于一般的机器学习算法不同的是,加法模型不是学习d维空间中的权重,而是直接学习函数(决策树)集合

那么一般化的损失函数是预测值$\hat y$与 真实值$y$之间的关系,如我们前面的平方损失函数,那么对于n个样本来说,则可以写成:

更一般的,我们知道一个好的模型,在偏差和方差上有一个较好的平衡,而算法的损失函数正是代表了模型的偏差面,最小化损失函数,就相当于最小化模型的偏差,但同时我们也需要兼顾模型的方差,所以目标函数还包括抑制模型复杂度的正则项,因此目标函数可以写成:

其中$\Omega$代表了基模型的复杂度,若基模型是书模型,则树的深度、叶子节点数等指标可以反映树的复杂度。

对于Boosting来说,它采用的是前向分布算法,即从前往后,逐渐建立基模型来优化逼近目标函数,具体过程如下:

那么,在每一步,如何学习一个新的模型呢,答案的关键还是在于gbdt的目标函数上,即新模型的加入总是以优化目标函数为目的的。

我们一第$t$步的模型拟合为例,在这一步,模型对第$i$个样本$x_i$的预测为:

其中$f_t(x_i)$就是我们这次需要加入的新模型,即需要拟合的模型,此时,目标函数就可以写成:

即此时最优化目标函数,就相当于求得了$f_t(x_i)$

$Xgboost$

$Xgboost$的目标函数

泰勒公式:设$n$是一个正整数,如果定义在一个包含$a$的区间上的函数$f$在$a$点处$n+1$次可导,那么对于这个区间上的任意$x$都有:$f(x)=\sum^N_{n=0}{f^{(n)}(a)\over n!}(x-a)^n+R_n(x)$,其中的多项式称为函数在$a$处的泰勒展开式,$R_n(x)$是泰勒公式的余项且是$(x-a)^n$的高阶无穷小。

​ ——维基百科

二阶泰勒展开:

那么在等式$(1)$中,我们把$\hat y^{t-1}_i$看成是等式$(2)$中的$x$,$f_t(x_i)$看成是$\Delta x$,因此等式$(1)$可以写成:

其中$g_i$和$h_i$分别为$l(y_i, \hat y_i^{t-1})$关于$\hat y_i^{t-1}$的一阶导和二阶导。我们一平方损失函数为例$\sum^n_{i=1}(y_i-(\hat y^{t-1}_i+f_t(x_i) ) )^2$,则$g_i=\partial _{\hat y^{t-1}}(\hat y^{t-1}-y_i)^2=2(\hat y^{t-1}-y_i)$,$h_i=\partial^2_{\hat y^{t-1}}(\hat y^{t-1}-y_i)^2=2$。

由于在第$t$步$\hat y^{t-1}_i$其实是一个已知的值,所以$l(y_i, \hat y^{t-1}_i)$是一个常数,其对函数优化不会产生影响,因此,等式$(3)$可以写成:

所以我们只需要求出前一步损失函数的一阶和二阶导的值(由于前一步的$\hat y^{t-1}$是已知的,所以这两个值就是常数)带入等式$(4)$,然后优化目标函数,就可得到每一步的$f(x)$,最后根据加法模型的到一个整体的模型。

如何用决策树来表示上一步的目标函数

假设我们$boosting$的基模型用决策树来实现,则一颗生成好的决策树,即结构确定,也就是说树的叶子结点其实是确定了的。假设这棵树的叶子节点有$T$片叶子,而每片叶子对应的值$w\in R^T$。熟悉决策树的同学应该清楚,每一片叶子结点中样本的预测值都会是一样的,在分类问题中,是某一类;在回归问题中,是某一个值,那么肯定存在这样一个函数$q:R^d\rightarrow \{1,2,…,T\}$,及将$f_t(x)$中的每个样本映射到每一个叶子节点上,当然$f_t(x)$和$q$我们都是不知道的,但我们也不关心,这里只是说明一下决策树表达数据结构的方法是怎么样的,不理解也没有问题。

那么$f_t(x)$就可以转成$w_{q(x)}$,这里的$q(x)$代表了每个样本在哪个叶子节点上,而$w_{q(x)}$则代表了哪个叶子结点去什么$w$值,所以$w_{q(x)}$就代表了每个样本的取值$w$(即预测值)。

如果决策树的复杂度可以由正则项来定义$\Omega(f_t)=\gamma T+{1\over2}\lambda\sum_{j=1}^Tw_j^2$ (这是xgb的正则项),即决策树模型的复杂度由生成的树的叶子节点数量和叶子节点对应的值向量的$L2$范数决定。

我们假设$I_j=\{i|q(x_i)=j\}$为第$j$个叶子节点的样本集合,则等式$(4)$根据上面的一些变换可以写成:

即我们之前样本的集合,现在都改写成了叶子结点的集合,由于一个叶子结点有多个样本存在,因此才有了$\sum_{i\in I_j}g_i$和$\sum_{i\in I_j}h_i$这两项。

定义$G_j=\sum_{i\in I_j}g_i,H_j=\sum_{i\in I_j}h_i$,则等式$(5)$可以写成:

如果树结构是固定的,即$q$是确定的,或者说我们已经知道了每个叶子结点有哪些样本,所以$G_j$和$H_j$是确定的,但$w$不确定($w$其实就是我们要预测的值),那么令目标函数一阶导数为$0$,则可以求得叶子结点$j$对应的值:

目标函数的值可以化简为:

如何求树的结构(单线程版本)

那么对于单棵决策树,一种理想的优化状态就是枚举所有可能的树结构,因此过程如下:

  1. 首先枚举所有可能的树结构;
  2. 计算每种树结构下的目标函数值,即等式$(7)$的值;
  3. 取目标函数最小(大)值为最佳的数结构,根据等式6求得每个叶子节点的$w$取值,即样本的预测值。

然而,可能的树结构数量是无穷的,所以实际上我们不可能枚举所有可能的树结构。通常情况下,我们采用贪心策略来生成决策树的每个节点。

  1. 从深度为0的树开始,对每个叶节点枚举所有的可用特征
  2. 针对每个特征,把属于该节点的训练样本根据该特征值升序排列,通过线性扫描的方式来决定该特征的最佳分裂点,并记录该特征的最大收益(采用最佳分裂点时的收益)
  3. 选择收益最大的特征作为分裂特征,用该特征的最佳分裂点作为分裂位置,把该节点生长出左右两个新的叶节点,并为每个新节点关联对应的样本集
  4. 回到第1步,递归执行到满足特定条件为止

那么如何计算上面的收益呢,很简单,仍然紧扣目标函数就可以了。假设我们在某一节点上二分裂成两个节点,分别是左$(L)$右$(R)$,则分列前的目标函数是$-{1\over 2}[{(G_L+G_R)^2\over H_L+H_R+\lambda}] $,分裂后则是$-{1\over 2}[{G_L^2\over H_L+\lambda}+{G_R^2\over H_R+\lambda}]+2\lambda$,则对于目标函数来说,分裂后的收益是(这里假设是最小化目标函数,所以用分列前减去分裂后):

等式$(8)$计算出来的收益,也是作为变量重要度输出的重要依据。

这时,就有两种后续。一种是当最好的分割的情况下,GainGain为负时就停止树的生长,这样的话效率会比较高也简单,但是这样就放弃了未来可能会有更好的情况。另外一种就是一直分割到最大深度,然后进行修剪,递归得把划分叶子得到的Gain为负的收回。一般来说,后一种要好一些,于是我们采用后一种,完整的算法如下(没有写修剪)

建树总结

所以gbdt的算法可以总结为:

  1. 算法在拟合的每一步都新生成一颗决策树;
  2. 在拟合这棵树之前,需要计算损失函数在每个样本上的一阶导和二阶导,即$g_i$和$h_i$;
  3. 通过上面的贪心策略生成一棵树,计算每个叶子节点的$G_j$和$H_j$,利用等式$(6)$计算预测值$w$;
  4. 把新生成的决策树$f_t(x)$加入$\hat y^t_i=\hat y^{t-1}_i+\epsilon f_t(x_i)$,其中$\epsilon$为学习率,主要为了抑制模型的过拟合

算法复杂度

  1. 按照某特征里的值进行排序,复杂度是$O(nlog n)$
      2. 扫描一遍该特征所有值得到最优分割点,因为该层(兄弟统一考虑)一共有$n$个样本,所以复杂度是$O(n)$
      3. 一共有$d$个特征,所以对于一层的操作,复杂度是$O(d(nlog n+n))=O(d nlog n)$
      4. 该树的深度为$k$。所以总复杂度是$O(k d nlog n)$

近似算法

近似算法思想

枚举特征所有可能分割在计算上要求很高,为有效做到这一点,算法必须根据特征值对数据预先排序。贪心算法很强大,然而当数据量过大,无法装入整个内存中时,会非常不高效。

树模型对特征取值范围不敏感,只对顺序敏感。近似算法首先根据特征分布的百分位提出候选分裂点,然后将连续特征映射到这些候选分割点形成的bucket中,聚合统计数据,并基于聚合数据找到最佳解决方案。近似算法通常使用加权百分位树选择候选分割点,使特征按照权重期望均匀分布在候选分割点之间。

我们用$D_k=\{(x_{1k},h_1),(x_{2k},h_2),(x_{3k},h_3),…,(x_{nk},h_n)\}$代表每个样本的第$k$个特征和其对应的二阶梯度所组成的集合。那么我们就可以用百分比来定义这个排名函数$r_k:\mathbb{R}\rightarrow[0,1]$:

上式表示的是该特征的值小于z的样本所占总样本的比例。于是我们就能用下面这个不等式来寻找分割点$\{s_{k1},s_{k2},s_{k3},…,s_{kl}\}$

上式中$\epsilon$表示的是一个近似比例,或者说一个扫描步进。从最小值开始,每次增加$\epsilon(\max_ix_{ik}-\min_ix_{ik})$作为分割点。然后再这些分割点中选择一个 最大的分数作为最后的分割点。并且这里每个数据点被$h_i$加权,这里等式$(4)$可以写成如下形式:

可以把$h_i$看做方差损失函数的权值。

两种近似算法

很明显这里有两种分割思路:

  • 全局分割:建树前将所有特征分割完
  • 局部分割:每次分裂节点后重新分割特征

全局方法比局部方法需要更少的分割步骤,但是全局方法通常需要更多的候选点才能保证效果,因为候选在每次节点分裂之后不会被重新完善,局部分割在每次分裂节点后被重新完善,并且有可能适合更深的树。

并行化

此部分引自知乎答主杨军

在$XGBoost$的实现中,对算法进行了模块化的拆解,几个重要的部分分别是:

​ I. $ObjFunction$:对应于不同的$Loss Function$,可以完成一阶和二阶导数的计算。

​ II. $GradientBooster$:用于管理$Boost$方法生成的$Model$,注意,这里的$Booster Model$既可以对应于线性$Booster Model$,也可以对应于$Tree Booster Model$。

​ III. $Updater$:用于建树,根据具体的建树策略不同,也会有多种$Updater$。比如,在$XGBoost$里为了性能优化,既提供了单机多线程并行加速,也支持多机分布式加速。也就提供了若干种不同的并行建树的$updater$实现,按并行策略的不同,包括:
I). $inter-feature exact parallelism $(特征级精确并行)
II). $inter-feature approximate parallelism$(特征级近似并行,基于特征分bin计算,减少了枚举所有特征分裂点的开销)
III). $intra-feature parallelism$ (特征内并行)
IV). $inter-node parallelism$ (多机并行)

处理缺失值

此部分引自知乎答主微调

$xgboost$处理缺失值的方法和其他树模型不同。根据作者$Tianqi Chen$在论文中章节3.4的介绍,$xgboost$把缺失值当做稀疏矩阵来对待,本身的在节点分裂时不考虑的缺失值的数值。通过这个工程$trick$来减少了为稀疏离散特征寻找$split point$的时间开销。缺失值数据会被分到左子树和右子树分别计算损失,选择较优的那一个。如果训练中没有数据缺失,预测时出现了数据缺失,那么默认被分类到右子树。具体的介绍可以参考链接1链接2

正则化

下面介绍GBDT中抵抗过拟合的技巧

  1. 限制树的复杂度:$\Omega$函数对树的节点数和节点上预测值$\sum^T_{j=1}w_j^2$的平方和具有惩罚。除此之外,我们通常在终止条件上增加一条:树的深度。
  2. 采样:训练每个树的时候,只使用一部分样本。
  3. 列采样:即训练每个树的时候,只使用一部分特征。这里是$xgboost$的创新,它将随机森林思想引入。
  4. $Shrinkage$:进一步惩罚$\{w_j\}^T_1$,设定学习率$\epsilon$,防止过拟合。
  5. $Early stop$:因为GBDT的可叠加性,我们使用的模型不一定是最终的$ensemble$,而是根据测试集的情况,选择使用前若干棵树。

参考链接:

  1. XGBoost: A Scalable Tree Boosting System
  2. xgboost
  3. xgboost原理
  4. 知乎
  5. GBDT算法原理深入解析
  6. 机器学习-一文理解GBDT的原理-20171001
  7. 火光摇曳
0%