以下内容均为个人理解,如有错误,欢迎指出
什么是XGBoost
以下内容摘自一文读懂机器学习大杀器XGBoost原理
XGBoost是boosting算法的其中一种。Boosting算法的思想是将许多弱分类器集成在一起形成一个强分类器(为什么是弱分类器待会会解释)。因为XGBoost是一种提升树模型,所以它是将许多树模型集成在一起,形成一个很强的分类器。对于回归问题,所用到的树模型则是CART回归树模型。
本文讲解的是回归类的XGBoost
CART回归树模型可查看我之前的文章机器学习——决策树(ID3、C4.5、CART)
XGBoost的推导过程
XGBoost的目标函数
K个学习器的目标函数为
Obj=i=1∑nl(yi,y^i)+k=1∑KΩ(fk)
目标函数由损失函数和正则项构成,Obj=∑i=1nl(yi,y^i)为损失函数,用于衡量预测值与真实值之间的差距,yi为真实值,y^i为预测值,依据自己的需要定义损失函数l(yi,y^i),i表示第几个样本,∑k=1KΩ(fk)为正则化项,正则化项包含两部分——叶子节点个数与叶子节点的值,即
Ω(fk)=γTk+λ21∣∣wk∣∣2
Tk表示第k个学习器的叶子节点的个数,wk表示第k个学习器的叶子节点的分数,γ、λ为事先指定的值
模型学习与训练误差
符号表
符号名 |
含义 |
y^i(i) |
前i个学习器在第i个样本上的预测值之和 |
fi(xi) |
第i个学习器在第i个样本上的残差预测值 |
Obj(t) |
加入第t个学习器后的目标函数值 |
XGBoost是集成学习的一种算法,从定义可知,其将许多弱分类器集成在了一起,它将多棵树的得分累加得到最终的预测得分,其过程如下:
第i个学习器拟合前i-1个学习器拟合的误差,例如二维坐标上的第i个样本为(1,9),前i-1个学习器的拟合值为7,则对于第i个样本,第i个学习器需要拟合的值为2,即对于第i个学习器,第i个样本变为(1,2),正是因为不断通过新的学习器拟合误差,所以XGBoost在训练样本上的误差会不断降低,基于此,我们将加入第t个学习器后的目标函数变为
Objt=i=1∑nl(yi,y^i(t))+k=1∑KΩ(fk)=i=1∑nl(yi,y^i(t−1)+ft(xi))+Ω(ft)+const(式1.0)
const为常数,由于前t−1个学习器的正则项已知,故为常数,yi表示第i个样本的真实值,y^i(t−1)表示前t−1个学习器在第i个样本上的预测值之和,对于l(yi,y^i(t−1)+ft(xi)),由于yi是常数,在正式训练以前,y^i(t−1)的值是一个变量,故我们可设f(y^i(t−1))=l(yi,y^i(t−1)),若将ft(xi)看为Δy^i(t−1),则l(yi,y^i(t−1)+ft(xi))可表示为f(y^i(t−1)+Δy^i(t−1)),我们对其进行二阶泰勒展开(泰勒展开请自行google,为什么进行泰勒展开原因后面解释),二阶泰勒展开式长这样f(x+Δx)≈f(x)+f′(x)Δx+21f′′(x)Δx2
基于此,式1.0可表示为
Obj(t)≈i=1∑n[l(yi,y^it−1)+gift(xi)+21hift2(xi)]+Ω(fk)+const(式1.1)
其中
gi=∂y^it−1∂l(yi,y^it−1)hi=∂(y^it−1)2∂2l(yi,y^it−1)
一般情况下,l(yi,y^i)为凸函数(想一想均方误差),所以hi>0,对于CART决策树,每一个样本最终会落到其中一个叶子节点上,我们用wq(xi)2表示第i个样本所处的叶子,在此基础上,代入正则项,假设第t个决策树具有T个叶子节点,则式1.1可变为
Obj(t)≈=i=1∑n[l(yi,y^it−1)+gift(xi)+21hift2(xi)]+Ω(fk)+consti=1∑n[giwq(xi)+21hiwq(xi)2]+γT+λ21j=1∑Twj2(式1.2)
将∑i=1n[giwq(xi)+21hiwq(xi)2]展开,将位于同一个叶子节点上的样本合并在一起,用Ij表示落在叶子点j上面样本的集合,则式1.2可变为
Obj(t)≈j=1∑T[iϵIi∑giwj+21(iϵIj∑hi+λ)wj2]+γT(式1.3)
由于hj>0,λ>0,所以式1.3是一个凸函数,设Gj=∑iϵIjgi,Hj=∑iϵIjhi,则式1.3可表示为
Obj(t)≈j=1∑T[Gjwj+21(Hj+λ)wj2]+γT(式1.4)
对wj求导置为0可得
wj∗=−Hj+λGj
将其代入式1.4可得
Obj=−21j=1∑THj+λGj2+γT(式1.5)
现在回头看看我们为什么使用泰勒展开式进行推导,可以看到整个推导过程都未涉及到损失函数的具体值,只是假定损失函数为凸函数(一般都是凸函数),因此使用泰勒展开式推导的式1.5对于不同的损失函数具有通用性
对于式1.5的计算,我们来举一个例子,假定现在有五个样本,求加入第t个CART回归决策树决后式1.5的值,我们可以计算出每个样本在t-1个CART回归决策树上的gi、hi,则有
到这里,我们把目标函数推导完了,也知道针对某一个新加入的具体的CART决策树后如何计算式1.5,那么接下来,CART决策树如何生成?XGBoost的作者给出了两种方案,此处只介绍其中一个,该方案使用贪心策略,与CART回归决策树的分裂方式类似,只是将基尼指数改为了下式
对于某个节点,每次选择能使Gain最高的特征与特征划分点(例如有样本在第j个特征上的取值为1,2,3,4,5,假设特征划分点为3.5,则第j个特征取值为1,2,3的样本被分到左子树,4,5被分到右子树)进行划分,为什么说这是贪心策略呢?
对于某一个节点来说,由于HL+HR+λ(GL+GH)2、γ是常数,Gain最大,意味着在所有划分方案中,此时对应的−21[HL+λGL2+HR+λGR2]+γ最小,即对于某个节点,不同的分裂方式,式1.5有不同的取值,我们取其中的最小,并用其对应的方案进行分裂,最终满足某个临界条件,此时停止分裂,每个叶子节点的取值为−Hj+λGj,那么临界条件是什么呢?这个方案比较多,具体而言
- 当引入的分裂带来的增益小于设定阀值的时候,我们可以忽略掉这个分裂,所以并不是每一次分裂loss function整体都会增加的,有点预剪枝的意思,阈值参数为(即正则项里叶子节点数T的系数);
- 当树达到最大深度时则停止建立决策树,设置一个超参数max_depth,避免树太深导致学习局部样本,从而过拟合;
- 当样本权重和小于设定阈值时则停止建树。什么意思呢,即涉及到一个超参数-最小的样本权重和min_child_weight,和GBM的 min_child_leaf 参数类似,但不完全一样。大意就是一个叶子节点样本太少了,也终止同样是防止过拟合;
- 貌似看到过有树的最大数量的…
以上内容摘自通俗理解kaggle比赛大杀器xgboost
这几个参数在Python的XGBoost包上也有,接下来,我们解释一下为什么XGBoost要使用弱分类器
XGBoost为什么要使用弱分类器
我们知道集成学习中的Bagging的基学习器是强学习器,Boosting的基学习器是弱学习器,同样是决策树,Bagging的决策树深度将大于Boosting,这一节,我们将从一定条件下对此进行简单解释,在此之前,先理解什么是机器学习中的偏差,什么是方差
偏差:模型的预测结果与真实结果之间的差距
方差:即模型的泛化能力,方差大的模型,对于不同的测试数据产生的结果差别较大,即对训练数据拟合过高,方差小的模型,对于不同测试数据产生的结果差别不大,一般来说,弱学习器的泛化能力较强,对于决策树来说,由于叶子节点较少,对于不同的测试数据,产生的结果自然差距不大,假设这个决策树只有五种结果(五个叶子),与具有几百种结果的决策树相比,对于不同测试数据产生的结果自然差距不大
在本节集成学习的讨论中,我们有以下假设
- 我们用期望来侧面反映偏差,若测试数据的期望与预测数据的期望近似,我们就认为模型的偏差小
- 基模型的权重γi、方差δi2以及两两之间的相关系数ρi相等,分别用γ、δ2、ρ表示
- Boosting的各个基学习器之间的相关系数ρ=1
由于Bagging与Boosting都是将基学习器用线性方式组成,假设有m个基础学习器,第i个学习器的输出用fi表示,第i个学习器的权重用γi表示,则集成学习器的输出F可表示为
F=i=1∑mγifi
推导过程将会用到以下公式
E(AX)=E(i=1∑nXi)=Var(i=1∑nXi)=Var(AX)=相关系数ρ=AE(X)i=1∑nE(Xi)i=1∑nj=1∑nCov(Xi,Xj)=i=1∑nVar(Xi)+21≤i<≤n∑Cov(Xi,Xj)A2Var(X)Var(Xi)Var(Xj)Cov(Xi,Xj)
集成学习输出的期望与方差可表示为
E(F)==Var(F)=====E(i=1∑mγifi)γi=1∑mE(fi)(式2.1)Var(i=1∑mγifi)i=1∑mVar(γifi)+i̸=j∑γiγjCov(Xi,Xj)i=1∑mγi2Var(fi)+i̸=j∑γiγjCov(Xi,Xj)mγ2δ2+(m2−m)γ2ρδ2(对相关系数的计算公式进行变形,自己与自己的相关系数为1)m2γ2δ2ρ+mγ2δ2(1−ρ)(式2.2)
Bagging的偏差与方差
对于Bagging,我们假定使用均值赋权法(即m个学习器的权重为m1),则期望与方差为
E(F)===Var(F)==γi=1∑mE(fi)m1∗m∗E(fi)E(fi)m2m21δ2ρ+mm21δ2(1−ρ)δ2ρ+mδ2(1−ρ)
由此可见,Bagging模型的期望与基学习器类似,因此,基学习器常常为强学习器,此时Bagging的偏差将较小,为了降低方差,我们常常会增加基学习器的个数m
Boosting的偏差与方差
Boosting的基学习器在同一训练集上进行训练,并且基学习器之间是串型结构,对于一个训练样本,某个学习器的输出越高,意味着位于其后的学习器的输出越低,各个学习器之间的线性相关性较强,而Bagging的基学习器在具有重叠的不同训练集上进行训练,并且基学习器之间是并型结构,对于一个训练样本,某个学习器的输出越高,并不意味着其他学习器的输出越低,各个学习器之间的线性相关性较弱,而ρ用于度量两个维度之间的线性相关性,因此,我们假定Boosting的ρ=1,则有
E(F)=Var(F)=γ∗i=1∑mE(fi)m2∗γ2∗δ2
由此可见,Boosting的方差与基学习器的方差与个数直接挂钩,而期望为基学习器的期望之和,为了让Boosting的期望尽可能趋近于训练数据的期望,我们常常增加学习器的个数,但是,这会导致模型的方差不断上升,为了缓和上升的趋势,我们常使用弱学习器,基于此。XGBoost也是弱学习器