学习笔记——XGBoost算法
学习笔记——XGBoost算法
XGBoost和GBDT两者都是boosting方法，除了工程实现、解决问题上的一些差异外，最大的不同就是目标函数的定义。
1、基本原理
1.1 目标函数
XGBoost算法是一个加法模型，在每一步迭代中，只调优当前的子模型：\(F_m(x_i)=F_{m-1}(x_i)+f_m(x_i)\)。其中\(f_m(x_i)\)表示当前的子模型，\(F_{m-1}(x_i)\)表示前\(m-1\)个已固定模型。
目标函数=经验风险+结构风险（正则项）： \[ \begin{aligned} obj& =\sum_{i=1}^NL[F_m(x_i),y_i]+\sum_{j=1}^m\Omega(f_j) \\ &=\sum_{i=1}^NL[F_{m-1}(x_i)+f_m(x_i),y_i]+\sum_{j=1}^m\Omega(f_j) \end{aligned} \]
其中正则项\(\Omega(f_j)\)表示模型\(f\)的复杂度。
XGBoost用2阶泰勒公式：\(f(x_0+\Delta x)\approx f(x_0)+f^{'}(x_0)\Delta x+\frac{f^{''}(x_0)}{2}(\Delta x)^2\)来逼近损 失函数，我们可以将\(F_{m-1}(x_i)\)看作\(x_0\),将\(f_m(x_i)\)看作\(\Delta x\),所以（1）式就可以转化为： \[ \begin{aligned}Obj=\sum_{i=1}^N\left[L[F_{m-1}(x_i),y_i]+\frac{\partial L}{\partial F_{m-1}(x_i)}f_m(x_i)+\frac{1}{2}\frac{\partial^2L}{\partial^2F_{m-1}(x_i)}f_m^2(x_i)\right]+\\\sum_{j=1}^m\Omega(f_j)\end{aligned} \] 由于前m-1个模型是确定的，所以\(\sum_{j=1}^m\Omega(f_j)\)，前m-1项均为常数，对目标函数的求解无影响，所以（2）式又可以转化为： \[ Obj=\sum_{i=1}^{N}\left[g_{i}f_{m}(x_{i})+\frac{1}{2}h_{i}f_{m}^{2}(x_{i})\right]+\Omega(f_{m}) \]
1.2 基于树的正则化
XGBoost支持的基分类器包括决策树和线性模型，为防止过拟合，XGBoost将树的深度设置为正则项：\(\Omega(f)=\gamma T+\frac{1}{2}\lambda||w||^{2}\)，其中\(\gamma\)和\(\lambda\)作为超参数。所以目标函数可以改写为： \[ Obj=\sum_{i=1}^{N}\left[g_if_m(x_i)+\frac{1}{2}h_if_m^2(x_i)\right]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_j^2 \] 通过数学处理，可以将正则项和经验风险项合并：将经验风险项从样本层面上求和转换为叶节点层面上的求和。可以定义结点j上的样本集为\(I(j)=\{x_{i}|q(x_{i})=j\}\),其中\(q(x_i)\)为将样本映射到叶节点上的索引函数，叶节点\(j\)上的回归值为\(w_{j}=f_{m}(x_{i}),i\in I(j)\).
所以式（4）进一步简化,令\(\sum_{i\in I(j)}g_i=G_j,\sum_{i\in I(j)}h_i=H_j\)： \[ Obj=\sum_{j=1}^T\left[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2\right]+\gamma T \] 如果一棵树的结构是确定的，则各个节点内的样本（\(x_i,y_i,g_i,h_i,G_j,H_j,T\)）也是确定的，每个叶子结点输出回归值应该使得式（5）最小，所以该函数的二次函数极值点为：\(w_j^*=-\frac{G_j}{H_j+\lambda}\)
树的评分也可以理解成所有叶节点的评分之和：\(Obj^*=\sum_{j=1}^T\left(-\frac{1}{2}\frac{G_j^2}{H_j+\lambda}+\gamma\right)\).
1.3 结点分裂准则
XGBoost的子模型树和决策树模型一样，要依赖节点递归分裂的贪心准则来实现树的生成：
从树的深度为0开始：
- 对每个叶节点枚举所有的可用特征；
- 针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；
- 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集；
- 回到第1步，递归执行直到满足特定条件为止；
过程如图所示：
显然分裂收益是树A的评分减去树B的评分，因此分裂收益表达式为： \[ Gain=\frac12\Big[\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}\Big]-\gamma \] XGBoost还支持近似算法：根据特征分布的分位数提出候选划分点，然后将连续型特征映射到由这些候选点划分的桶中，然后聚合统计信息找到所有区间的最佳分裂点。具体而言，特征分位数的选取有global和local两种可选策略：
- global在全体样本上的特征值中选取，在根节点分裂之前进行一次即可；
- local则是在待分裂节点包含的样本特征值上选取，每个节点分裂前都要进行。
通常，global由于只能划分一次，其划分粒度需要更细。通过这个方法可以解决数据量过大超过内存、或有并行计算需求的情况。
由（3）式可得：令其偏导为0可以得到\(f_{m}^{*}(x_{i})=-\frac{g_{i}}{h_{i}}\),此目标函数可理解为以\(h_i\)为权重，\(-\frac{g_{i}}{h_{i}}\)为标签的二次损失函数： \[ \begin{aligned} obj& =\sum_{i=1}^{N}\left[g_{i}f_{m}(x_{i})+\frac{1}{2}h_{i}f_{m}^{2}(x_{i})\right]+\Omega(f_{m}) \\ &=\sum_{i=1}^{N}\frac{1}{2}h_{i}\Big[f_{m}(x_{i})-(-\frac{g_{i}}{h_{i}})\Big]^{2}+\Omega(f_{m})+C \end{aligned} \] 因此，在近似算法取分位数时，实际上XGBoost会取以二阶导\(h_i\)为权重的分位数。
1.4 列采样和学习率
XGBoost还引入了两项特性：列采样和学习率
- 列采样：即随机森林中的做法，每次节点分裂的待选特征集合不是剩下的全部特征，而是剩下特征的一个子集。是为了更好地对抗过拟合，还能减少计算开销。
- 学习率：或者叫步长、shrinkage，是在每个子模型前（即在每个叶节点的回归值上）乘上该系数，削弱每颗树的影响，使得迭代更稳定。可以类比梯度下降中的学习率。XGBoost默认设定为0.3。
1.5 稀疏感知
XGBoost将缺失值和稀疏0值等同视作缺失值，将这些缺失值“绑定”在一起，分裂结点的遍历则会跳过缺失值整体，提升了运算效率。
2. 工程优化
2.1 并行列块的设计
XGBoost将每一列特征提前进行排序，以块（Block）的形式储存在缓存中，并以索引将特征值和梯度统计量\(g_i,h_i\)对应起来，每次节点分裂时会重复调用排好序的块。而且不同特征会分布在独立的块中，因此可以进行分布式或多线程的计算。
2.2 缓存访问
特征值排序后通过索引来取梯度 \(g_i,h_i\) 会导致访问的内存空间不一致，进而降低缓存的命中率，影响算法效率。为解决这个问题，XGBoost为每个线程分配一个单独的连续缓存区，用来存放梯度信息。
2.3 核外块计算
数据量过大时，不能同时全部载入内存。XGBoost将数据分为多个blocks并储存在硬盘中，使用一个独立的线程专门从磁盘中读取数据到内存中，实现计算和读取数据的同时进行。为了进一步提高磁盘读取数据性能，XGBoost还使用了两种方法：
- 块压缩：通过压缩block，用解压缩的开销换取磁盘读取的开销；
- 块分区：将block分散储存在多个磁盘中，有助于提高磁盘吞吐量。
3. 与GBDT比较
- 性质：GBDT是机器学习算法，XGBoost除了算法内容还包括一些工程实现方面的优化。
- 基于二阶导：GBDT使用的是损失函数一阶导数，相当于函数空间中的梯度下降；而XGBoost还使用了损失函数二阶导数，相当于函数空间中的牛顿法。
- 正则化：XGBoost显式地加入了正则项来控制模型的复杂度，能有效防止过拟合。
- 列采样：XGBoost采用了随机森林中的做法，每次节点分裂前进行列随机采样。
- 缺失值处理：XGBoost运用稀疏感知策略处理缺失值，而GBDT没有设计缺失策略。
- 并行高效：XGBoost的列块设计能有效支持并行运算，提高效率。
缺点
- 虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集；
- 预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。