最近打比赛又用上了XGBoost和LightGBM, 但是对二者实现细节上的差异特别是LightGBM的细节一直有些模糊，最近重新读了一次两篇论文，记录一下细节，毕竟调参也得科学调参不是。
从论文结构来讲，我觉得XGBoost相较LightGBM还是很好理解的，很符合我们平时学习模型时从模型原理推导，到细节实现，再到系统实现的这一过程，而XGBoost的主要创新与贡献也在于这三方面，接下来就从这三方面来进行总结。
一、模型原理推导
在模型原理上，个人觉得XGBoost并没有太大的创新，而是在前人研究的基础上进行了融合，算是结合了不同模型的优势。按照论文，这部分的工作主要可以分成三部分：正则化的损失函数，二阶导数的梯度提升，学习率（收缩率）与列采样。
Regularized Learning Objective
相较于传统的GBDT模型，XGBoost的第一点改进在于损失函数添加上了正则化项，类似的正则技巧在Regularized greedy forest(RGF)中已经被采用过，但是文中提出的方法会更简单且利于并行。
其中T为叶子结点的个数，w为叶子结点的输出权值。
Gradient Tree Boosting
对XGBoost的损失函数进行二阶泰勒展开来代替原GBDT中的梯度是这篇论文最重要的点之一。这一方法在之前的工作中也已有人做过（Friedman）。二者之间的差别可以认为是：
- GBDT在函数空间利用梯度下降法进行优化
- XGBoost在函数空间中利用牛顿法进行优化
这里又涉及到两种优化方法之间的区别，简单来讲梯度下降法用超平面去拟合当前所在局部曲面，只考虑目标函数再迭代点的局部性质；而牛顿法用的是超曲面来进行拟合，直接搜索怎样到达极值点，不仅考虑当前坡度是否足够大，还会考虑之后的情况，收敛速度会更快。这里先不总结了，等之后总结最优化方法的时候再写写算算吧。
在第t次迭代时，损失函数可化为：
利用二阶泰勒展开近似：
通过省略常数项，可得到：
中间替换过程按下不表，最终损失函数可化为：
对上式求导求极值，可解出叶子结点的权值：
最优的损失函数值则可化为：
与传统的ID3,C4.5,CART不同，上式就是用来确定分类点的度量值，选择能够使损失函数值最小的分类点。通过父节点的值与左右两个子节点的值相减，得到损失函数的降低程度：
Shrinkage and Column Subsampling
模型原理上的第三点改进也就是学习率与列采样。和正则化项一样，这两项也是用于防止过拟合的策略。Skrinkage同样由Friedman提出，在GBDT中也有类似的设置，shrinkage的作用与随机最优化中的学习率相似，减弱了单颗树的权重。
列采样来源于随机森林，也就是对特征进行采样。同时也实现了行采样，不过与随机森林中的自主采样法不同，这里的行采样是不放回的采样。
在sklearn的GBDT的实现中，上述的方法也都进行了实现。
二、结点分裂算法 Split Finding Algorithms
这一部分算法的实现与第四章的系统实现决定了XGBoost的超快运行速度。
Basic Exact Greedy Algorithm
在GBDT算法的计算过程中，最为耗时的过程也就是寻找最佳分割点的过程。传统的做法也就是暴力遍历所有可能的分割点，包括sklearn中的算法也就是采用这一策略, XGBoost也同样支持这一算法。
这一算法的常规做法是：首先根据特征的值进行排序，再依次遍历每一个可能的分割点进行计算。
Exact Greedy Algorithm这个算法的时间复杂度O(d m + m log(m)) = O(m (d + log(m)))，m log(m)是因为对样本特征进行约排序，d * m是对每个样本的每个特征进行分裂判断。(来自这里)
Approximate Algorithm
暴力算法的缺点在于当数据量很大的时候难以高效的运行，所以XGB提出了一种近似算法能加快运行,其流程如下：
对于某个特征k，算法首先根据特征分布的分位数找到特征切割点的候选集合S,然后将特征k的值根据集合S划分成桶（bucket），接着对每个桶内的样本统计其G/H值，最后在这些累计的统计量上寻找最佳的分裂点。相当于降低分裂的精度来提升运行的速度。
文中提出了两种不同的近似算法：Global和Local。Gloabl即在初始化tree的时候划分好候选分割点，并且在树的每一层都使用这些候选分割点；Local即每一次划分的时候都重新计算候选分割点。这两者各有利弊，全局算法不需要多次计算候选节点，但需要一次获取较多的候选节点供后续树生长使用，而局部算法一次获取的候选节点较少，可以在分支过程中不断改善，即适用于生长更深的树。
Weighted Quantile Sketch
近似算法的核心在于候选分割点的选取，Xgboost提出了Weighted Quantile Sketch来解决这个问题。这一算法设计到大量数据情况下分位数点的计算问题，我其实理解的不是很好，在这篇博客里有很好的描述。
那么为什么是加权的算法呢？10000个样本取10个的话，每1000个样本计算一次split value看似可行，其实是不可以的，我们要均分的是loss，而不是样本的数量，而每个样本对loss的贡献可能是不一样的，按样本均分会导致loss分布不均匀，取到的分位点会有偏差(来自这里)。
对损失函数进行变形可以得到：
这个形式的loss说明了, xi的loss也可以看做是以−gi/hi作为label的均方误差，乘以大小为hi的权重，换句话说，xi对loss的贡献权重为hi。
那么，对loss取k分位点就是对误差的均分。
这一部分感觉确实不太好理解，再贴几篇参考文章，结合其中的例子更好理解一些：
Sparsity-aware Split Finding
XGB还增加了对稀疏数据和缺失值的处理算法，XGB训练数据的时候，它使用没有缺失的数据去进行节点分支。然后我们将特征上缺失的数据尝试放左右节点上，看缺失值应当分到那个分支节点上。我们把缺失值分配到的分支称为默认分支。
三、系统设计 System Design
文章最后一大块也就是系统设计了。工程上的精妙实现才能发挥出最好的效果。这一部分内容不少，但大多都是接触较少的内容，所以简单提炼几个要点。
Column Block for Parallel Learning
XGB的并行计算的粒度不在树上，而是在特征上
在我们训练过程中最耗时的过程也就是做分支处理，需要对每一列（特征）找出适合的分裂点。为了加快处理速度，将数据按照列存储成一个数据块方便我们在分裂的时候进行并行计算。这里XGB将所有的列数据都预先排了序，以压缩形式分别存到block里，不同的block可以分布式存储，甚至存到硬盘里。在特征选择的时候，可以并行的处理这些列数据，XGB就是在这实现的并行化，用多线程来实现加速。
Cache-aware Access
Blocks for Out-of-core Computation
这两部的内容更偏于工程实现上的技巧，这里就不进行总结了，详见：