Paper | XGBoost: A Scalable Tree

简单记录一下重点内容，待后续仔细看后补充。

参考博客：http://d0evi1.com/xgboost/

主要内容

• 1.设计和建立了一个高度可扩展的end-to-end tree boosting系统
• 2.提出了一种理论正确的加权分位数略图过程(theoretically justified weighted quantile sketch procedure)，用于高效地进行预计算
• 3.介绍了一种新的稀疏感知算法（sparsity-aware algorithm），用于并行化tree learning
• 4.提出了一种高效的内存感知块结构（cache-aware block structure），用于核外（out-of-core）tree learning

参考博客：https://blog.csdn.net/taotiezhengfeng/article/details/74858303

与GBDT的主要区别

• 1.加入了正则化项
• 2.二阶泰勒展开，更快收敛
• 3.寻找分割点

优化

• 在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，xgboost实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
• xgboost考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率，paper提到50倍。
• 特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然boosting算法迭代必须串行，但是在处理每个特征列时可以做到并行。
• 按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer，然后再计算，提高算法的效率。
• xgboost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。