AI目录：sheng的学习笔记-AI目录-CSDN博客
前置知识：
sheng的学习笔记-AI-集成学习（bagging，随机森林，堆叠法）
sheng的学习笔记-AI-决策树（Decision Tree）
目录
基础知识
什么是Xgboost
定义
举例
完整流程
流程图
建树过程
总体算法
初始化预测值
目标函数
什么是泰勒公式
泰勒公式在xgboost的推导
新增t棵树
泰勒展开（核心）编辑
定义树结构
XGBoost 单棵树的标准公式
每个符号意思
整棵树就是
举个例子
按叶子聚合
每个叶子的最优权重
节点分裂
XGBoost 的分裂依据是：
计算gain
节点分裂总结一下
单个特征值的最优切分点
加权分位数缩略图
XGBoost 建树逻辑总结（第t颗树）
基础知识
集成学习，就是指构建多个弱分类器对数据集进行预测，然后用某种策略将多个分类器预测的结果集成起来，作为最终预测结果
集成学习分为Boosting和Bagging。
- Boosting流派，各分类器之间有依赖关系，必须串行，比如Adaboost、GBDT(Gradient Boosting Decision Tree)、Xgboost
- Bagging流派，各分类器之间没有依赖关系，可各自并行，比如随机森林（Random Forest）
Xgboost是boosting流派，
什么是Xgboost
定义
Xgboost 的全称是eXtreme Gradient Boosting，boosting算法每一步的弱分类器生成都是依据损失函数的梯度方向，则称之为梯度提升(Gradient boosting)
举例
这一家子人中每个人想玩游戏的意愿值。我们用xgboost解决这个问题，就是我先训练出来第一棵决策树， 预测了一下小男孩想玩游戏的意愿是2， 然后发现离标准答案差一些，又训练出来了第二棵决策树， 预测了一下小男孩想玩游戏的意愿是0.9， 那么两个相加就是最终的答案2.9。这个其实就接近了标准答案。所以xgboost是训练出来的弱分类结果进行累加就是最终的结论。
xgboost方案跟GBDT很像，比较大的不同是目标函数的定义，但这俩在策略上是类似的，都是聚焦残差（更准确的说， xgboost其实是gbdt算法在工程上的一种实现方式），GBDT旨在通过不断加入新的树最快速度降低残差，而XGBoost则可以人为定义损失函数（可以是最小平方差、logistic loss function、hinge loss function或者人为定义的loss function），只需要知道该loss function对参数的一阶、二阶导数便可以进行boosting，其进一步增大了模型的泛化能力，其贪婪法寻找添加树的结构以及loss function中的损失函数与正则项等一系列策略也使得XGBoost预测更准确。
完整流程
流程图
建树过程
假设我想预测学生考试分数， 给定若干个学生属性(比如天赋，每天学习时间，是否谈恋爱等)，
- 初始化三个样例的考试成绩预测值为0，属性为
(天赋高、不恋爱、每天学习时间有16个小时)，
（天赋低、不恋爱、每天学习时间有16个小时)，
(天赋高、不恋爱、每天学习时间有6个小时)，
真实成绩分别为100，70，86分。
- 通过一个决策树A， 我们可以看到一个天赋属性的预测结果：天赋高的人+90， 不高的人+60
- 在构建第二颗决策树时就会考虑残差(100-90=10)，(70-60)=10，(86-90=-4)来构建一颗新的树
- 通过决策树B, 可以看到每天学习时间高于10小时的+5，低于10小时的-5
- 通过决策树C， 可以看到谈恋爱的-1， 单身狗的+1
- 后面依次类推，还可能有更多的决策树通过学生的某些属性来推断分数。 XGboost就是这样一个不断生成新的决策树A,B,C,D…的算法，当迭代次数达到上限或是残差不再减小，最终生成的决策树算法就是树A+B+C+D+…的和的决策树。
我们有了第一棵树， 通过这个树的预测结果：
那么我们建立第二棵树的时候，我们是考虑的残差，也就是样本其实变成了下面这样：
通过最小化残差学习到一个通过学习时间属性构建的决策树得到了90+5，60+5，90-5的预测值，再继续通过（100-95=5）（70-65）（86-85）的残差构建下一个决策树，以此类推，当迭代次数达到上限或是残差不再减小是停止，就得到一个拥有多个（迭代次数）决策树的强分类器。
总体算法
XGBoost算法是采用分步前向加性模型，只不过在每次迭代中生成弱学习器后不再需要计算一个系数，XGBoost 是由 k 个基模型组成的一个加法运算式：
XGBoost算法通过优化结构化损失函数（加入了正则项的损失函数，可以起到降低过拟合的风险）来实现弱学习器的生成，并且XGBoost算法没有采用搜索方法，而是直接利用了损失函数的一阶导数和二阶导数值，并通过预排序、加权分位数等技术来大大提高了算法的性能。
初始化预测值
初始化三个样本的考试成绩预测值为0
目标函数
损失函数可由预测值与真实值yi进行表示：
其中， n为样本的数量。
模型的预测精度由模型的偏差和方差共同决定，损失函数代表了模型的偏差，想要方差小则需要在目标函数中添加正则项，用于防止过拟合。所以目标函数由模型的损失函数 L 与抑制模型复杂度的正则项Ω组成，目标函数的定义如下：
其中，正则项是将全部t棵树的复杂度进行求和，添加到目标函数中作为正则化项，用于防止模型过度拟合。
由于XGBoost是boosting族中的算法，所以遵从前向分步加法，以第t 步的模型为例，模型对第i个样本 Xi的预测值为：
其中，y（t-1）是由第t-1的模型给出的预测值，是已知常数，ft(xi) 是这次需要加入的新模型的预测值。此时，目标函数就可以写成：
注意上式中，只有一个变量，那就是第t棵树ft(xi)，其余都是已知量或可通过已知量可以计算出来的。
解释一下上图第二行到第三行到推导：将其中正则项进行拆分，由于前t-1棵树的结构已经确定，因此前t-1棵树的复杂度之和可以用一个常量表示
什么是泰勒公式
泰勒公式（Taylor formula）本质上是在说：
任何“足够光滑”的函数，都可以在某一点附近，用一个多项式来近似表示。
核心思想
如果一个函数 f(x)在某点 a 附近变化平滑，那么它可以展开成：
- 常数项（函数值）
- 一阶项（斜率）
- 二阶项（曲率）
- 三阶项……
- 无限叠加
多项式越高阶，近似越精确。
泰勒公式
其中Rn(x)是截断到 n 阶之后，剩下没写出来的误差，太小了，在xgboost中去掉，通用写法为：
举个例子：
如果换一个“机器学习视角”，泰勒展开就是：
用低阶导数信息，把一个复杂函数变成一个“局部二次函数”。
XGBoost 本质是：
用泰勒展开，把损失函数变成一个可以逐步优化的二次形式。
泰勒公式在xgboost的推导
新增t棵树
XGBoost优化的目标是：
其中正则项：
代入新模型
泰勒展开（核心）![]()
解释一下泰勒原始公式到泰勒二阶展开公式：
定义“增量”
这里借用别人的写法（注意，此处的fx有歧义，上面的fx是第t个模型函数）：
继续推导去掉常数项
定义树结构
上面是推导过程的树，下面是具体的树的样子
XGBoost 单棵树的标准公式
每个符号意思
整棵树就是
举个例子
假设我们只有两个特征，训练出一棵很简单的树，这棵树长这样：
每个叶子的输出（w）
假设训练完后得到：
- leaf 1 → w1=2.0w_1 = 2.0w1=2.0
- leaf 2 → w2=−1.0w_2 = -1.0w2=−1.0
- leaf 3 → w3=0.5w_3 = 0.5w3=0.5
来算具体样本
汇总得到：
根据公式，得出：
这里的2.0，-1.0，0.5都是w的值，后续的优化计算就是计算最优的w
按叶子聚合
遍历所有的样本后求每个样本的损失函数，但样本最终会落在叶子节点上，所以我们也可以遍历叶子节点，然后获取叶子节点上的样本集合，最后再求损失函数。即我们之前是单个样本，现在都改写成叶子结点的集合，G和H在当前t轮次，是常数，但是在整个训练过程中不是常量，所以t轮只有w是变量
目标函数变成：
推导最终的目标函数
每个叶子的最优权重
代回得到目标函数的最优值
节点分裂
XGBoost 的分裂依据是：
比较“分裂前 vs 分裂后”的目标函数变化（loss reduction）
也就是：
计算gain
不分裂的loss
如果分裂成左右子节点
计算 Gain
需要判断：“分裂后是否让 loss 下降足够多”
如果Gain>0,裂是有收益的 → 可以分裂
如果Gain<=0，分裂没有意义 → 不分裂
注意：这是 XGBoost 的精髓：
👉原始 loss 不用再算了
👉 只用：
- 一阶信息（G）
- 二阶信息（H）
就可以决定结构
XGBoost 的分裂本质是：
用“泰勒二阶近似下的目标函数下降量（Gain）”作为分裂标准，贪心选择让 Gain 最大的切分点。
节点分裂总结一下
- 从深度为 0 的树开始，对每个叶节点枚举所有的可用特征；
- 针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；（这个过程每个特征的收益计算是可以并行计算的，xgboost之所以快，其中一个原因就是因为它支持并行计算，而这里的并行正是指的特征之间的并行计算，千万不要理解成各个模型之间的并行）
- 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集（这里稍微提一下，xgboost是可以处理空值的，也就是假如某个样本在这个最优分裂点上值为空的时候， 那么xgboost先把它放到左子树上计算一下收益，再放到右子树上计算收益，哪个大就把它放到哪棵树上。）
- 回到第 1 步，递归执行到满足特定条件为止
单个特征值的最优切分点
假设我有这一家子人样本，每个人有性别，年龄，兴趣等几个特征，我想用xgboost建立一棵树预测玩游戏的意愿值。首先，五个人都聚集在根节点上，现在就考虑根节点分叉，我们就遍历每个特征，对于当前的特征，我们要去寻找最优切分点以及带来的最大收益，比如当前特征是年龄，我们需要知道两点：* 按照年龄分是否有效，也就是是否减少了obj的值 * 如果真的可以分，特征收益比较大， 那么我们从哪个年龄点分开呢？
对于这两个问题，我们可以这样做，首先我们先把年龄进行一个排序， 如下图：
这就是xgboost贪心建树的一个思路了，即遍历所有特征以及所有分割点，每次选最好的那个。GBDT也是采用的这种方式， 这算法的确不错，但是有个问题：就是计算代价太大了，尤其是数据量很大，分割点很多的时候，计算起来非常复杂并且也无法读入内存进行计算。
所以作者想到了一种近似分割的方式（可以理解为分割点分桶的思路），选出一些候选的分裂点，然后再遍历这些较少的分裂点来找到最佳分裂点。那么怎么进行分桶选候选分裂点才比较合理呢？我们一般的思路可能是根据特征值的大小直接进行等宽或者等频分桶， 像下面这样
扩展一下等分发，比如三分位发：
上面就是等频和等宽分桶的思路了
加权分位数缩略图
类似个平方损失，但是加了权重，权重就是二阶梯度，利用二阶梯度进行切分 为什么这么干？因为二阶梯度类似一个频率，所以相当于出现了多次，所以按照它进行切分
XGBoost 建树逻辑总结（第t颗树）
注意：在计算Gain的时候，因为已经对于w已经消元了，所以此处不需要计算w，但是从数学推导的过程中，在此过程是包含了w的，从工程实现角度在树的结构确认了之后再计算w
一文读懂XGBoost（含公式推导）_xgboost公式-CSDN博客
机器学习分类算法之XGBoost（集成学习算法）-CSDN博客
【白话机器学习】算法理论+实战之Xgboost算法-腾讯云开发者社区-腾讯云
