XGBoost详解（原理篇）

符号定义：

n表示样本数目；

$l\left(y_{i}, \hat{y}_{i}^{(t)}\right)$ 表示与有关的损失函数，这个损失函数是可以根据需要自己定义的；

$y_{i}$ 表示样本 i 的实际值；

$\hat{y_{i}}^{(t)}$ 表示前 t 棵决策树一起对样本 i 的预测值；

$\Omega\left(f_{t}\right)$ 表示第t棵树的模型复杂度，这里是正则化项，为了惩罚更复杂的模型（通过减小树的深度和单个叶子节点的权重值），减缓过拟合。

$\Omega(f)=\gamma T+\frac{1}{2} \lambda\|\omega\|^{2}$

T为当前子树的深度，w为叶子节点的节点值。

（2）推导

A、根据Boosting的原理简化

根据Boosting的原理：第 t 棵树对样本 i 的预测值=前 t-1 棵预测树的预测值 + 第 t 棵树的预测值

即： $\hat{y}_{i}^{(t)} = \hat{y}_{i}^{(t-1)}+f_{t}\left(\mathbf{x}_{i}\right)$

这里补充一下：Shrinkage(收缩过程)：

Shrinkage即：每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。就是说它不完全信任每一个棵残差树（达到防止过拟合的效果），它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。即给每棵数的输出结果乘上一个步长η （收缩率），如下公式所示：

$\hat{y}_{i}^{(t)}=\hat{y}_{i}^{(t-1)}+\eta f_{t}\left(\mathbf{x}_{i}\right) , 0< \eta \leq 1$

后续的公式推导都默认 η = 1。

那么最初的目标函数就可以化为： $\mathcal{L}^{(t)}=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t-1)}+f_{t}\left(\mathbf{x}_{i}\right)\right)+\Omega\left(f_{t}\right)$

符号定义：

$f_{t}\left(\mathbf{x}_{i}\right)$ 表示第 t 棵决策树对样本 i 的预测值

B、根据二阶泰勒展开

分析：

我们知道，二阶泰勒展开公式： $f(x+\Delta x) \approx f(x) + f'(x)\Delta x + \frac{f''(x)(\Delta x)^{2}}{2}$

将上面的 $\mathcal{L}^{(t)}=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t-1)}+f_{t}\left(\mathbf{x}_{i}\right)\right)+\Omega\left(f_{t}\right)$ 当成 $f(x+\Delta x)$ ，即把 $\hat{y}_{i}^{(t-1)}$ 当作 x ，把 $f_{t}\left(\mathbf{x}_{i}\right)$ 当作 $\Delta x$ 。

这样一来， $\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t-1)}\right)+\Omega\left(f_{t}\right)$ 就是 $f(x)$ 啦。

那么就有：

$\mathcal{L}^{(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)$

其中：

$\mathrm{g}_{\mathrm{i}}=\frac{\partial l\left(\mathrm{y}_{\mathrm{i}}, \hat{\mathrm{y}}_{\mathrm{i}}^{\mathrm{t}-1}\right)}{\partial \hat{\mathrm{y}}_{\mathrm{i}}^{\mathrm{t}-1}}$ ——表示一阶导数，是可以求出来的已知数

$\mathrm{h}_{\mathrm{i}}=\frac{\partial^{2} l\left(\mathrm{y}_{\mathrm{i}}, \hat{\mathrm{y}}_{\mathrm{i}}^{\mathrm{t}-1}\right)}{({\partial\hat{\mathrm{y}}_{\mathrm{i}}^{\mathrm{t}-1}})^{2}}$ ——表示二阶导数，是可以求出来的已知数

C、去掉常数项

因为我们的目的是要最小化目标函数，那些常数项我们可以把它们暂时搁置。

$\mathcal{L}^{(t)} =\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)$

4、从目标函数到特征划分准则 + 叶子节点的值的确定

（1） $f_{t}\left(\mathbf{x}_{i}\right)$ 的定义

XGBoost把 $f_{t}\left(\mathbf{x}_{i}\right)$ 定义为 $w_{q(x_{i})}$

其中 $q(x_{i})$ 代表了样本 i 在哪个叶子节点上，w表示叶子结点的权重（即决策树的预测值）

（2）引入真实的 $f_{t}\left(\mathbf{x}_{i}\right)$ 和正则化项代换

$\mathcal{L}^{(t)} \approx \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}$

进一步化为： $\mathcal{L}^{(t)}=\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$

其中：

$I_{j}=\left\{i \mid q\left(x_{i}\right)=j\right\}$ 代表决策树 q 在叶子节点 j 上的取值（即表示位于第j个叶子结点有哪些样本）

这样就把累加项从样本总数变为了针对当前决策树的叶子节点。

再令 $G_{j}=\sum_{i \in I_{j}} g_{i}$ 和 $H_{j}=\sum_{i \in I_{j}} h_{i}$ ，

再次化简为：

$\mathcal{L}^{(t)}=\sum_{j=1}^{T}\left[G_{j} w_{j}+\frac{1}{2}\left(H_{j}+\lambda\right) w_{j}^{2}\right]+\gamma T$

（3）求出 $w_{j}$ —— 定下该叶子结点的值

因为我们的目的是最小化目标函数，因此我们对上式求导，令其为0。

$w_{j}^{*}=-\frac{G_{j}}{H_{j}+\lambda}$

即我们应该将叶子结点的值 $w_{j}$ 设为 $-\frac{G_{j}}{H_{j}+\lambda}$

（4）目标函数的最优解——与信息增益的连接

${\mathcal{L}^{(t)}}^{*}=-\frac{1}{2} \sum_{j=1}^{T} \frac{G_{j}^{2}}{H_{j}+\lambda}+\gamma T$

这个 ${\mathcal{L}^{(t)}}^{*}$ 又叫结构分数，类似于信息增益，可以对树的结构进行打分。

信息增益：更能确定多少——目标函数：预测对了多少

（5）特征划分准则——“信息增益”

$\operatorname{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$

其中 L 下标是值划分到左子树时的目标函数最优值，R 下标是值划分到右子树时的目标函数最优值。在实际划分时，XGBoost会基于“Gain最大”的节点进行划分。

第一部分是新的左子叶的分数（即该节点进行特征分裂后左子叶的目标函数）；第二部分是新的右子叶的分数（即该节点进行特征分裂后右子叶的目标函数）；第三部分是原来叶子的分数（即该节点未进行特征分裂前的目标函数）；第四部分是新增叶子的正则系数。

体现的意义即为：判断分裂节点后的信息增益（第一部分+第二部分）是否大于未分裂的情况，并且考虑到模型会不会太复杂的问题（如果增加的分数小于正则项，节点不再分裂）。

5、从目标函数到加权分位法（实现对每个特征具体的划分）

（1）引入原因

比如说，有一个特征A是一个离散的连续变量，有100个不同的值，范围是[1,100]。那么如果选择特征D来分裂节点时，需要尝试100种不同的划分，一个一个算然后再对比Gain，可以是可以，但会导致算法的效率很低。

XGBoost为了实现可以不用尝试每一种的划分，只选取几个值进行尝试，提出了加权分位法。

（2）“特征值重要性”的提出

为了得到值得进行尝试的划分点，我们需要建立一个函数对该特征的特征值进行"重要性"排序。根据排序的结果，再选出值得进行尝试的特征值。

（3）目标函数到平方损失

我们前面得到的目标函数长这样：

$\mathcal{L}^{(t)} =\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)$

我们把 $\frac{1}{2}h_{i}$ 提出来，变成：

$\mathcal{L}^{(t)} =\sum_{i=1}^{n}\frac{1}{2} h_{i}\left[2\frac{g_{i}}{h_{i}} f_{t}\left(x_{i}\right)+ f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right)$

然后因为 $g_{i}$ 和 $h_{i}$ 都是已知数，相当于常量，我们给他加上它们的相关运算，在后面再给他减掉一个常数，结果不变。

$\mathcal{L}^{(t)} =\sum_{i=1}^{n}\frac{1}{2} h_{i}\left[f_{t}(x_{i}) - \frac{g_{i}}{h_{i}}\right]^{2}+\Omega\left(f_{t}\right) + C$

C为常数项

现在我们得到的式子即为：真实值为 $\frac{g_{i}}{h_{i}}$ ，权重为 $h_{i}$ 的平方损失项+正则化项+常数项

（4）特征值重要性排序函数

因此，我们可以得出结论：一个样本对于目标函数值的贡献，在于其 $h_{i}$ 。因此可以根据 $h_{i}$ 对特征值的“重要性”进行排序。XGBoost提出了一个新的函数，这个函数用于表示一个特征值的"重要性"排名：（这里的特征值表示：某个等待判断分裂的节点属性，中的某个取值）

其中：

$D_{k}$ ：第k个特征的每个样本的特征值（ $x_{nk}$ ）与其相应的 $h_{i}$ 组成的集合；

$(x_{ik},h_{i})$ ：表示第 i 个样本对于第k个特征的特征值，和其对应的 $h_{i}$ ；

$D_{k} = \left \{(x_{1k},h1), ... ,(x_{nk},h_{n}) \right \}$
$r_{k}(z)$ 的分母：第k个特征的所有样本的 $h_{i}$ 的总和；
$r_{k}(z)$ 的分子：所有特征值小于z的样本的 $h_{i}$ 总和；

式子表示的意义是：特征值小于z的样本特征重要性分布占比

（5）切分点寻找

之后对一个特征的所有特征值进行排序。在排序之后，设置一个值 ϵ （采样频率）。这个值用于对要划分的点进行规范。对于特征k的特征值的划分点 $\left \{s_{k1},s_{k2},...,s_{kl} \right \}$ 有，两个相连划分点的 $r_{k}$ 值之差的绝对值要小于 ϵ （为了让相邻的划分点的贡献度都差不多）。同时，为了增大算法的效率，也可以选择每个切分点包含的特征值数量尽可能多。

（6）计算分裂点的策略

基于加权分位法，我们有两种策略进行分裂点的计算：全局策略和局部策略。

A、全局策略

即在一棵树的生成之前，就已经计算好每个特征的分裂点。在整个树的生成过程当中，用的都是一开始计算的分裂点。这也就代表了使用全局策略的开销更低，但如果分裂点不够多的话，准确率是不够高的。

B、局部策略

根据每一个节点所包含的样本，重新计算其所有特征的分裂点（即边建立树边重新更新分裂点）。

因为在一棵树的分裂的时候，样本会逐渐被划分到不同的结点中（即每个结点所包含的样本，以及这些样本有的特征值是不一样的）。因此，我们可以对每个结点重新计算分裂点，以保证准确性，但这样会使局部策略的开销更大，但分裂点数目不用太多，也能够达到一定的准确率。

（1）在分裂点数目相同，即 ϵ 相同的时候，全局策略的效果比局部策略的效果差；

（2）全局策略可以通过增加分裂点数目，达到逼近局部策略的效果

三、XGBoost对缺失值的处理

对于特征A，我们首先将样本中特征A的特征值为缺失值的样本全部剔除。然后我们正常进行样本划分。

最后，我们做两个假设：一个是缺失值全部归在左子节点；一个是归在右子节点。哪一个得到的增益大，就代表这个特征最好的划分。

Note：对于加权分位法中对于特征值的排序，缺失值不参与（即缺失值不会作为分裂点，gblinear将缺失值视为0）

四、XGBoost的优缺点

1、优点

（1）精度高

XGBoost对损失函数进行了二阶泰勒展开，一方面为了增加精度，另一方面也为了能够自定义损失函数，二阶泰勒展开可以近似许多损失函数。（对比只用到一阶泰勒的GBDT）

（2）灵活性强

XGBoost不仅支持CART，还支持线性分类器；

XGBoost还支持自定义损失函数，只要损失函数有一二阶导数。

（3）防止过拟合

A、正则化

XGBoost在目标函数中加入了正则项，用于惩罚过大的模型复杂度，有助于降低模型方差，防止过拟合。
B、Shrinkage（缩减）

主要是为了削弱每棵树的影响，让后面有更大的学习空间，学习过程更加的平缓。

C、列抽样

在建立决策树的时候，不用再遍历所有的特征了，可以进行抽样。

一方面简化了计算，另一方面也有助于降低过拟合。

（4）缺失值处理

（5）并行化操作

有一些不相关可以很好的支持并行计算

2、缺点

时间复杂度和空间复杂度都较高（预排序过程）。

欢迎大家在评论区批评指正，谢谢~

详解 XGBoost xff 7D latex 机器学习算法人工智能决策树

有关XGBoost详解（原理篇）的更多相关文章

物联网MQTT协议详解 - 2
一、什么是MQTT协议MessageQueuingTelemetryTransport：消息队列遥测传输协议。是一种基于客户端-服务端的发布/订阅模式。与HTTP一样，基于TCP/IP协议之上的通讯协议，提供有序、无损、双向连接，由IBM（蓝色巨人）发布。原理：（1）MQTT协议身份和消息格式有三种身份：发布者（Publish）、代理（Broker）（服务器）、订阅者（Subscribe）。其中，消息的发布者和订阅者都是客户端，消息代理是服务器，消息发布者可以同时是订阅者。MQTT传输的消息分为：主题（Topic）和负载（payload）两部分Topic，可以理解为消息的类型，订阅者订阅（Su
Tcl脚本入门笔记详解（一） - 2
TCL脚本语言简介•TCL（ToolCommandLanguage）是一种解释执行的脚本语言（ScriptingLanguage）,它提供了通用的编程能力：支持变量、过程和控制结构；同时TCL还拥有一个功能强大的固有的核心命令集。TCL经常被用于快速原型开发，脚本编程，GUI和测试等方面。•实际上包含了两个部分：一个语言和一个库。首先，Tcl是一种简单的脚本语言，主要使用于发布命令给一些互交程序如文本编辑器、调试器和shell。由于TCL的解释器是用C\C++语言的过程库实现的，因此在某种意义上我们又可以把TCL看作C库，这个库中有丰富的用于扩展TCL命令的C\C++过程和函数，所以，Tcl是
【Unity游戏破解】外挂原理分析 - 2
文章目录认识unity打包目录结构游戏逆向流程Unity游戏攻击面可被攻击原因mono的打包建议方案锁血飞天无限金币攻击力翻倍以上统称内存挂透视自瞄压枪瞬移内购破解Unity游戏防御开发时注意数据安全接入第三方反作弊系统外挂检测思路狠人自爆实战查看目录结构用il2cppdumper例子2-森林whoishe后记认识unity打包目录结构dll一般很大，因为里面是所有的游戏功能编译成的二进制码游戏逆向流程开发人员代码被编译打包到GameAssembly.dll中使用il2ppDumper工具，并借助游戏名_Data\il2cpp_data\Metadata\global-metadata.dat
【详解】Docker安装Elasticsearch7.16.1集群 - 2
开门见山|拉取镜像dockerpullelasticsearch:7.16.1|配置存放的目录#存放配置文件的文件夹mkdir-p/opt/docker/elasticsearch/node-1/config#存放数据的文件夹mkdir-p/opt/docker/elasticsearch/node-1/data#存放运行日志的文件夹mkdir-p/opt/docker/elasticsearch/node-1/log#存放IK分词插件的文件夹mkdir-p/opt/docker/elasticsearch/node-1/plugins若你使用了moba，直接右键新建即可如上图所示依次类推创建
【Elasticsearch基础】Elasticsearch索引、文档以及映射操作详解 - 2
文章目录概念索引相关操作创建索引更新副本查看索引删除索引索引的打开与关闭收缩索引索引别名查询索引别名文档相关操作新建文档查询文档更新文档删除文档映射相关操作查询文档映射创建静态映射创建索引并添加映射概念es中有三个概念要清楚，分别为索引、映射和文档（不用死记硬背，大概有个印象就可以）索引可理解为MySQL数据库；映射可理解为MySQL的表结构；文档可理解为MySQL表中的每行数据静态映射和动态映射上面已经介绍了，映射可理解为MySQL的表结构，在MySQL中，向表中插入数据是需要先创建表结构的；但在es中不必这样，可以直接插入文档，es可以根据插入的文档（数据），动态的创建映射（表结构），这就
最强Http缓存策略之强缓存和协商缓存的详解与应用实例 - 2
HTTP缓存是指浏览器或者代理服务器将已经请求过的资源保存到本地，以便下次请求时能够直接从缓存中获取资源，从而减少网络请求次数，提高网页的加载速度和用户体验。缓存分为强缓存和协商缓存两种模式。一.强缓存强缓存是指浏览器直接从本地缓存中获取资源，而不需要向web服务器发出网络请求。这是因为浏览器在第一次请求资源时，服务器会在响应头中添加相关缓存的响应头，以表明该资源的缓存策略。常见的强缓存响应头如下所述：Cache-ControlCache-Control响应头是用于控制强制缓存和协商缓存的缓存策略。该响应头中的指令如下：max-age：指定该资源在本地缓存的最长有效时间，以秒为单位。例如：Ca
IDEA 2022 创建 Spring Boot 项目详解 - 2
如何用IDEA2022创建并初始化一个SpringBoot项目？目录如何用IDEA2022创建并初始化一个SpringBoot项目？0. 环境说明1. 创建SpringBoot项目 2.编写初始化代码0. 环境说明IDEA2022.3.1JDK1.8SpringBoot1. 创建SpringBoot项目打开IDEA，选择NewProject创建项目。填写项目名称、项目构建方式、jdk版本，按需要修改项目文件路径等信息。选择springboot版本以及需要的包，此处只选择了springweb。此处需特别注意，若你使用的是jdk1
详解Unity中的粒子系统Particle System (二) - 2
前言上一篇我们简要讲述了粒子系统是什么，如何添加，以及基本模块的介绍，以及对于曲线和颜色编辑器的讲解。从本篇开始，我们将按照模块结构讲解下去，本篇主要讲粒子系统的主模块，该模块主要是控制粒子的初始状态和全局属性的，以下是关于该模块的介绍，请大家指正。目录前言本系列提要一、粒子系统主模块1.阅读前注意事项2.参考图3.参数讲解DurationLoopingPrewarmStartDelayStartLifetimeStartSpeed3DStartSizeStartSize3DStartRotationStartRotationFlipRotationStartColorGravityModif
Slowloris DoS攻击的原理与简单实现 - 2
前言 Slowloris攻击是我在李华峰老师的书——《MetasploitWeb 渗透测试实战》里面看的，感觉既简单又使用，现在这种攻击是很容易被防护的啦。不过我也不敢真刀实战的去试，只是拿个靶机玩玩罢了。废话还是写在结语里面吧。（划掉）结语可以不看（划掉）Slowloris攻击的原理 Slowloris是一种资源消耗类DoS攻击，它利用部分HTTP请求进行操作。也叫做慢速攻击，这里的慢速并不是说发动攻击慢，而是访问一条链接的速度慢。Slowloris攻击的功能是打开与目标Web服务器的连接，然后尽可能长时间的保持这些连接打开。如果由多台电脑同时发起Slo
VMware虚拟机与本地主机进行磁盘共享(详解) - 2
VMware虚拟机与本地主机进行磁盘共享前提虚拟机版本为Windows10（专业版，不是可能有问题）本地主机为家庭版或学生版(此版本会有问题，但有替代方式)最好是专业版VMware操作1.关闭防火墙，全部关闭。2.打开电脑属性3.点击共享-》高级共享-》权限4.如果没有everyone，就添加权限选择完全控制，然后应用确定。5.打开cmd输入lusrmgr.msc(只有专业版可以打开)如果不是专业版，可以跳过这一步。点击用户-》administrator密码要复杂密码，否则不行。推荐admaiN@1234类型的密码。设置完密码，点击属性，将禁用解开。6.如果虚拟机的windows不是专业版，可

XGBoost详解（原理篇）

一、XGBoost简介

二、XGBoost原理

1、基本组成元素

2、整体思路

（1）训练过程——构建XGBoost模型

（2）测试过程

3、目标函数

（1）最初的目标函数