xgboost论文

陈天奇xgb论文
算法部分：
提升树方面：
1.受正则贪心森林(RGF)的启发在损失中引入了l2正则项和叶节点个数来控制模型的复杂度从而防止过拟合。(RGF中的正则项会随着节点变深而加大惩罚力度与xgb不同)其中xgb的正则项权重对应参数中的lambda，节点数权重对应gamma。
2.xgb在损失优化时的原理：通过对损失函数进行二阶展开，将以前的多次迭代结果和当前树区分开，从而在一次迭代中只需优化与当前树相关的损失部分。并且将损失简化为了二次函数，来简化计算。每次构建树时，选取使损失减少最多的点作为分裂点。
3.权值收缩和列采样：权值收缩率可理解为学习时的步长，每生成一个树就在树的前面乘上一个收缩系数eta 列采样：（在随机森林中使用）是指在生成一棵树进行节点分裂时选取随机特征集合来进行分裂，最后得到的最优分割点来自于该随机特征集合。
分裂查找算法：
1.精确贪心算法：遍历每个特征以及特征中所有的分裂点，从而精确的找出使loss减少最多的分裂点。O(n2)的复杂度（代码中通过EnumerateSplit函数进行遍历再利用ComputeSplitscore获取评分）
2.近似分裂算法：利用分位点对原来对特征进行分桶，对分位点进行评估找出使loss减少最多的点。O(n)的复杂度。这种分法有两种实现方式，一种是global分割，在开始时就把所有特征中的待选点分桶。另一种是loacl分割，在每次进行分割时都要进行分桶。gloabl算法需要分出更多的侯选点，来保证精度，而local算法不用。
3.加权分位图：在对损失函数式进行变形之后发现，特征点关于损失函数的二阶梯度的值可以被单独提出来作为系数，（我目前的理解是这样可以看作增益以hi为单位进行增长所以用hi作为权重）。
4.稀疏感知分裂查找：由于应用中的特征有比较强的稀疏性，对于那些缺省值。在进行分裂时直接将为缺省值的点单独拿出来，最后统一分在一边，这样就不再对缺省点进行遍历分裂从而提高了算法的效率，具体是放在左分支还是右分支要计算增益来决定。
系统设计部分：
1.可并行学习的特征块：在进行训练之前先将特征值排序并存储在block中，以减少排序的耗时。在寻找分裂点时在不同的block中对不同的特征进行并行计算。对于贪婪分裂法，一个block就对应一个特征中的所有数据。对于分布式计算，可将某列数据分成多个块分别存储在不同的地方，并且可以通过不同的机器对某列进行线性扫描。
2.缓存感知访问：由于需要对特征所对应的梯度值进行顺序访问，但是梯度是按照example的index存储的，因而不是连续的内存访问这样会导致缓存的命中率低从而降速。在精确贪婪分割中xgboost中采用了预取的方式，在每个线程中设置了缓冲，小批量地把相应的梯度数据放在缓冲当中这样就把不连续的数据变成了连续数据（这部分的实现在分裂查找的代码中有体现）。在近似分裂方法中通过选取合适的block size从而找到存取和运行效率之间的平衡。
3.块的核外计算：在数据量大的情况下，需要在运算的同时对磁盘数据进行读取，为了加快读取速度采用了压缩算法对数据进行压缩，在读取时用专门对线程进行解压。另一种方式是用多个磁盘进行数据预取，并将他们存入内存中对缓冲区。