XGBoost

从GBDT到XGBoost

XGBoost相对GBDT的优化

1. 算法：在算法的弱学习器模型选择上，GBDT只支持CART回归树，XGBoost还可以使用很多其他的弱学习器。在算法的优化方式上，GBDT的损失函数只对误差部分做负梯度（一阶泰勒）展开，而XGBoost损失函数对误差部分做二阶泰勒展开，更加准确。
2. 算法运行效率：对每个弱学习器（如决策树）建立过程中做并行选择，找到合适的子树分裂特征和特征值。在并行选择之前，先对所有的特征的值进行排序分组，方便并行选择。对分组的特征，选择合适的分组大小，使用CPU缓存进行读取加速。将各个分组保存到多个硬盘以提高IO速度。
3. 算法健壮性：对于缺失值的特征，通过枚举所有缺失值在当前节点是进入左子树还是右子树来决定缺失值的处理方式。算法本身加入了L1和L2正则化项，可以防止过拟合，泛化能力更强。

XGBoost损失函数

GBDT的回归算法

1. 得到负梯度（残差），或者是泰勒展开式的一阶导数。
2. 第一个优化求解：基于残差拟合一颗CART回归树，得到J个叶子节点区域。
3. 第二个优化求解：在第二步优化求解的结果上，对每个节点区域做一次线性搜索，得到每个叶子节点区域的最优取值。
4. 最终得到当前轮的强学习器。

求解当前决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解????????????。
GBDT分两步走，先求出最优的所有J个叶子节点区域，再求出每个叶子节点区域的最优解。
XGBoost则一次求解出决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解????????????。

1. 加入正则化项的XGBoost损失函数$\Omega(h_t) = \gamma J + \frac{\lambda}{2}\sum\limits_{j=1}^Jw_{tj}^2$Ω(ht​)=γJ+2λ​j=1∑J​wtj2​????是叶子节点的个数，而$w_{tj}$wtj​是第j个叶子节点的最优值($c_{tj}$ctj​)$L_t=\sum\limits_{i=1}^mL(y_i, f_{t-1}(x_i)+ h_t(x_i)) + \gamma J + \frac{\lambda}{2}\sum\limits_{j=1}^Jw_{tj}^2$Lt​=i=1∑m​L(yi​,ft−1​(xi​)+ht​(xi​))+γJ+2λ​j=1∑J​wtj2​$\approx \sum\limits_{i=1}^m( L(y_i, f_{t-1}(x_i)) + \frac{\partial L(y_i, f_{t-1}(x_i)) }{\partial f_{t-1}(x_i)}h_t(x_i) + \frac{1}{2}\frac{\partial^2 L(y_i, f_{t-1}(x_i)) }{\partial f_{t-1}^2(x_i)} h_t^2(x_i)) + \gamma J + \frac{\lambda}{2}\sum\limits_{j=1}^Jw_{tj}^2$≈i=1∑m​(L(yi​,ft−1​(xi​))+∂ft−1​(xi​)∂L(yi​,ft−1​(xi​))​ht​(xi​)+21​∂ft−12​(xi​)∂2L(yi​,ft−1​(xi​))​ht2​(xi​))+γJ+2λ​j=1∑J​wtj2​把第i个样本在第t个弱学习器的一阶和二阶导数分别记为$g_{ti} = \frac{\partial L(y_i, f_{t-1}(x_i) }{\partial f_{t-1}(x_i)}, \; h_{ti} = \frac{\partial^2 L(y_i, f_{t-1}(x_i) }{\partial f_{t-1}^2(x_i)}$gti​=∂ft−1​(xi​)∂L(yi​,ft−1​(xi​)​,hti​=∂ft−12​(xi​)∂2L(yi​,ft−1​(xi​)​$L_t \approx \sum\limits_{i=1}^m( L(y_i, f_{t-1}(x_i)) + g_{ti}h_t(x_i) + \frac{1}{2} h_{ti} h_t^2(x_i)) + \gamma J + \frac{\lambda}{2}\sum\limits_{j=1}^Jw_{tj}^2$Lt​≈i=1∑m​(L(yi​,ft−1​(xi​))+gti​ht​(xi​)+21​hti​ht2​(xi​))+γJ+2λ​j=1∑J​wtj2​
2. 损失函数里面$L(y_i, f_{t-1}(x_i))$L(yi​,ft−1​(xi​))是常数，对最小化无影响可以去掉，同时由于每个决策树的第j个叶子节点的取值最终会是同一个值$w_{tj}$wtj​，因此损失函数继续化简$L_t \approx \sum\limits_{i=1}^m g_{ti}h_t(x_i) + \frac{1}{2} h_{ti} h_t^2(x_i)) + \gamma J + \frac{\lambda}{2}\sum\limits_{j=1}^Jw_{tj}^2 \\$Lt​≈i=1∑m​gti​ht​(xi​)+21​hti​ht2​(xi​))+γJ+2λ​j=1∑J​wtj2​$= \sum\limits_{j=1}^J (\sum\limits_{x_i \in R_{tj}}g_{ti}w_{tj} + \frac{1}{2} \sum\limits_{x_i \in R_{tj}}h_{ti} w_{tj}^2) + \gamma J + \frac{\lambda}{2}\sum\limits_{j=1}^Jw_{tj}^2 \\$=j=1∑J​(xi​∈Rtj​∑​gti​wtj​+21​xi​∈Rtj​∑​hti​wtj2​)+γJ+2λ​j=1∑J​wtj2​$= \sum\limits_{j=1}^J [(\sum\limits_{x_i \in R_{tj}}g_{ti})w_{tj} + \frac{1}{2}( \sum\limits_{x_i \in R_{tj}}h_{ti}+ \lambda) w_{tj}^2] + \gamma J$=j=1∑J​[(xi​∈Rtj​∑​gti​)wtj​+21​(xi​∈Rtj​∑​hti​+λ)wtj2​]+γJ把每个叶子节点区域样本的一阶和二阶导数的和单独表示$G_{tj} = \sum\limits_{x_i \in R_{tj}}g_{ti},\; H_{tj} = \sum\limits_{x_i \in R_{tj}}h_{ti}$Gtj​=xi​∈Rtj​∑​gti​,Htj​=xi​∈Rtj​∑​hti​$L_t = \sum\limits_{j=1}^J [G_{tj}w_{tj} + \frac{1}{2}(H_{tj}+\lambda)w_{tj}^2] + \gamma J$Lt​=j=1∑J​[Gtj​wtj​+21​(Htj​+λ)wtj2​]+γJ

XGBoost损失函数的优化求解

• 一次求解出决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解$w_{tj}$wtj​

1. 如果已经求出了第t个决策树的J个最优的叶子节点区域，如何求出每个叶子节点区域的最优解$w_{tj}$wtj​
2. 对当前决策树做子树分裂决策时，应该如何选择哪个特征和特征值进行分裂，使最终的损失函数????????最小

• 对于第一个问题，直接基于损失函数对$w_{tj}$wtj​求导并令导数为0。这样得到叶子节点区域的最优解????????????$w_{tj} = - \frac{G_{tj}}{H_{tj} + \lambda}$wtj​=−Htj​+λGtj​​

• 第二个问题：在GBDT里面是直接拟合的CART回归树，所以树节点分裂使用的是均方误差。XGBoost这里使用贪心法，即每次分裂都期望最小化损失函数的误差。

  ????????????取最优解时$L_t = -\frac{1}{2}\sum\limits_{j=1}^J\frac{G_{tj}^2}{H_{tj} + \lambda} +\gamma J$Lt​=−21​j=1∑J​Htj​+λGtj2​​+γJ
  假设当前节点左右子树的一阶二阶导数和为$G_L,H_L,G_R,H_L$GL​,HL​,GR​,HL​, 则我们期望最大化下式：$-\frac{1}{2}\frac{(G_L+G_R)^2}{H_L+H_R+ \lambda} +\gamma J -( -\frac{1}{2}\frac{G_L^2}{H_L + \lambda} -\frac{1}{2}\frac{G_{R}^2}{H_{R} + \lambda}+ \gamma (J+1) )$−21​HL​+HR​+λ(GL​+GR​)2​+γJ−(−21​HL​+λGL2​​−21​HR​+λGR2​​+γ(J+1))使分裂后的损失函数误差尽可能小，即$\max \frac{1}{2}\frac{G_L^2}{H_L + \lambda} + \frac{1}{2}\frac{G_R^2}{H_R+\lambda} - \frac{1}{2}\frac{(G_L+G_R)^2}{H_L+H_R+ \lambda} - \gamma$max21​HL​+λGL2​​+21​HR​+λGR2​​−21​HL​+HR​+λ(GL​+GR​)2​−γ举个简单的年龄特征的例子，假设选择年龄这个特征的值a作为决策树的分裂标准，则可以得到左子树2个人，右子树三个人，这样可以分别计算出左右子树的一阶和二阶导数和，进而求出最终的上式的值。
  使用不同的划分标准，找出可以使上式最大的组合，以它对应的特征值来分裂子树。

XGBoost算法主流程

输入是训练集样本$I=\{(x_1,y_1),(x_2,y_2), ...(x_m,y_m)\}$I={(x1​,y1​),(x2​,y2​),...(xm​,ym​)}，最大迭代次数T，损失函数L， 正则化系数????, ????。
输出是强学习器f(x)

对迭代轮数 $t=1, 2, ...T$t=1,2,...T ：

1. 计算样本$x_i$xi​在当前轮损失函数L基于$f_{t-1}(x_i)$ft−1​(xi​)的一阶导数$g_{ti}$gti​，二阶导数$h_{ti}$hti​，计算所有样本的一阶导数和$G_{tj} = \sum\limits_{x_i \in R_{tj}}g_{ti}$Gtj​=xi​∈Rtj​∑​gti​以及二阶导数和$H_{tj} = \sum\limits_{x_i \in R_{tj}}h_{ti}$Htj​=xi​∈Rtj​∑​hti​
2. 基于当前节点尝试分裂决策树，默认分数score=0，G和H为当前分裂节点的一阶二阶导数之和。
   对特征序号 $k=1,2...K$k=1,2...K:
   • $G_L=0,H_L=0$GL​=0,HL​=0
   • 将样本按特征k从小到大排列，依次取出第i个样本，依次计算当前样本放入左子树后，左右子树一阶和二阶导数和：$G_L = G_L+ g_{ti}, G_R=G-G_L$GL​=GL​+gti​,GR​=G−GL​$H_L = H_L+ h_{ti}, H_R=H-H_L$HL​=HL​+hti​,HR​=H−HL​
   • 更新最大的分数$score = max(score, \frac{1}{2}\frac{G_L^2}{H_L + \lambda} + \frac{1}{2}\frac{G_R^2}{H_R+\lambda} - \frac{1}{2}\frac{(G_L+G_R)^2}{H_L+H_R+ \lambda} -\gamma )$score=max(score,21​HL​+λGL2​​+21​HR​+λGR2​​−21​HL​+HR​+λ(GL​+GR​)2​−γ)
3. 基于最大score对应的划分特征和特征值分裂子树。
4. 如果最大score为0，则当前决策树建立完毕，计算所有叶子区域的$w_{tj}$wtj​，得到弱学习器 $h_t(x)$ht​(x)，更新强学习器 $f_t(x)$ft​(x)，进入下一轮弱学习器迭代。如果最大score不是0，则转到第2步继续尝试分裂决策树。

XGBoost算法运行效率的优化

• Boosting算法的弱学习器不可以并行迭代，但是单个弱学习器里面最耗时的是决策树的分裂过程，XGBoost针对这个分裂做了比较大的并行优化。对于不同的特征的特征划分点，XGBoost分别在不同的线程中并行选择分裂的最大增益。
• 同时，对训练的每个特征排序并且以块的的结构存储在内存中，方便后面迭代重复使用，减少计算量。默认所有的样本都在右子树，然后从小到大迭代，依次放入左子树，并寻找最优的分裂点。这样做可以减少很多不必要的比较。
• 此外，通过设置合理的分块的大小，充分利用了CPU缓存进行读取加速（cache-aware access）。使得数据读取的速度更快。另外，通过将分块进行压缩（block compressoin）并存储到硬盘上，并且通过将分块分区到多个硬盘上实现了更大的IO。
  

XGBoost算法健壮性的优化

• 除了正则化项提高算法的泛化能力外，XGBoost还对特征的缺失值做了处理。

• XGBoost没有假设缺失值一定进入左子树还是右子树，则是尝试通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向，这样处理起来更加的灵活和合理。

  算法流程中步骤2会执行2次，第一次假设特征k所有有缺失值的样本都走左子树，第二次假设特征k所有缺失值的样本都走右子树。然后每次都是针对没有缺失值的特征k的样本走上述流程，而不是所有的的样本。

  如果是所有的缺失值走右子树，使用原步骤即可。如果是所有的样本走左子树，则步骤2要变成：$G_R=0,H_R=0$GR​=0,HR​=0$G_R = G_R+ g_{ti}, G_L=G-G_R$GR​=GR​+gti​,GL​=G−GR​$H_R= H_R+ h_{ti}, H_L=H-H_R$HR​=HR​+hti​,HL​=H−HR​

XGBoost小结

陈天奇(师兄·。·）设计的XGBoost将GBDT的优化走向了一个极致，GBDT的优点及缺点都成为了XGBoost的优点。
详见XGboost论文及PPT。