一般而言, 穷举所有可能的树结构是不可能的, 作为代替, 我们考虑贪心算法. 从一个叶节点开始二分, 假设 \(I_L\) 和 \(I_R\) 分别表示分裂后归为左节点和右节点的实例集合, 记 \(I = I_L \cup I_R\), 则易得分裂后的目标函数减少值 (loss reduction) 为
\[ \frac12\left[\frac{(\sum_{i\in I_L}g_i)^2}{\sum_{i\in I_L} h_i + \lambda} + \frac{(\sum_{i\in I_R}g_i)^2}{\sum_{i\in I_R} h_i + \lambda} - \frac{(\sum_{i\in I}g_i)^2}{\sum_{i\in I} h_i + \lambda}\right] - \gamma \]
把上式第一项视为 gain, 则 \(\gamma\) 相当于设置了分裂所需的最小的 gain, 起到了剪枝的作用.
寻找分裂点的精确贪心算法 (原文 [3] 中本段有一些 typo)
输入: \(I\), 当前节点的实例集; \(d\), 特征维数 (个数).
初始化 \(\mathrm{gain} \leftarrow 0\)
\(G \leftarrow \sum_{i\in I}g_i\), \(H \leftarrow \sum_{i\in I}h_i\)
for \(k=1\) to \(d\) do
\(G_L \leftarrow 0\), \(H_L \leftarrow 0\)
for \(j\) in sorted (\(I\), by \(x_{jk}\)) do
\(G_L\leftarrow G_L + g_j\), \(H_L\leftarrow H_L + h_j\)
\(G_R \leftarrow G-G_L\), \(H_R \leftarrow H- H_L\)
\(\mathrm{gain} \leftarrow \max(\mathrm{gain}, \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{G^2}{H + \lambda})\)
输出: 最大 gain 的分裂
精确贪心法是在所有特征上, 对所有可能的分裂点都进行遍历, 在数据量大的时候是不现实的. 一个简单的近似方法是, 排序后 (for \(j\) in sorted (\(I\), by \(x_{jk}\)) 那步), 取适当的分位数作为分裂候选点进行贪心算法.
3.3. 稀疏数据的分裂点寻找 (sparsity-aware)主要分为两种情况:
若数据有缺失值, 则把缺失值都归到同一个节点. 这是处理缺失值的常用方法之一 (另一种常用方法是用适当的方法填补缺失值), 这使得 XGB 可以直接训练和预测带有缺失值的数据.
若数据稀疏 (比如 one-hot 编码, 使得数据包含大量的 0), 则把 0 当做缺失值处理. 这个做法的关键点在于遍历时只对非缺失 (非零) 数据遍历, 在稀疏数据的情况下会大大提高训练速率.
注: 按照原论文 [3] 的说法, 作者似乎把缺失和稀疏时的 0 都统称为 "稀疏/缺失", 用同样的方式处理, [5] 也证实了这一点.
图中 \(m\) 应该为 \(d\), score 应该为 gain.
3.4. XGB 的优点XGB 把决策树的许多启发式的想法通过最小化目标函数统一起来处理. 除了使用近似算法, 在系统设计上, 通过并行处理, 优化缓存等工程层面上的优化大幅提高了运行速度, 减小了内存使用.
References[1] 李航. (2012). 统计学习方法 (pp. 55-74, 137-153). 北京: 清华大学出版社.
[2] Friedman, J., Hastie, T., & Tibshirani, R. (2001). The elements of statistical learning (pp. 299-344). New York: Springer series in statistics.
[3] Chen, T., & Guestrin, C. (2016). Xgboost: A scalable tree boosting system. Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining (pp. 785-794). ACM.
[4] Introduction to Boosted Trees. (n.d.). Retrieved from
[5] Kodi Arfer. XGBoost, missing values, and sparsity. (2018). Retrieved from