GBDT(Gradient Boosting Decision Tree):梯度提升决策树 是一种集成使用多个弱分类器(决策树)来提升分类效果的机器学习算法,在很多分类和回归的场景中,都有不错的效果。
如图1所示,这是是对一群消费者的消费力进行预测的例子。简单来说,处理流程为:
如图2所示,为了优化算法性能,在参数服务器上,需要存储如下几个参数矩阵,包括:
所有这些参数矩阵,在整个GBDT的计算过程中,都会被反复更新和传递。
GBDT的流程包括几大步骤
反复调用这几个步骤,直到完成所有树的建立,如果训练完所有决策树,计算并输出性能指标(准确率、误差等),输出训练模型。
其中,第3个步骤,寻找最佳的分裂点和分裂树节点,是最难和最重要的环节,所以我们单独讲。
如何寻找最佳分裂点,并进行分裂,是GBDT的精髓和难点,而且也是参数服务器对它的重要意义所在。整体流程为:
计算梯度直方图: 从待处理树节点的队列中取出待处理的树节点,在Worker上,根据本节点的训练数据计算局部梯度直方图(包括一阶和二阶)。
同步&合并直方图: Worker通过PS接口,将局部梯度直方图推送到参数服务器。在发送之前,每个局部梯度直方图被切分为P个分块(P为参数服务器节点的个数),每个分块分别被发送到对应的参数服务器节点。PS节点在接收到Worker发送的局部梯度直方图后,确定处理的树节点,将其加到对应的全局梯度直方图上
寻找最佳分裂点: Worker使用参数服务器提供的的计算最佳分裂点的接口,从参数服务器获取每个参数服务器节点上的最佳分裂点,然后比较P个分裂点的目标函数增益,选取增益最大的分裂点作为全局最佳分裂点。
分裂树节点: Worker根据计算得到的最佳分裂点,创建叶子节点,将本节点的训练数据切分到两个叶子节点上。如果树的高度没有达到最大限制,则将两个叶子节点加入到待处理树节点的队列。
从上面的算法逻辑剖析可以看出,GBDT这个算法,存在这大量的模型更新和同步操作,非常适合参数服务器的系统架构。具体来说,包括:
超大模型: GBDT用到的梯度直方图的大小与特征数量成正比,对于高维大数据集,梯度直方图会非常大,Angel将梯度直方图切分到到多个PS节点上存储,有效解决了高维度模型在汇总参数时的单点瓶颈问题。
两阶段树分裂算法: 在寻找最佳分裂点时,在多个PS节点上并行处理,只需要将局部最佳分裂点返回给Worker,通信开销几乎可以忽略不计。
整体来看,Angel的PS优势,使得它在这个算法上,性能远远超越了Spark版本的GBDT实现,也显著优于MPI版本的xgBoost。
算法参数
输入输出参数
资源参数
训练任务启动命令示例
angel-submit
-Dangel.am.log.level=INFO
-Dangel.ps.log.level=INFO
-Dangel.worker.log.level=INFO
-Dangel.app.submit.class=com.tencent.angel.ml.GBDT.GBDTRunner
-Daction.type=train
-Dml.data.type=libsvm
-Dml.model.type=T_FLOAT_DENSE
-Dml.data.validate.ratio=0.1
-Dml.feature.index.range=10000
-Dml.gbdt.cate.feat=none
-Dml.gbdt.tree.num=20
-Dml.gbdt.tree.depth=7
-Dml.gbdt.split.num=10
-Dml.gbdt.sample.ratio=1.0
-Dml.learn.rate=0.01
-Dml.gbdt.server.split=true
-Dangel.compress.bytes=2
-Dangel.train.data.path=$input_path
-Dangel.save.model.path=$model_path
-Dangel.workergroup.number=50
-Dangel.worker.memory.gb=10
-Dangel.task.data.storage.level=memory
-Dangel.worker.task.number=1
-Dangel.ps.number=50
-Dangel.ps.memory.gb=10
angel-submit
-Dangel.am.log.level=INFO
-Dangel.ps.log.level=INFO
-Dangel.worker.log.level=INFO
-Dangel.app.submit.class=com.tencent.angel.ml.GBDT.GBDTRunner
-Daction.type=predict
-Dml.data.type=libsvm
-Dml.model.type=T_FLOAT_DENSE
-Dml.data.validate.ratio=0.1
-Dml.feature.index.range=10000
-Dml.gbdt.tree.num=20
-Dml.gbdt.tree.depth=7
-Dml.gbdt.sample.ratio=1.0
-Dml.learn.rate=0.01
-Dangel.predict.data.path=$input_path
-Dangel.save.model.path=$model_path
-Dangel.predict.out.path=$predict_path
-Dangel.workergroup.number=50
-Dangel.worker.memory.gb=10
-Dangel.task.data.storage.level=memory
-Dangel.worker.task.number=1
-Dangel.ps.number=50
-Dangel.ps.memory.gb=10
评测腾讯的内部的数据集来比较Angel和XGBoost的性能。
数据集 | 数据集大小 | 数据数量 | 特征数量 | 任务 |
---|---|---|---|---|
UserGender1 | 24GB | 1250万 | 2570 | 二分类 |
UserGender2 | 145GB | 1.2亿 | 33万 | 二分类 |
实验的目的,是预测用户的性别。数据集 UserGender1 大小为24GB,包括1250万个训练数据,其中每个训练数据的特征纬度是2570;数据集 UserGender2 大小为145GB,包括1.2亿个训练数据,其中每个训练数据的特征纬度是33万。两个数据集都是高维稀疏数据集。
实验环境
实验所使用的集群是腾讯的线上Gaia集群(Yarn),单台机器的配置是:
参数配置
Angel和XGBoost使用如下的参数配置:
* 树的数量:20
* 树的最大高度:7
* 梯度直方图大小:10
* 学习速度:0.1(XGboost)、0.2(Angel)
* 工作节点数据:50
* 参数服务器数量:10
* 每个工作节点内存:2GB(UserGender1)、10GB(UserGender2)
实验结果
系统 | 数据集 | 训练总时间 | 每棵树时间 | 测试集误差 |
---|---|---|---|---|
XGBoost | UserGender1 | 36min 48s | 110s | 0.155008 |
Angel | UserGender1 | 25min 22s | 76s | 0.154160 |
XGBoost | UserGender2 | 2h 25min | 435s | 0.232039 |
Angel | UserGender2 | 58min 39s | 175s | 0.243316 |
参考文献
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。