FrankLearningMachine作者

大规模GBDT系统应用场景及效果对比(LightGBM,XgBoost,DimBoost等)

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.

机器学习blog
机器学习blog

本专栏专注于机器学习(主要包含但不限于深度学习)相关知识分享,其中涉及自然语言处理以及图像处理前沿论文等,欢迎大家关注交流

理论DimBoosXGBoostLightGBMGBDT
3
相关数据
数据分析技术

数据分析是一类统计方法,其主要特点是多维性和描述性。有些几何方法有助于揭示不同的数据之间存在的关系,并绘制出统计信息图,以更简洁的解释这些数据中包含的主要信息。其他一些用于收集数据,以便弄清哪些是同质的,从而更好地了解数据。 数据分析可以处理大量数据,并确定这些数据最有用的部分。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

分类数据技术

一种特征,拥有一组离散的可能值。以某个名为 house style 的分类特征为例,该特征拥有一组离散的可能值(共三个),即 Tudor, ranch, colonial。通过将 house style 表示成分类数据,相应模型可以学习 Tudor、ranch 和 colonial 分别对房价的影响。 有时,离散集中的值是互斥的,只能将其中一个值应用于指定样本。例如,car maker 分类特征可能只允许一个样本有一个值 (Toyota)。在其他情况下,则可以应用多个值。一辆车可能会被喷涂多种不同的颜色,因此,car color 分类特征可能会允许单个样本具有多个值(例如 red 和 white)。

数据管理技术

数据管理是利用计算机硬件和软件技术对数据进行有效的收集、存储、处理和应用的过程,其目的在于充分有效地发挥数据的作用。

XGBoost技术

XGBoost是一个开源软件库,为C ++,Java,Python,R,和Julia提供了渐变增强框架。 它适用于Linux,Windows,MacOS。从项目描述来看,它旨在提供一个“可扩展,便携式和分布式的梯度提升(GBM,GBRT,GBDT)库”。 除了在一台机器上运行,它还支持分布式处理框架Apache Hadoop,Apache Spark和Apache Flink。 由于它是许多机器学习大赛中获胜团队的首选算法,因此它已经赢得了很多人的关注。

推荐文章
暂无评论
暂无评论~