机器学习：集成算法 - xgboost

xgboost（eXtreme Gradient Boosting）

大规模并行 boosting tree 的工具，据说是现在最好用的 boosting 算法，针对传统 GBDT 算法做了很多改进

xgboost 和传统 GBDT 的区别

GBDT 基学习器只用 CART 树，而 xgboost 除了用 CART 树，还可以用其他分类器
优化目标函数里，用到了二阶导数信息，能够更快地收敛，而普通的 GBDT 只用到一阶
优化目标函数里，对衡量模型复杂度的正则项进行了改进，GBDT 只对叶子个数做惩罚，而 xgboost 对叶子个数做惩罚的同时，还对叶子节点的权值做惩罚，有效地避免了过拟合
利用优化目标函数的推导作为树的分裂准则
在分割节点、寻找最佳分割点的时候，可以引入并行计算
利用了特征的稀疏性
能处理特征缺失
支持列采样

输出函数

设有样本数据 $\normalsize (x_{i}, y_{i})_{i=1}^{n}$
第 j 棵树记为 $\normalsize f_{j}(x)$
则由 m 棵树组成的 xgboost 输出为
$\normalsize y_{i} = F_{m}(x_{i}) = F_{m-1}(x_{i}) + f_{m}(x_{i}) = \sum_{j=1}^{m}f_{j}(x_{i})$
看起来就和 GBDT 一样，但 xgboost 的优化函数不一样

优化目标函数

xgboost 的优化目标函数为
$\normalsize Obj = \sum_{i=1}^{n}L(y_{i}, F_{m}(x_{i})) + \Omega(F)$
$\normalsize \Omega(F) = \gamma T +\frac{1}{2}\lambda\sum_{k}^{T}(||w_{k}||^{2})$
其中 $\small T$ 是所有树的叶子节点的总数， $\small w$ 是每个叶子节点的系数

泰勒展开公式
$\normalsize f(x+\Delta x) = \frac{f(x)}{0!} + \frac{f^{'}(x)}{1!}\Delta x + ... + \frac{f^{(n)}(x)}{n!}\Delta x^{n} + R_{n}(x)$

其中 $\small R_{n}(x)$ 是泰勒公式的余项，是 $\small \Delta x^{n}$ 的高阶无穷小

将优化目标函数按泰勒公式展开，并取前三项目得到近似值
$\normalsize Obj = \sum_{i=1}^{n}L(y_{i}, F_{m}(x_{i})) + \Omega(F)$
$\normalsize = \sum_{i=1}^{n}L(y_{i}, y_{i(m-1)}+f_{m}(x_{i})) + \Omega(F)$
$\normalsize=\sum_{i=1}^{n}[L(y_{i}, y_{i(m-1)})+\frac{\partial L(y_{i}, y_{i(m-1)})}{\partial y_{i(m-1)}}f_{m}(x_{i})$
$\normalsize + \frac{1}{2}\frac{\partial^{2} L(y_{i}, y_{i(m-1)})}{\partial^{2} y_{i(m-1)}}f^{2}_{m}(x_{i})] + \Omega(F)$

将一阶导数记为 $\normalsize g_{i}$ 将二阶导数记为 $\normalsize h_{i}$ 改写为
$\normalsize Obj = \sum_{i=1}^{n}[L(y_{i}, y_{i(m-1)}) +g_{i}f_{m}(x_{i}) + \frac{1}{2}h_{i}f^{2}_{m}(x_{i})] + \Omega(F)$

由于在计算第 m 棵树的时候，前 m-1 棵树已经确定，所以可以只保留和第 m 棵树有关的项，将优化目标改写为
$\normalsize Obj = \sum_{i=1}^{n}[g_{i}f_{m}(x_{i})+\frac{1}{2}h_{i}f^{2}_{m}(x_{i})]+\Omega(f_{m})$

设 $\normalsize f_{m}$ 的每个叶子节点是输出一个固定的值 $\normalsize w_{j}$
设 $\normalsize I_{j}$ 代表所有会被映射到叶子节点 $\normalsize j$ 的 $\normalsize x_{i}$ 集合
设 $\normalsize T$ 代表 $\normalsize f_{m}$ 的叶子节点数

进一步改写为
$\normalsize Obj = \sum_{j=1}^{T}[(\sum_{i\in I_{j}}g_{i})w_{j} + \frac{1}{2}(\sum_{i\in I_{j}}h_{i})w_{j}^{2}] + \gamma T +\frac{1}{2}\lambda\sum_{j=1}^{T}(w_{j}^{2})$
$\normalsize = \sum_{j=1}^{T}[(\sum_{i\in I_{j}}g_{i})w_{j}+\frac{1}{2}(\sum_{i\in I_{j}}h_{i}+\lambda)w_{j}^{2}] + \gamma T$

设有
$\normalsize G_{j} = \sum_{i\in I_{j}}g_{i}$
$\normalsize H_{j} = \sum_{i\in I_{j}}h_{i}$

可改写为
$\normalsize Obj = \sum_{j=1}^{T}[(G_{j}w_{j} +\frac{1}{2}(H_{j}+\lambda)w_{j}^{2}] + \gamma T$

对 $\normalsize w_{j}$ 求导并另导数为 0
$\normalsize G_{j}+(H_{j}+\lambda)w_{j} = 0$

得到最优的

$\normalsize w_{j} = -\frac{G_{j}}{H_{j} + \lambda}$

$\normalsize Obj = -\frac{1}{2}\sum_{j=1}^{T} \frac{G_{j}^{2}}{H_{j}+\lambda} + \gamma T$

用于衡量树的优劣的就是 $\normalsize Obj$ ，其值越小，树结构越好

分裂叶子节点的依据

假设现在有一个叶子节点，属于这个叶子节点的样本的一阶导数的和为 $\normalsize G_{M}$ ，二阶导数的和为 $\normalsize H_{M}$ ，如果需要对这个叶子节点分裂成两个节点，那么叶子节点数量就 +1，假设分到左叶子的样本的值为 $\normalsize G_{L}$ 和 $\normalsize H_{L}$ ，分到右叶子的样本的值为 $\normalsize G_{R}$ 和 $\normalsize H_{R}$ ，则有 $\normalsize G_{L} + G_{R} = G_{M}$ 以及 $\normalsize G_{L} + G_{R} = H_{M}$ ，那么 $\normalsize Obj$ 减小的值为

$\normalsize Gain = (-\frac{1}{2}\frac{G_{M}^{2}}{H_{M} + \lambda} + \gamma T) - (-\frac{1}{2}\frac{G_{L}^{2}}{H_{L}+\lambda} - \frac{1}{2}\frac{G_{R}^{2}}{H_{R} + \lambda} + \gamma(T+1))$

$\normalsize = \frac{1}{2}[\frac{G_{L}^{2}}{H_{L} + \lambda} + \frac{G_{R}^{2}}{H_{R} + \lambda} - \frac{(G_{L} + G_{R})^{2}}{(H_{L} + H_{R})+\lambda}] - \gamma$

选择使得 $\normalsize Gain$ 值最大的分割特征和分割点

并计算分割后新的叶子节点的系数

$\normalsize w_{L} = -\frac{G_{L}}{H_{L} + \lambda}$

$\normalsize w_{R} = -\frac{G_{R}}{H_{R} + \lambda}$

停止分割的条件
○ 如果最大的 $\normalsize Gain$ 比 $\normalsize\gamma$ 还小
○ 树已经达到了最大深度
○ 样本权重和小于某一个阈值

寻找最佳分裂点

精确算法 - 穷举法
遍历所有特征的所有特征值，该方法精度高但计算量大
近似算法 - 分位点分割
每个特征按照样本特征值的百分比选择候选分裂点
近似法又有两种
（1）全局法：生成树之前就确定候选分裂点，这可以减少计算，但要一次取比较多的点
（2）局部法：每个节点确定候选分裂点，每次取的点较少，且可不断改善，但计算量大
近似算法 - 二阶导数的分位点分割
同样是按百分比选择候选分裂点，但不是直接用特征值，而是用二阶导数 $\small h$

提高计算速度

提前计算和排序
生成树的过程是串行的，在生成第 m 棵树时，第 m-1 棵树已经有了
这样每个样本的一阶和二阶导数是已知的，可提前计算所有样本的 $\normalsize g$ 和 $\normalsize h$ 值，并提前排序
如果是近似算法，还可以提前将各个分位点之间的 $\normalsize g$ 和 $\normalsize h$ 值进行累加得到 $\normalsize G$ 和 $\normalsize H$ 值
并行分裂节点
每个节点的分裂都是独立互不影响的，所以可以并行计算
每个节点的分裂要遍历所有特征，特征计算也可以并行处理
存储优化
采用 Block 结构以稀疏矩阵 CSC 存储特征数据并排序，后续的并行计算可以重复使用 Block
Block 按列存储，方便计算
Block 的特征需要指向对应样本的导数值，会导致非连续内存访问，使用缓存预取来避免
不同的 Block 可以存在不同的机器上，该方法对局部近似法尤其有效
当数据太大无法全写入内存时，需要将 Block 压缩落盘，然后有独立的线程做读取解压

特征评价

xgboost 有三个指标用于对特征进行评价

weight - 某个特征被用于分裂的次数
gain - 某个特征被用于分裂时得到的平均增益
cover - 某个特征在分裂时结点处的平均二阶导数

学习率（Shrinkage）

和 GBDT 一样，xgboost 也使用了学习率做 Shrinkage，在计算出了节点的 $\normalsize w$ 值后，会乘以一个小于 1 的系数，这能够防止过拟合

列采样

xgboost 支持列抽样，能避免过拟合，同时能减少计算

稀疏数据

xgboost 能学习缺失值的分裂方向，在分裂的过程中，会尝试把所有特征缺失的样本都分入左节点，或是都分入右节点，看是哪边增益大，然后决定其分裂方向