Xgboost原理分析

从陈天奇的PPT中进行总结，重点了解模型的构建，策略的选择和优化算法的选取。

机器学习的目标函数基本都是：

也就是 损失函数和正则化项的组合。

在目标函数，偏差和方差之间 做trade-off

也称分类回归树

上图可以看出来，每个叶子结点都有一个分数，那么被分到该结点的数据获得这个分数。

我们通过将多个这样的回归树集成起来，获得我们的集成算法。

上图可以看出来，对于小男孩的总体分数，就是两棵树的加和结果。

集成树的特点有：

模型假设我们有K棵树（上面提到的回归树）：

F就是我们的假设空间（函数空间，包含k个回归树）

这个模型中的参数包括：

定义目标函数，然后去优化这个目标函数

上图中，是以时间为变量，来构建回归树，评价个人随着时间t是否喜欢浪漫音乐。

将一个回归树等价到一个分段函数中，那么我们从中需要学习的“参数”也就是我们的：

上面四幅图中，给出了不同划分位置和划分高度，最后的参数模型也就是图四的效果。

那么从一棵树开始，我们可以来定义我们模型的目标函数。

我们有K棵树

目标函数是:

第一项是我们的损失函数项，第二项是我们的正则化项。

当我们讨论决策树的时候，都是启发式的从一些方面进行考虑：

我们使用决策树算法时候，就是通过信息增益来划分分支，那么这里我们可以用每一次划分的信息增益当做我们的损失函数。（划分后的信息增益-划分前的信息增益）

决策树中的剪枝，就是为了控制决策树的模型复杂度，这里我们也通过控制叶子节点的个数，来实现正则化，控制模型的复杂度。

限制树的深度，也是一定程度上限制我们的模型复杂度。

尽可能的让我们的叶子上的score平滑，使用L2正则化来控制叶子结点上的权重。

目标函数是:

那我们是如何学习这个目标函数的呢？

我们不能使用梯度下降算法来进行计算损失函数，因为我们这里的参数是回归树，而不是一些数值型数据（类比线性模型里面的参数 w）

从常数开始，然后每次加入一棵新树（一个新的函数）

其中，我们的 是第t轮的训练模型， 是t轮前我们的训练结果， 是新加入的函数（新加入的一棵树）

那么我们怎么样决定一个新加入的树（函数 ），这个函数就是我们上面提到的我们的参数，即如何选择一个参数来优化我们的模型，当然从优化目标函数中找。

上述目标函数还是很复杂，于是作者引入了泰勒展开式来替换损失函数。

类比泰勒展开式的

在我们的目标函数中损失函数 相当于函数

所以我们可以得到我们的目标函数带入泰勒展开之后的结果是：

这里面 是我们前t-1轮的对 预测和 的目标的损失，这是一个常数项。因为我们优化的是第t轮，研究怎么选择第t轮需要加进去的树，所以前面的 我们都可以看作是一个常量。

给目标函数对权重求偏导，得到一个能够使目标函数最小的权重，把这个权重代回到目标函数中，这个回代结果就是 求解后的最小目标函数值 。

是一个叶子结点上的 每一个样本的梯度值，同理理解

从我们的损失函数 ，说起，看我们如何定义这个 ，不如这里我们以简单的 为例子：

针对我们的平方差损失函数来说， 就是如下式子：

其中 项也就是我们常说的残差项。

从例子中理解各个参数的含义，

比如叶子结点1代表的权重（分数）是+2，叶子结点2对应的是+0.1，叶子结点3对应是-1

然后看我们的正则化项，其中T代表叶子结点的数目， 从上面的例子可以很容易的计算得到我们的正则化结果。

我们定义： 就是第i个数据属于第j个叶子结点。

然后我们将属于同一个叶子结点的数据放入一个group里面得到

也就是将从各个样本上的遍历，映射到了对叶子结点的遍历（叶子结点里可能包含多个样本）

重新定义G 和H ，也将其从单个样本上的遍历，映射到对叶子结点的遍历。

其中的 是来评价一棵树的结构是否很好，分数越小，结构越好。

但是仍然有无数颗树可以进行选择，那么我们如何选择才能保证最优化呢？

从常数0开始，我们选择一个树加入，每一次尝试去对已有的叶子加入一个分割。

然后我们来计算分割后的结构分数（左子树+右子树）与我们不进行分割的结构分数进行做差，同时还要减去因为分割引入的结构复杂度。

也可以很好的处理非数值型特征，并且不需要将类别特征（离散的）和数值型特征（连续的）分开进行处理。

我们可以通过one-hot编码将离散的特征类别映射到数值型。

如果类别特别多，向量会非常稀疏，但是这个算法也很擅长处理稀疏的数据。

设置最大树深度，然后递归的去剪裁所有叶子节点出现负的Gain的分裂情况

更细节的问题是，我们不会每个树做到最优化，这样容易过拟合，我们赋予一个参数，来控制每次的优化（不让优化效果太好），这样留下更多的优化空间给后边的树。

分类回归树的集成算法可以用来做回归，分类，ranking等等，这取决于我们的损失函数如何定义。

（1）objective [ default=reg:linear ] 定义学习任务及相应的学习目标，可选的目标函数如下：

（2）’eval_metric’ The choices are listed below，评估指标:

（3）lambda [default=0] L2 正则的惩罚系数

（4）alpha [default=0] L1 正则的惩罚系数

（5）lambda_bias 在偏置上的L2正则。缺省值为0（在L1上没有偏置项的正则，因为L1时偏置不重要）

（6）eta [default=0.3]

为了防止过拟合，更新过程中用到的收缩步长。在每次提升计算之后，会直接获得新特征的权重。 eta通过缩减特征的权重使提升计算过程更加保守。缺省值为0.3

取值范围为：[0,1]

（7）max_depth [default=6] 数的最大深度。缺省值为6 ，取值范围为：[1,∞]

（8）min_child_weight [default=1]

孩子节点中最小的样本权重和。如果一个叶子节点的样本权重和小于min_child_weight则拆分过程结束。在现行回归模型中，这个参数是指建立每个模型所需要的最小样本数。该参数越大算法越保守。

取值范围为: [0,∞]

xgboost适用场景：分类回归问题都可以。优缺点如下：

1）在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，xgboost实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。

2）xgboost考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率，paper提到50倍。

3）特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然boosting算法迭代必须串行，但是在处理每个特征列时可以做到并行。

4）按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer，然后再计算，提高算法的效率。

5）xgboost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。

xgboost是时下热门的机器学习算法，在面试和竞赛中出现的频率非常高，但网上却没有一篇能够完全讲清楚的文章，因此，本文旨在用尽量少的公式，将xgboost讲清楚，明白，透彻。

xgboost是Boost（提升）算法家族中的一员，Boost根本思想在于通过多个简单的弱分类器，构建出准确率很高的强分类器。简单地来说，Boost（提升）就是指每一步我都产生一个弱预测模型，然后加权累加到总模型中，可以用于回归和分类问题。如果每一步的弱预测模型生成都是依据损失函数的梯度方向，则称之为梯度提升(Gradient boosting)，这样若干步以后就可以达到逼近损失函数局部最小值的目标。

boosting集成学习，由多个相关联的决策树联合决策，什么叫相关联，举个例子，有一个样本[数据->标签]是[(2，4，5)->4]，第一棵决策树用这个样本训练得预测为3.3，那么第二棵决策树训练时的输入，这个样本就变成了[(2，4，5)->0.7]，也就是说，下一棵决策树输入样本会与前面决策树的训练和预测相关。其中，0.7是模型预测和样本标记的差，称为残差。我们每次要学习的目标是上次学习的残差，直到残差小到满足我们的要求或其他终止条件。这个残差就是一个加预测值后能得真实值的累加量。

上面的例子，如果第二次直接预测得到0.7，并不一定好，因为每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。换句话说我们思想不完全信任每一个棵残差树，我们认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，只有通过多学几棵树才能弥补不足。

与之对比的是random forest（随机森林）算法，各个决策树是独立的、每个决策树在样本堆里随机选一批样本，随机选一批特征进行独立训练，各个决策树之间没有啥毛线关系。

xgboost本质上就是k个CART树，k是一个正整数。

CART树也叫分类与回归树，是一种决策树，既能做分类任务也能做回归任务。分类树的输出是样本的类别， 回归树的输出是一个实数（连续型变量）。

回归树的运行流程与分类树基本类似，但有以下两点不同之处：

对于回归问题，我们常用的损失函数是MSE（均方误差），即：

对于分类问题，我们常用的损失函数是对数损失函数：

前面提到，xgboost是具有k个CART树的集成学习算法，那么问题来了，我们应该怎么得到这k个树，k又是多少呢？（注意：不是随机得到k个树，是一个一个来，后一个依赖于前一个）

在我们一颗接着一颗树的构建过程中，我们的目标是：预测误差尽量小，叶子节点尽量少，节点数值尽量不极端。第一个目标很清晰，而第二个目标的原因是因为树的复杂度越低，泛化能力越强，在后面我们会知道叶子节点数量是树的复杂度计算中的一个考量，叶子节点数越多，树越复杂。节点数值尽量不极端指的是某棵树对一个样本的预测值相对于其它树对这个样本的预测值相差比较大，比如某个样本label数值为4，那么第一个回归树预测3，第二个预测为1；另外一组回归树，一个预测2，一个预测2，那么倾向后一种，为什么呢？前一种情况，第一棵树学的太多，太接近4，也就意味着有较大的过拟合的风险。

生成决策树：决策树算法相信大家都比较熟悉了，还不清楚的读者请先了解一下决策树算法。在xgboost中，生成决策树时，划分属性的方式如下：

为了更好的解释xgboost算法，我们必须定义一些公式了。

首先是模型的预测：

模型的目标函数：

综上，我们可以将损失函数用以下函数表示：

但是，损失函数一定是二次函数吗？如果不是，就泰勒展开成二次，简单粗暴。

它背后的思路就是在损失函数上执行梯度下降，然后用基学习器对其进行拟合。当梯度为负时，我们称它为伪残差，因为它们依然能间接帮助我们最小化目标函数。

建树的过程中，在以下情况下完成这棵树的创建：

（1）当引入的分裂带来的增益小于一个阀值的时候，我们可以剪掉这个分裂，所以并不是每一次分裂loss function整体都会增加的，有点预剪枝的意思。

（2）当树达到最大深度时则停止建立决策树，设置一个超参数max_depth，树太深很容易出现的情况学习局部样本，过拟合。

（3）当样本权重和小于设定阈值时则停止建树。

1）将树模型的复杂度加入到正则项中，来避免过拟合，因此泛化性能会好于GBDT。XGBoost的正则项会惩罚具有多个叶子节点的树结构。

2）损失函数是用泰勒展开式展开的，同时用到了一阶导和二阶导，可以加快优化速度。

3）和GBDT只支持CART作为基分类器之外，还支持线性分类器，在使用线性分类器的时候可以使用L1，L2正则化。

4）引进了特征子采样，像RandomForest那样，这种方法既能降低过拟合，还能减少计算。

5）在寻找最佳分割点时，考虑到传统的贪心算法效率较低，实现了一种近似贪心算法，用来加速和减小内存消耗，除此之外还考虑了稀疏数据集和缺失值的处理，对于特征的值有缺失的样本，XGBoost依然能自动找到其要分裂的方向。

6）XGBoost支持并行处理，XGBoost的并行不是在模型上的并行，而是在特征上的并行，将特征列排序后以block的形式存储在内存中，在后面的迭代中重复使用这个结构。这个block也使得并行化成为了可能，其次在进行节点分裂时，计算每个特征的增益，最终选择增益最大的那个特征去做分割，那么各个特征的增益计算就可以开多线程进行。

---