算法回顾：Xgboost

作者: 张虾米试错 | 来源:发表于2019-02-12 10:02 被阅读0次

温故而知新，感觉每次重读看过的论文都有新的收获，今天复习的是Xgboost，本文主要介绍了xgboost的原理。

提纲

GBDT
Xgboost
RF vs. GBDT vs. Xgboost

1. GBDT

由于Xgboost也是一种gradient boosting算法，因此在介绍xgboost之前简单地说一下gbdt。

1.1 提升树模型

提升树模型采用加法模型与前向分步算法，对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。提升树模型可以表示为：

$f_M(x) = \sum_{m=1}^{M} T(x;\Theta_m)$
其中， $T(x;\Theta_m)$ 表示决策树； $\Theta_m$ 为决策树的参数；M为树的个数。

1.2 提升树算法

提升树使用前向分步算法（虽然这个算法不是太懂，但是我的理解是前向迭代吧）：

$f_0(x) = 0$
$f_m(x) = f_{m-1}(x) + T(x; \Theta_m), m=1,2,...,M$
$f_M(x) = \sum_{m-1}^{M}{T(x;\Theta_m)}$
那么在前向分步算法的第m步，给定当前模型 $f_{m-1}$ ，需求解目标函数：

$\Theta_m^{'} = argmin_{\Theta_m}\sum{L(y_i, f_{m-1}(x_i)+T(x;\Theta_m))}$
可以看出， $f_m(x_i)=f_{m-1}(x_i)+T(x;\Theta_m)$

由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。

针对不同问题的提升树学习方法，其主要区别在于使用的损失函数不同，包括用平方误差损失函数的回归问题，用指数损失函数的分类问题，以及用一般损失函数的一般决策问题。（根据不同的损失函数，可以构建不同的提升树，因此需要弄清楚不同的损失函数。）

对于每一棵树 $T(x;\Theta)$ :

$T(x;\Theta) = \sum_{j=1}^J{c_jI(x \in R_j)}$
其中，参数 $\Theta={(R_1,c_1), (R_2,c_2), ...,(R_J, c_J)}$ 表示树的区域划分和各区域上的常数，J是回归树的复杂度即叶节点的个数。

另外，对于回归问题的提升树算法而言，

$r = y-f_{m-1}(x)$
是当前模型拟合数据的残差，所以回归提升树只需简单地拟合当前模型的残差即可。

对残差还是负梯度的解释来自于通俗理解kaggle比赛大杀器xgboost

对残差还是负梯度的解释

1.3 提升梯度

提升树的优化过程，当损失函数时平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易，针对这个问题，就有了梯度提升算法。这是利用最速下降法的近似方法，其关键时利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中残差的近似值。

$-[\frac{\varphi(L(y,f(x_i)))}{\varphi(f(x_i))}]$
这里用 $\varphi$ 表示偏导。

有一点，提升树模型是加法模型，因此我认为是不能只用某一棵树作为模型的。

2. Xgboost

Xgboost是对梯度提升算法的改进，目标函数由两部分构成，第一部分为梯度提升算法损失，第二部分为正则化项。Xgboost的损失函数定义为：
$L(\phi) = \sum_i l(\hat y_i, y_i) + \sum_k \Omega(f_k)$
$where \space \Omega(f) = \gamma T + \frac{1}{2}\lambda||w||^2$
$n$ 个样本， $m$ 个特征， $T$ 表示数的叶子个数，叶子的权重为 $w$ 。

由于上式无法通过常规的优化算法求解，因此借鉴gbdt，将模型看成加法模型，令 $\hat y_i^{(t)}$ 表示 $i^{th}$ 样本在 $t^{th}$ 次迭代的预测值，于是目标函数可写成
$L(t) = \sum_i l(y_i, \hat y_i^{(t-1)}+f_t({x}_i)) + \Omega(f_t)$
利用泰特公式的二阶展开
$f({x}) = f({x}_0) + f'({x}_0)({x}-{x}_0) + f''({x}_0)({x}-{x}_0) + O(({x}-{x}_0)^2)$
因此目标函数可近似为
$L(t) \approx \sum_i[l(y_i, \hat y_i^{(t-1)}) + g_if_t({x}_i) + \frac{1}{2}h_if_t^2({x}_i)] + \Omega(f_t)$
$g_i = \varphi_{{\hat y}^{(t-1)}}l(y_i, \hat y_i^{(t-1)})$ , $h_i=\varphi^2_{{\hat y}^{(t-1)}}l(y_i, \hat y_i^{(t-1)})$ ； $y_i$
和 $\hat y^{(t-1)}$ 都是常量，因此，上式去掉常量后，可得到
$\tilde L^{(t)} \approx \sum_i[g_if_t({x}_i) + \frac{1}{2}h_if_t^2({x}_i)] + \Omega(f_t)$
由于 $f_t({x}_i)$ 是 $t^{th}$ 迭代的预测值，而每次迭代为一棵决策树，每个样本终会只落到某个叶子节点，因此目标函数又可以拆分为对所有叶子节点损失函数的和：
$\tilde L^{(t)} \approx \sum_i[g_if_t({x}_i) + \frac{1}{2}h_if_t^2({x}_i)] + \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$
根据求极值的方法，可以得到
$w_j*=-\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}$
将 $w_j*$ 带入损失函数可以得到:
$\tilde L^{(t)} (q) = -\frac{1}{2}\sum_{j=1}^{T}\frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma T$
$\tilde L^{(t)} (q)$ 可以看做是对决策树结构优劣的一个度量，求其极小值，类似于impurity(不纯度指标)对于决策树。由于不可能穷举所有的分裂方式，因此采用贪心方法，只计算左右的值， $I = I_L \cup I_R$ ，因此分裂点的损失函数可以写成：
$L_{split} = \frac{1}{2}[\frac{(\sum_{i \in I_ L} g_i)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{(\sum_{i \in I_ R} g_i)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{(\sum_{i \in I} g_i)^2}{\sum_{i \in I} h_i + \lambda}] - \gamma$

2.1 寻找分裂点

论文中说到两种寻找分裂点的方法：一种是Exact Greedy Algorithm，另一种是Approximate Algorithm。第一种是排序后穷举所有的点；第二种是选取数据的percentiles作为分裂点的候选集，然后在候选集中得到分裂点。另外文中还提到，如果是全局候选集的话，那么当下迭代的决策树的所有分裂点都从候选集中得到；如果是局部，那么只是当前的分裂点从候选集中得到。

论文中还提到如果数据有不同的权重，则使用weighted quantile sketch，但目前这部分还没看懂，后期看懂后再补充。

2.2 缺失值

Xgboost对缺失值有默认的方向，方法如下：

Sparsity-aware Split Finding

最佳的默认方法通过无缺失值的数据分别比较左右最大score得到。需要注意的是，在xgboost的源码中如果是libsvm格式的数据，值为0的特征也需要写出来，不然会当做缺失值处理。

2.3 某些参数的新认识

max_depth
通常情况在6--8，如果max_depth偏大容易过拟合，而xgboost大多是通过增加迭代次数(num_round)来提高模型效果。
scale_pos_weight
对于正负样本比例不平衡的数据集，可设置该参数。

3. RF vs. GBDT vs. Xgboost

3.1 Xgboost vs. RF

随机森林（RF）是一种bagging的组合方法，其中的每棵树是独立的，最终的结果由所有的树投票决定；而xgboost是在上一棵树的基础上迭代。
Xgboost和RF一样都有行采样和列采样的用法，防止过拟合。
RF采取平均每棵树结果的方法降低了模型的方差，相比决策树防止过拟合。

3.2 Xgboost vs. GBDT

这两种都是boosting的方法，最大的区别就是xgboost采用二阶导数，而gbdt只用了一阶导数。
xgboost在损失函数中加入了正则项，用于控制模型的复杂度。
对缺失值的处理，xgboost可以学习出缺失值的默认方向。
xgboost支持并行，这点还没仔细学习，暂不展开。

参考资料

Tianqi Chen and Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. In 22nd SIGKDD Conference on Knowledge Discovery and Data Mining, 2016
github xgboost
xgboost parameters
理解XGBoost
《统计学习方法》李航
机器学习算法之LightGBM
7.机器学习算法之XGBoost
8.XGBoost

有讲到分裂算法

关于特征处理

关于sklearn中的决策树是否应该用one-hot编码？