XGBoost

总结

• 在GBDT的基础上加了诸多创新点和工程化的东西达到了可以快速、分布式训练的目的
• 首先通过层层推导，利用泰勒展开的二阶项信息得到了一个判断分割点收益的方程：$$L_{split}=\frac{1}{2}[\frac{\sum _{i\in I_L}{g}_i^2}{\sum _{i\in I_L}(h_i+\lambda )}+\frac{\sum _{i\in I_R}{g}_i^2}{\sum _{i\in I_R}(h_i+\lambda )}-\frac{\sum _{i\in I}{g}_i^2}{\sum _{i\in I}(h_i+\lambda )}]-\gamma$$
• 提出了两个防止过拟合的方法
  • 新训练出的树所给出的预测结果需要乘上shrinkage因子再加到森林中去
  • 对于特征（列）做采样（等同于RF中的方法）
• 介绍了两种找最佳分割点的方法
  • 枚举所有分割点，然后找出最佳
  • 利用二阶导数信息当做权重，然后根据权重值来进行等权重划分，划分点即为分割点的候选点，然后依次遍历，此种方法可以应用于分布式计算
• 针对于稀疏数据，提出了学习default路径的思路，在枚举分割点的时候，将缺失的信息归到两个分支的其中一个，比较效果后决定default路径的方向
• 文章的工程化创新思路也非常多
  • 针对树训练中所需的大量排序操作设计了Block结构，把每个特征按照特征值排序，存成索引。这样可以在计算前完成排序工作
  • 文章还针对CPU的cache机制进行了存储优化，主要是使CPU的访问地址尽量连续
  • 在内存不足时，设计了Out-of-core机制，过多的数据先写在硬盘上，在要用的时候由一个独立的线程预先加载进来，加大了训练数据的最大规模。在此基础上加入了，内容压缩，存储块共享技术，对训练过程提速
• 补充一些与传统GBM的区别
  • 使用了泰勒展开二阶项信息（牛顿法）计算下降方向
  • 不搜索步长
  • 加入正则项
  • 可以并行处理
  • 内置缺失值处理规则
  • 使用后剪枝而非预剪枝（GBM）

ABSTRACT

We propose a novel sparsity-aware algorithm for sparse data and weighted quantile sketch for approximate tree learning.

INTRODUCTION

factor of success is scalability in all scenarios

• a novel tree learning algorithm is for handling sparse data
• a theoretically justified weighted quantile sketch procedure enables handling instance weights in approximate tree learning
• We propose an effective cache-aware block structure for out-of-core tree learning.

we also make additional improvements in proposing a regularized learning objective

TREE BOOSTING IN A NUTSHELL

Regularized Learning Objective

$$L(\varphi )=\sum _{i}l(\widehat{y_i},y_i)+\sum _k\mathrm{\Omega }(f_k)$$

Where $\mathrm{\Omega }(f_k)=\gamma T+\frac{1}{2}\lambda ||w|{|}^2$
It penalizes the complexity of the model to avoid over-fitting

Gradient Tree Boosting

The model is trained in an additive manner:

$$L^{(t)}=\sum _{i=1}^{n}l(y_i,{\widehat{y_i}}^{(t-1)}+f_t(x_i))+\mathrm{\Omega }(f_t)$$

Second-order approximation can be used to quickly optimize the objective:

$$L^{(t)}=\sum _{i=1}^n[l(y_i,{\hat{y}}^{(t-1)})+g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\mathrm{\Omega }(f_t)$$

where $g_i={\partial }_{{\hat{y}}^{(t-1)}}l(y_i,{\hat{y}}^{(t-1)})$ and $h_i={\partial }_{{\hat{y}}^{(t-1)}}^{2}l(y_i,{\hat{y}}^{(t-1)})$

define $I_j=\{i|q(x_i)=j\}$ as the instance set of leaf j, we rewrite L as follows:

$${\tilde{L}}^{(t)}=\sum _{j=1}^T[(\sum _{i\in I_j}{g}_i)w_j+\frac{1}{2}(\sum _{i\in I_j}{h}_i+\lambda )w_j^2]+\gamma T$$

for a fixed structure q(x), we can compute the optimal weight $w_j^{\ast }$ of j (set derivative of $w_j$ to 0):

$$w_j^{\ast }=-\frac{\sum _{i\in I_j}{g}_i}{\sum _{i\in I_j}{h}_i+\lambda }$$

and calculate the corresponding optimal value by:

$${\tilde{L}}^{(t)}=-\frac{1}{2}\sum _{j=1}^T\frac{\sum _{i\in I_j}{g}_i^2}{\sum _{i\in I_j}{h}_i+\lambda }+\gamma T$$

This equation can be used as a scoring function to measure the quality of a tree structure q

We can also give the function of the loss reduction after the split:

$$L_{split}=\frac{1}{2}[\frac{\sum _{i\in I_L}{g}_i^2}{\sum _{i\in I_L}(h_i+\lambda )}+\frac{\sum _{i\in I_R}{g}_i^2}{\sum _{i\in I_R}(h_i+\lambda )}-\frac{\sum _{i\in I}{g}_i^2}{\sum _{i\in I}(h_i+\lambda )}]-\gamma$$

Shrinkage and Column Subsampling

Prevent over-fitting:

• shrinkage
• column (feature) sub-sampling (better than row sub-sampling)

SPLIT FINDING ALGORITHMS

Basic Exact Greedy Algorithm

Approximate Algorithm

To support effective gradient tree boosting in:

• the data dose not fit entirely into memory
• distributed setting

we need an approximate algorithm:

• first proposes candidate splitting points according to percentiles of feature distribution
• then maps the continuous features into buckets split by these candidate points
• aggregates the statistics and finds the best solution among proposals based on the aggregated statistics

Weighted Quantile Sketch

define rank function:

the goal is to find candidate split points $\{s_{k1},s_{k2},\dots ,s_{kl}\}$, such that:

$$|r_k(s_{k,j})-r_k(s_{k,j+1})|<ϵ$$$$s_{k,1}=\underset{i}{min}{x}_{ik},s_{k,l}=\underset{i}{max}{x}_{ik}$$

where $ϵ$ is an approximation factor

Sparsity-aware Split Finding

We propose to add a default direction in each tree node

The key improvement is to only visit the non-missing entries $I_k$

SYSTEM DESIGN

Column Block for Parallel Learning

Cache-aware Access

we allocate an internal buffer in each thread, fetch the gradient statistics into it, and then perform accumulation in a mini-batch manner.

Blocks for Out-of-core Computation

During computation, it is important to use an independent thread to pre-fetch the block into a main memory buffer

It is important to reduce the overhead and increase the throughput of disk IO

We mainly use two techniques to improve the out-of-core computation:

• Block Compression
• Block Sharding

RELATED WORKS

END TO END EVALUATIONS

System Implementation

skip

Dataset and Setup

skip

Classification

Learning to Rank

Out-of-core Experiment

Distributed Experiment

It is able to take advantage of out-of-core computing and smoothly scale to all 1.7 billion examples

CONCLUSION

skip