XGBoost推导

目标

目标：我们希望学习一个既准确又简单的模型来实现预测
因此目标函数可以定为：
$\sum _{i=1}^{n}l(y_i,{\widehat{y}}_i)+\sum _k\Omega \left(f_k\right),f_k\in F$i=1∑n​l(yi​,y^​i​)+k∑​Ω(fk​),fk​∈F
由于我们使用的是树模型,而不是权重向量，因此无法使用SGD算法来找到函数 $f$f。但是可以使用Additive Training（Boosting）加性训练的方式来找到函数 $f$f.

Additive Training(Boosting)

从一个常数预测开始，每一轮训练增加一个新的函数
$\begin{array}{c}{\widehat{y}}_i^{\left(0\right)}=0\\ {\widehat{y}}_i^{\left(1\right)}=f_1\left(x_i\right)={\widehat{y}}_i^{\left(0\right)}+f_1\left(x_i\right)\\ {\widehat{y}}_i^{\left(2\right)}=f_1\left(x_i\right)+f_2\left(x_i\right)={\widehat{y}}_i^{\left(1\right)}+f_2\left(x_i\right)\\ {\widehat{y}}_i^{\left(t\right)}={\sum }_{k=1}^t{f}_k\left(x_i\right)={\widehat{y}}_i^{(t-1)}+f_t\left(x_i\right)\end{array}$y^​i(0)​=0y^​i(1)​=f1​(xi​)=y^​i(0)​+f1​(xi​)y^​i(2)​=f1​(xi​)+f2​(xi​)=y^​i(1)​+f2​(xi​)y^​i(t)​=∑k=1t​fk​(xi​)=y^​i(t−1)​+ft​(xi​)​

如何决定新加入的函数

由目标函数决定！
在第 $t$t轮训练中， ${\widehat{y}}_i^{\left(t\right)}={\widehat{y}}_i^{(t-1)}+f_t\left(x_i\right)$y^​i(t)​=y^​i(t−1)​+ft​(xi​)
因此目标函数可写成：
$\begin{array}{cc}{\displaystyle Ob{j}^{\left(t\right)}}& {\displaystyle =\sum _{i=1}^{n}l(y_i,{\widehat{y}}_i^{\left(t\right)})+\sum _{i=1}^t\Omega \left(f_i\right)}\\ {\displaystyle }& {\displaystyle =\sum _{i=1}^{n}l(y_i,{\widehat{y}}_i^{(t-1)}+f_t\left(x_i\right))+\Omega \left(f_t\right)+\text{ constant }}\end{array}$Obj(t)​=i=1∑n​l(yi​,y^​i(t)​)+i=1∑t​Ω(fi​)=i=1∑n​l(yi​,y^​i(t−1)​+ft​(xi​))+Ω(ft​)+ constant ​

由于前 $t-1$t−1轮的模型已确定，因此其复杂度是确定，所以 ${\sum }_{t=1}^{t-1}\Omega \left(f_t\right)=constant$∑t=1t−1​Ω(ft​)=constant

将目标函数泰勒展开

泰勒展开式
一维：
$f(x+\Delta x)\simeq f\left(x\right)+f^{\prime }\left(x\right)\Delta x+\frac{1}{2}{f}^{\prime \prime }\left(x\right)\Delta x^2$f(x+Δx)≃f(x)+f′(x)Δx+21​f′′(x)Δx2
二维：
$f(x,y+\Delta y)\simeq f(x,y)+\frac{\partial f(x,y)}{\partial y}\Delta y+\frac{1}{2}\frac{{\partial }^{2}f(x,y)}{\partial y^2}\Delta y^2$f(x,y+Δy)≃f(x,y)+∂y∂f(x,y)​Δy+21​∂y2∂2f(x,y)​Δy2

记 $g_i={\partial }_{{\widehat{y}}^{(t-1)}}l(y_i,{\widehat{y}}^{(t-1)}),h_i={\partial }_{{\widehat{y}}^{(t-1)}}^{2}l(y_i,{\widehat{y}}^{(t-1)})$gi​=∂y^​(t−1)​l(yi​,y^​(t−1)),hi​=∂y^​(t−1)2​l(yi​,y^​(t−1)),目标函数为:
$Ob{j}^{\left(t\right)}\simeq \sum _{i=1}^n[l(y_i,{\widehat{y}}_i^{(t-1)})+g_i{f}_t\left(x_i\right)+\frac{1}{2}{h}_i{f}_t^2\left(x_i\right)]+\Omega \left(f_t\right)+constant$Obj(t)≃i=1∑n​[l(yi​,y^​i(t−1)​)+gi​ft​(xi​)+21​hi​ft2​(xi​)]+Ω(ft​)+constant

移除常数项后，目标函数为：
$\sum _{i=1}^n[g_i{f}_t\left(x_i\right)+\frac{1}{2}{h}_i{f}_t^2\left(x_i\right)]+\Omega \left(f_t\right)$i=1∑n​[gi​ft​(xi​)+21​hi​ft2​(xi​)]+Ω(ft​)

定义树的复杂度

将样本到叶子节点分数的映射关系表示成：
$f_t\left(x\right)=w_{q\left(x\right)}q\left(x\right)\in 1,2,...,T$ft​(x)=wq(x)​q(x)∈1,2,...,T

$w$w是叶子节点的权重, $T$T为叶子节点总个数

定义树的复杂度为:
$\Omega \left(f_t\right)=\gamma T+\frac{1}{2}\lambda \sum _{j=1}^T{w}_j^2$Ω(ft​)=γT+21​λj=1∑T​wj2​

目标函数求解

现按照样本所属的叶子节点划分样本子集， $I_j=\left\{i\mid q\right(x_i)=j\}$Ij​={i∣q(xi​)=j},属于同一个叶子节点的归为一类，共有 $T$T类。

$\begin{array}{cc}{\displaystyle Ob{j}^{\left(t\right)}}& {\displaystyle \simeq \sum _{i=1}^n[g_i{f}_t\left(x_i\right)+\frac{1}{2}{h}_i{f}_t^2\left(x_i\right)]+\Omega \left(f_t\right)}\\ {\displaystyle }& {\displaystyle =\sum _{i=1}^n[g_i{w}_{q\left(x_i\right)}+\frac{1}{2}{h}_i{w}_{q\left(x_i\right)}^2]+\gamma T+\lambda \frac{1}{2}\sum _{j=1}^T{w}_j^2}\\ {\displaystyle }& {\displaystyle =\sum _{j=1}^T[\left(\sum _{i\in I_j}{g}_i\right)w_j+\frac{1}{2}(\sum _{i\in I_j}{h}_i+\lambda )w_j^2]+\gamma T}\end{array}$Obj(t)​≃i=1∑n​[gi​ft​(xi​)+21​hi​ft2​(xi​)]+Ω(ft​)=i=1∑n​[gi​wq(xi​)​+21​hi​wq(xi​)2​]+γT+λ21​j=1∑T​wj2​=j=1∑T​⎣⎡​⎝⎛​i∈Ij​∑​gi​⎠⎞​wj​+21​⎝⎛​i∈Ij​∑​hi​+λ⎠⎞​wj2​⎦⎤​+γT​

记 $G_j={\sum }_{i\in I_j}{g}_i,H_j={\sum }_{i\in I_j}{h}_i$Gj​=∑i∈Ij​​gi​,Hj​=∑i∈Ij​​hi​

则目标函数简化成
$\begin{array}{cc}{\displaystyle Ob{j}^{\left(t\right)}}& {\displaystyle =\sum _{j=1}^T[\left(\sum _{i\in I_j}{g}_i\right)w_j+\frac{1}{2}(\sum _{i\in I_j}{h}_i+\lambda )w_j^2]+\gamma T}\\ {\displaystyle }& {\displaystyle =\sum _{j=1}^T[G_j{w}_j+\frac{1}{2}(H_j+\lambda )w_j^2]+\gamma T}\end{array}$Obj(t)​=j=1∑T​⎣⎡​⎝⎛​i∈Ij​∑​gi​⎠⎞​wj​+21​⎝⎛​i∈Ij​∑​hi​+λ⎠⎞​wj2​⎦⎤​+γT=j=1∑T​[Gj​wj​+21​(Hj​+λ)wj2​]+γT​

对 $w_j$wj​来说是一个一元二次函数，当
$w_j^{\ast }=-\frac{G_j}{2\times \frac{1}{2}(H_j+\lambda )}=\frac{G_j}{H_j+\lambda }$wj∗​=−2×21​(Hj​+λ)Gj​​=Hj​+λGj​​
目标函数取得最小值：
$\begin{array}{cc}{\displaystyle Ob{j}^{\left(t\right)}}& {\displaystyle =\sum _{j=1}^T[-\frac{G_j^2}{4\cdot \frac{1}{2}(H_j+\lambda )}]+\gamma T}\\ {\displaystyle }& {\displaystyle =-\frac{1}{2}\sum _{j=1}^T\frac{G_j^2}{H_j+\lambda }+\gamma T}\end{array}$Obj(t)​=j=1∑T​[−4⋅21​(Hj​+λ)Gj2​​]+γT=−21​j=1∑T​Hj​+λGj2​​+γT​

树的生成

• 从根结点（所有数据在同一个结点中），深度为0开始
• 对每一个叶子结点，尝试将其分裂成两个叶子结点，分裂后目标函数值的变化如下：
  $Gain=\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$Gain=21​[HL​+λGL2​​+HR​+λGR2​​−HL​+HR​+λ(GL​+GR​)2​]−γ
• 一直分裂直至不满足分裂条件为止

如何找到最优分裂特征

• 对每一个特征，将其特征值排序
• 尝试使用每一个特征值进行划分
• 选出所有特征所有特征值中增益最大的作为分类依据

剪枝和正则

• 增益不能为负。训练损失和树的复杂度得到平衡
  $Gain=\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$Gain=HL​+λGL2​​+HR​+λGR2​​−HL​+HR​+λ(GL​+GR​)2​−γ
• 提前停止。当最优分裂的增益值为负时，停止生长。（但可能这一次分裂有利于后续分裂）
• 设定最大深度，修剪所有增益为负的叶子结点

XGBoost算法步骤

• 在每一轮中，新建一棵空树 $f_t\left(x\right)$ft​(x)
• 计算每个叶子节点中每个样本的一阶梯度和二阶梯度值
  $g_i={\partial }_{{\widehat{y}}^{(t-1)}}l(y_i,{\widehat{y}}^{(t-1)}),h_i={\partial }_{{\widehat{y}}^{(t-1)}}^{2}l(y_i,{\widehat{y}}^{(t-1)})$gi​=∂y^​(t−1)​l(yi​,y^​(t−1)),hi​=∂y^​(t−1)2​l(yi​,y^​(t−1))
• 计算不同特征不同特征值作为分裂依据时的增益
  $Gain=\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$Gain=HL​+λGL2​​+HR​+λGR2​​−HL​+HR​+λ(GL​+GR​)2​−γ
• 不断地生长树，直至不满足分裂条件
• 将这一轮的树 $f_t\left(x\right)$ft​(x)添加到模型中
  $y^{\left(t\right)}=y^{(t-1)}+ϵf_t\left(x_i\right)$y(t)=y(t−1)+ϵft​(xi​)

$ϵ$ϵ称为步长，即在每一轮中，并不是做完了所有的优化，而是留一部分给后续的优化轮次，这样可以防止过拟合

参考资料