XGBoost算法

XGBoost（eXtreme Gradient Boosting）算法近年来在各种比赛中可谓是“香饽饽”，预测性能很好。下面我们就来介绍它的原理。

原理

首先，我们要了解的是，XGBoost是GBDT算法的一种改进。

在进行第k轮的迭代时，GBDT的损失函数可记为L(y,F[k](x))。那么它在F[k-1](x)处的二阶泰勒展开式为

根据前向分布算法，我们有

将上式代入刚才的损失函数，再令a等于一阶导，b等于2阶导，则损失函数可写为

其中，a和b分别是

那么，对于所有的样本而言，其损失函数为

对上式的优化，可以等价于优化

具体原因我们在介绍AdaBoost算法时已经介绍过，这里不再赘述。

正则化

为了防止过拟合，我们在优化损失函数时，往往要给其添加一个正则化项。

那么，添加了正则化项的损失函数为

在上一篇，我们介绍过

而正则化项由如下的公式构成

其中，M是叶子节点的个数，α和β都是正则化项的参数，用来控制模型的复杂度。

将（3）（4）式代入（2）式，可得

要想求得（5）式的最小值，我们需要对c[m]求偏导，即

然后令（6）式为0，可得

接下来，我们再把（7）式反代回（5）式，可以得到损失函数L为

（8）式就是第k轮所得到的损失函数。

回顾整个过程，我们发现，其实XGBoost就是将损失函数进行二阶泰勒展开后，求得一个解，然后将其反带入损失函数。换句话说，就是用这个解来帮助构造其中的决策树，从而使残差和最小，模型性能达到最优。