【三部曲02】从GBDT到XGBoost

参考文献引用来源：

1.
2.
3.Chen T , Guestrin C . XGBoost: A Scalable Tree Boosting System[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016.
4.
5.

Question1. 从论文本身表述看，xgboost有哪些工作点？

【1】设计和构建高度可扩展的端到端提升树系统。
【2】提出了一个理论上合理的加权分位数略图。 这个东西就是推荐分割点的时候用，能不用遍历所有的点，只用部分点就行，近似地表示，省时间。
【3】引入了一种新颖的稀疏感知算法用于并行树学习。 令缺失值有默认方向。
【4】提出了一个有效的用于核外树形学习的缓存感知块结构。 用缓存加速寻找排序后被打乱的索引的列数据的过程。
除了这些主要的贡献之外，还提出了一个改进正则化学习的方法。

Question2. 相较于GBDT，xgboost在算法层面的改进点有哪些？

【1】改进残差函数，不用Gini作为残差，用二阶泰勒展开+树的复杂度（正则项）
带来如下好处：
1.可以控制树的复杂度
2.带有关于梯度的更多信息，获得了二阶导数
3.可以用线性分类器

【2】采用预排序
因为每一次迭代中，都要生成一个决策树，而这个决策树是残差的决策树，所以传统的不能并行；
但是陈天奇注意到，每次建立决策树，在节点的时候，比如选中A特征，就要对A进行排序，再计算残差，这个花很多时间。于是陈天奇想到： 每一次残差计算好之后，全部维度预先排序，并且此排序是可以并行的；并行排序好后，对每一个维度，计算一次最佳点，求出对应的残差增益，于是只要不断选择最好的残差作为点就可以。

也就是说：虽然森林的建立是串行的没有变，但是每一颗树的建立变成并行的了

这样带来的好处：
1.点的计算可并行了，不需要等到一个特征的算完再下一个了；
2.每层可以并行：当点的计算可以并行，对每一层，比如了左儿子和右儿子，那么在这两个儿子上哪个特征及其增益也计算好了；

【3】Shrinkage（缩减）
相当于学习速率（XGBoost中的eta）。XGBoost在进行完一次迭代时，会将叶子节点的权值乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。（GBDT也有学习速率）

【4】列抽样
XGBoost借鉴了随机森林的做法，支持列抽样，不仅防止过 拟合，还能减少计算。

Question3. xgboost具体内容

首先我们知道：
在GBDT中，针对的是损失函数进行的梯度计算；
而在xgboost中，是对误差函数进行了泰勒二阶展开，并且添加了正则化项。

需要强调的是：
1.等式右侧第二项的正则项，作用只是用于迭代时防止模型fk出现过拟合，其并不出现在模型集成中！
2.此外，XGBoost要求损失函数L 至少是二阶连续可导的凸函数。因为后面的计算要用到它的一阶和二阶导数

我们将上面加了正则项的目标函数中的损失函数部分进行二阶泰勒展开 ，则有：

这样展开后，由于第一项对于第t次迭代来说是常数，因此在优化过程中是可以去掉的，这样目标函数就变为：

可以这么理解：
就是说一共n个样本，我们当然可以对每一个样本计算设定的损失函数值，这样n个样本的损失函数值加起来自然就是目标损失函数值；但是从另一个角度，n个样本最终是要分到T个叶子结点的，既然我们可以从样本的角度进行损失函数值的统计，那么我们当然可以从叶子结点的角度进行损失函数的统计，这种统计就是（4）中下面的式子的表示形式：即分别对于每一个叶子结点，统计划分到该节点的样本所产生的损失函数值；

附：关于上面公式中的参数说明：
（1）数据集是n*m的，就是有n个数据，每个数据有m维特征；
（2）F就是组合成的回归树模型，共k棵树组成了F；
（3）每棵树fk有T片叶子，γ是这一项的系数，λ是所有叶子节点的输出值的L2正则之和的系数。当正则项系数为0时（即γ和λ为0时），整体的目标就退化为了GBDT；
（4）gi为函数Fm-1关于样本xi的一阶导数，h为函数Fm-1关于样本xi的二阶导数；
（5）ωj为第j个叶子结点的输出值；

注：关于这个二阶泰勒展开形成的目标公式，陈天奇的解释：

他说：这个目标函数有一个很明显的特点，那就是只依赖于每个数据点的在目标函数上的一阶和二阶导数，有人可能会问，这个形式似乎比我们之前学过的决策树学习难懂。为什么要花这么多力气来做推导呢？因为这样做使得我们可以很清楚地理解整个目标是什么，并且一步一步推导出如何进行树的学习。
这一个抽象的形式对于实现机器学习工具也是非常有帮助的。传统的GBDT可能大家可以理解如优化平方残差，但是我们这里的这样一个形式包含所有可以求导的目标函数。也就是说有了这个形式，我们写出来的代码可以用来求解包括回归，分类和排序的各种问题，正式的推导可以使得机器学习的工具更加一般。

我们将（5）式求出的ωj的值带入（4）式即可得到目标损失函数最小值，如（6）式所示；其中 q 表示第 m 轮迭代中生成的树的结构，（6）式的值代表了第 m 次迭代中生成的模型带来的损失减小值；很显然这个值是小于0的，而且其越小，则第 m 个模型加入后得到的新集成模型Fm相对于加入前的集成模型Fm-1减小的损失函数值就越大。

公式（5）和公式（6）反映出：使得新集成模型Fm损失最小的第m棵树，其叶子结点的最优输出值只由损失函数在Fm-1的一阶导数和二阶导数决定，因此在第 m 轮迭代时，只要我们预先计算出 g 和 h，在训练生成一颗树模型后就可以直接算出每个叶子节点的最优输出值。

那么现在的问题是根据什么条件来生成一颗合适的树呢？

我们知道，树结构对应的具体就是各特征的分割点的确定。很显然不可能去计算所有的树结构。直观上，一种简单的贪婪方法就是从一个单叶子开始，迭代计算并添加分支到树中。
具体操作方面，我们令IL为分支左边里的样本集合，IR为分支右边里的样本集合。前面介绍的(6)式可以视为一种不纯度得分函数，用于衡量树结构的合理性。这样的话，我们可以借用其表示形式，将损失函数表示为下式（7）所示，这种形式经常用于候选分割点的计算，是XGBoost点选取的核心 （这个指标的作用类似于ID3中的信息增益，C4.5中的信息增益比等指标） ，而且区别于传统的 CART 回归树的条件是均方差（或绝对偏差等等）减小最大的点作为点：

处理过拟合

上面损失函数算是改进完了。基于上述算法，经过T次迭代，我们就可以得到T+1个弱学习器，集成的方法就是将这T+1个弱学习器直接相加：

我们知道在学习过程中存在过拟合问题，相应的有两种抑制过拟合的技术：

1.就是GBDT里讲到的Shrinkage技术。简单来说就是对于本轮新加入的树模型，调低权值η能减少个体的影响，给后续的模型更多学习空间。

2.就是列的重采样技术（column subsampling）。根据一些使用者反馈，列的subsampling比行的subsampling效果好，列的subsampling也加速了并行化的特征筛选。这里应该就跟RF差不多吧，不过论文没说具体怎么column subsampling，API里有个参数能控制subsampe的比例。

调参经验：关于η和迭代次数 T 的取值，可以通过交叉验证得到合适的值，通常针对不同问题，其具体值是不同的。一般来说，当条条件允许时（如对模型训练时间没有要求等）可以设置一个较大的迭代次数 T，然后针对该 T 值利用交叉验证来确定一个合适的η值。但η的取值也不能太小，否则模型达不到较好的效果；

Question4.XGBoost的优化

1.xgboost核心的分割点选取算法

分割点选取算法正是xgboost算法速度较快的原因之一!

我们继续上一部分的思路，上面公式（5）-（7）介绍了分割点的衡量标准，但这只是分割点的衡量指标，我们还不知道怎么选取分割点合适；对于具体分割点的选取，直观上我们当然可以采用 穷举的方法来暴力搜索最优分割点，如下算法1所示：

算法说明：
该算法会在所有特征 (features) 上，枚举所有可能的划分(splits)。为了更高效，该算法必须首先根据特征值对数据进行排序，以有序的方式访问数据来枚举Gain公式中的结构得分 (structure score) 的梯度统计 (gradient statistics)。

但是很显然这种方法是很耗时的，而且当数据量过大时，内存方面会承受巨大压力或者完全运行不了，因此为了进行有效可行的分割点选取，需要提出一种近似算法，如下算法2所示：

原文中的算法说明：
该算法会首先根据特征分布的百分位数 (percentiles of feature distribution)，提出候选划分点 (candidate splitting points)。接着，该算法将连续型特征映射到由这些候选点划分的分桶(buckets) 中，聚合统计信息，基于该聚合统计找到在 proposal 间的最优解。

step1：这个算法根据特征分布的百分位数 (percentiles of feature distribution)，做个proposal（获取某个特征K的候选切割点的方式叫proposal），提出候选分割点 (candidate splitting points)。
step2：然后该算法将连续型特征映射到由这些候选分割点划分的分桶(buckets) 中，聚合统计信息，则要选取的分割点就从这几个proposed candidate points里选，能大大提高效率。
（将每个特征的取值映射到由这些该特征对应的候选点集划分的分桶(buckets)区间中，对每个桶（区间）内的样本统计值 G,H 进行累加统计，最后在这些累计的统计量上寻找最佳点。这样做的主要目的是获取每个特征的候选分割点的 G,H 量）

这里有两种proposal的方式，一种是global的，一种是local的：
【1】global的是在建树之前就做proposal，然后之后每次分割都要更新一下proposal；（学习每棵树前，提出候选切分点；）
【2】local的方法是在每次split之后更新proposal。（每次前，重新提出候选切分点；）

通常发现local的方法需要更少的candidate，而global的方法在有足够的candidate的时候效果跟local差不多。我们的系统能充分支持exact greedy跑在单台机器或多台机器上，也支持这个proposal的近似算法，并且都能设定global还是local的proposal方式；
（这个算法的参数我没有在一般的API里看到，可能做超大型数据的时候才会用这个吧，因为前者虽然费时间但是更准确，通常我们跑的小数据用exact greedy就行）

我们总结整理一下，这一算法所做的就是：

1.首先基于特征分布的百分比，挑出每个特征的几个候选分割点；
2.而后基于这些分割点，将连续的特征值划分到区间桶内，而后基于汇总的统计数据来确定最优的分割点；
（感觉和采样的思路很像？？就是缩小候选集范围）

加权分位数略图
这里算法在研究特征分布然后做候选点集合提取的时候，用到了加权分位数略图（weighted quantile sketch），原文说不加权的分位数略图有不少了，但是支持加权的以前没人做。

插播：关于分位点、分位数略图和加权分位数略图

1.关于分位点

2.关于分位数略图

3.关于加权分位数略图

XGBoost 算法在计算特征 k 的分位数点时并没有按照均匀分为的方式来将样本等分到各个区间，而是采用了加权求分位数的方式。那这个权重是怎么来的呢？

样本权重代表的就是概率，概率越大表示该点出现的次数或是该点附近的值出现的次数就越多。XGBoost 算法依据该权重分步来选取分位数。

算法步骤如下：

Question5. 稀疏感知的划分查找算法(Sparsity-aware Split Finding)

在实际使用中，考虑到输入数据的稀疏表示的现象，使算法能够意识到数据的稀疏模式是很重要的。因此在文中提出在每个树节点中添加一个默认方向，作为值缺失时，能够直接使用的方向。

让算法意识到数据中的稀疏模式很重要。为了这么做，我们提出了在每个树节点上增加一个缺省的方向（default direction），如上图所示。当稀疏矩阵x中的值缺失时，样本实例被归类到缺省方向上。在每个分枝上，缺省方向有两种选择。最优的缺省方向可以从数据中学到。如算法3所示。关键的改进点是：只访问非缺失的条目Ik。上述算法会将未出现值（non-presence）当成是一个missing value，学到最好的方向来处理missing values。当未出现值对应于一个用户指定值时，应用相同的算法，可以通过将枚举(enumeration)限定到一致的解上。

一个值是缺失值时，我们就把他分类到默认方向，每个分支有两个选择，具体应该选哪个？这里提出一个算法，枚举向左和向右的情况，稀疏感知的划分查找算法计算切分后的评判标准是：哪个Gain大选哪个：

Question6. XGBoost在系统层面做了哪些优化？

这里XGB将所有的列数据都预先排了序：

以压缩形式分别存到block里，不同的block可以分布式存储，甚至存到硬盘里。在特征选择的时候，可以并行的处理这些列数据，XGB就是在这实现的并行化，用多线程来实现加速。同时这里陈博士还用cache加了一个底层优化：

一些其他点：

实验数据里提到column subsampling表现不太稳定，有时候sub比不sub要好，有时候sub要好，什么时候该用subsampling呢？当没有重要的特征要选，每个特征值的重要性都很平均的时候，对列的subsampling效果就比较差了。