论文的第三节阐述了一种新的分裂点寻找算法，我们从CART开始一步步看XGB是如何做的。
CART的分裂点选取
单棵树模型的核心内容就是如何选择分裂点，其实寻找最优的树结构是NP难问题，我们只能采用启发式方法进行，比如贪心算法。对于分类树ID3和C4.5来说，每次分裂都选取信息熵增益最大的特征和特征值进行分裂，对于CART树来说，每次遍历特征和特征值，找到使平方差函数最小的点作为分裂点。
假设样本的特征有k维特征，一共有n个样本，意味着每次寻找分裂点的时间复杂度为O(kn)，如果树的深度为d,那么每一层都要进行一遍分裂点的寻找，时间复杂度就变成了O(knd)，除此之外，每一维特征都需要进行排序，最终的时间复杂度为$O(knd+kn\log(n))=O(kn(d+\log(n)))$。
粗略计算，关于深度d那部分没有细想，肯定有问题。
可以说它的复杂度是很高的，当样本数量很大、维度k很大时，整个算法运行速度极慢。
XGB的分裂点选取
XGB不同于CART的地方在于，分裂使用的标准不一样。
在上一章中介绍过，论文推导出了损失函数的最小值：
它是关于树结构$q(x)$的函数，当树结构确定的时候，就能算出损失函数值。那么一个自然的想法就是遍历所有候选点，尝试在某个候选点分裂为左右叶子后($I=I_L \cup I_R$)，计算损失函数的”增益”:
和信息熵增益意思一样，假设在这个候选点分裂，损失函数降低的数值是多少，我们选取能使损失函数降低最多的候选点进行分裂即可。论文给的算法流程如下图所示：
论文称此算法为“精确贪心算法”，因为每次寻找分裂点都要遍历所有样本的特征值，效果相对来说是最好的。
虽然叫精确贪心算法，但仍然是启发式算法，得到的树结构不是全局最优的。
精确贪心算法的时间复杂度和CART一样，比较耗时，当样本特别多的时候，排序和遍历都很困难，因此需要使用一些优化手段，一个常用的优化手段是对连续型特征值进行分箱操作，每一段的交界点就是候选点，这样能大幅度减少遍历操作的时间，论文称为近似切分点算法：
问题就变成了如何寻找候选点，常用的方式是将分位点作为候选点，如果要寻找精确分位点，就需要对特征值进行排序，比较耗时，尤其是当特征数量特别大，不能一次性加载到内存中，处理起来比较麻烦，每次都需要自己去写相应的处理函数。
XGBoost提供了一整套解决方案叫做”Weighted Quantile Sketch”，它大概的功能是，可以在流式数据或者超大规模数据中，找到有一定精度保证的“近似分位点”，在论文的补充材料中有详细的理论证明，这个方案源自GK Summary算法和Fast Algorithm for GK Summary，比较复杂，可以参考最后列出的其他博客。
我们不需要精确的分位点作为候选点，只需要近似分位点就可以，保证误差在一定范围内，这样可以大大减小排序的时间复杂度。对于下面一列排序好的特征：
| value | 1 | 4 | 8 | 10 | 15 | 16 | 20 | 20 | 21 | 25 |
| rank | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
精确的$\frac{1}{2}$分位点在rank=5的位置。
近似分位点称为$\epsilon-approximate \ \phi-quantiles$，意思就是，在给定误差$\epsilon$的情况下，给出一个分位点集合，集合中的点在精确的分位点附近。
比如$\epsilon=0.1$的时候，$0.5$近似分位点rank和value的集合为$rank=\{4,5,6\} value=\{10,15,16\}$
对于候选点选择任务来说，精度满足一定范围即可。
除了“近似”这个特性，还有“权重”。权重指的是每个样本都会带有一个权重，选取分位点的时候，需要按权重进行计算：
| value | 1 | 4 | 8 | 10 | 15 | 16 | 20 | 20 | 21 | 25 |
| rank | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| weight | 0.1 | 0.1 | 0.1 | 0.1 | 0.4 | 0.1 | 0.1 | 0.1 | 0.1 | 0.4 |
这样的话，0.25分位点就是$rank=4$，0.5分位点是$rank=5$。
可以看见，权重会对分位点的位置产生很大的影响，我们用什么作为样本的权重比较合适呢？
论文中使用了样本的二阶导数作为权重，它是这样推导的，把公式：
进行配方，得到：
可以看到，损失函数实际是按照$h_i$进行加权的，如果一个样本的$h_i$越小，那么这个样本对损失函数的影响越小。反之，样本的$h_i$越大，对损失函数影响越大。更具体一些，假如$\mathcal{L}$是平方差损失函数，那么$\mathcal{L}$关于$f_t$的二阶导数是常数$h_i=2$。如果$\mathcal{L}$是交叉熵损失函数，那么它的二阶导数是$h_i=\sigma(\hat {y}^{(t-1)})(1-\sigma(\hat {y}^{(t-1)}))$，其中$\sigma(\cdot)$是sigmoid函数，取值范围(0,1)，因此$h_i$可以看做是一个开口向下的二次函数，在$\sigma(\hat {y}^{(t-1)})=0.5$时取得最大值，在$\sigma(\hat {y}^{(t-1)})=1\ or\ 0$时取得最小值。
$h_i$的推导见附录
这是一个很有趣又符合逻辑的解释，当$\sigma(\hat {y}^{(t-1)})$取值为0.5左右时，表示这个样本在上一轮迭代中很难进行分类，处于正负类交界处，同时$h_i$处于较大值，这类样本对损失函数的影响较大，本次应该重点照顾。将$h_i$作为样本权重，在分位点划分的时候，较大的权重会让这个样本被分的“更细”。
如果觉得抽象可以看下面这个例子：
每个小方格代表一个样本，一列方格已经按照特征值排序，方格内的数值是每个样本的二阶导数$h_i$，红色方格是按25%、50%、75%划分的分位点。上面一组没有使用权重，正常划分，下方是按照权重划分，可以看到，我们希望重点照顾的蓝色方块因为权重高，被单独划在一个集合，这样它可以落在相对浅的叶子节点，可以降低分错的概率。
为什么在浅叶子节点就能降低分错的概率？个人理解，每一轮生成的树模型都是有固定最大深度的，例如6层，如果这个样本分对需要7层，那么它可能在6层时仍然和其他样本混在一起，这个叶子的值不是最优值。如果能在第四层得到它的最优值，就加大了它分对的概率。
将权重的特性和之前提到的Fast Algorithm for GK Summary算法结合起来，就得到了”Weighted Quantile Sketch”，前者主要是提供快速的近似分位点查找。
缺失值处理
XGB的缺失值处理也很有特点。模型会学习到每个缺失特征值分裂的默认方向，算法如下所示：
在每次计算最佳分裂点的时候，将所有缺失该特征的样本分到左边计算一次，再都分到右边计算一次，取最大收益作为默认的分裂方向。训练完毕后，如果要预测的样本值缺失某个特征，就会按照之前学习的默认分裂方向分到对应的分支。如果训练时没有缺失值但是预测时有，就默认分向右分支。
并行化
除了上述这些算法特性，XGB在工程上也优化了很多，尤其是针对分布式、并行化做了很多优化。整个算法最耗时的步骤是分位点查找，涉及到海量数据的排序问题，论文针对这部分做了两方面的优化。
1.Column Block for Parallel Learning
按列将数据分块，分成不同的子集，可以在不同的机器上进行排序、分位点的计算。另外，按列分块后，特征之间是独立的，也可以并行计算候选点。
2.Cache-aware Access
这部分没有细看，主要是增加CPU的缓存命中率，让block结构更容易在cache中命中，从而加快计算速度。
3.Blocks for Out-of-core Computation
因为有大部分的块都是保存在磁盘上的，因此也要对这些block的存取进行优化，主要使用了压缩和缓冲区技术。
附录(二阶导数推导)
XGBoost的交叉熵损失函数:
因为有求导公式：
那么一阶导数为：
然后求二阶导数直接套用公式可得：
可以参考的资料
https://www.csuldw.com/2019/07/20/2019-07-20-xgboost-theory/