Abstract

[文章结构]

XGBoost: A Scalable Tree Boosting System” 是陈天奇博士在2016年的SIGKDD会议上发表的文章，该文描述了一个可扩展的端到端的tree boosting系统，也就是XGBoost。

本文尝试分析一下这篇论文以及XGB的源码，看一下细节之处。

Tree Boosting

首先回顾一下tree boosting算法。

预测函数

假设我们的数据集为

$D = {(x_i,y_i)} (

= n,x_i \in R^m, y_i \in R)$

假设模型有$K$棵树，预测结果是$K$个additive function的输出：

$\hat{y_i}=\phi(x_i)=\sum_{k=1}^Kf_k(x_i), f_k\in F$ $F=\{f(x)=w_{q(x)}\}(q: R^m\to T, w\in R^T)$

这里$F$是回归树(CART)的空间，$q$是每棵树的结构，$T$是树的叶子数量，$w$是叶子权重，每个$f_k$对应一个独立的树结构$q$和叶子权重$w$。与决策树不同，每棵回归树的每个叶子是一个连续值，我们用$w_i$代表第$i$个叶子的得分。预测时，我们用每棵树的$q$提供的决策规则将样本分类到相应的叶子节点上，然后将所有树的叶子节点的得分($w$提供)加起来，就是最终的预测结果。以上是预测函数，下面介绍目标函数。

目标函数

下面是加入正则项的损失函数：

$\cal L(\phi) = \sum_i l(\hat{y_i}, y_i) + \sum_k\Omega(f_k)$ $\Omega(f) = \gamma T + \frac12 \lambda ||w||^2$

这里$l$是一个可微的凸函数，【写其他变量的含义】

由于是拟合的残差，损失函数可以写成：

$\cal L^{(t)} = \sum_{i=1}^nl(y_i, \hat{y_i}^{(t-1)} + f_t(x_i)) + \Omega(f_t)$

我们将损失函数按泰勒公式二阶展开：

$\cal L^{(t)} \approx \sum_{i=1}^n [l(y_i, \hat y^{t-1}) + g_if_t(x_i) + \frac12h_if_t^2(x_i)] + \Omega(f_t)$

$g_i = \partial_{\hat y^{(t-1)}}l(y_i, \hat y^{(t-1)})$

$h_i = \partial^2_{\hat y^{(t-1)}}l(y_i, \hat y^{(t-1)})$