# XGBoost论文笔记原理篇(上)

我准备用两篇的笔记来记录陈天奇的XGBoost论文<<XGBoost: A Scalable Tree Boosting System>>的原理部分，第一篇是主要是结合自己的理解对改论文的section2和section3做笔记；第二篇是论文附录中的WEIGHTED QUANTILE SKETCH算法的理论的理解。下面开始码字：

1,XGBoost对传统梯度提升树的改进

XGBoost的目标函数的推导和已有的提升树算法是一样的，特别是关于损失函数的二阶泰勒展开是源于Friedman等人的思想。不过XGBoost还是在提出了很多小的改进，量变产生质变，最终使得XGBoost成为逆天的存在。

1.1正则化的目标函数

1.2梯度提升

1.3列采样

除了添加正则化项外，XGBoost还使用了另外两种技巧来抑制过拟合。一个是由Friedman引入的shrinkage思想，shrinkage在每一次树提升后会对新增加的所有叶子节点的权重乘以一个因子。和随机优化的学习率一样，shrinkage减少每棵树的影响，为进一步提高模型保留了空间。第二个是和随机森林一样的列采样，在抑制过拟合方面，列采样的效果甚至要好于行采样，另外列采样对并行算法的效率提高帮助也不小。

2 分裂点搜索算法

根据上面的讨论可知，XGBoost的关键问题之一是搜索最优分裂点。第一种分裂点搜索算法是遍历所有样本的所有特征，这种搜索方式称为精确贪心算法。具体过程如下：

但精确贪心算法也有缺点：当数据不能一次性加载到内存中时其效率将大打折扣，在分布式情景中也面临着同样的问题，为此近似算法应运而生。

近似算法首先根据特征分布的分位数给出候选分裂点集合，然后把连续的特征映到由这些分裂点组成的桶中，接着把每个桶中的和统计量进行累加，最后根据这些累加的统计量在候选分裂点集合中寻找最优分割点。具体操作如下：

依据候选分裂点集合是在何时给出的，近似算法有两个版本：全局近似和局部近似。由于分位数策略的分布性和可重计算性，XGBoost采用分位数策略生成候选分裂点集合。至于如何产生这些候选分裂点，是我们下一篇的主题，敬请期待。

3 weighted Quantile Sketch

其中式2.7如下

##4 稀疏感知机制
现实中的数据集出现稀疏情况是相当普遍的，因此算法能够感知数据的稀疏模式是十分有益的。XGBoost的做法是为树的每个节点增加一个默认分裂方向，如果一个样本关于该节点最优分裂特征的缺失，则该样本按节点的默认方向分到子节点里。最优的默认方向可以从数据中学习，这样的算法称为稀疏感知分裂点寻找算法。XGBoost的一大改进是算法只访问没有缺失值的样本，将缺失值样本分到左节点一次，分到右节点一次，比较出最优默认方向。稀疏感知分裂点寻找算法的具体过程如下

XGBoost的原理大致就是上面这些，论文的其他部分是对算法效率提升的一些想法，以我的水平来讲，我应该还接触不到这些，我只想先把原理搞懂。下一篇写写论文附录的WEIGHTED QUANTILE SKETCH算法。