XGBoost之分位点算法

2018-05-08 本文已影响550人只为此心无垠

一、综述XGBoost

很多方法并非XGBoost第一次提出，当然也不是说XGBoost没改进，可以说XGBoost把算法和系统实现都做得淋漓尽致

1、系统实现

决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

2、算法

XGBoost利用泰勒公式将目标函数的作用发挥到极致。
目标函数了树生成，叶子节点分数和叶子节点分裂等等方方面面。
决策树的学习过程就是为了找出最优的决策树，然而从函数空间里所有的决策树中找出最优的决策树是NP-C问题，所以常采用启发式（Heuristic）的方法，如CART里面的优化GINI指数、剪枝、控制树的深度。这些启发式方法的背后往往隐含了一个目标函数，这也是大部分人经常忽视掉的。

二、分位点算法 -- quantile sketch

XGBoost则采取了一种trade off，近似地找到best split，就是标题的一种weighted quantile sketch算法。既然样本数量太大，我们可不可以按比例来选择，从n个样本中抽取k个样本来进行计算，取k个样本中的最优值作为split value，这样就大大减少了运算数量。这就是k分位点选取的思想，即quantile sketch。

三、按权重的分位点算法 -- weighted quantile sketch

1、来源（为什么）

要如何抽取k个样本？10000个样本取10个的话，每1000个样本计算一次split value看似可行，其实是不可以的，我们要均分的是loss，而不是样本的数量，而每个样本对loss的贡献可能是不一样的，按样本均分会导致loss分布不均匀，取到的分位点会有偏差。
回忆loss function的早期形式：

对其变形得到：

这个形式的loss说明了, xi的loss也可以看做是以−gi/hi作为label的均方误差，乘以大小为hi的权重，换句话说，xi对loss的贡献权重为hi。
那么，对loss取k分位点就是对误差的均分

2、具体划分策略

那么具体划分策略如何计算？paper提出了一个weighted quantile sketch，即将样本对应的残差二阶导h作为划分依据，将同范围h占比的特征值划分到同一范围内。

这里讲的占比即排序函数r(z)，特征x小于z的样本中二阶导的总和占比，另外s为划分节点。h相当于是一个加权系数weight，不同于权重为1的情况（即每个范围有相同的样本数），残差二阶导差异越大的地方，样本分布越稀疏，反之则稠密。个人理解，其加权的意义在于，把候选节点选取的机会更多地让于二阶导更大的地方，同时忽略导数差异小的节点。

3、应用

流程如下：

不同于基本的穷举算法，paper指出两种近似算法：一种是全局算法，即在初始化tree的时候划分好候选节点，并且在树的每一层都使用这些候选节点；另一种是局部算法，即每一次划分的时候都重新计算候选节点。这两者各有利弊，全局算法不需要多次计算候选节点，但需要一次获取较多的候选节点供后续树生长使用，而局部算法一次获取的候选节点较少，可以在分支过程中不断改善，即适用于生长更深的树，两者在effect和accuracy做trade off。

局部算法：这个k分位点的选取是近似的，不能像遍历一样保证取到的split value是最佳的split value。不过经过试验，k取到3的时候，算法性能就已经相差无几了，见下图：