XGBoost

XGBoost的符号表示稍微有些不同，参考 陈天奇 的 slide 。

XGBoost本质上也是一个gradient boosting。

我们每轮都训练一个基础分类器：

$\hat y_i^{(0)} = 0$

$\hat y_i^{(1)} = f_1(x_i) = \hat y_i^{(0)} + f_1(x_i)$

$\hat y_i^{(2)} = f_1(x_i) + f_2(x_i) = \hat y_i^{(1)} + f_2(x_i)$

$\hat y_i^{(t)} = \sum_{k=1}^t f_k(x_i) = \hat y_i^{(t-1)} + f_t(x_i)$

上面的最后一条式子解释如下：当我们训练了t轮以后，有了t个弱学习器，每一轮都将之前已经Boosting的强学习器和现在这轮的弱学习器的结果相加。

目标函数（损失函数） ：$Obj^{(t)} = \sum_{i=1}^nl(y_i, \hat y_i^{(t)})+\sum_{i=1}^tΩ(f_i)$

回忆 泰勒展开 ：$f(x + \Delta x)≈f(x)+f’(x)\Delta x+\frac{1}{2}f’’(x)\Delta x^2$

将$\hat y_i^{(t)} = \hat y_i^{(t-1)} + f_t(x_i)$带入目标函数，转换成：

$Obj^{(t)} = \sum_{i=1}^n[l(y_i, \hat y_i^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+Ω(f_t)+constant$，其中，$g_i = \partial_{\hat y_i^{(t-1)}}l(y_i, \hat y_i^{(t-1)})$，$h_i = \partial^2_{\hat y_i^{(t-1)}}l(y_i, \hat y_i^{(t-1)})^2$

把上面的常数都去掉，剩下：

$Obj^{(t)} = \sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+Ω(f_t)$

引入叶结点的权重：$f_t(x) = w_{q(x)}$，$q(x)$是样本到叶结点的映射，正则函数：$Ω(f_t) = \gamma T + \frac{1}{2}\lambda \sum^T_{j=1}w^2_j$。$T$是叶结点的个数。

定义在叶结点j的样本集：$I_j = {i|q(x_i) = j}$ 把叶结点权重和正则函数带入目标函数，得到：

$$Obj^{(t)} = \sum_{i=1}^n[g_iw_{q(x_i)}+\frac{1}{2}h_iw^2_{q(x_i)}]+\gamma T +
\frac{1}{2}\lambda \sum^T_{j=1}w^2_j$$

$$=\sum_{j=1}^T[(\sum_{i∈I_j }g_i)w_j +
\frac{1}{2}(\sum_{i∈I_j}h_i+\lambda)w_j^2]+\gamma T$$

定义：$G_j = \sum_{i∈I_j}g_i$，$H_j = \sum_{i∈I_j}h_i$，

$Obj^{(t)} =\sum_{j=1}^T[G_jw_j + \frac{1}{2}(H_j + \lambda)w_j^2] + \lambda T$

回忆一下一元二次函数的性质：

对于：$Gx + \frac{1}{2}Hx^2$，（$H>0$），最小值为：$-\frac{1}{2}\frac{G^2}{H}$，在$ -\frac{G}{H}$处取得。

回到目标函数中去，如果树的结构（$q(x)$）固定，那最优的权值分配是：

$w_j^* = -\frac{G_i}{H_j+\lambda}$

$Obj^* = -\frac{1}{2}\sum^T_{j=1}\frac{G_j^2}{H_j+\lambda}+\gamma T$

接下来考虑 如何学习树的结构（Greedy Learning） ：

回忆一下CART是如何做的：

对现有特征A的每一个特征，每一个可能的取值a， 根据样本点对$A=a$的测试是“是”还是“否” ，将$D$分割成$D_1$和$D_2$两部分，计算$A=a$时的基尼指数。选择基尼指数最小的特征机器对应的切分点作为 最优特征 和 最优切分点 。

这里不算基尼指数，这里的Gain是：$\frac{1}{2}[\frac{G^2_L}{H_L+\lambda}+\frac{G^2_R}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}] - \gamma$。

上式方括号中的三项分别代表： 左子树的得分 ； 右子树的得分 ； 如果不分割的得分 。得分可以理解成是损失的反面。
寻找最优分割的算法：