文章目录
  1. 1. Xgboost
    1. 1.1. 概念
    2. 1.2. Xgboost公式推导
      1. 1.2.1. 目标函数
      2. 1.2.2. 进一步推导及形象化说明
    3. 1.3. 训练方法

引言:果然需要手推一遍才能有点感觉。

Xgboost

Xgboost和AdaBoost都具有集成思想,是说将若干个弱分类器组合成一个强分类器。

概念

可参考https://www.bilibili.com/video/av26088803,以及字幕和评论区。

以及https://xgboost.readthedocs.io/en/latest/tutorials/model.html

Xgboost公式推导

目标函数

Obj(t)=i=1nl(yi,y^i(t))+i=1tΩ(fi)=i=1nl(yi,y^i(t1)+ft(xi))+Ω(ft)+constant\begin {aligned} Obj^{(t)}=&\sum_{i=1}^nl(y_i,\hat y_i^{(t)})+\sum_{i=1}^t\Omega(f_i)\\ =&\sum_{i=1}^nl(y_i,\hat y_i^{(t-1)}+f_t(x_i))+\Omega(f_t)+constant \end {aligned}

上述目标函数是一个递归式,ll代表经验风险函数,Ω\Omega代表结构风险函数。nn是样本个数,tt是指当前迭代次数,也就是当前森林中树的个数。

由于整个优化目标只和变量ft(xi)f_t(x_i)有关,我们求的也是ft(xi)f_t(x_i)中参数的值,因此前t1t-1轮已建立的模型都属于常数,都放进constant了。

结构损失函数采用:

Ω(ft)=γT+12λj=1Twj2\Omega(f_t)=\gamma T+\frac 1 2 \lambda \sum_{j=1}^Tw_j^2

其中大TTtt树中叶子个数,ww为该叶子的权重。

进一步推导及形象化说明

形象化说明

我们假定经验损失函数采用均方误差:

l(yi,y^i)=(yiy^i)2l(y_i,\hat y_i)=(y_i-\hat y_i)^2

其中y^i=jwjxij\hat y_i=\sum_jw_jx_{ij}ii为第ii个样本,jj为第jj个叶子。

将其转换为等价的:y^i=k=1Kfk(xi),fkF\hat y_i=\sum_{k=1}^Kf_k(x_i),f_k \in \mathcal F,广泛意义讲,其中fkf_k是第kk个分类器,具体来讲就是第kk个决策树。

也就是说fk(xi)f_k(x_i)即样本ii在第kk棵树上的带权得分。

下面将经验损失函数具体化,进行一个推导。

Obj(t)=i=1nl(yi,y^i(t))+i=1tΩ(fi)=i=1nl(yi,y^i(t1)+ft(xi))+Ω(ft)+constant=i=1n(yi(y^i(t1)+ft(xi)))2+Ω(ft)+constant=i=1n[2(y^i(t1)yi)ft(xi)+ft(xi)2]+Ω(ft)+constant\begin {aligned} Obj^{(t)}=&\sum_{i=1}^nl(y_i,\hat y_i^{(t)})+\sum_{i=1}^t\Omega(f_i)\\ =&\sum_{i=1}^nl(y_i,\hat y_i^{(t-1)}+f_t(x_i))+\Omega(f_t)+constant\\ =&\sum_{i=1}^n(y_i-(\hat y_i^{(t-1)}+f_t(x_i)))^2+\Omega(f_t)+constant\\ =&\sum_{i=1}^n[2(\hat y_i^{(t-1)}-y_i)f_t(x_i)+f_t(x_i)^2]+\Omega(f_t)+constant\\ \end {aligned}

与上述相似,我们将与ft(xi)f_t(x_i)无关的项都归入constant。注意Ω(ft)\Omega(f_t)是指第tt棵树的结构风险函数,我们将前t-1棵树的结构风险归为了constant。

上式中y^i(t1)yi\hat y_i^{(t-1)}-y_i被称为残差,即第ii个样本在上一模型中的值与真实值的差距。

显然,为了使得2(y^i(t1)yi)ft(xi)+ft(xi)22(\hat y_i^{(t-1)}-y_i)f_t(x_i)+f_t(x_i)^2尽量小,取ft(xi)=(y^i(t1)yi)f_t(x_i)=-(\hat y_i^{(t-1)}-y_i)即可,即第tt棵树存在的目的就是要抹平这个残差。当然,这只是我们的优化目标。

进一步推导

回到最初的目标函数式子,我们观察发现这很像一个迭代式,我们可以用泰勒展开(这里用二阶泰勒展开):

f(x+Δx)Δx0f(x)0!+Δxf(x)1!+Δx2f(x)2!=f(x)+Δxf(x)+12Δx2f(x)\begin {aligned} f(x+\Delta x)\backsimeq&\frac{\Delta x^0 f(x)}{0!}+\frac{\Delta x f'(x)}{1!}+\frac {\Delta x^2 f''(x)}{2!}\\ =&f(x)+\Delta x f'(x)+\frac 1 2\Delta x^2 f''(x) \end {aligned}

我们以y^(t1)\hat y^{(t-1)}xxft(xi)f_t(x_i)为增量,构造二阶泰勒展开:

Obj(t)=i=1nl(yi,y^i(t))+i=1tΩ(fi)=i=1nl(yi,y^i(t1)+ft(xi))+i=1tΩ(fi)Tayler Formula   i=1n[l(yi,y^i(t1))+gift(xi)+12hift2(xi)]+i=1tΩ(fi)=i=1n[gift(xi)+12hift2(xi)]+i=1tΩ(fi)\begin {aligned} Obj^{(t)} =&\sum_{i=1}^nl(y_i,\hat y_i^{(t)})+\sum_{i=1}^t\Omega(f_i)\\ =&\sum_{i=1}^nl(y_i,\hat y_i^{(t-1)}+f_t(x_i))+\sum_{i=1}^t\Omega(f_i)\\ \scriptsize\text{Tayler Formula}~~~\backsimeq&\sum_{i=1}^n[l(y_i,\hat y_i^{(t-1)})+g_if_t(x_i)+\frac 1 2 h_if_t^2(x_i)]+\sum_{i=1}^t\Omega(f_i)\\ =&\sum_{i=1}^n[g_if_t(x_i)+\frac 1 2 h_if_t^2(x_i)]+\sum_{i=1}^t\Omega(f_i) \end {aligned}

其中gig_i是一阶偏导(梯度),hih_i是二阶偏导(梯度),gi=δy^(t1)l(yi,y^(t1)), hi=δy^(t1)2l(yi,y^(t1))g_i=\delta_{\hat y^{(t-1)}}l(y_i,\hat y^{(t-1)}),~h_i=\delta^2_{\hat y^{(t-1)}}l(y_i,\hat y^{(t-1)})

目前我们是针对每一个样本进行的遍历的,下面做一些变换,使得针对每个叶子进行遍历,而无关样本,更贴合模型计算。

Obj(t)=i=1nl(yi,y^i(t))+i=1tΩ(fi)Tayler Formula   i=1n[gift(xi)+12hift2(xi)]+i=1tΩ(fi)=i=1n[gift(xi)+12hift2(xi)]+i=1t(12λjTiwj2+γTi)Transform and travel leaves   =jT[(iIjgi)wj+12(iIjhi)wj2]+12λjTwj2+γT=jT[(iIjgi)wj+12(iIjhi+λ)wj2]+γT\begin {aligned} Obj^{(t)} =&\sum_{i=1}^nl(y_i,\hat y_i^{(t)})+\sum_{i=1}^t\Omega(f_i)\\ \scriptsize\text{Tayler Formula}~~~\backsimeq&\sum_{i=1}^n[g_if_t(x_i)+\frac 1 2 h_if_t^2(x_i)]+\sum_{i=1}^t\Omega(f_i)\\ =&\sum_{i=1}^n[g_if_t(x_i)+\frac 1 2 h_if_t^2(x_i)]+\sum_{i=1}^t(\frac 1 2 \lambda \sum_j^{T_i}w_j^2+\gamma T_i)\\ \scriptsize\text{Transform and travel leaves}~~~=&\sum_j^T[(\sum_{i \in I_j}g_i)w_j+\frac 1 2 (\sum_{i\in I_j}h_i)w_j^2]+\frac 1 2 \lambda\sum_j^T w_j^2+\gamma T\\ =&\sum_j^T[(\sum_{i \in I_j}g_i)w_j+\frac 1 2 (\sum_{i\in I_j}h_i+\lambda)w_j^2]+\gamma T \end {aligned}

其中大TT为森林中叶子总数目(与目标函数一节的描述略有差别);

TiT_i为第ii棵树上的叶子数目(注意第三行到第四行消除了两个TiT_i);

tt为当前迭代次数,即当前森林中树的数目。

hi,gih_i,g_i都是和样本相关的,而wjw_j只与叶子相关,同一片叶子上的样本权重相同。

注:按理说wj=iIjweightjxijw_j=\sum_{i \in I_j}\text{weight}_jx_{ij},但由于xij{1,1}x_{ij}\in\{-1,1\},所以直接将其包含于wjw_j作为正负符号。

训练方法

我们现在已经求得目标函数的表达式了,那么为了使得目标函数最小化,新的一棵树该如何设计呢?

我们将目标函数简单化:

Obj(t)jT[Gjwj+12(Hj+λ)wj2]+γTObj^{(t)}\backsimeq \sum_j^T[G_jw_j+\frac 1 2(H_j+\lambda)w_j^2]+\gamma T

其中Gj=iIjgi,Hj=iIjhiG_j=\sum_{i\in I_j}g_i,H_j=\sum_{i\in I_j}h_i,即某叶子的样本偏导和。

其后求其极值点:

δJ(ft)δwj=Gj+(Hj+λ)wj=0\frac {\delta J(f_t)}{\delta w_j}=G_j+(H_j+\lambda)w_j=0

wj=GjHj+λ\Rightarrow w_j=-\frac{G_j}{H_j+\lambda}

好,求得wjw_j了,代回去得:

Obj(t)12jTGj2Hj+λ+γTObj^{(t)}\backsimeq -\frac 1 2 \sum_j^T\frac{G_j^2}{H_j+\lambda}+\gamma T

Xgboost的树是二叉树,二叉树的叶子是什么呢,其实就是某结点的两个分支,只不过没有子结点罢了。因此新树的生长无非就是对一个叶子割(将其分为左右两个叶子)还是不割,如果割在哪割一刀的问题。

那到底割不割,在哪割,是通过计算增益来决定的。

Gain=(12jTGL2HL+λ+γ12jTGR2HR+λ+γ)(12jT(GL+GR)2HL+HR+λ+γ)=12[(GL2HL+λ+GR2HR+λ)(GL+GR)2HL+HR+λ]γ\begin {aligned} Gain =&(-\frac 1 2\sum_j^T\frac{G_L^2}{H_L+\lambda}+\gamma-\frac 1 2\sum_j^T\frac{G_R^2}{H_R+\lambda}+\gamma)-(-\frac 1 2\sum_j^T\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}+\gamma)\\ =&\frac 1 2 [(\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda})-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}]-\gamma \end {aligned}

上式γ\gamma是割之后加入新的叶子结点引入的复杂度代价。

为了使得增益最大化,我们需要选择一个最好的分割L和R的方法,如果不存在增益为正的分割方法,则不割。

枚举所有割法即可。

文章目录
  1. 1. Xgboost
    1. 1.1. 概念
    2. 1.2. Xgboost公式推导
      1. 1.2.1. 目标函数
      2. 1.2.2. 进一步推导及形象化说明
    3. 1.3. 训练方法