An Experimental Evaluation of Large Scale GBDT Systems
Fangcheng Fu, Jiawei Jiang, Yingxia Shao, Bin Cui
Peking University, Beijing University of Posts and Telecommunications, Tencent
VLDB 2019
https://arxiv.org/pdf/1907.01882.pdf
GBDT是一种广泛应用的机器学习算法，该算法不仅广泛应用于数据分析竞赛中，而且在工业界也广泛应用。由于数据量的快速增长，部分研究人员试图利用分布式来训练GBDT，进而支撑大规模工作负载。
然而，现有系统在管理训练数据方面方式各异，而且他们都未曾研究数据管理所带来的影响。这篇文章旨在研究多种数据管理方法的优劣，并对这些分布式GBDT的性能进行比较。
这篇文章基于数据分区和数据存储对数据管理策略进行了象限划分。然后进行深度系统分析，并对各个象限的适用场景进行总结。基于以上分析，这篇文章提出一种新的分布式GBDT系统，名曰Vero，该系统采用了纵向分区和行式存储，这种组合适用于很多大规模数据的情景。
为了验证本文的分析，作者们基于同样代码实现了多个象限，并且在大量工作负载下对比了这些象限，最终在多个数据集上将Vero跟其他STOA系统进行对比。
根据本文的理论分析和实验结果，在给定工作负载的前提下，可以对如何选择适当的数据管理方式进行指导。
上面所提到的纵向分区即为基于特征的类别对数据进行列式分区，而横向分区即为按样本进行分区。而所谓行式存储即为以(特征下标, 特征值)对的方式进行存储，即Compressed Sparse Row (CSR) 格式，而列式存储即为以(样本下标, 特征值)对的方式进行存储，即Compressed Sparse Column (CSC)格式。
几种方法对应的象限如下
XGBoost是横向分区，列式存储的，即按样本进行分区，并且每个样本的所有特征存在一起; LightGBM和DimBoost是横向分区，行式存储的，即按样本进行分区，并且每个样本的特征是按(特征下标，特征值)对存储的，并不是一个样本的所有特征都在一个分区；Yggdrasil是纵向分区，列式存储的，即按特征进行分区，并且样本的同一个特征存在一起
GBDT结构图示如下
小知识点1：LogitBoost会利用二阶泰勒展开。
小知识点2：ID3 利用熵决定分割点，CART利用基尼系数决定分割点。
对于每个特征如何选择分割点有多种方法，比较常用的是基于直方图的方法，图示如下
小知识点3: 直方图分割的初始分割常用的方法是基于分位数。
小知识点4: 父节点的梯度等于两个叶节点的梯度之和，因此，右子节点的梯度可以用父节点的梯度减去左子节点的梯度。
横向分区时构建直方图和最佳分割的通信方法图示如下
纵向分区情形下计算直方图和最优分割的通信方式图示如下
行存储与列存储的区别如下
直方图的规模跟三个因素相关
1 特征数(D) 由于直方图需要计算一阶梯度和二阶梯度，所以直方图的规模跟2D呈正比
2 候选分割的个数(q) 跟候选分割个数q呈正比
3 类别数(C) 跟类别数C呈正比
横向分区时每个worker都需要计算所有特征的直方图，所需存储空间为
而纵向分区时，每个worker只需要计算一部分特征的直方图，所需存储空间为
横向分区时通信成本为
主要耗在各个worker之间通信直方图
纵向分区时通信成本为
示例对比如下
不同的index方法对比图示如下
列式节点到实例的索引更新图示如下
不同象限适用场景对比如下
Vero概览如下
其中横向分区转为纵向分区需要五步
1 针对每个特征计算分位数
2 生成候选分割
3 列分组
4 列分组重分区
5 广播样本标签
列组成块与二阶段索引图示如下
不同象限对比图如下
其中包含了样本数的影响，特征维度的影响，树深度的影响，类别数的影响，存储空间的对比等。
数据集信息统计如下
不同数据集上几种方法的耗时对比如下
几种方法的效果对比图示如下
小知识点5：DimBoost是用Java实现的，而XGBoost 和 LightGBM是C++实现的
小总结：LightGBM 比较适用于低维数据集，Vero 比较适用于高维或多分类数据集。
环境及资源如下
每个机器64GB RAM, 24 cores， 10Gbps Ethernet.
20GB memory，10 cores for each container
数据集
年龄分为9段
年龄模型和性别模型特征数有33万
口味偏好有100个标签，特征数有1万5千
小知识点6：LightGBM由于环境限制不适用于生产环境， 没有跟hadoop集成
三个工业级数据集上的效果对比如下
每个树的运行时间对比如下
数据加载及预处理耗时对比如下
机器数的影响如下
低维数据集上几种方法速度对比如下
跟LightGBM速度对比如下
XGBoost对应的论文为
Xgboost: A scalable tree boosting system. SIGKDD 2016
代码地址
https://github.com/dmlc/xgboost
特性
Scalable, Portable and Distributed Gradient Boosting (GBDT, GBRT or GBM) Library, for Python, R, Java, Scala, C++ and more. Runs on single machine, Hadoop, Spark, Flink and DataFlow
DimBoost对应的论文为
Dimboost: Boosting gradient boosting decision tree to higher dimensions, ICMD 2018
LightGBM对应的论文为
Lightgbm: A highly efficient gradient boosting decision tree, NIPS 2017
代码地址
https://github.com/Microsoft/LightGBM
简介
A fast, distributed, high performance gradient boosting (GBT, GBDT, GBRT, GBM or MART) framework based on decision tree algorithms, used for ranking, classification and many other machine learning tasks. It is under the umbrella of the DMTK(http://github.com/microsoft/dmtk) project of Microsoft.
