【目录】一、XG提升算法总体思路
二、本质区别
三.增益推导
1损失函数表示
2 hhdyg二路展开近似替代损失函数
3消除常数项
4将包含抽象残差树的损失函数转换为不包含抽象残差树的形式(引入一个未知变量) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )。
5对未知变量求偏导数=0,得到极值点代入损失函数,得到极值,即结构点
6求增益:增益等于分裂前的结构分减去分裂后的左、右结构分
四、其他有关问题
一、xgboost算法整体思路
xgboost算法是属于boosting框架的算法。 因此,boosting的总体思路满足boosting框架的总体思路。
初始化-f0(Xi )
拟合残差树H1(Xi ) ()通过不同的分裂准则(即不同的增益,是每个提升算法的最大区别,也是本节的重点) ) )。
f1=F0 (Xi ) h1 (Xi )更新
-依次重复,直到模型满足收敛条件。
boosting框架算法的本质区别和说明侧重于在每次迭代过程中如何拟合残差树。 本文也围绕这一展开,说明xgboost算法如何在各迭代过程中拟合残差树,主要是推导各拟合残差树分裂时的增益表达式。
二、本质区别
每次迭代适合的残差树都不同。 残差树差异的本质是分裂标准的不同,即增益的不同。 因此,无论是XGBoost还是其他boosting类算法,其本质区别在于每次拟合残差树时增益定义都不同。 Xgboost采用的增益是分裂前的结构点和分裂后的结构点之差。
三、增益的推导
Xgboost的一个亮点是定义分裂准则,从而与没有分裂的情况相比,最佳分割点的分裂可以最大限度地减少损失。 这也是XG boost高效的理由之一。 因此,找到了将从分裂前的构造点减去分裂后的构造点定义为分割点的增益,找出增益最大的分割点作为该子分裂的最佳分割点的方法。 结构分的含义:知道树的结构时的损失函数的最小值。 在已知gi、hi的条件下,结构分可以求解。
结构分的含义:知道树的结构时的损失函数的最小值。 Xgboost的增益定义是从分裂前的结构点中减去分裂后的结构点,选择增益最大的分割点作为最佳分割点,使分裂后的模型损失比分裂前的损失最小。 这种增益定义方法拟合出的该轮残树效果优良。1 损失函数表达
第k次迭代时的模型公式:
,
这里,表示第k个拟合残差树
第k次模型的损失函数如下。
这里表示第k回合的正则化项,这是Xgboost和GBDT的区别之一。
2 hhdyg二街展开近似代替损失函数
高清yg官方第二大街将按如下方式展开。
这里,表示第I个样本一次微分也称为一次残差; 表示第I个样本的二次微分,也称为二次残差。 可以看出,在每次迭代之前,每个样本的一阶、二阶残差都已经可以确定。 请注意,和在重复之前已经确定。
因此,损失函数的hhdyg二次展开式如下。
3 去掉常数项
因为结构分数的意思是知道树的结构时的损失函数的最小值。 我们的目的是要求损耗函数的最小值,在求极值的过程中去掉常数项,可以简化如下
4 把包含抽象残差树的损失函数转化为没有包含抽象残差树的形式(引入一个未知变量)
为什么要换成叶子的结构?
结构分最后导出的结构用gi和hi表示。 也就是说,如果求出各回合的gi和hi,就可以求出每个回合的结构部分。 也就是说,如果求出各回合的gi和hi,就可以求出每个回合的所有分割点的增益。 将树结构式转换为叶结构的公式是为了导出用gi和hi表示的结构成分而准备的。
怎么转换?
根据以上公式,如果对该循环迭代的残差树进行某种变换,则损失函数不是用抽象的残差树表示,而是由具体的常数和变换后可导入的变量构成,可以导出变换后导入的变量,用gi、hi这样的常数表示损失函数的极值,即结构分以下说明如何变换这个迭代的残差树,使损失函数不是用抽象的残差树表示,而是由具体的常数和变换后可能引入的变量构成。
将残差树映射到叶子,也就是与样本有关的函数
假定最后生成的残差树如下,而不考虑复杂的决策树生成过程:
对于树结构,用另一种方法表示树。 在每个叶节点的输出(唯一值)中表示树,函数表达式如下:
假设gi=(0.2、0.8、0.5、0.1 ),对所有样品范围求出
=[0.28 0.89 0.59 0.110]
=[(0.2 )8)0.80.5 )9) 0.1 ) ) 10]
同样,对于
br><5> 对未知变量求偏导=0,得到极值点代入损失函数,得到极值,即结构分
假设wj与Gj,Hj无关,即假设一直树的结构,对wj求导=0,即:
得:
极值点
代入得结构分:
即结构分的意义:当已知树的结构时的损失函数的最小值。
<6> 求增益:增益等于分裂前结构分减去分裂后左、右结构分
增益的意义
Xgboost的增益定义就是分裂前的结构分减去分裂后的结构分,选择增益最大的分割点作为最优分割点,其意义为使分裂后模型损失比分裂前损失减小最大的那个分割点。这样的增益定义方法拟合的该轮残差树效果很优。
最终增益表达式如下:
举例,在某一轮迭代时进行节点2分裂某一个分割点分裂后如下:
分裂前的gi,hi为2节点的样本所对应的gi,hi,分裂后的gli,hli为节点4的样本所对应的gi,hi,分裂后的gri,hri为节点5的样本所对应的gi,hi。
四、其他相关问题
gi、hi的理解
gi,hi表示损失函数对某一样本的一阶导和二阶导,也叫样本误差。而不是整个目标函数的一阶导数和二阶导数。
*损失函数hhdyg二阶展开的目的是什么?
*当基学习器不是决策树时(比如是线性回归算法)的xgboost是如何运行的?
怎样计算每个叶子节点的误差?
第j节点所有样本的误差之和
就是结构分数中的
xgboost根据什么准则进行分裂?(祥见宝典)
根据分裂前后结构分数之差作为增益:
在设置γ不等于0的时候,这个值有什么作用?
设置γ不等于0之后,当Gain<=0,则不进行分裂,这其实预剪枝的效果。
xgboost生长方式是什么样子的?
Level-wise
*xgboost的预排序算法是什么样子的?
xgboost如何做分类(或GBDT怎么做分类、lgb怎么做分类)
xgboost和GBDT的区别
1 损失函数:
xgboost损失函数二阶hhdyg展开近似替代,只要损失函数有二阶导的都能用xgboost框架,所以不限制基函数的使用,GBDT只求一阶,基函数只能是CART;
xgboost在损失函数中加入正则化项,所以xgboost相比GBDT比较不容易过拟合。
2 优化速度:xgboost自定义的增益分裂(通过二阶hhdyg展开推导得到),让每轮迭代模型损失函数减小的幅度最大;GBDT用负梯度代替残差,拟合残差树,每一轮迭代模型损失有减小,但减小的幅度不能保证最大。加快优化速度。
3 特征采样:xgboost采样类似随机森林的做法,对特征采样。这样做降低了计算量也防止过拟合。
4 并行:xgboost每一轮迭代中支持增益、样本损失并行,支持预测时并行。
*为什么xgboost比GBDT效果好?
xgboost自定义的增益分裂,让每轮迭代模型损失函数减小的幅度最大;GBDT用负梯度代替残差,拟合残差树,每一轮迭代模型损失有减小,但减小的幅度不能保证最大。
Xgboost的缺点(与LightGBM的区别,参考《LightGBM算法详解》)