XGboost模型

发表于 | 分类于 ，

XGBoost论文阅读及其原理
XGBoost很棒的原理解读
https://blog.csdn.net/guoxinian/article/details/79243307
https://blog.csdn.net/matrix_zzl/article/details/78635221#2-xgboost%E5%8E%9F%E7%90%86%E6%8E%A8%E5%AF%BC

boosting集成框架

  • boosting集成是后一个模型是对前一个模型产生误差信息进行矫正
  • gradient boost更具体，新模型的引入是为了减少上个模型的残差(residual)，我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型
  • 框架算法：
    • 1.设定函数初始值F0，为一个恒值函数，论文中基于变量优化出恒值，实际上也可以给定任意值或者直接为0
    • 2.泛函优化
      根据参数MM，进行MM次迭代，不断将当前函数$F_{m−1}$往最优函数F∗空间上逼近，逼近方向就是当前函数下的函数负梯度方向-$\delta L(y,F)$,由于优化函数，而非变量，本质上属于泛函优化
    • 3.每次迭代计算出函数负梯度，基于训练数据构建模型来拟合负梯度。原则上可以选择任何模型：树模型，线性模型或者神经网络等等，很少框架支持神经网络，推测：神经网络容易过拟合，后续函数负梯度恒为0就无法继续迭代优化下去。如果用树模型进行拟合，就是我们熟悉的CART建树过程
  • 泛函优化与变量优化
  • 和bagging比较并行性
    谈到集成学习，不得不说bagging集成，比如随机森林
    • 1）建树前对样本随机抽样（行采样）
    • 2）每个特征分裂随机采样生成特征候选集（列采样）
    • 3）根据增益公式选取最优分裂特征和对应特征分裂值建树。
      • 建树过程完全独立，不像boosting训练中下一颗树需要依赖前一颗树训练构建完成，因此能够完全并行化。Python机器学习包sklearn中随机森林RF能完全并行训练
      • 而GBDT算法不行，训练过程还是单线程，无法利用多核导致速度慢。希望后续优化实现并行，Boosting并行不是同时构造N颗树，而是单颗树构建中遍历最优特征时的并行，类似XGBoost实现过程。随机森林中行采样与列采样有效抑制模型过拟合，XGBoost也支持这2种特性，此外其还支持Dropout抗过拟合。

XGboost改进(算法)-Loss方程

  • Loss进行泰勒二阶展开并且加入了惩罚项

    • 目标函数只依赖于每个数据点的在误差函数上的一阶导数和二阶导数

    • 目标函数通过二阶泰勒展开式做近似。传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。注：支持自定义代价函数，只要函数可一阶和二阶求导

      • 泰勒展开理解
        • 如何让两个人运动轨迹一样？
          就是让两个人的速度，加速度，加速度的加速度…都一致。那么翻译成数学语言，也就是两条曲线想要一样，那么在某一点的一阶导数，二阶导数，三阶导数，四阶导数….n阶导数也相同，就说这两条曲线是相同的。也就是泰勒展开式的核心思想

    • 定义了树的复杂度，即xgboost在代价函数里加入了正则项，用于控制模型的复杂度，正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。代替了剪枝。

  • obj fucntion的形式已经非常漂亮，是一个典型的二次函数。可是问题在于，loss是sample wise的，而正则项则关注tree structure，两者尚不能统一，仍然不能直接得到一个直观的结果
    • 我们希望的obj function的形式是易于计算的，所以下一步我们要将training loss从sample-wise转化成tree-structure-wise
    • $I_j$为所有对应到叶子节点j的样本的集合
      $I_j={i|q(x_i)=j}$
    • 我们就可以顺利地将样本group by叶子，实现统一obj function的关注目标
      • 它只关注tree structure相关信息，没有其他杂质
      • 它的形式依然是一个简单的二次函数的形式，其极值是直接可求得的，换句话说，对于每一棵树，其最佳参数可以在O(1)的时间内求出数值解。这使得XGBoost相对于传统GBDT的个求解速度大大提升
      • 简单求解一下这个二次函数的极值，我们有，在给定的tree structure下，最佳的参数取值$w_j$和loss:
        • 同样loss值只和样本的一阶和二阶梯度有关
        • 梯度就和具体的$h_{\theta}(x)$，以及具体的loss方程有关系了

XGboost改进-tree structure原理

  • 不同的决策树算法有不同的度量（information gain, gini, etc.），用来评价新划分对模型的loss有多少影响。
    因为XGBoost已经有了一个需要minimize的object function，XGBoost的score/gain的度量方式就可以简单选取新划分的loss和划分之前的loss的差值，如果新划分让loss变小，换言之，划分前的loss比划分后的loss大，那么就说明划分是有用的
  • 有了这个前提，才有下面的find best split
    • 现有的boosted tree基本基于贪心的思想，即“每次仅考虑对当前层次/树效果最好的结点作为分裂节点
      • 时间复杂度$o(m*n^2)$(m是特征数量，n是样本数量)
        • 相当于对每个特征，又需要两重的for循环，以每个样本的该特征的值作为分割点进行整体收益计算，比它大的放左边，比它小的放右边（因为没有排序，所以只能两重for循环，就是$o(n^2)$）

XGboost改进-特征树分割点选择(精确法)

  • XGBoost在单机默认是exact greedy，搜索所有的可能分割点。分布式是dynamic histogram
  • 精确算法由于需要遍历特征的所有取值，计算效率低，适合单机小数据，对于大数据、分布式场景并不适合
  • 时间复杂度$o(m*n^2)$(m是特征数量，n是样本数量),因为进行pre-sort
    • 相当于只需要消耗排序的时间$O(n*log(n))$
    • 排好序后直接将自己的左右的样本划分到左右子树就好

XGboost改进-特征树分割点选择(近似法)(Weighted Quantile Sketch)

(近似方法Approximate Algorithm)（分布式加权直方图算法）

  • 核心思想：分位数
    • 既然样本数量太大，我们可不可以按比例来选择，从n个样本中抽取k个样本来进行计算，取k个样本中的最优值作为split value，这样就大大减少了运算数量。这就是k分位点选取的思想，即quantile sketch
    • 要如何抽取k个样本？我们要均分的是loss，而不是单纯的对样本，而每个样本对loss的贡献可能是不一样的，按样本均分会导致loss分布不均匀，取到的分位点会有偏差
    • 近似方法采用的分桶原理正是这个：按照二阶梯度来进行rank
  • 对特征k,构造数据集$D_k=(x_{1k},h_1),(x_{2k},h_2),…(x_{nk},h_n)$(就不用pre-sort)
    • h是$x_{ik}$对损失函数的二阶梯度
  • rank 排序定义
    • 对某一个特征上，样本特征值小于z的二阶梯度除以所有的二阶梯度总和。其实就是对样本的二阶梯度进行累加求和
    • 就是代表特征k上，特征值小于z的样本的权重(二阶梯度)累积
  • 选择分割点$s_{k1},s_{k2}…s_{kl}$：相邻两个分割点的rank值不超过$\epsilon$
  • 直方图理解
  • 所以$\epsilon$越小，那么桶个数$\frac{1}{\epsilon}$越多，越精细
  • 离散化两种方式(global&local)
    • glocal:是在建立第k棵树的时候利用样本的二阶梯度对样本进行离散化，每一维的特征都建立buckets。在建树的过程中，我们就重复利用这些buckets去做
      • m个buckets就相当于只有m个样本
    • local:每次进行分支时，我们都重新计算每个样本的二阶梯度并重新构建buckets，再进行分支判断
      • 显然局部选择的编码复杂度更高，但是实验当中效果极其的好，甚至与Exact Greedy Algorithm一样
  • 没有理解分桶后，按照每个同为节点，如何进行树的划分，而且每个特征都有不同的分桶

对缺失值的处理

  • 对于稀疏性的离散特征，在寻找split point的时候，不会对该特征为missing的样本进行遍历统计
    • 通过这个工程技巧来减少了为稀疏离散特征寻找split point的时间开销
  • 在逻辑实现上，为了保证完备性，会处理将缺失样本分配到左右子树节点两种方案，或者指定默认的分支，大大提升了效率

XGboost改进-并行化

支持并行化处理。xgboost的并行是在特征粒度上的，在训练之前，预先对特征进行了排序(pre-sort)，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行，即在不同的特征属性上采用多线程并行方式寻找最佳分割点。

XGboost改进（工程上）

  • 缓存
    结合工程上数据存储技巧：比如block概念等
    • 对于有大量数据或者说分布式系统来说，我们不可能将所有的数据都放进内存里面。因此我们都需要将其放在外存上或者分布式存储。但是这有一个问题，这样做每次都要从外存上读取数据到内存，这将会是十分耗时的操作。因此我们使用预读取（prefetching）将下一块将要读取的数据预先放进内存里面。其实就是多开一个线程，该线程与训练的线程独立并负责数据读取。此外，我还要考虑block的大小问题。如果我们设置最大的block来存储所有样本在k特征上的值和梯度的话，cache未必能一次性处理如此多的梯度做统计。如果我们设置过少block size，这样不能充分利用的多线程的优势，也就是训练线程已经训练完数据，但是prefetching thread还没把数据放入内存或者cache中
  • 对数据进行压缩存在外存
    • 一种是对数据进行压缩存于外存中，到内存中需要训练时再解压，这样来增加系统的吞吐率，尽管消耗了一些时间来做编码和解码但还是值得的
    • 多外存存储，其实本质上就是分布式存储。这样说有多个线程对分布式结构管理，吞吐率自然高

XGboost改进-其他

  • 自定义损失函数
  • 列抽样（特征子采样）（column subsampling）[传统GBDT没有]xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性
  • Shrinkage(缩减)
    • 相当于学习速率(xgboost中的eta)[传统GBDT也有]
    • 权值收缩也就是对叶子节点的权值乘上收缩因子，该收缩因子是人为设定的参数。其作用是为了给后面的迭代保留优化空间。大家想想假如一棵树把损失函数降得很低很低，那么后续的优化空间就少了，训练的样本和特征也就少了，最后也就overfitting
  • 传统GBDT以CART作为基分类器，xgboost还支持线性分类器

总结

  • Loss上的优化，引入泰勒二阶，对自定义loss方法比较好；精度也比较高（二阶梯度）；同时推导出来是二阶函数(极致只和一阶二阶梯度有关系)，计算上快很多O(1)负责度；同时加上了以树复杂度相关的正则项
  • 算法对树的分裂上面：精准分裂用了pre-sort技巧。近似分裂大大提高了效率
  • 工程上：比如缓存(block)的考虑，数据压缩存储，树内多特征分化并行等