决策树（四）- xgboost
xgboost也是一种基于boosting策略的算法，其与GBDT最大的差别在于其目标函数的定义：GBDT算法利用了损失函数一阶导数信息来近似残差，而xgboost对损失函数做了二阶的泰勒展开，并加入了正则项以权衡模型的复杂度，减轻过拟合问题。
xgboost的目标函数定义如下： \(L^t = \sum_{i=1}^{n}l(y_i, \hat{y}_i^t) + \sum_{j=1}^t\Omega(f^j)\) \(=\sum_{i=1}^nl\left(y_i, \hat{y_i}^{t-1}+f^t(x_i)\right) + \Omega(f^t) + \text{常数}\)
其中t为第t轮，对应的$f^t$表示第t轮的模型，$\Omega(f^j)$表示正则项，常数项$=\sum_{j=1}^{t-1}\Omega(f^j)$
泰勒展开式 : $f(x+\Delta x) \simeq f(x)+f^{\prime}(x)\Delta x + \frac{1}{2}f^{\prime\prime}(x)\Delta x^2$
由泰勒展开式，我们可以将刚才的目标公式重新写成： \(L^t\simeq\sum_{i=1}^n\left( l(y_i, \hat{y_i}^{t-1}) + g_if^t(x_i)+\frac{1}{2}h_i[f^t(x_i)]^2\right) + \Omega(f^t) + \text{常数}\)
其中 \(g_i = \frac{\partial l(y_i, \hat{y}^{t-1})}{\partial y^{t-1}}\), \(h_i = \frac{\partial^2 l(y_i, \hat{y}^{t-1})}{\partial^2 y^{t-1}}\)
对于$L^t$来说，常数项与$l(y_i, \hat{y_i}^{t-1})$都是一个常数，对于loss的梯度下降并不起作用，因此我们可以将公式简化为： \(L^t\simeq\sum_{i=1}^n\left( g_if^t(x_i)+\frac{1}{2}h_i[f^t(x_i)]^2\right) + \Omega(f^t)\)
我们可以将$f^t$重新定义为： \(f^t(x)=w_q(x)\)
w为叶子的权重(即叶子结点的值)，q是将样本映射到某个叶子的函数。由此，我们可以将复杂度$\Omega(f^t)$定义为： \(\Omega(f^t)=\gamma T + \frac{1}{2}\lambda\sum_{j=1}^Tw_j^2\)
将公式带入原来的目标公式： \(L^t\simeq\sum_{i=1}^n\left( g_if^t(x_i)+\frac{1}{2}h_i[f^t(x_i)]^2\right) + \Omega(f^t)\) \(=\sum_{i=1}^n\left( g_iw_q(x_i)+\frac{1}{2}h_i[w_q(x_i)]^2\right) + \gamma T + \frac{1}{2}\lambda\sum_{j=1}^Tw_j^2\) \(=\sum_{j=1}^T\left((\sum_{i\subset I_j}g_i)w_j+\frac{1}{2}(\sum_{i\subset I_j}h_i+\lambda)w_j^2\right)+\gamma T\)
| 其中$I_j$为每个叶子结点上的样本集合，即$I_j={i | q(x_i=j)}$ |
令$G_j=\sum_{i\subset I_j}g_i$，$H_j=\sum_{i\subset I_j}h_i$ 则目标公式最终化简为： \(L^t = \left(G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2\right)+\gamma T\)
对给定的一棵树，其q已知，则由$\frac{\partial L^t}{\partial w}=0$可得： \(w_j^*=-\frac{G_j}{H_j+\lambda}\)
调参方法经验总结
-
先固定其他参数，设一个较大的学习率，比如0.1，然后调整参数n_estimators（或num_boost_round）,获得最好的n_estimators（或num_boost_round）；
-
将n_estimators（或num_boost_round）设为第一步得到的最优值，并固定其他参数，调整跟树有关的参数，建议调整顺序：
2.1 max_depth（3～10）,
2.2 min_child_weight,
2.3 gamma,
2.4 subsample（0.5～1）, colsample_bytree（0.5～1）
3、在第二步最优参数设置的基础上，调整正则化参数alpha和lambda
4、调整／降低学习率
参考资料
【1】Boosting学习笔记（Adboost、GBDT、Xgboost） 【2】Complete Guide to Parameter Tuning in XGBoost with codes in Python
