3 xgboost

1 定义

1.1 模型定义

1.2 损失函数

1.3 化简损失函数

xgboost比赛以及工程利器。目前存在大量有关算法文档。

XGBoost（eXtreme Gradient Boosting）是一种基于决策树集成的机器学习算法，被广泛应用于分类、回归和排名等任务。XGBoost 在 Kaggle 等数据科学竞赛中取得了很好的表现，被认为是一种高效且强大的机器学习算法。

XGBoost算法通过优化结构化损失函数（加入了正则项的损失函数，可以起到降低过拟合的风险）来实现弱学习器的生成，并且XGBoost算法没有采用搜索方法，而是直接利用了损失函数的一阶导数和二阶导数值，并通过预排序、加权分位数等技术来大大提高了算法的性能。

1 定义

1.1 模型定义

XGBoost与GBDT比较大的不同就是目标函数的定义，基本思想是一致的，同样是利用加法模型与前向分步算法实现学习的优化过程。预测过程如下：

1.2 损失函数

1.3 化简损失函数

1 把 $\hat{y}^{k} = \hat{y}^{k-1} + f_{k}(x_i)$ 替换进目标函数。过程如下

$obj = \sum l(y_i,\hat{y_i}) +\sum \Phi (f_k)\\ =\sum l(y_i,\hat{y_i}^{k-1}+f_{k}(x_i)) + \sum \Phi (f_k)$

$f(x+\Delta x) = f(x)+f'(x)\Delta x+\frac{1}{2}f''(x)\Delta x$

$l(y_i,\hat{y_i}^{k-1}+f_{k}(x_i)) = l(y_i,\hat{y_i}^{k-1}) +\frac{\partial l(y_i,\hat{y_i}^{k-1})}{\partial f_{k}(x_i)}f_k(x_i) + \frac{\partial^2l(y_i,\hat{y_i}^{k-1}) }{\partial f_{k}(x_i)^2}f^{2}_{k}(x_i)$

什么时候上面的损失函数有最优解呢？

记住叶子的值是什么！先求每个叶子结点中的样本的偏差的一次导数和二次导数相除，再对所有叶子节点求和。

如下：需要知道样本的在损失函数的一阶导数g与二阶导数信息H.

2 面试知识点

1.1XGBoost与GBDT有什么不同

基分类器：XGBoost的基分类器不仅支持CART决策树，还支持线性分类器，此时XGBoost相当于带L1和L2正则化项的Logistic回归（分类问题）或者线性回归（回归问题）。
导数信息：XGBoost对损失函数做了二阶泰勒展开，GBDT只用了一阶导数信息，并且XGBoost还支持自定义损失函数，只要损失函数一阶、二阶可导。
正则项：XGBoost的目标函数加了正则项，相当于预剪枝，使得学习出来的模型更加不容易过拟合。
列抽样：XGBoost支持列采样，与随机森林类似，用于防止过拟合。
缺失值处理：对树中的每个非叶子结点，XGBoost可以自动学习出它的默认分裂方向。如果某个样本该特征值缺失，会将其划入默认分支。
并行化：注意不是tree维度的并行，而是特征维度的并行。XGBoost预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度

1.2 XGBoost为什么使用泰勒二阶展开

精准性：相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，可以更为精准的逼近真实的损失函数
可扩展性：损失函数支持自定义，只需要新的损失函数二阶可导。

4. XGBoost为什么可以并行训练。

XGBoost的并行，并不是说每棵树可以并行训练，XGB本质上仍然采用boosting思想，每棵树训练前需要等前面的树训练完成才能开始训练。
XGBoost的并行，指的是特征维度的并行：在训练之前，每个特征按特征值对样本进行预排序，并存储为Block结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。

5. XGBoost为什么快。

分块并行：训练前每个特征按特征值进行排序并存储为Block结构，后面查找特征分割点时重复使用，并且支持并行查找每个特征的分割点
候选分位点：每个特征采用常数个分位点作为候选分割点
CPU cache 命中优化：使用缓存预取的方法，对每个线程分配一个连续的buffer，读取每个block中样本的梯度信息并存入连续的Buffer中。
Block 处理优化：Block预先放入内存；Block按列进行解压缩；将Block划分到不同硬盘来提高吞吐

6. XGBoost防止过拟合的方法

XGBoost在设计时，为了防止过拟合做了很多优化，具体如下：

目标函数添加正则项：叶子节点个数+叶子节点权重的L2正则化
列抽样：训练的时候只用一部分特征（不考虑剩余的block块即可）
子采样：每轮计算可以不使用全部样本，使算法更加保守
shrinkage: 可以叫学习率或步长，为了给后面的训练留出更多的学习空间

7. XGBoost如何处理缺失值。

XGBoost模型的一个优点就是允许特征存在缺失值。对缺失值的处理方式如下：

在特征k上寻找最佳 split point 时，不会对该列特征 missing 的样本进行遍历，而只对该列特征值为 non-missing 的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找 split point 的时间开销。
在逻辑实现上，为了保证完备性，会将该特征值missing的样本分别分配到左叶子结点和右叶子结点，两种情形都计算一遍后，选择分裂后增益最大的那个方向（左分支或是右分支），作为预测时特征值缺失样本的默认分支方向。
如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子结点。

https://zhuanlan.zhihu.com/p/562983875

https://blog.51cto.com/u_15127666/3281624

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/553563.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！