XGBoost原理必知必会

原理推导

定义损失函数的一般形式为$L$ ，虽然很多教程默认为$MSE$ ,但是这样更有一般性。基学习器为$T(X, \Theta)$ , 其中$\Theta$就是学习器的参数

那么：

$$L(y, y_i^k) = L(y, y_i^{k - 1} + T(X_i, \Theta)) = L(y, y_i^{k - 1}) + T(X_i, \Theta) \frac{\\partial L(y, y_i^{k - 1})}{\\partial y_i^{k - 1}} + \frac{1}{2} T^2(X_i, \Theta) \frac{\\partial ^2 L(y, y_i^{k - 1})}{\\partial (y_i^{k - 1})^ 2}$$

注意了，$g_i$和$h_i$的公式虽然丑陋，但是一旦确定$L$的形式，$g_i$和$h_i$是可以推导出一个确定的值或者一个简洁的形式。

比如，假设$L = MSE$, 那么$g_i = \frac{ \\partial (y - y_i^{k - 1})^2 }{y_i^{k - 1}} = 2 (y_i^{k -1} - y)$ , $h_i = 2$

这里将一阶导数和二阶导数分别记为$g_i$和$h_i$从而方便数学，目标函数$Obj$为：

$$Obj = \sum_i L(y_i, y_i^k) = \sum_i L(y, y_i^{k - 1}) + T(X_i, \Theta) g_i + \frac{1}{2} T^2(X_i, \Theta) h_i$$

肯定是还要对模型做些防过拟合的操作，我们假设基学习器是最常用的Cart树， 那么树的复杂程度由叶子结点的个数$T$和每个叶子节点的输出值$T_i$表示。

因为XGBoost是一个加法模型，训练出来的N棵树加起来才是最终输出，所以如果某一棵树的输出结果非常大，那么它将会主导总体的输出结果，容易过拟合，因此，我们希望每棵树的叶子节点的输出值尽可能地都要小

因此基模型做正则化公式：$T + \sum_{j = 1} \frac{1}{2} ||T_j||^2$ ， 其中$j$表示树的第$j$个叶子节点，$T_j$表示第$j$个叶子节点的输出值。

目标函数又改写成了：

$$Obj = \sum_{i = 1}[ L(y, y_i^{k - 1}) + T(X_i, \Theta) g_i + \frac{1}{2} T(X_i, \Theta) h_i ] + T + \sum_{j = 1} \frac{1}{2} ||T_j||^2$$

反正每个样本$i$总是会输出到某个叶子结点$j$上，输出结果是$T_j$ , 那么上述公式$\sum_{i = 1}$的部分不如直接改成用叶子结点表示，此外，$L(y, y_i^{k - 1})$是固定值，不影响优化，所以公式更新为：

$$Obj = \sum_{j = 1}[ (j节点的样本个数) \cdot T_j \cdot G_j + \frac{1}{2} \cdot (j节点的样本个数) \cdot T^2_j H_j ] + T + \sum_{j = 1} \frac{1}{2} ||T_j||^2 \\ = \sum_{j = 1}[ (j节点的样本个数) \cdot T_j \cdot G_j + \frac{1}{2} \cdot T^2_j ((j节点的样本个数) \cdot H_j + 1 ) ] + T$$

要想优化$Obj$, 就等价于优化 $(j节点的样本个数) \cdot T_j \cdot G_j + \frac{1}{2} \cdot T^2_j ((j节点的样本个数) \cdot G_j + 1 )$, 这就是一个简单的一元二次方程，通过判别公式就能得到最优值的位置和大小

$$T_j^* = \frac{ (j节点的样本数) \cdot G_j }{(j节点的样本数) \cdot H_j + 1}\\ Obj_{min} = ... (不写了，反正就是代入T_j^*得到一元二次方程的最小值)$$

训练方法

已经推导出了结论：需要让一棵树的的叶子结点$j$的输出值为$T_j^*$， 而优化目标的值变为$Obj_{min}$ ,现在问题是如何构造这么一颗Cart树 。

首先，假设有$A, B, C$三个特征：

特征	取值范围
特征A	[1, 3, 6, 8, 10]
特征B	[3, 5, 9, 89, 49]
特征c	[2, 4, 5, 7, 10, 22]

遍历每一个特征，对每一个特征遍历所有可能得分裂节点，分别计算分裂之前的$Obj$ 和分裂之后的左子树的$Obj_{left}$ ，右子树的$Obj_{right}$ 。由于我们计算过$Obj$的公式，所以这些都是能够直接得到具体的值。我们比较分裂的增益$Gain = Obj_{left} + Obj_{right} - Obj$ ， 通过找到最大增益来确定最佳分裂特征和分裂值。

常见疑难点

训练速度太慢了，怎么办？

XGBoost在工程实现上，采用了预排序的思路来加速训练。比如对于特征A，我们对特征A的所有可能取值进行排序（上面表中已经是排序好的结果）

当我们选择某个取值分裂节点，将会得到左子树和右子树，分别算出$Obj$ , 如果此时继续算下一个特征取值作为分裂节点时候，只需要将部分右子树的样本挪到左子树中，大大降低计算量。

如何并行化？

XGboost本身是串行模型，是无法并行化的，后一棵树的生成必须要等待前一棵树生成完全。但是树内部的生成是可以并行化的。

XGBoost内部将数据按照Block块结构存储, 具体来说，是按照特征列来存储数据。块结构允许对每个特征独立处理，比如一个线程计算在特征A上的分裂增益，另一个线程计算在特征B上的分裂增益。此外Block块结构更是利用了计算机的局部性原理，因为遍历某个特征的所有可能取值的时候，需要经常对样本进行分类（分类到左子树还是右子树中），块数据直接将特征列和样本数据放在一起，缓存命中率更高。

总结： 使用Block来存储一整个特征列的数据，不同特征计算信息增益就可以多线程并行化了。 在Block内部，早起的XGBoost版本是预排序的思路，因为这样去找最佳分裂点的时候更快。后来的版本采用的是LightGBM中的直方图近似法，将连续型特征分隔到不同的Bin箱中，这样就等价于只有不同的Bin箱中的数据，只需要 计算Bin箱内部的梯度和海塞矩阵。

高维特征如何处理

我们知道，在进行特征分裂的时候，需要遍历所有特征，还要遍历特征的所有取值，那么在高维特征情况下，遍历特征取值将会非常耗时。

XGBoost通过分桶的思路（也叫做直方图近似法）来近似，对某个特征（比如A） 的所有可能性取值进行排序，然后分成若干个桶，分别统计各个桶的$G_i$和$H_i$ , 然后对各个桶尝试分裂求增益，这种方法将会减少训练时间

过拟合如何缓解

除了上述了正则化思路，XGBoost还借鉴了RF中的随机特征选择的方法，也叫做列抽样。对于某个节点进行分裂的时候，何必遍历所有的特征（比如A，B，C），抽一部分不好吗，比如就抽出A和B再各自算分裂增益。

XGBoost的level wise生长策略也可以当做是缓解过拟合的措施。对于一层的节点分裂时候是同时进行分裂的，不会让某一个节点过度分裂（leaf wise），当然这样的方式内存占用稍高。

怎么做分类问题

我们知道，基学习器Cart树是可以做分类也可以做回归问题。

在二分类中，我们直接将整体模型的输出结果做Sigmoid处理，这样就将实数值的输出变成了概率，那么损失函数修改为对数损失(Log Loss) ，即：

$$Log Loss(y, \hat{y}_i^k) = -(y \log (\hat{p_i}) + (1 - y) \log( 1 - \hat{p_i}))\\ \hat{p_i} = sigmoid(\hat{y}_i^k)$$

这个也是能算一阶导和二阶导的：

$$g_i = \frac{\partial LogLoss}{\partial \hat{y}_i^k } = \hat{p_i} - y_i\\ h_i = \frac{ \partial^2 LogLoss }{ \partial (\hat{y}_i^k)^2 } = \hat{p_i} (1 - \hat{p_i})$$

在多分类问题中，XGBoost的输出稍微不一样，因为一棵树是无法输出多个类别的概率，我们就让一棵树专注于一个类别的预测,这样，$N$棵树输出了$N$个类别的分数，再通过softmax函数归一化为概率

$$p_i = \frac{\exp (f_i(x))}{\sum_{j = 1}^C \exp(f_j(x))}$$

每一轮构造N棵树, 训练$M$轮就构造$M \cdot N$棵树。

xgboost特征的重要性是如何评估的

特征重要性评估是非常常见的问题，评估方法也是GBDT类模型中通用的。

可以通过基尼指数来计算特征重要性：训练过程中记录下特征分裂的总次数（分裂多肯定重要嘛），总/平均信息增益来对特征重要性进行量化，最后将所有特征的重要性排序就行了，这是单个树种特征重要性评估方法。那么GBDT/XGBoost是多棵树Ensemble，直接取平均就好了

LR和XGBoost哪个适合处理高维稀疏数据

GBDT的树模型（XGBoost、LightGBM）都不太适合处理高维数据，LR更加适合。

高维稀疏特征大部分都是0，只有少部分是非0. 树模型在分裂特征的时候只能利用到非常少量的非0信息，而LR采用权重能够很好地处理这一点。类似的也能解释，GBDT不太适合one hot。