GBDT + LR

前言

  • 本文为GBDT+LR的总结,包括GBDT模型、GBDT的生成、GBDT+LR等内容

GBDT模型

  • GBDT全称梯度提升决策树,在传统机器学习算法里面是对真实分布拟合的最好的几种算法之一,在前几年深度学习还没有大行其道之前,gbdt在各种竞赛是大放异彩。
  • GBDT是通过采用加法模型(即基函数的线性组合),以及不断减小训练过程产生的误差来达到将数据分类或者回归的算法, 其训练过程如下:

  • gbdt通过多轮迭代, 每轮迭代会产生一个弱分类器, 每个分类器在上一轮分类器的残差基础上进行训练。 gbdt对弱分类器的要求一般是足够简单, 并且低方差高偏差。 因为训练的过程是通过降低偏差来不断提高最终分类器的精度。 由于上述高偏差和简单的要求,每个分类回归树的深度不会很深。最终的总分类器 是将每轮训练得到的弱分类器加权求和得到的(也就是加法模型)。
  • 这里只分析GBDT如何来进行二分类的,因为我们要明确一点就是gbdt 每轮的训练是在上一轮的训练的残差基础之上进行训练的, 而这里的残差指的就是当前模型的负梯度值, 这个就要求每轮迭代的时候,弱分类器的输出的结果相减是有意义的, 所以gbdt 无论用于分类还是回归一直都是使用的CART 回归树, 那么既然是回归树, 是如何进行二分类问题的呢? 如果是只用GBDT就可以进行二分类,那为啥后来又在GBDT的后面加上了逻辑回归模型呢? 如果是加上了逻辑回归模型, 那么两者究竟是怎么组合得到最后输出的呢? 后面两个问题的答案会在下一部分给出, 这里先分析一下GBDT的二分类问题, 也就是在二分类问题的时候, GBDT树的生成过程。

GBDT的生成

  • GBDT 来解决二分类问题和解决回归问题的本质是一样的,都是通过不断构建决策树的方式,使预测结果一步步的接近目标值, 但是二分类问题和回归问题的损失函数是不同的, 回归问题中一般使用的是平方损失, 而二分类问题中, GBDT和逻辑回归一样, 使用的下面这个:
  • $y_i$ 是第 $i$个样本的观测值, 取值要么是0要么是1, 而 $p_i$是第 $i$个样本的预测值, 取值是0-1之间的概率(sigmoid),由于我们知道GBDT拟合的残差是当前模型的负梯度, 那么我们就需要求出这个模型的导数, 即 $\frac{dL}{dp_i}$, 对于某个特定的样本, 求导的话就可以只考虑它本身, 去掉加和号, 那么就变成了 $\frac{dl}{dp_i}$, 其中 $l$如下:
  • 这里令 $\eta_i=\frac{p_i}{1-p_i}$, 即 $p_i=\frac{\eta_i}{1+\eta_i},$ 则上面这个式子变成了:
  • 这时候, 我们对 $log(\eta_i)$求导, 得:
  • 这样, 我们就得到了某个训练样本在当前模型的梯度值了, 那么残差就是$ y_i-p_i$。

  • GBDT的生成过程, 构建分类GBDT的步骤有两个:初始化GBDT;循环生成决策树

初始化GBDT

  • 和回归问题一样, 分类 GBDT 的初始状态也只有一个叶子节点,该节点为所有样本的初始预测值,如下:
  • 上式里面, $F$代表GBDT模型, $F_0$是模型的初始状态, 该式子的意思是找到一个 $\gamma$,使所有样本的 Loss 最小,在这里及下文中, $\gamma$都表示节点的输出,即叶子节点, 且它是一个 $log(\eta_i)$ 形式的值(回归值),在初始状态,$ \gamma =F_0$。下面看例子, 假设我们有下面3条样本:

  • 我们希望构建 GBDT 分类树,它能通过「喜欢爆米花」、「年龄」和「颜色偏好」这 3 个特征来预测某一个样本是否喜欢看电影,因为是只有 3 个样本的极简数据集,所以我们的决策树都是只有 1 个根节点、2 个叶子节点的树桩(Stump),但在实际应用中,决策树的叶子节点一般为 8-32 个。我们把数据代入上面的公式中求Loss:
  • 为了令其最小, 我们求导, 且让导数为0,导数为 $-y{i}+p{i}$,则$-1 + p -1 + p + p =0$,得$p=\frac{2}{3}$,$\gamma=log(\frac{p}{1-p})=0.69$, 模型的初识状态 $F_0(x)=0.69$

循环生成决策树

  • 回归树的生成步骤有4小步, 第一就是计算负梯度值得到残差, 第二步是用回归树拟合残差, 第三步是计算叶子节点的输出值, 第四步是更新模型。 下面我们一一来看:

  • 计算负梯度得到残差

    此处使用 $m-1$ 棵树的模型, 计算每个样本的残差 $r_{im}$, 就是上面的 $y_i-p_i$, 于是例子中, 每个样本的残差:

  • 使用回归树来拟合$ r_{im}$, 这里的 $i$ 表示样本,回归树的建立过程简单的说就是遍历每个特征, 每个特征下遍历每个取值, 计算分裂后两组数据的平方损失, 找到最小的那个划分节点。 假如我们产生的第2棵决策树如下:

  • 对于每个叶子节点 $j$, 计算最佳残差拟合值:

  • 更新模型 $F_m(x)$

仔细观察该式,实际上它就是梯度下降——「加上残差」和「减去梯度」这两个操作是等价的,这里设学习率 $\nu$ 为 0.1,则 3 个样本更新如下:

  • 可以看到, 样本1和样本3离正确的预测方向进了一步。最终, 循环M次, 或者总残差低于预设的阈值时, 我们的分类GBDT的建模就完成了。
  • 我们可以把树的生成过程理解成自动进行多维度的特征组合的过程,从根结点到叶子节点上的整个路径(多个特征值判断),才能最终决定一棵树的预测值, 另外,对于连续型特征的处理,GBDT 可以拆分出一个临界阈值,比如大于 0.027 走左子树,小于等于 0.027(或者 default 值)走右子树,这样很好的规避了人工离散化的问题。这样就非常轻松的解决了逻辑回归那里自动发现特征并进行有效组合的问题, 这也是GBDT的优势所在。
  • 但是GBDT也会有一些局限性, 对于海量的 id 类特征,GBDT 由于树的深度和棵树限制(防止过拟合),不能有效的存储;另外海量特征在也会存在性能瓶颈,当 GBDT 的 one hot 特征大于 10 万维时,就必须做分布式的训练才能保证不爆内存。所以 GBDT 通常配合少量的反馈 CTR 特征来表达,这样虽然具有一定的范化能力,但是同时会有信息损失,对于头部资源不能有效的表达。

GBDT + LR

  • 利用GBDT自动进行特征筛选和组合, 进而生成新的离散特征向量, 再把该特征向量当做LR模型的输入, 来产生最后的预测结果, 这就是著名的GBDT+LR模型。GBDT+LR 使用最广泛的场景是CTR点击率预估,即预测当给用户推送的广告会不会被用户点击。

  • 比如上图中, 有两棵树,x为一条输入样本,遍历两棵树后,x样本分别落到两颗树的叶子节点上,每个叶子节点对应LR一维特征,那么通过遍历树,就得到了该样本对应的所有LR特征。构造的新特征向量是取值0/1的。 比如左树有三个叶子节点,右树有两个叶子节点,最终的特征即为五维的向量。对于输入x,假设他落在左树第二个节点,编码[0,1,0],落在右树第二个节点则编码[0,1],所以整体的编码为[0,1,0,0,1],这类编码作为特征,输入到线性分类模型(LR or FM)中进行分类。

注意的点

  • 通过GBDT进行特征组合之后得到的离散向量是和训练数据的原特征一块作为逻辑回归的输入, 而不仅仅全是这种离散特征
  • 建树的时候用ensemble建树的原因就是一棵树的表达能力很弱,不足以表达多个有区分性的特征组合,多棵树的表达能力更强一些。GBDT每棵树都在学习前面棵树尚存的不足,迭代多少次就会生成多少棵树。
  • RF也是多棵树,但从效果上有实践证明不如GBDT。且GBDT前面的树,特征分裂主要体现对多数样本有区分度的特征;后面的树,主要体现的是经过前N颗树,残差仍然较大的少数样本。优先选用在整体上有区分度的特征,再选用针对少数样本有区分度的特征,思路更加合理,这应该也是用GBDT的原因。
  • 在CRT预估中, GBDT一般会建立两类树(非ID特征建一类, ID类特征建一类), AD,ID类特征在CTR预估中是非常重要的特征,直接将AD,ID作为feature进行建树不可行,故考虑为每个AD,ID建GBDT树。

    • 非ID类树:不以细粒度的ID建树,此类树作为base,即便曝光少的广告、广告主,仍可以通过此类树得到有区分性的特征、特征组合
    • ID类树:以细粒度 的ID建一类树,用于发现曝光充分的ID对应有区分性的特征、特征组合
  • 树模型不能处理大量高维度离散数据的原因是容易导致过拟合, 但是具体是怎么导致的过拟合呢?

-------------The End-------------
谢谢大锅请我喝杯阔乐~