XGBoost 介绍

目标函数

我之前的博客提到过,Boosting 是一种将弱分类器转化为强分类器的方法,它的函数模型具有叠加性。

XGBoost 的目标函数由损失函数和复杂度组成。复杂度又由叶子数量和 L2 正则组成。

$$L(\phi) = \sum_i l(y^{*}_i, y_i) + \sum_k \Omega(f_k) $$

$$where \,\, \Omega(f) = \gamma T + \frac{1}{2}\lambda||w||^2$$

其中 i 是样本 id,k 是树 id(轮数),由于 loss 函数和复杂度项都是凸函数,所以有最小值。w 是与真实值的残差,将 w 的 L2 正则项加在目标函数中,可以有效的防止过拟合。叶子节点的数目也作为正则项加在了目标函数中,一定程度上限制了叶子数量,防止过拟合。而传统 GBDT 防止过拟合的手段是预剪枝或者后剪枝。

推导过程

对于每次迭代过程,可以将一颗树的训练目标函数写成形式如下:

$$L^{(t)} = \sum_{i=1}^n l(y_i, y_i^{*(t-1)} + f_t(x_i)) + \Omega(f_t)$$

输入是 \(t-1\) 轮后预测的值和真实值,用来拟合残差 \(f(x)\)。对于这个式子,因为无法对 \(f(x)\) 进行有效的最优估计,所以要进行如下推导:

首先将目标函数泰勒二阶展开:

$$L^{(t)} = \sum_{i=1}^n [ l(y_i, y_i^{*(t-1)}) + g_i f_i(x_i) + \frac{1}{2} h_if^2_t(x_i)] + \Omega(f_t)$$

去掉常数项,

$$L^{(t)} = \sum_{i=1}^n [g_i f_i(x_i) + \frac{1}{2} h_if^2_t(x_i)] + \Omega(f_t)$$

正则项展开,

$$L^{(t)} = \sum_{i=1}^n [g_i f_i(x_i) + \frac{1}{2} h_if^2_t(x_i)] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2$$

首先做一下转换,

$$w_j = f(x_i) \, \, i \in _jI$$

所以,公式可以转化为:

$$L^{(t)} = \sum_{j=1}^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$$

这是一个二次项形式,所以最后使得目标函数最小的 w 为,

$$w^*_j = - \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}$$

带入原方程最小值为:

$$L^{t}(q) = - \frac{1}{2} \sum_{j=1}^T \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma T$$

最后求得的w就是目标函数在一个样本集合条件下的最优解。

总结

为什么要用泰勒二阶近似展开。

由于 gbdt 只用到了一阶信息,相当于 loss 函数只进行了一阶泰勒展开。在没有复杂度项的情况下,无法确定步长,所以只能用常数步长根据一阶梯度方向去逼近。这就是牛顿下降法和梯度下降法的区别。由于二阶展开用二次函数去逼近函数,所以可以利用二阶信息确定更新步长,比只利用一阶信息的 gdbt 用更少的迭代获得更好的效果。

为何要对目标函数进行推导。

  1. 为了适应各种损失函数。
  2. 正则项的加入对参数估计产生了影响。
  3. 如果只考虑平方损失的条件下,在没有正则项的情况下参数的最优估计为样本均值。在没有指定损失函数情况下,我们也很容易想到均值是给定样本条件下的误差最小的最优估计。但是损失函数换成绝对值损失,那么最优估计就为中位数。可见不同损失函数下,结果并不想我们想的那么简单。