浅析Xgboost原理

浅析Xgboost原理

内容

  1. 泰勒公式
  2. 最优化方法
  3. 从参数空间到函数空间
  4. 详解Xgboost
  5. LightGBM

泰勒公式:

梯度下降法:

牛顿法:

从参数空间到函数空间

GBDT在函数空间中利用梯度下降法进行优化
Xgboost在函数空间中用牛顿法进行优化

Xgboost的正则项:

上面式子中,第一部分rT,T表示叶子节点的数量,r是超参,也就是说r越大,那么我们的叶子节点数量就会越小。第二部分是L2正则项,通过对叶子结点的权重进行惩罚,使得不会存在权重过大的叶子结点防止过拟合。w就表示叶子结点的权重。

但是对于上面这么一个目标函数,我们是很难进行优化的,于是我们将它变换一下,我们通过每一步增加一个基分类器ft,贪婪地去优化这个目标函数,使得每次增加,都使得loss变小。如此一来,我们就得到了一个可以用于评价当前分类器ft性能的一个评价函数:

这个算法又可以称为前向分步优化。为了更快地去优化这个函数,我们可以在ft=0处二阶泰勒展开:

由于我们的目标函数L只受函数f的影响,上一次的loss对本次迭代并没有影响,于是我们可以删除掉常数项。

误差函数的二阶泰勒展开:

Xgboost的打分函数:

树节点分裂算法–精确算法,遍历所有特征的所有可能的分割点,计算gain值,选取值最大的(feature,value)去分割

树节点分裂方法–近似算法,对于每个特征,只考察分位点,减少计算复杂度

树节点分裂方法–近似算法举例:三分位数

实际上Xgboost不是简单地按照样本个数进行分为,而是以二阶导数值作为权重。

Xgboost的其他特性

  1. 行抽样(row sample)
  2. 列抽样(column sample),借鉴了随机森林
  3. Shrikage(缩减),即学习速率。将学习速率调小,迭代次数增多,有正则化作用
  4. 支持自定义损失函数(需二阶可导)

Column Block 和 Cache Aware Access:

LightGBM的改进

  1. 直方图算法:
    把连续的浮点特征值离散化成k个整数,同时构造一个宽度为k的直方图。在遍历数据的时候,根据离散化后的值作为索引在直方图中累积统计量,当遍历一次数据后,直方图累积了需要的统计量,然后根据直方图的离散值,遍历寻找最优的分割点。

    这样减少了内存占用;也减少了split finding时计算增益的计算量。

  2. 直方图差加速
    一个叶子的直方图可以由它的父亲节点的直方图与它兄弟节点的 直方图做差得到,提升一倍速度。

  3. 建树过程的两种方法
    Level-wise tree growth:同一层所有节点都做分裂,最后剪枝。代表有Xgboost
    Leaf-wise tree growth:选取具有最大增益节点分裂,容易过拟合,可以通过max_depth限制。代表有LightGBM

  4. 并行优化
    LightGBM的特征并行:
    每个worker保存所有数据集
    (1)每个worker在其特征子集上寻找最佳切分点
    (2)worker之间互相通信,找到全局最佳切分点
    (3)每个worker根据全局最佳切分点进行节点分裂

    优点:避免广播instance indices,减小网络通信量
    缺点:split finding计算复杂度没有减小;且当数据量比较大时,单个worker存储所有数据代价高

传统的数据并行
(1)水平切分数据,每个worker只有部分数据
(2)每个worker根据本地数据统计局部直方图
(3)合并所有局部直方图得到全局直方图
(4)根据全局直方图进行节点分裂

缺点:网络通信代价巨大

LightGBM的数据并行
(1)不同的worker合并不同特征的局部直方图
(2)采用直方图做差算法,只需要通信一个节点的直方图

LightGBM其他地方的改进:

Xgboost和GBDT的区别

  1. 传统GBDT以CART作为基分类器,xgboost还支持线性分类器,这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归(分类问题)或者线性回归(回归问题)。

  2. 传统GBDT在优化时只用到一阶导数信息,xgboost则对代价函数进行了二阶泰勒展开,同时用到了一阶和二阶导数。顺便提一下,xgboost工具支持自定义代价函数,只要函数可一阶和二阶求导。

  3. xgboost在代价函数里加入了正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲,正则项降低了模型的variance,使学习出来的模型更加简单,防止过拟合,这也是xgboost优于传统GBDT的一个特性。

  4. Shrinkage(缩减),相当于学习速率(xgboost中的eta)。xgboost在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了削弱每棵树的影响,让后面有更大的学习空间。实际应用中,一般把eta设置得小一点,然后迭代次数设置得大一点。(补充:传统GBDT的实现也有学习速率)

  5. 列抽样(column subsampling)。xgboost借鉴了随机森林的做法,支持列抽样,不仅能降低过拟合,还能减少计算,这也是xgboost异于传统gbdt的一个特性。

  6. 对缺失值的处理。对于特征的值有缺失的样本,xgboost可以自动学习出它的分裂方向。

  7. xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的?注意xgboost的并行不是tree粒度的并行,xgboost也是一次迭代完才能进行下一次迭代的(第t次迭代的代价函数里包含了前面t-1次迭代的预测值)。xgboost的并行是在特征粒度上的。我们知道,决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点),xgboost在训练之前,预先对数据进行了排序,然后保存为block结构,后面的迭代中重复地使用这个结构,大大减小计算量。这个block结构也使得并行成为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行。

  8. 可并行的近似直方图算法。树节点在进行分裂时,我们需要计算每个特征的每个分割点对应的增益,即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下,贪心算法效率就会变得很低,所以xgboost还提出了一种可并行的近似直方图算法,用于高效地生成候选的分割点。

Xgboost使用经验总结

  1. 多类别分类时,类别需要从0开始编码

  2. Watchlist不会影响模型训练。

  3. 类别特征必须编码,因为xgboost把特征默认都当成数值型的

  4. 训练的时候,为了结果可复现,记得设置随机数种子。

  5. XGBoost的特征重要性是如何得到的?某个特征的重要性(feature score),等于它被选中为树节点分裂特征的次数的和,比如特征A在第一次迭代中(即第一棵树)被选中了1次去分裂树节点,在第二次迭代被选中2次…..那么最终特征A的feature score就是 1+2+….

参考链接:
http://wepon.me/2016/05/07/XGBoost%E6%B5%85%E5%85%A5%E6%B5%85%E5%87%BA/