Content

Introduction
Regularized Learning Objective - 正则化目标方程
Split Finding Algorithm - 节点切分算法
Dealing with Missing value - 缺失值处理
Difference between XGBoost and GBDT - XGBoost和GBDT的区别

1. Introduction

最近引起关注的一个Gradient Boosting算法：xgboost，在计算速度和准确率上，较GBDT有明显的提升。xgboost 的全称是eXtreme Gradient Boosting，它是Gradient Boosting Machine的一个c++实现，作者为正在华盛顿大学研究机器学习的大牛陈天奇。xgboost最大的特点在于，它能够自动利用CPU的多线程进行并行，同时在算法上加以改进提高了精度。它的处女秀是Kaggle的希格斯子信号识别竞赛，因为出众的效率与较高的预测准确度在比赛论坛中引起了参赛选手的广泛关注。值得我们在GBDT的基础上对其进一步探索学习。

2. Regularized Learning Objective

机器学习问题的本质是数据分布的模型拟合，用数学语言表达就是目标函数的最优化问题。跟GBDT类似，Xgboost对于给定数据集进行additive trainning，学习K棵树，得到下面的预测函数：
$\begin{align} & \hat{y_i} = \phi(x_i) = \sum_{k=1}^{K} f_k(x_i), f_k \in \mathcal{F} \\ & \mathcal{F} = {f(x) = w_{q(x)}}(q : \mathbb{R}^m \rightarrow T, w \in \mathbb{R}^T) \\ & \text{space of regression trees(also known as CART)}\\ & T \leftarrow \text{# of leaves in the tree} \\ & f_k \leftarrow \text{an independent tree structure q and leaf weights w} \end{align}$

和决策树不同，每一个回归树的每一个叶节点都包含一个continuous score. 我们用 $w_i$ 表示第 $i$ 个叶节点
上述预测函数是如何得到的呢？我们需要分析目标函数，如下：

其中，第一项跟GBDT中是一样的，选定某个损失函数，计算预测值与真实值的偏差，第二项为正则项，传统的GBDT并没有，也是Xgboost改进的地方。我们知道决策树的一个缺点就是易过拟合，需要剪枝操作，这里的正则项起到类似的作用。
第t次迭代，目标函数具体写作：
$\mathcal{L}^{(t)} = \sum_{i=1}^{n} l(y_i, \hat{y_i}^{t-1} + f_t(x_i)) + \Omega f(t)$
然后，基于前t-1次的预测值yt-1处做二阶的泰勒展开：

而GBDT的这部分则是基于前t-1次的预测值yt-1处做一阶的泰勒展开，这也是Xgboost改进的地方，泰勒二阶近似比一阶近似更接近真实的Loss Fnction，自然优化的更彻底。
接下来分析正则项的形式，如下：

为什么是这样的形式，官网的说明是：
Of course there is more than one way to define the complexity, but this specific one works well in practice.
其中，T为叶子节点的数目，w为叶子节点的value向量。
对树函数f作如下变换：

将正则项的具体形式和变换后的树函数带入目标函数，如下：

统一i，j的求和，如下：

可以看出t轮的L函数是关于w的二次函数，求极值：

3. Split Finding Algorithm - 节点切分算法

我们已经确定了损失函数，以及最优解，接下来我们需要缺点树的结构，即如何选出最优分裂节点。我们可以参照决策树算法：ID3选择信息增益为切分准则，C4.5选择信息增益率为切分准则。XGBoost基本思想是和决策树一致的：贪心法枚举所有节点，计算各个节点分裂前后的信息增益，选出信息增益最大的。下面是XGBoost信息增益的定义：

XGBoost提供了两种切分算法：精确贪心算法(Exact Greedy Algorithm)和近似算法(Approximate Algorithm)

3.1 Exact Greedy Algorithm

Exact Greedy Algorithm

遍历所有特征的所有可能的分割点，计算Gain值，选取最大的 (Feature，label) 去分裂。

为了达到这个目标，split finding算法会在所有特征 (features) 上，枚举所有可能的划分(splits)。为了更高效，该算法必须首先根据特征值对数据进行排序，以有序的方式访问数据来枚举 $Gain$ 公式中的结构得分 (structure score) 的梯度统计 (gradient statistics)。

3.2 Approximate Algorithm

Approximate Algorithm

对于每个特征，只考察分位点，减少计算复杂度。

该算法会首先根据特征分布的百分位数 (percentiles of feature distribution)，提出候选划分点 (candidate splitting points)。接着，该算法将连续型特征映射到由这些候选点划分的分桶(buckets) 中，聚合统计信息，基于该聚合统计找到在 proposal 间的最优解。

Global：学习每棵树前，提出候选切分点；
Local：每次分裂前，重新提出候选切分点；

近似算法举例：三分位数

近似算法中使用到了分位数，关于分位数的选取，论文提出了一种算法Weighted Quantile Sketch 。XGBoost不是按照样本个数进行分位，而是以二阶导数为权重。

Q:为什么使用hi加权？
A：比较直观的解释是因为目标函数可以化简为如下形式：
$\sum_{i=1}^{n} \frac{1}{2}h_i(f_t(x_i) - g_i/h_i)^2 + \Omega(f_t) + constant$

4. Dealing with Missing value 对缺失值的处理

缺失值是实际的机器学习项目中不容忽视的问题。自带的工具包帮你解决不是好事，因为默认的处理方式不一定符合你的场景。Xgboost的处理方式是，缺失值数据会被分到左子树和右子树分别计算损失，选择较优的那个。如果训练中没有数据缺失，预测时出现了数据缺失，默认分类到右子树。

5. XGBoost和GBDT的区别

GBDT

GBDT 它的非线性变换比较多，表达能力强，而且不需要做复杂的特征工程和特征变换。
GBDT 的缺点也很明显，Boost 是一个串行过程，不好并行化，而且计算复杂度高，同时不太适合高维稀疏特征；
传统 GBDT 在优化时只用到一阶导数信息。
XGBoost

它有以下几个优良的特性：
1. 显示的把树模型复杂度作为正则项加到优化目标中。
2. 公式推导中用到了二阶导数，用了二阶泰勒展开。（GBDT 用牛顿法貌似也是二阶信息）
3. 实现了分裂点寻找近似算法。
4. 利用了特征的稀疏性。
  5 . 数据事先排序并且以 block 形式存储，有利于并行计算。
5. 基于分布式通信框架 rabit，可以运行在 MPI 和 yarn 上。（最新已经不基于 rabit 了）
6. 实现做了面向体系结构的优化，针对 cache 和内存做了性能优化。

XGBoost原理梳理