GBDT总结

前言

  • 对BDT、GBDT、CART的总结

BDT: Boosting Decision Tree

  • BDT:提升树,以CART决策树为基学习器的集成学习方法,提升树模型可表示为决策树的加法模型:
  • 其中, $T(x;\Theta_m)$表示决策树; $\Theta_m$为决策树的参数, M表示树的个数, 即M棵树的结果相加。

  • 提升树采用的是前向分布算法, 首先确定初始提升树 $f_0(x)=0$, 第m步的模型是:

  • 其中,$f_{m-1}(x)$是当前模型,通过经验风险极小化(损失最小)确定下一棵树的参数$\Theta_m$:
  • 这里的$L()$是损失函数,回归算法选择的损失函数一般是均方差(最小二乘)或者绝对值误差;而在分类算法中一般的损失函数选择对数损失函数来表示。

  • 提升树的学习流程图:BDT中弱学习器的关联是残差

  • 上图可通俗理解为:获得一些训练样本, 我们先训练第一个弱学习器, BDT里面的弱学习器话就是决策树,训练完了第一个学习器, 就可以对样本进行一个预测, 此时会得到一个与真实标签的一个残差, 那么就可以用这个残差来训练后面的学习器, 也就是第二个分类器关注于前面学习器与真实标签的差距, 这样依次类推, 最后会得到n个弱分类器。 那么将这n个分类器进行加和, 就得到了最终的学习器。最后就是用这个东西进行预测。

  • 不同问题的提升树, 损失函数不同。如果我们解决的是一个回归问题, 我们用平方损失函数的话, 第m次迭代的损失函数为:

  • 这里的 r 就是残差, 所以第 m 棵决策树 $T(x, \Theta_m)$是对该残差的拟合。 要注意的是提升树算法中的基学习器是CART回归树

  • BDT的算法流程图:初始化一棵树,计算残差,根据残差拟合一棵树,然后更新

CART回归树

  • 牢记:CART树是二叉树

  • 一棵回归树对应着特征空间的一个划分以及在划分单元上的输出值。 假设已将输入空间划分为M个单元 $R_1, R_2, …, R_M$, 并且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$ , 于是回归树模型表示为:

  • 其中,I为指示函数,若属于该单元则为1;若x不属于则为0;
  • 当输入空间的划分确定时, 可以用平方误差 $\sum{x{i} \in R{m}}\left(y{i}-f\left(x_{i}\right)\right)^{2}$ 来表示回归树训练数据的误差, 用平方误差最小的准则求解每个单元上的最优输出值。 单元 $R_m$ 上的 $c_m$ 的最优输出值 $\hat c_m$ 是 $R_m$ 上的所有输入实例 $x_i$对应的 $y_i$ 的均值, 即:
  • 现在问题是如何对输入空间进行划分? 用启发式的方法, 选择第$j$个变量(特征) $x^{(j)}$和它的取值s, 作为切分变量和切分点, 并定义两个区域:
  • 然后寻找最优切分变量 $j$ 和 最优切分点 $s$,具体的,求解:
  • 对固定输入变量 $j$ 可以找到最优切分点 $s$:
  • 遍历所有输入变量, 找到最优切分变量 $j$, 构成一个对 $(j,s)$。 依此将输入空间划分为两个区域。 重复上面的过程, 直到满足条件, 这样就生成了一棵回归树,通常称为最小二乘回归树。

回归问题的提升树算法例子

  • 《李航-统计学习方法》例8.2

梯度提升:GBDT的原理

  • 提升树利用加法模型和前向分布算法实现学习的优化过程, 但损失函数是平方损失或者指数损失时, 优化比较简单, 但是对于一般的损失函数而言, 往往每一步优化不容易, 针对这个问题, Friedman提出了利用最速下降的近似方法, 即利用损失函数的负梯度在当前模型的值(如下所示)作为回归问题提升树算法中的残差的近似值来拟合一个回归树。
  • 怎么来理解这个近似呢? 如果是平方损失函数的话, 就一目了然,对其求导,就会发现,残差正好是梯度的相反数:
  • 所以在GBDT中使用负梯度作为残差进行拟合, 当然这是平方损失函数, 其他损失的话, 也会得到近似的结论, 只不过不是完全相等, 这里放张图体会一下:

  • 这其实就是GBDT的核心了, 即利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值去拟合一个回归树。gbdt 每轮迭代的时候,都去拟合损失函数在当前模型下的负梯度。这样每轮训练的时候都能够让损失函数尽可能快的减小,尽快的收敛达到局部最优解或者全局最优解。

GBDT的算法流程

  • GBDT和提升树的区别是残差使用了梯度来替代, 且每个基学习器有了对应的参数权重。gbdt通过多轮迭代,每轮迭代产生一个弱分类器,每个分类器在上一轮分类器的残差基础上进行训练。对弱分类器的要求一般是足够简单,并且是低方差和高偏差的(因为训练的过程是通过降低偏差来不断提高最终分类器的精度)。 弱分类器一般会选择为CART TREE(也就是分类回归树)。由于上述高偏差和简单的要求每个分类回归树的深度不会很深。最终的总分类器是将每轮训练得到的弱分类器加权求和得到的(也就是加法模型)

  • gbdt无论用于分类还是回归一直都是使用CART回归树:
  • 算法流程:第 1 步初始化,估计使损失函数极小化的常数值, 它是只有一个根结点的树第 2(a) 步计算损失函数的负梯度在当前模型的值,将它作为残差的估计。对于平方损失函数,它就是通常所说的残差,对于一般损失函数,它就是残差的近似值。第 2(b) 步估计回归树叶结点区域,以拟合残差的近似值第 2(c )步利用线性搜索估计叶结点区域的值,使损失函数极小化第 2(d) 步更新回归树。第 3 步得到输出的最终模型。

GBDT计算特征重要度

  • 首先明确:cart树,如果有n个特征,实际上就是n维空间,那么每次选特征,实际上是对n维空间的划分,那么特征会重复出现
    • 例如:把树打印出来,属性会重复出现,但是当前节点的判定条件会不同; 比如对于age这个属性来说 有的节点是 age>20 years old 有的节点是>40 years old
  • 特征 $j$ 的全局重要度通过特征 $j$ 在单棵树中的重要度的平均值来衡量:

其中,M是树的数量。特征 $j$ 在单颗树中的重要度如下:

其中,$L$ 为树的叶子节点数量,$L-1$ 即为树的非叶子节点数量(构建的树都是具有左右孩子的二叉树),$vt$ 是和节点 $t$ 相关联的特征,$\hat{i{t}^{2}}$ 是节点 $t$ 分裂之后平方损失的减少值

GBDT构建特征

  • 说gbdt能够构建特征并非很准确,gbdt 本身是不能产生特征的,但是我们可以利用gbdt去产生特征的组合。在CTR预估中,工业界一般会采用逻辑回归去进行处理,在逻辑回归那篇文章中已经说过,逻辑回归本身是适合处理线性可分的数据,如果我们想让逻辑回归处理非线性的数据,其中一种方式便是组合不同特征,增强逻辑回归对非线性分布的拟合能力。
  • 长久以来,我们都是通过人工的先验知识或者实验来获得有效的组合特征,但是很多时候,使用人工经验知识来组合特征过于耗费人力,造成了机器学习当中一个很奇特的现象:有多少人工就有多少智能。关键是这样通过人工去组合特征并不一定能够提升模型的效果。所以我们的从业者或者学界一直都有一个趋势便是通过算法自动,高效的寻找到有效的特征组合。Facebook 在2014年 发表的一篇论文便是这种尝试下的产物,利用gbdt去产生有效的特征组合,以便用于逻辑回归的训练,提升模型最终的效果。

  • 如上图,使用 GBDT 生成了两棵树,两颗树一共有五个叶子节点。我们将样本 X 输入到两颗树当中去,样本X 落在了第一棵树的第二个叶子节点,第二颗树的第一个叶子节点,于是我们便可以依次构建一个五维的特征向量,每一个纬度代表了一个叶子节点,样本落在这个叶子节点上面的话那么值为1,没有落在该叶子节点的话,那么值为 0.
  • 于是对于该样本,我们可以得到一个向量[0,1,0,1,0] 作为该样本的组合特征,和原来的特征一起输入到逻辑回归当中进行训练。实验证明这样会得到比较显著的效果提升。

  • LR+GBDT模型一般是用于点击率预测里面, 而点击率预测是个典型的分类问题(点击或者不点击), 而我们上面一直说GBDT用的是CART回归树, 那么我们上面那部分进行样本类别划分的时候, 是怎么划分的呢? 回归树不是输出连续值吗? 我们怎么训练上面的GBDT模型?

GBDT用于分类

  • 首先明确一点,gbdt 无论用于分类还是回归一直都是使用的CART 回归树。不会因为我们所选择的任务是分类任务就选用分类树,这里面的核心是因为gbdt 每轮的训练是在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值 。这个要求每轮迭代的时候,弱分类器的输出的结果相减是有意义的。残差相减是有意义的。如果选用的弱分类器是分类树,类别相减是没有意义的。上一轮输出的是样本 x 属于 A类,本一轮训练输出的是样本 x属于 B类。 A 和 B 很多时候甚至都没有比较的意义,A 类- B类是没有意义的。 那么我们如何进行分类呢?

  • 假设样本X总共有K类, 来了一个样本, 我们使用gbdt来判断样本x属于哪一类? 流程如下:

    • 我们在训练的时候, 是针对样本X每个可能的类训练一个分类回归树。举个例子, 假设目前样本一共三类, 也就是K=3, 样本x属于第二类。 那么针对该样本x的分类结果, 我们可以用一个三维向量[0, 1, 0]来表示。 0表示样本不属于该类, 1表示属于该类。
    • 针对样本有三类的情况, 我们实质上每轮训练的时候是训练三棵树:第一棵针对样本x得第一类, 输入为(x, 0), 第二棵是针对样本x的第二类, 输入(x, 1), 第三棵针对样本x的第三类, 输入(x, 0), 这里的具体训练过程就是我们上面CART 回归树生成过程了, 按照上面的生成过程, 我们就可以解出这三棵树以及三棵树上x类别的预测值 $f{1}(x), f{2}(x), f_{3}(x)$。
    • 在此类训练中, 我们仿照多分类的逻辑回归, 使用softmax产生概率, 则属于类别1的概率:
    • 对每个类别分别计算残差,如类别1: $\tilde{y}{1}=0-p{1}\left(\mathbf{x}{\mathbf{}}\right)$, 类别2: $\tilde{y}{2}=1-p{2}\left(\mathbf{x}{\mathbf{}}\right)$, 类别3: $\tilde{y}{3}=0-p{3}\left(\mathbf{x}{\mathbf{}}\right)$

    • 开始第二轮的训练, 针对第一类输入为 $\left(\mathbf{x}{\mathbf{}}, \tilde{y}{1}\right)$, 针对第二类输入为 $\left(\mathbf{x}{\mathbf{}}, \tilde{y}{2}\right)$, 针对第三类输入为 $\left(\mathbf{x}{\mathbf{}}, \tilde{y}{3}\right)$, 继续训练出三棵树。

    • 重复5直到迭代M轮, 就得到了最后的模型, 预测的时候只要找出概率最高的即为对应的类别。
  • GBDT多分类的例子:

  • 这是一个有6个样本的三分类问题。我们需要根据这个花的花萼长度,花萼宽度,花瓣长度,花瓣宽度来判断这个花属于山鸢尾,杂色鸢尾,还是维吉尼亚鸢尾。
  • 具体应用到gbdt多分类算法上面。我们用一个三维向量来标志样本的label。[1,0,0] 表示样本属于山鸢尾,[0,1,0] 表示样本属于杂色鸢尾,[0,0,1] 表示属于维吉尼亚鸢尾。
  • 以样本1为例, 第一轮要训练3棵CART树, 对于第一棵CART回归树, 训练样本是[5.1, 3.5, 1.4, 0.2], label是1,第二棵 训练样本是[5.1, 3.5, 1.4, 0.2], label是0, 第三棵训练样本是[5.1, 3.5, 1.4, 0.2], label是0。
  • CART 1生成过程是从这四个特征中找一个特征作为CART 1的节点, 比如花萼长度作为节点, 6个样本当中花萼长度 大于5.1 cm的就是 A类,小于等于 5.1 cm 的是B类。生成的过程其实非常简单,但是有两个问题 :

    • 哪个特征最合适?
    • 这个特征的什么特征值作为切分点?
  • 即使我们已经确定了花萼长度做为节点。花萼长度本身也有很多值。在这里我们的方式是遍历所有的可能性,找到一个最好的特征和它对应的最优特征值可以让当前式子的值最小

  • 我们以第一个特征的第一个特征值为例。 $R_1$ 为所有样本中花萼长度小于 5.1 cm 的样本集合, $R_2$ 为所有样本当中花萼长度大于等于 5.1cm 的样本集合。所以 $R_1={2}, R_2={1,3,4,5,6}$

  • 上面这个图就是 $y_1$是 $R_1$ label的均值, 由于 $R_1$只有一个元素且label为1, 则均值为1, 即$ y_1=1$, $y_2$是$R_2$的label均值, 由于$R_2$里面只有1的label是1, 3、 4、 5、 6的label是0, 故均值是0.2, 下面就是用上面的公式计算的损失函数了。 就会发现山鸢尾类型在特征1的第一个特征值上的损失为0.8。

  • 同样的方式, 我们可以计算特征1上第二个特征值上的损失, $R_1$为所有样本花萼长度小于4.9cm的样本集合, $R_2$为所有样本中花萼长度大于等于4.9cm的样本集合。 所以 $R_1={}, R_2={1, 2, 3, 4, 5, 6}$, 再计算得到特征1的第二个特征上的损失:

  • 这样我们可以遍历所有特征的所有特征值,找到让这个式子最小的特征以及其对应的特征值。 在这里我们算出来让这个式子最小的特征是花萼长度,特征值为5.1 cm。这个时候损失函数最小为 0.8。

  • 于是预测函数为:

  • 此时,$R_1={2}, R_2={1, 3, 4, 5, 6}$,$y_1 = 1,y_2=0.2$,所以最终的预测函数为:
  • 因此, 我们得到对样本属于类别1的预测值:
  • 同理, 我们也可以构建CART 2和CART 3计算得到样本属于类别2和类别3的预测值 $f_2(x), f_3(x)$,那么我们就可以根据softmax得到样本属于类别1的概率,类别2和类别3的也能算出来, 然后就可以得到残差, 每个样本都是如此, 就可以进行第二轮的训练了
-------------The End-------------
谢谢大锅请我喝杯阔乐~