β

xgboost算法和工程

点我达技术 116 阅读

理论

监督学习三要素

模型和参数

模型指给定输入Xi如何去预测 输出 Yi。 我们比较常见的模型如线性模型(包括线性回归和logistic regression)采用了线性叠加的方式进行预测 。这里的预测y可以有不同的解释,比如我们可以用它来作为回归目标的输出,或者进行sigmoid 变换得到概率,或者作为排序的指标等。而一个线性模型根据y的解释不同(以及设计对应的目标函数)用到回归,分类或排序等场景。 参数指我们需要学习的东西,在线性模型中,参数指我们的线性系数w。

目标函数:代价 + 正则

模型和参数本身指定了给定输入我们如何做预测,但是没有告诉我们如何去寻找一个比较好的参数,这个时候就需要目标函数登场了。一般的目标函数包含下面两项 前者称为代价函数,评估模型有多拟合训练数据,又称为经验风险。(对于单条记录,真实值和预测值之间的差异,我们叫做损失函数;对于整个样本,我们称之为代价函数。) 后者称为正则函数,度量模型的复杂度,又称为结构风险。 常见的误差函数有 比如平方误差 ,logistic误差函数 等。而对于线性模型常见的正则化项有L2正则和L1正则。

目标函数就是要最优化经验风险和结构风险。

优化算法

就是给定目标函数之后怎么高效学习的问题。比如CART树的分枝和剪枝问题。

Boosted Tree

就是不断的生成树的过程,最终将这些树组合成最终的模型。但是后一棵树根节点的数据是真实值与前面所有的树预测的值的差异。 比如要做一个年龄预测的模型,简单起见训练集只有4个人A,B,C,D,树的最大深度为2。

训练后会得到的模型是多棵树,每棵树有若干叶子节点,每个叶子节点对一个分数, 假如来了一个样本,根据这个样本的特征,在每棵树上会落到对应一个叶子节点, 总分数就是把落到的叶子节点的分数加起来,作为预测值。 直观的感受就是 每一轮新的预测,是上次预测值+本次学习的函数。

于是对应监督学习的三要素之中的模型和目标函数 上面只是抽象的,那么要实现一个这样的算法,我们要知道: 1、树是什么类型的树?
2、怎么生长一棵树?怎么分枝?
3、树什么时候停止生长?
4、确定了一棵树之后,怎么求叶子节点的权重?

Xgboost

传统GBDT以CART作为基分类器,xgboost还支持线性分类器,这个时候xgboost相当于带L1和L2正则化项的逻辑回归(分类问题)或者线性回归(回归问题)。本文主要讨论CART类型的xgboost。

CART采用一种二分递归分割的技术,将当前的样本集分为两个子样本集,使得生成的的每个非叶子节点都有两个分支。因此,CART算法生成的决策树是结构简洁的二叉树。它既可以用于分类,也可以用于回归问题。
树的定义:

用保存有叶子节点的权重的向量来表示一颗树,叶子节点的索引定义在树结构里面。q代表树结构,输入一个样本的特征给q,会落到唯一对应的叶子节点,返回该叶子节点的编号。w代表叶子权重,输入一个叶子节点编号给w,返回对应的权重。

树的复杂度的定义: 树的复杂度由叶子节点数量以及对应权重的平方和组成。上面这个并不是唯一的树的复杂度定义,只要是满足L2范数的表达式都能作为树的复杂度。 到此,就回答了 第一个问题——树是什么类型的树

然后我们看下 第二个问题——树要怎么分裂 ? 这要从目标函数讲起。 假如穷举所有可能的分裂点(遍历每一个特征和特征值)和分裂方向,我们可以得到N课树,每一颗树都能计算出目标函数的值,其中目标函数值最小的树就是我们要的最优树。 但是这样做太慢、太消耗资源。 我们采取贪心算法来生长一棵树,每次找一个最优的特征进行分裂,每个特征是寻找最优点进行分裂,直到到达一定的深度或者不能再分裂(分裂后损失值更大)。

那么什么是最优特征?最优分裂点? 以目标函数值为标准,对比分裂前和分裂后的最小目标函数值。增益(分裂后的代价函数的值减去分裂前的代价函数)最大的点为最优点,对应的特征为最优特征。 具体的做法就是,每一次选特征时,遍历所有特征,求出每个特征对应的最佳分裂点。 把增益最大的特征和分裂点作为下一次特征分裂。

当分裂之后的增益比分裂之前的增益更小时,或者达到了自定义的树的最大深度时,停止生长。这就是 问题三——树什么时候停止生长 。 从这也可以看出xgboost可以很方便做预剪枝。因为每次都计算分裂前后的增益,当增益小于我们自定义的某个值时,停止分裂。(预剪枝)

问题四——怎么求每棵树的叶子节点的权重 ? 根据泰勒二级展开近似目标函数 目标函数变形 其中I被定义为每个叶子上面样本集合。可以看到,T个叶子节点的权重是未知项,其他都是已知的。 要使Obj最小,相当于求Wj的一元二次方程的最小值问题。

boosted算法概述
整个算法的理解如下:

a 每次迭代添加一棵树
b 每次迭代前,求出上次预测损失函数一阶导数和二阶导数的函数值
c 根据分裂增益最大化,去生长这棵树
d 把新的树添加到原来模型(新的树可以乘上一个系数,防止过拟合,这个系数就是自己传进来的eta参数,学习速率)

工程

单机多线程

learner->InitModel()、learner->Configure初始化Model,确定目标函数和模型,初始化目标函数结构体和模型。模型可以是gbtree或GBLinear的。
根据模型参数param.num round迭代调用UpdateOneIter()来建树。 UpdateOneIter有4步,分别是懒加载数据(转为以列为基础的结构),上一步的预测值,目标函数的一阶导数、二阶导数以及DoBoost建树。
其中DoBoost又分为BoostNewTrees(生成多棵树,由参数中的num
parallel_tree决定) 和 CommitModel(将多棵树提交到模型,随机森林的思想得到这一次迭代的树)

然后我们看下BoostNewTrees生成树的过程。 ColMaker继承于TreeUpdater,是单机多线程建树的实现过程。
为了实现多线程定义了三个结构体:ThreadEntry、NodeEntry、Builder。 ThreadEntry结构体用于多线程中单个线程内的样本统计,一个线程拥有一个ThreadEntry 变量。
NodeEntry 用于一个树节点,所拥有的样本的统计信息。一个节点在分列前,需要将自己的样本分给不同的线程进行处理,最后得到多个ThreadEntry 变量,汇总到每个节点自己的NodeEntry 变量中。

多线程使用的是OpenMP,遍历所有的特征,每个特征一个线程,找到该特征最大增益的分割点,这一部分是并行的。最后通过SyncBestSolution来汇总所有线程,找到最优的特征和分割点。直到达到树的最大深度。

在线程内部,会先将数据排序并分块,如果数量较小调用EnumerateSplit方法。也就是一个特征只有一个线程。但是它不是遍历每个特征,而是有一个步长,每隔一个步长取一个特征值作为split point。一个split point将样本分为两个子集,然后计算左右子集的增益和权重。选出最优split point。

如果数据量大则使用ParallelFindSplit,每一个块对应一个线程。 a 在每个线程里汇总各个线程内分配到的数据样本的统计量(grad/hess);
b aggregate所有线程的样本统计(grad/hess),计算出每个线程分配到的样本集合的边界特征值作为split point的最优分割点;
c 在每个线程分配到的样本集合对应的特征值集合进行枚举作为split point,选出最优分割点;
d 最后通过SyncBestSolution来汇总所有线程,找到最优的特征和分割点。

分布式实现

陈天奇博士一开始的目标基本总结下来就是,速度快,可移植,少写代码。

速度快是自然的目标,体现这个目标的一个的想法是在写的似乎机器内部依然沿用单机多线程的优化来减少通信,只在机器之间来进行通信。

可移植性是一个更大的困难,要做分布式机器学习必须有分布式的通信框架。要想要让分布式程序可以运行在不同的环境下比起让一个单机机器学习程序从linux移植到windows困难许多。但是其实本质上,这个东西和把linux移植到windowss又没有差别。之所以一个程序可以从linux移植到windows,是因为程序仅仅依赖一些系统调用的接口,而我们只需要在每个平台下面提供一套这类接口就可以了。同样的,根据算法本身的需求,抽象出合理的接口,通过通用的库让平台往接口需求上面去走,就有可能实现一个分布式的通信框架。最后选择了Allreduce。 MPI_Allreduce将规约值结果分发到所有进程
假设有4个节点,每个节点有一个长度为2的一维数组a,然后发送一个sum求和的指令。它会将所有节点的a[0]求和,a[1]求和,然后发送到所有的节点上,这样所有的节点保存的是同样的东西。

我们将训练集repartition为N个分区,起N个机器,每个机器处理一个分区,对于一个特征来说,每个分区都能找到一个最佳分割点,然后allreduce一下,那么每一台机器就会得到其他所有的机器的结果,然后更新自己机器上的模型,这样每台机器上的模型都是一样的。

Rabit(Reliable Allreduce and Broadcast Interface)是一个可容错的Allreduce,保留了Allreduce和Broadcast,底层是通过socket通讯。说它可容错是因为它为所有的节点设计了一个环状结构,假如某个节点down掉了可以通过ring replication strategy从相邻的节点恢复。
在yarn上的实现是

1 当一个xgboost任务提交到yarn上时,先在driver端启动一个RabitTracker,RabitTracker提供N个end point给worker连接。
2 然后通过yarnclient向RM请求资源来创建AM。
3 RM先在NM上创建一个container,并在这个container里面启动任务的AM。
4 AM根据资源配置向RM请求具体执行的容器。
5 AM申请到容器之后,会将boost程序发送到容器并启动,同时管理这些容器。
6 每一个xgboost通过rabit框架和rabitTracker通信完成注册,rabitTracker将这些rabit编号并形成环形网络结构。
7那么AM监控和管理容器的运行情况,rabittracker协调xgboost的运作。

RabitTracker过执行dmlc-core工程下的tracker.py来创建。具体做得事:
1启动daemon线程,提供worker结点注册联接所需的end point,所有的worker结点都可以通过与Tracker程序通信来完成自身状态信息的注册。
2 co-ordinate worker结点的执行:
为worker结点分配Rank编号。 基于收到的worker注册信息完成环形网络结构的构建,并广播给worker结点,以确保worker结点之间建立起合规的网络拓扑。 当所有的worker结点都建立起完备的网络拓扑关系以后,就可以启动计算任务监控整个执行过程。

参考了很多资料,但是还是只有个大概印象,具体的实现还是要看源码,权当做个记录吧。肯定有很多不对的地方,欢迎批评指正!

作者:点我达技术
<h2 id="">前言</h2> <p>在上一篇文章<a href="http://blog.5udou.cn/blog/You-formBiao-Dan-Lai-Shuo-Shuo-Qian-H
原文地址:xgboost算法和工程, 感谢原作者分享。

发表评论