机器学习14 XGBoost

这一篇开始介绍XGBoost。

和GBDT不同， XGBoost不仅仅使用了一阶梯度，还使用了二阶梯度。同时增加了正则化。

第m步的损失函数：

$L = \sum_{i=1}^n(y_i, F_m(x_i))+\sum_{i=1}^m\Omega (f_i) = \sum_{i=1}^n(y_i, F_{m-1}(x_i) +f_m(x_i))+\Omega (f_m) +C$

$\Omega (f_m)$ 是第m棵树的复杂度， $C$ 是前m-1棵树的复杂度之和，对第m棵树的学习没有影响，所以是常数。

同GBDT，我们把损失函数第一部分泰勒展开，但这次保留前两项，即

$L(y, F_m(x)) = L(y,F_{m-1}(x)) +f_m(x)\frac{\partial L(y,X)}{\partial X}_{|X=F_{m-1}(x)} + \frac{1}{2}f_m(x)\frac{\partial ^2 L(y,X)}{\partial ^2 X}_{|X=F_{m-1}(x)} +\Omega (f_m) +C$

定义 $g_i = \frac{\partial L(y_i, F_{m-1}(x_i))}{\partial F_{m-1}(x_i)}$ ， $h_i = \frac{\partial ^2 L(y_i, F_{m-1}(x_i))}{\partial ^2 F_{m-1}(x_i)}$

针对不同的场合，选择不同的损失函数即可，例如回归问题可以使用MSE，分类问题可以用对数似然。

其中， $\Omega(f) = \gamma T +\frac{1}{2}\lambda\sum_{j=1}^Tw_j^2$ , $\gamma$ 是对叶子节点个数的惩罚系数， $\lambda$ 是对参数的惩罚系数

同GBDT一样，我们可以把每一个基模型，写成 $f_m(x_i) = w_{q(x_i)}$ , $w_{q(x_i)}$ 是 $x_i属于的$ 叶子结点的输出值

现在我们的优化问题变成了

$\mathop{argmin}_{f}\sum_{x_i} [g_iw_{q(x_i)} +\frac{1}{2}h_iw_{q(x_i)}^2] +\gamma T + \frac{1}{2}\lambda \sum_{j=1}^Tw_{j}^2$

$=\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 = \sum_{j=1}^T[G_jw_j + \frac{1}{2}(H_j+\lambda)w_j^2] +\gamma T$