重读XGBoost

在使用xgboost方法调参时，对其中个别参数不是特别理解。故重新读了一遍原论文。

1. 引言 #

阐述机器学习和数据驱动的方法应用时两个重要的因素：

能捕捉数据间复杂依赖关系的模型
可扩展的学习系统，可以从大量数据中学习

在目前常用的方法中，梯度提升树（gradient tree boosting）在许多场景中效果都不错，作者列举了一些。提出xgboost方法在比赛以及各类问题中的应用。

叙述XGBoost的优点：运行更快、拓展性更好。创新点包括：

高度可拓展的端到端提升树（tree boosting）系统
用于高效计算的加权分位数图（weighted quantile sketch）
新颖的稀疏感知算法（sparsity-aware algorithm），用于并行树学习
有效的缓存优化以及块（cache-aware block）结构用于外存（out-of-core）树学习关于以上几点在正文中详解。

论文结构：

提升树（tree boosting）简介以及目标函数正则化
分裂点寻找的方法
系统设计，包括为每个优化提供量化支持的结果
相关工作
详细的端到端评估
总结

2. 提升树（Tree Boosting）简介 #

首先需要了解CART（Classification And Regression Tree）算法，对于cart分类树和回归树分别采用了：Gini系数、和方差度量方式来划分节点[1]。例如回归树，对于划分特征A, 划分点s使两边数据集D1和D2,求出使 D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小。 $$\underline{min}_{\text{A,s}}[\underline{min}_{\text{c1}}\sum_{x_i\in{D1(A,s)}}(y_i - c1)^2+\underline{min}_{\text{c2}}\sum_{x_i\in{D2(A,s)}}(y_i - c2)^2]$$ 其中，c1为D1的样本输出均值，c2为D2的样本输出均值, 回归树采用叶子节点的均值或者中位数来预测输出结果，$y_i$即样本的label，此时的输出值即下文中用到的$w_{q(x)}$。

2.1 正则化目标函数 #

对于这种类型的集成树模型，用K棵树的结果来预测最后的结果（式1），那么问题来了我们怎么来求这些树的参数，每棵树都可以看做一个函数$f_i$包含树的结构以及最后叶节点权重，集成模型不像传统优化问题一样通过简单用梯度下降可以对所有的树进行学习求解，所以，在这里用到了加法策略，即固定已经学习到的，每次加一棵树来进行学习（式3）。 $$\hat{y_i} = \phi(x_i) = \sum_{k = 1}^{K} f_k(x_i)\tag1$$ 其中$f(x) = w_{q(x)}$，每个$f_k$对应一个独立的树结构q以及其叶节点权重w，为了学习模型中的参数，最小化下面正则化的目标函数。 $$L(\phi) = \sum_i l(\hat{y_i}, y_i) + \sum_k \Omega(f_k)\tag2$$

$$\Omega(f_k) = \gamma T + \frac{1}{2}\lambda||w||^2$$ T是树的叶节点数

2.2 梯度提升树（Gradient Tree Boosting） #

第t次预测值等于t-1加上第t棵树的结果 $$\hat{y_i} = \hat{y_i}^{t-1} + f_t(x_i)\tag3$$ 此时目标函数(式2)可以写成 $$L^{(t)} = \sum_{i=1} ^n l(y_i, \hat{y_i}^{(t-1)}+f_t(x_i)) + \Omega(f_t)\tag4$$ 该式子的二阶近似可以表达为(式5），可以参考补充中二阶泰勒展开的一般形式 $$L^{(t)} \approx \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)]+\Omega(f_t)\tag5$$ 其中 $g_i=\partial_{\hat{y}^{(t-1)}}{l(y_i, \hat{y_i}^{(t-1)})}， h_i=\partial_{\hat{y}^{(t-1)}}^2{l(y_i, \hat{y_i}^{(t-1)})}$

式5中去掉常数项，即label与第t-1次结果的损失函数，可以得到：

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

式6即对新树的优化目标函数，进一步合并可以写为：

$$obj^{t} \approx \sum_{i=1}^{n}[g_i w_{q(x_i)} + \frac{1}{2}h_i w^2_{q(x_i)}] + \gamma T+ \frac{1}{2}\lambda \sum _{j=1}^T w_j^2$$

定义$I_j = {i|q(x_i)=j}$即叶节点j上的实例。

$$obj^{t} \approx \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\tag7$$

上式7对$w_j$求导即可求出w最优值

$$w_j^* = -\frac{\sum_{i\in{I_j}}g_i}{\sum_{i\in{I_j}}h_i+\lambda} $$

令$G_j = \sum_{i\in{I_j}}g_i，H_j=\sum_{i\in{I_j}}h_i$

此时，对应的最小值为: $$obj^* = -\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T$$ $\color{red}\frac{G_j^2}{H_j+\lambda}$越大，loss越小，所以对叶节点进行分裂，分裂后增益定义为 $$Gain=\frac{1}{2}[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}]-\gamma\tag8$$

2.3 缩减和列抽样（Shrinkage and Column Subsampling） #

除了在目标函数中引入正则项，在防止过拟合方面xgboost还运用了两项技术，给每一步tree...

在使用xgboost方法调参时，对其中个别参数不是特别理解。故重新读了一遍原论文。

1. 引言 #

阐述机器学习和数据驱动的方法应用时两个重要的因素：

能捕捉数据间复杂依赖关系的模型
可扩展的学习系统，可以从大量数据中学习

在目前常用的方法中，梯度提升树（gradient tree boosting）在许多场景中效果都不错，作者列举了一些。提出xgboost方法在比赛以及各类问题中的应用。

叙述XGBoost的优点：运行更快、拓展性更好。创新点包括：

高度可拓展的端到端提升树（tree boosting）系统
用于高效计算的加权分位数图（weighted quantile sketch）
新颖的稀疏感知算法（sparsity-aware algorithm），用于并行树学习
有效的缓存优化以及块（cache-aware block）结构用于外存（out-of-core）树学习关于以上几点在正文中详解。

论文结构：

提升树（tree boosting）简介以及目标函数正则化
分裂点寻找的方法
系统设计，包括为每个优化提供量化支持的结果
相关工作
详细的端到端评估
总结

2. 提升树（Tree Boosting）简介 #

2.1 正则化目标函数 #

$$\Omega(f_k) = \gamma T + \frac{1}{2}\lambda||w||^2$$ T是树的叶节点数

2.2 梯度提升树（Gradient Tree Boosting） #

式5中去掉常数项，即label与第t-1次结果的损失函数，可以得到：

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

式6即对新树的优化目标函数，进一步合并可以写为：

$$obj^{t} \approx \sum_{i=1}^{n}[g_i w_{q(x_i)} + \frac{1}{2}h_i w^2_{q(x_i)}] + \gamma T+ \frac{1}{2}\lambda \sum _{j=1}^T w_j^2$$

定义$I_j = {i|q(x_i)=j}$即叶节点j上的实例。

$$obj^{t} \approx \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\tag7$$

上式7对$w_j$求导即可求出w最优值

$$w_j^* = -\frac{\sum_{i\in{I_j}}g_i}{\sum_{i\in{I_j}}h_i+\lambda} $$

令$G_j = \sum_{i\in{I_j}}g_i，H_j=\sum_{i\in{I_j}}h_i$

2.3 缩减和列抽样（Shrinkage and Column Subsampling） #

除了在目标函数中引入正则项，在防止过拟合方面xgboost还运用了两项技术，给每一步tree...

在使用xgboost方法调参时，对其中个别参数不是特别理解。故重新读了一遍原论文。

1. 引言 #

阐述机器学习和数据驱动的方法应用时两个重要的因素：

能捕捉数据间复杂依赖关系的模型
可扩展的学习系统，可以从大量数据中学习

在目前常用的方法中，梯度提升树（gradient tree boosting）在许多场景中效果都不错，作者列举了一些。提出xgboost方法在比赛以及各类问题中的应用。

叙述XGBoost的优点：运行更快、拓展性更好。创新点包括：

高度可拓展的端到端提升树（tree boosting）系统
用于高效计算的加权分位数图（weighted quantile sketch）
新颖的稀疏感知算法（sparsity-aware algorithm），用于并行树学习
有效的缓存优化以及块（cache-aware block）结构用于外存（out-of-core）树学习关于以上几点在正文中详解。

论文结构：

提升树（tree boosting）简介以及目标函数正则化
分裂点寻找的方法
系统设计，包括为每个优化提供量化支持的结果
相关工作
详细的端到端评估
总结

2. 提升树（Tree Boosting）简介 #

2.1 正则化目标函数 #

$$\Omega(f_k) = \gamma T + \frac{1}{2}\lambda||w||^2$$ T是树的叶节点数

2.2 梯度提升树（Gradient Tree Boosting） #

式5中去掉常数项，即label与第t-1次结果的损失函数，可以得到：

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

式6即对新树的优化目标函数，进一步合并可以写为：

$$obj^{t} \approx \sum_{i=1}^{n}[g_i w_{q(x_i)} + \frac{1}{2}h_i w^2_{q(x_i)}] + \gamma T+ \frac{1}{2}\lambda \sum _{j=1}^T w_j^2$$

定义$I_j = {i|q(x_i)=j}$即叶节点j上的实例。

$$obj^{t} \approx \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\tag7$$

上式7对$w_j$求导即可求出w最优值

$$w_j^* = -\frac{\sum_{i\in{I_j}}g_i}{\sum_{i\in{I_j}}h_i+\lambda} $$

令$G_j = \sum_{i\in{I_j}}g_i，H_j=\sum_{i\in{I_j}}h_i$

2.3 缩减和列抽样（Shrinkage and Column Subsampling） #

除了在目标函数中引入正则项，在防止过拟合方面xgboost还运用了两项技术，给每一步tree...