XGBoost

xgboost和gbdt都是boosting方法，除了工程实现、解决问题上的一些差异外，最大的不同就是目标函数的定义

目标函数

XGboost 也是前向分布算法的加法模型，这里的损失函数更加复杂，加入了正则项，将目标损失函数看成 $\hat{y}_{i}^{t-1}+f_{t}\left(x_{i}\right)$ 的函数泰勒展开，展开了二阶导

boosting：前向分布算法，从前往后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数，就可以简化复杂度

模型是加法模型： $\hat{y}_{i}=\sum_{k=1}^{K} f_{k}\left(x_{i}\right), f_{k} \in F$ ，第 t 步对 $x_i$ 的预测为： $\hat{y}_{i}^{t}=\hat{y}_{i}^{t-1}+f_{t}\left(x_{i}\right)$
指导原则是最小化目标函数： $\begin{aligned} O b j^{(t)} &=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{t}\right)+\sum_{i=i}^{t} \Omega\left(f_{i}\right) =\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{t-1}+f_{t}\left(x_{i}\right)\right)+\Omega\left(f_{t}\right)+\text { constant } \end{aligned}$
如果损失函数是平方损失函数： $\begin{aligned} O b j^{(t)} &=\sum_{i=1}^{n}\left(y_{i}-\left(\hat{y}_{i}^{t-1}+f_{t}\left(x_{i}\right)\right)\right)^{2}+\Omega\left(f_{t}\right)+\text { constant } =\sum_{i=1}^{n}\left[2\left(\hat{y}_{i}^{t-1}-y_{i}\right) f_{t}\left(x_{i}\right)+f_{t}\left(x_{i}\right)^{2}\right]+\Omega\left(f_{t}\right)+\text { constant } \end{aligned}$

泰勒公式： $f(x+\Delta x) \approx f(x)+f^{\prime}(x) \Delta x+\frac{1}{2} f^{\prime \prime}(x) \Delta x^{2}$ ，把 $\hat{y}_{i}^{t-1}$ 看成 $x$ ， $f_{t}\left(x_{i}\right)$ 看成 $\Delta x$ ，目标函数变为：

$O b j^{(t)}=\sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}_{i}^{t-1}\right)+g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right)+\text {constant}$ ，g 是损失函数一阶导，h 是二阶

函数中的常量在最小化的过程中不起作用，可以从上式中移除常量项，得 $O b j^{(t)} \approx \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right)$

基于决策树的目标函数

决策树假设叶子节点个数为 $T$ ，是由所有叶子节点对应的值组成的向量 $w \in R^{T}$ ，和一个把特征向量映射到叶子节点索引的函数 $q : R^{d} \rightarrow\{1,2, \cdots, T\}$ 组成的，因此决策树可以定义为 $f_{t}(x)=w_{q(x)}$

决策树的复杂度由正则项 $\Omega\left(f_{t}\right)=\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2}$ 定义，即叶子节点的数量和叶子节点对应值向量的 L2范数决定

所以 $\begin{aligned} O b j^{(t)} =\sum_{i=1}^{n}\left[g_{i} w_{q\left(x_{i}\right)}+\frac{1}{2} h_{i} w_{q\left(x_{i}\right)}^{2}\right]+\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2} =\sum_{j=1}^{T}\left[\left(\sum_{i \in I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T \end{aligned}$

定义 $G_{j}=\sum_{i \in I_{j}} g_{i}, H_{j}=\sum_{i \in I_{j}} h_{i}$ ，上式可以写成 $O b j^{(t)}=\sum_{j=1}^{T}\left[G_{i} w_{j}+\frac{1}{2}\left(H_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T$

令目标函数一阶导为0，可求得叶子节点j对应的值为： $w_{j}^{*}=-\frac{G_{j}}{H_{j}+\lambda}$ ，此时目标函数的值为： $O b j=-\frac{1}{2} \sum_{j=1}^{T} \frac{G_{j}^{2}}{H_{j}+\lambda}+\gamma T$

经过泰勒展开，并带入正则项，目标函数变为 $O b j^{(t)}=\sum_{j=1}^{T}\left[G_{i} w_{j}+\frac{1}{2}\left(H_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T$

对w求偏导并令为0解得： $w_{j}^{*}=-\frac{G_{j}}{H_{j}+\lambda}$ ，此时目标函数的值为： $O b j=-\frac{1}{2} \sum_{j=1}^{T} \frac{G_{j}^{2}}{H_{j}+\lambda}+\gamma T$

而这里的 $G_j$ 和 $H_j$ 的取值都是由第j个树叶上数据样本决定的，而第j个树叶上所具有的数据样本是由树结构函数决定的。也就是说树的结构确定，相应的目标函数就能够根据上式计算出来。所以树的生成问题就转换为找到一个最优的树结构，使得它具有最小的目标函数

最优切分点划分算法

如何找到最优的树结构？枚举所有的树结构肯定不行，所以我们利用贪心法，每次尝试对已有的叶子节点加入一个分割：

从深度为 0 的树开始，对每个叶节点枚举所有的可用特征；
针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；
选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集
回到第 1 步，递归执行到满足特定条件为止

对于一个具体的分割，我们获得的增益可以由如下公式计算得到：

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

其中第一项代表左子树分数，第二项代表右子树分数，第三项代表不分割我们可以获得的分数，最后一个代表新叶子节点引入的复杂度代价

为什么XGBOOST要用二阶展开，优势在哪里？

xgboost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了xgboost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。

XGboost如何分裂

xgboost使用levelwise的生成策略，即每次对同一层级的全部叶子节点尝试进行分裂。利用贪心算法，遍历所有特征的所有特征划分点，计算 loss function 最小值。与 cart 不同的是使用的目标函数不同。具体做法就是分裂后的目标函数值比单叶子节点的目标函数的增益。为了限制树生长过深，还加了阈值，只有增益大于阈值才进行分裂。还会设置一个超参数max_depth，即最大深度。超过最大深度则停止分裂。

xgboost采用特征并行的方法进行计算选择要分裂的特征，即用多个线程，尝试把各个特征都作为分裂的特征，找到各个特征的最优分割点，计算根据他们分裂后产生的增益，选择增益最大的那个特征作为分裂的特征。

XGBoost 缺点

每轮迭代时，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。

为什么xgboost不适合高维稀疏矩阵

高维稀疏的 ID 类特征会使树模型的训练效率变得极为低效，容易过拟合。因为树模型的训练过程是一个贪婪选择特征的算法，要从候选特征集合中选择一个使分裂后信息增益最大的特征来分裂。按照高维的ID特征做分裂时，子树数量非常多，计算量会非常大，训练会非常慢。同时按照 ID分裂得到的子树的泛化性也比较弱，样本稀疏时也容易过拟合

XGBoost

目标函数

基于决策树的目标函数

最优切分点划分算法

推荐阅读更多精彩内容