XGBoost原理总结

Xgboost, 是GBDT的一种实现方式，并且xgboost做了一些改进和优化。

1. 原理

1.1 优化目标函数

对于GBDT方法，都是基模型组成的加法公式。

$$\hat y_i = \sum_{i=1}^kf_t(x_i)\tag{1}$$

其中$f_k$为基模型,$y_i$表示第$i$个样本预测值。

正则化损失函数

$$\zeta^t=\sum_{i=1}^n l(y_i,\hat y_i^{(t-1)})+\Omega(f_t)\tag{2}$$

对于损失函数（2）进行二阶展开有：

$$\zeta^{(t)} \approx \sum_{i=1}^n[l(y_i,\hat y_i) +g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t) \\ where\quad \Omega(f)=\gamma T+\frac{1}{2}\lambda||w||^2\tag{3}$$

对于损失函数，xgboost在处理的时候进行了二阶展开，其中$g_i=\frac{\partial l(y_i,\hat y_i^{(t-1)})}{\partial \hat y_i^{(t-1)}}$, $h_i=\frac{\partial ^2l(y_i,\hat y_i^{(t-1)})}{\partial (\hat y_i^{(t-1)})^2}$。其中$g_i$和$h_i$分别对应一阶倒和二阶倒数，正则项$T$表示叶子节点数目，$w$表示叶子的分数。$\gamma$空值叶子节点的个数，保证叶子节点不会过多分裂，而$\lambda$空值叶子结点的分值，避免分值过大造成过拟合。

对于第$t$步而言，前面的$t-1$步已经固定，因此有一阶、二阶梯度$g_i$和$h_i$为一个常数。因此目标函数可以化简为

$$\hat \zeta^t=\sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)\tag{4}$$

定义$I_j=\{x|q(x_i)=j\}$,表示为叶子结点$j$中的样本。所以上式(3)可以重写为

$$\hat\zeta^{(t-1)}=\sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if^2_t(x_i)]+\gamma T + \frac{1}{2}\lambda \sum_{j=1^T}w_j^2\tag{5}$$ $$=\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 \tag{6}$$

这里其实进行了一个转换，对于公式5而言，计算的损失函数是将所有数据得到损失函数。对于决策树，样本最终会落到叶子结点，因此公式6是通过叶子节点求损失值。

对于固定结构的$q(x)$，即改树节点时固定的，可以计算叶子结点$j$的最优权重$w_j^*$

$$w_j^*=-\frac{2\sum_{i\in I_j}g_i}{\sum_{i\in I_j}h_i+\lambda}$$

将结果带入上式6有

$$\hat \zeta^{(t)}=-\frac{1}{2} \sum_{j=1}^T\frac{(\sum_{i\in I_j}g_i)^2}{\sum_{i\in I_j}h_i+\lambda}\tag{7}$$

定$G_j=\sum_{i\in I_j}g_i$,$H_j=\sum_{i\in I_j}h_i$，则有

$$w_j^*=-\frac{G_j}{H_j+\lambda}$$

将上式带入公式7化简有

$$\zeta^{(t)}=-\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}\tag{8}$$

对于Xgboost使用泰勒展开的原因是因为想统一损失函数的形式，方便自定义损失函数。

1.2最佳切分点算法

xgboost支持两种实现，贪心算法和近似算法。sklearn中GBDT是贪心算法

1）贪心算法，和GBDT一样，暴力枚举

1、对于所有叶子节点枚举可用的特征，并且将特征值按照升序排序

2、计算节点分裂时候的收益

3、选择收益做大的节点和特征进行分裂

4、重复1，直到分裂结束

关键点在于对收益的计算

假设某一节点完成分裂，在分裂前，其目标函数为

$$L(y,\hat y_i)=-\frac{1}{2}[\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}]+\gamma\tag{9}$$

分裂后的目标函数为

$$L=-\frac{1}{2}[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}]+2\gamma\tag{10}$$

所以分裂一个节点的收益可以从用式（9）-（10）

$$Gain=-\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$$

G表示所有叶子节点的梯度

2)近似算法

作用在于选择，当数据量比较大，无法全部读入内存时，给出近似最优解。对比贪心算法，可能在精度上有所缺失，但是提升了速度，降低了内存消耗。

该算法的核心思想是根据特征分布的分位数提出候选点，然后将特征映射到候选划分的桶之中，然后统计桶中的聚合信息(指的前面的$g$和$h$)，找到所有区间最佳分裂点。

1、对于特征k根据分位数找到候选集合

2、将样本映射到改候选集合对应的分区桶中

该算法有两种变体，区别在于何时剔除候选点：

• Global：在初始阶段就给出所有候选节点，并且在后续分裂中使用相同的分裂节点。
• Local：每次分裂重新提出候选节点

分位图

加权分位图：

由于前面我们知道目标函数为

$$L=\sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)\tag{11}$$

由于$g_i$和$h_i$是有上一轮迭代得到，因此都是常数，所以上式可以变形为：

$$L\approx\sum_{i=1}^n\frac{1}{2}h_i[(f_t(x_i)+\frac{g_i}{h_i})^2]+\Omega(f_t)+C \\C=-\frac{g_i^2}{h_i}\tag{12}$$

这样损失函数就变成了加权的形式，因此对于每个样本，其实权值是不等的，所以采用加权分位图。

1.3 稀疏感知分裂

在实际问题中，通常输入数据都是稀疏的，造成稀疏的原因有：

• 数据缺失
• 一些统计量常常为0
• 特征工程的结果，如one-shot

稀疏感知算法的目的是给每个节点一个默认的分裂方向，其思想非常简单，就是分别计算缺失值样本分裂到左边或者右边是的收益，选择收益大的一个分支作为最优缺省值方向

2. 工程优化

2.1 块结构设计

树学习中最耗时的部分是数据排序。为了减少排序的成本，我们提出将数据存储在内存单元中，称之为block。每个block中的数据每列根据特征取值排序，并以压缩列（CSC）格式储存。这种输入数据布局只需要在训练前计算一次，可以在后续迭代中重复使用。

• 每个块包含一个或者多个已经排好序的特征
• 缺失值将不在进行排序
• 每个特征值都会存储样本梯度统计值索引

因为每个特征都是独立存放，因此在选择特征进行分裂的时候可以分布式实现

2.2 缓存方法优化

算法是通过行索引提取梯度统计量，但是在排序之后就会乱掉，不能够直接访问。并且当统计量没法放进CPU缓存是，会导致访问失败，因此xgb给每个线程分配一个内部缓冲区。

2.3 核外快计算方式

对于数据量比较大的数据，没有办法存储到内存，可以考虑部分读取，将数据存储到硬盘，但是硬盘读取会占用大量时间

XGBoost采用两种方式降低硬盘读取开销

1、块压缩：对Block进行案列压缩，并且在读取时解压

2、块拆分：将每个块存储到不同的磁盘，然后从多个磁盘读取增加吞吐量。

3. GBDT和XGBoost区别

• 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
• 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
• xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
• Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
• 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
• 对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
• xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
• 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

调参技巧略，直接看API就行了。。。。懒得总结了

参考资料

[1].https://www.zhihu.com/question/41354392/answer/98658997

[2].https://mp.weixin.qq.com/s/LoX987dypDg8jbeTJMpEPQ

[3].行抽样、列抽样