0%

机器学习基本算法2-XGBoost

Posted on Edited on In

突然发现XGBoost好像不能算是基本算法，不过也姑且整理再这里了。本文梳理了陈天奇Introduction to Boosted Trees的slides，有些长。

背景

需要的预备知识：CART回归树算法，梯度下降法及泰勒公式。
看预备知识就可以知道，XGBoost（eXtreme Gradient Boosting）由GBDT发展而来，是一种基于树模型的集成算法。目前在各大比赛场上斩杀无数算法，可以说是是数据挖掘比赛必备。

算法简述

陈天奇的slides对于算法的解释十分详细，简述基于PPT。

Review of key concepts of supervised learning | 回顾监督学习的关键概念

  • Model|模型：如何用xi来预测yi_hat。对于线性模型来说，预测值yi_hat基于不同的任务有不同的计算。
  • Parameters|参数：从数据中学得。
  • Objective function|目标函数：由训练误差（损失函数）training loss和正则化项Regularization组成。训练误差有平方误差和交叉熵损失函数；正则化项有L1和L2。
    其中，线性回归模型加L2正则是Ridge regression，线性回归模型加L1正则是Lasso，逻辑回归模型加L2正则。
  • The conceptual separation between model, parameter, objective also gives you engineering benefits。
    • 损失函数表示模型对训练数据的拟合程度，loss越小，代表模型预测的越准，即偏差Bias越小。
    • 正则化项衡量模型的复杂度，regularization越小，代表模型模型的复杂度越低，即方差Variance越小。
    • 目标函数越小，代表模型越好。Bias-variance tradeoff也是一个模型能力的体现。

Regression Tree and Ensemble (What are we Learning)

关于树模型集成方法Tree Ensemble methods：
  • Very widely used, look for GBM, random forest…
    被广泛使用
    • Almost half of data mining competition are won by using some variants of tree ensemble methods
      接近半数数据挖掘比赛冠军队使用树集成方法
  • Invariant to scaling of inputs, so you do not need to do careful features normalization.
    和输入数据的取值范围无关，所以无需做很细致的特征归一化
  • Learn higher order interaction between features.
    能学习到高位特征的相关性
  • Can be scalable, and are used in Industry
    扩展性好，工业使用
  • yi_hat由所有树模型决定，模型复杂度space of function包含所有回归树。
  • 不学习权重， 而是学习function，即fK（tree）。
  • 决策树具有启发式思想。用信息增益决定分裂节点，减少损失。
  • 树的剪枝，最大深度以及叶节点权重都会影响模型复杂度。对树进行剪枝，对叶节点的权重进行L2正则化能减少模型复杂度，提高模型稳定性。
  • 回归树不仅可以解决回归问题，还能做分类、排序问题，这取决于你的目标函数。例如平方误差和交叉熵损失函数。

Gradient Boosting (How do we Learn)

  • Bias-variance tradeoff is everywhere
    偏差方差均衡无处不在
  • The loss + regularization objective pattern applies for regression tree learning (function learning)
    损失函数+正则的目标函数模式适用于回归树的学习
  • We want predictive and simple functions
    我们需要泛化能力强又简单的模型（奥卡姆剃刀原则）

来求解优化一下目标函数，感受一下算法的精华。
和一般Boosting方法一样，采用加性模型，并考虑平方差损失，引入泰勒展开来近似损失。（嗯，可以掏出小本本算一算了）

于是，得到了新的目标函数Obj = 损失函数+正则项+常数项。

Why spending s much efforts to derive the objective, why not just grow trees …
为什么花这么多时间去分解目标函数，而不是单纯使树增长

  • Theoretical benefit: know what we are learning, convergence
    理论优势：能知道模型在学什么
  • Engineering benefit: recall the elements of supervised learning
    工程优势：回顾一下监督学习的元素
    • gi and hi comes from definition of loss function
      gi和hi由损失函数的定义而来
    • The learning of function only depend on the objective via gi and hi
      需要学习的函数只取决于gi和hi
    • Think of how you can separate modules of your code when you are asked to implement boosted tree for both square loss and logistic loss

Summary

参数说明

原始函数

Before running XGBoost, we must set three types of parameters: general parameters, booster parameters and task parameters.

  • General parameters relate to which booster we are using to do boosting, commonly tree or linear model
  • Booster parameters depend on which booster you have chosen
  • Learning task parameters decide on the learning scenario. For example, regression tasks may use different parameters with ranking tasks.
  • Command line parameters relate to behavior of CLI version of XGBoost.
    具体参数详见XGBoost官方文档。

Python API

Python API官方文档
括号内为 sklearn 参数。

通用参数
  • booster：基学习器类型，gbtree，gblinear 或 dart（增加了 Dropout） ，gbtree 和 dart 使用基于树的模型，而 gblinear 使用线性模型
  • silent：使用 0 会打印更多信息
  • nthread：运行时线程数
Booster 参数

树模型Tree booster

  • eta（learning_rate）：更新过程中用到的收缩步长，[0, 1]。
  • gamma：在节点分裂时，只有在分裂后损失函数的值下降了，才会分裂这个节点。Gamma 指定了节点分裂所需的最小损失函数下降值。这个参数值越大，算法越保守。
  • max_depth：树的最大深度，这个值也是用来避免过拟合的
  • min_child_weight：决定最小叶子节点样本权重和。当它的值较大时，可以避免模型学习到局部的特殊样本。但如果这个值过高，会导致欠拟合。
  • max_delta_step：这参数限制每颗树权重改变的最大步长。如果是0意味着没有约束。如果是正值那么这个算法会更保守，通常不需要设置。
  • subsample：这个参数控制用于每棵树随机采样的比例。减小这个参数的值算法会更加保守，避免过拟合。但是这个值设置的过小，它可能会导致欠拟合。
  • colsample_bytree：用来控制每颗树随机采样的列数的占比。
  • colsample_bylevel：用来控制的每一级的每一次分裂，对列数的采样的占比。
  • lambda（reg_lambda）：L2 正则化项的权重系数，越大模型越保守。
  • alpha（reg_alpha）：L1 正则化项的权重系数，越大模型越保守。
  • tree_method：树生成算法,auto, exact, approx, hist, gpu_exact, gpu_hist
  • scale_pos_weight：各类样本十分不平衡时，把这个参数设置为一个正数，可以使算法更快收敛。典型值是 sum(negative cases) / sum(positive cases)

Dart 额外参数

  • sample_type：采样算法
  • normalize_type：标准化算法
  • rate_drop：前置树的丢弃率，有多少比率的树不进入下一个迭代，[0, 1]
  • one_drop：设置为 1 的话每次至少有一棵树被丢弃。
  • skip_drop：跳过丢弃阶段的概率，[0, 1]，非零的 skip_drop 比 rate_drop 和 one_drop 有更高的优先级。

线性模型

  • lambda（reg_lambda）：L2 正则化项的权重系数，越大模型越保守。
  • alpha（reg_alpha）：L1 正则化项的权重系数，越大模型越保守。
  • lambda_bias（reg_lambda_bias）：L2 正则化项的偏置。
学习任务参数
  • objective：定义需要被最小化的损失函数。
  • base_score：初始化预测分数，全局偏置。
  • eval_metric：对于有效数据的度量方法，取值范围取决于 objective。
  • seed：随机数种子，相同的种子可以复现随机结果，用于调参。

代码实现

XGB-sklearn示例官方源码

和GBDT的比较以及优点

  1. 损失函数：GBDT是一阶，XGB是二阶泰勒展开
  2. XGB的损失函数可以自定义，具体参考 objective 这个参数
  3. XGB的目标函数进行了优化，有正则项，减少过拟合，控制模型复杂度
  4. 预剪枝：预防过拟合
    • GBDT：分裂到负损失，分裂停止
    • XGB：一直分裂到指定的最大深度（max_depth），然后回过头剪枝。如某个点之后不再正值，去除这个分裂。优点是，当一个负损失(-2)后存在一个正损失(+10)，(-2+10=8>0)求和为正，保留这个分裂。
  5. XGB有列抽样/column sample，借鉴随机森林，减少过拟合
  6. 缺失值处理：XGB内置缺失值处理规则，用户提供一个和其它样本不同的值，作为一个参数传进去，作为缺失值取值。
    XGB在不同节点遇到缺失值采取不同处理方法，并且学习未来遇到缺失值的情况。
  7. XGB内置交叉检验（CV），允许每轮boosting迭代中用交叉检验，以便获取最优 Boosting_n_round 迭代次数，可利用网格搜索grid search和交叉检验cross validation进行调参。
    GBDT使用网格搜索。
  8. XGB运行速度快：data事先安排好以block形式存储，利于并行计算。在训练前，对数据排序，后面迭代中反复使用block结构。
    关于并行，不是在tree粒度上的并行，并行在特征粒度上，对特征进行Importance计算排序，也是信息增益计算，找到最佳分割点。
  9. 灵活性：XGB可以深度定制每一个子分类器
  10. 易用性：XGB有各种语言封装
  11. 扩展性：XGB提供了分布式训练，支持Hadoop实现
  12. 共同优点：
    • 当数据有噪音的时候，树Tree的算法抗噪能力更强
    • 树容易对缺失值进行处理
    • 树对分类变量Categorical feature更友好

和LGB的比较

  1. XGB用贪心算法排序累加，LGB用投票采样
  2. XGB 异常影响全局，LGB有筛选
  3. XGB速度慢，LGB改成轻量级
  4. XGB 的GPU版本比LGB快，LGB则不然
  5. 分布式由XGB，很少用LGB
  6. XGBoost使用按层生长(level-wise)的决策树生长策略，不断优化到最大深度；LightGBM则采用带有深度限制的按叶子节点(leaf-wise)算法。在分裂次数相同的情况下，leaf-wise可以降低更多的误差，得到更好的精度。leaf-wise的缺点在于会产生较深的决策树，产生过拟合。

Reference

陈天奇PPT
XGBoost: A Scalable Tree Boosting System原著论文
CodewithZhangyi（一个很优秀的小姐姐的博客）
GBDT、XGBoost、LightGBM的使用及参数调优