机器学习笔记(13)-XGBoost

机器学习笔记(13)-XGBoost

XGBoost陈天奇等人开发的一个开源机器学习项目，高效地实现了GBDT算法并进行了算法和工程上的许多改进，被广泛应用在Kaggle竞赛及其他许多机器学习竞赛中并取得了不错的成绩。可以说在深度学习热门前和当年SVM一样属于比赛中的明星算法了。

Bagging和Boosting

介绍XGBoost之前，首先简单介绍下Bagging和Boosting的区别，我们知道这两个都是集成学习的框架，主要针对一系列弱分类器，使它们在集成后成为一个效果比较好的强分类器。比如随机森林就是一个采用bagging的学习算法，而我们这次介绍的XGBoost就是一个Boosting算法。

Bagging：是由多个过拟合的弱分类器组合而成，通过每个弱分类器的权重来判断结果。通俗的理解就是Bagging算法是由多个领域专家（弱分类器）组成，单个专家只在该领域（数据分布）下时预测准确率高，当符合某个领域时，会挑选出该领域的专家（权重最高）来判断（加权组合）。

Boosting：与Bagging相同的时它也是由多个弱分类器组成，不同点在于每个弱分类器都是欠拟合的，同样是协同所有弱分类器一起判断结果。

XGBoost顾名思义，采用的是Boosting的思想，训练多棵树模型，来组合判断结果，但是不同于随机森林，它的每一个分类器采用残差的方式来训练每棵树，使得每棵树的结果之和为预测结果，并且在每棵树的建立算法上也和传统的决策树分枝算法（C4.5）不同。

举个例子就是，比如有一个预测样本的值为10：

1. 训练第一个弱分类器预测的结果为6，得到残差为：10-6=4；
2. 接下来训练第二个弱分类器预测的结果为2，得到残差为：4-2=2；
3. 再训练第三个弱分类器预测的结果为1，得到残差为：2-1=1；
4. 最后训练第四个弱分类器预测的结果为1；
5. 我们把四个弱分类器的预测结果累加就是我们真实的预测值10。

这就是XGBoost利用Boosting算法来集成的强学习器。

XGBoost算法推导

上一节讲了XGBoost采用了Boosting通过残差的方式来求和拟合结果。XGBoost的每个弱分类器都是一棵决策树，分枝算法先放到之后再说，通过训练一棵树来预测结果，得到残差后再训练第二棵树，依此类推，训练若干个弱分类器后，模型收敛完成训练。

这就是XGBoost的算法思想，真的非常简单，下面我们来推导过程。

残差损失

之前说了XGBoost是根据每棵树的预测结果和样本真实值的残差来迭代优化的，假设有：

1. 数据样本(X={(x_{1},y_{1}),(x_{2},y_{2}),cdots,(x_{n},y_{n})}^N)，其中(x_{i}inmathbb{R}^p,y_{i}inmathbb{R})；
2. 模型总共需要构建K棵树，每棵树预测值表示为：(f_{k}(x_{i}))

于是我们得到单个样本的预测值为：

[hat y_{i}=sum_{k=1}^{K}f_{k}(x_{i}) ]

那么我们就可以进一步得到目标函数：

[Obj=sum_{i=1}^{N}mathcal{L}(y_{i},hat y_{i})+sum_{k=1}^{K}Omega(f_{k}) ]

其中(mathcal{L}(y_{i},hat y_{i}))为样本真实值和预测值的损失函数，(Omega(f_{k}))为每棵树的复杂度（可以理解为正则项）。

事实上，对于一棵树，复杂度一般采用以下几项来表示：

1. 树的深度
2. 叶节点个数
3. 叶节点值

树的深度很好理解，树越深表示节点越多，也就是复杂度越高，越容易过拟合；

叶节点个数和深度表示的含义基本一样；

叶节点值表示如果我的预测值是100，原来每棵树叶节点值为50，那么我用两棵树就可以完成，当我们设置每棵树的叶节点值不超过10，那么我们至少需要10棵树才能拟合真实值。而树越多，越不容易过拟合。

训练第k棵树

有了目标函数后，我们需要进一步来简化问题，XGBoost是根据我们每次预测值和真实值的残差来提升模型的，也就是假设我们已知前k-1棵树后，我们通过模型迭代训练来得到第k棵树，依次把所有k棵树全部训练完成的。

于是我们令：

1. 第0棵树：(hat y^{(0)}_{i}=0)；
2. 第1棵树：(hat y^{(1)}_{i}=f_{1}(x_{i})=hat y^{(0)}_{i}+f_{1}(x_{i}))；
3. 第2棵树：(hat y^{(2)}_{i}=f_{1}(x_{i})+f_{2}(x_{i})=hat y^{(1)}_{i}+f_{2}(x_{i}))；
4. 第k棵树：(hat y^{(k)}_{i}=sum_{k=1}^{K}f_{k}(x_{i})=hat y^{(k-1)}_{i}+f_{k}(x_{i}))；

我们把结论代入到目标函数中，就得到：

[egin{aligned} Obj&=sum_{i=1}^{N}mathcal{L}(y_{i},hat y_{i})+sum_{k=1}^{K}Omega(f_{k})\ &=sum_{i=1}^{N}mathcal{L}(y_{i},hat y^{(k-1)}_{i}+f_{k}(x_{i}))+sum_{j=1}^{K-1}Omega(f_{j})+Omega(f_{k}) end{aligned} ]

观察上式，我们因为已知前k-1棵树，求第k棵树，所以前k-1棵树的项都应该是已知常数，我们令：

1. (hat y^{(k-1)}_{i}=C_{1})
2. (sum_{j=1}^{K-1}Omega(f_{j})=C_{2})

得到：

[Obj=sum_{i=1}^{N}mathcal{L}(y_{i},C_{1}+f_{k}(x_{i}))+C_{2}+Omega(f_{k}) ]

泰勒级数

大学高等数学课中，我们知道当一个函数为连续函数时（函数处处可导），我们可以采用泰勒展开式近似该函数，XGBoost正是采用了泰勒展开式中的二阶导数来近似表示函数的。引用下百度百科：

事实上当到二阶导数时，已经非常接近原函数了。于是有二阶泰勒展开式（Taylor Expansion）近似：

[f(x+Delta x)=f(x)+f'(x)cdot Delta x+frac{1}{2}f''(x)cdot Delta x^2 ]

XGBoost利用了该思想，它把前k-1棵树预测的值看成时(f(x))，加上第k棵树预测的值看成(f(x+Delta x))。

也就是：

[hat y^{(k-1)}_{i}=C_{1} ightarrow f(x)\ f_{k}(x) ightarrow Delta x ]

代入到目标函数也就是：

[egin{aligned} Obj &=sum_{i=1}^{N}mathcal{L}(y_{i},C_{1}+f_{k}(x_{i}))+C_{2}+Omega(f_{k})\ &=sum_{i=1}^{N}[mathcal{L}(y_{i},C_{1})+frac{partial mathcal{L}(y_{i},C_{1})}{partial hat y^{(k-1)}_{i}}f_{k}(x_{i})+frac{partial^2 mathcal{L}(y_{i},C_{1})}{partial hat y^{(k-1)}_{i}}cdot frac{1}{2}cdot f^2_{k}(x_{i})]+C_{2}+Omega(f_{k}) end{aligned} ]

上式同样有几个已知常数项，我们简化一下令：

[l_{i}=mathcal{L}(y_{i},C_{1})\ g_{i}=frac{partial mathcal{L}(y_{i},C_{1})}{partial hat y^{(k-1)}_{i}}\ h_{i}=frac{partial^2 mathcal{L}(y_{i},C_{1})}{partial hat y^{(k-1)}_{i}}cdot frac{1}{2} ]

目标函数再次简化形式：

[Obj=sum_{i=1}^{N}[l_{i}+g_{i}f_{k}(x_{i})+h_{i}f^2_{k}(x_{i})]+C_{2}+Omega(f_{k}) ]

上式目标函数，我们要令该函数的值最小，只保留和(f_{k})有关的项，求得：(argmin;Obj)：

[argmin;Obj=argmin;sum_{i=1}^{N}[g_{i}f_{k}(x_{i})+h_{i}f^2_{k}(x_{i})]+Omega(f_{k}) ]

定义树的表示

下面我们要想一个办法来表示我们的(f_{k}(x_{i}))和(Omega(f_{k}))，最好可以用一种统一的参数形式来表示。

现在考虑在一棵树中，我们尝试使用样本在树中的叶节点位置和叶节点的值来定义(f_{k}(x_{i}))和(Omega(f_{k}))。

我们令：

1. (I)：叶节点总个数
2. (q_{x_{i}})：每个样本(x_{i})在树中的位置为
3. (W_{q_{x_{i}}})：每个样本在叶节点上的值
4. (gamma T)：其中(T)表示树的高度，(gamma)是超参数，用于调节高度的权重

先来看复杂度项(Omega(f_{k}))，我们采用树的高度加上叶节点的值作为复杂度项，就有：

[Omega(f_{k})=gamma T+lambdasum_{i=1}^{I}frac{1}{2}W^2_{i} ]

其中(lambda)是叶节点的值的超参数，同样用于控制权重。定义每个叶节点的值的平方作为复杂度项。

再来看树的预测函数(f_{k}(x_{i}))：

[f_{k}(x_{i})=W_{q_{x_{i}}} ]

我们这么幸苦地采用这个形式来改变形式，其实核心思想就是原本目标函数是通过数据样本的个数来表示的，我们现在想采用数的叶节点个数来表示目标函数，其中多个数据样本可能落在同一个叶子节点上。

也就是说：所有的N个数据样本分布在(I)个叶节点上，每个叶节点中假设有M个样本，即：

[sum_{i=1}^{N}g_{i}W_{q_{x_{i}}}=sum_{j=1}^{I}(sum_{m=1}^{M}g_{m})W_{j}\ sum_{i=1}^{N}h_{i}W^2_{q_{x_{i}}}=sum_{j=1}^{I}(sum_{m=1}^{M}h_{m})W^2_{j} ]

代入到目标函数中得到：

[egin{aligned} argmin;Obj &=argmin;sum_{i=1}^{N}[g_{i}f_{k}(x_{i})+h_{i}f^2_{k}(x_{i})]+Omega(f_{k})\ &=underset{W}{argmin};sum_{j=1}^{I}[(sum_{i=1}^{M}g_{i})W_{j}+(sum_{i=1}^{M}h_{i})W^2_{j}]+gamma T+lambdasum_{i=1}^{I}frac{1}{2}W^2_{i}\ &=underset{W}{argmin};sum_{j=1}^{I}[(sum_{i=1}^{M}g_{i})W_{j}+(sum_{i=1}^{M}h_{i}+frac{1}{2}lambda)W^2_{j}]+gamma T end{aligned} ]

我们再把常数项简化表示，令：

[sum_{i=1}^{M}g_{i}=G\ sum_{i=1}^{M}h_{i}=frac{1}{2}H ]

代入得：

[argmin;Obj=underset{W}{argmin};sum_{j=1}^{I}[G_{j}W_{j}+frac{1}{2}(H_{j}+lambda)W^2_{j}]+gamma T ]

对(W)求导得：

[sum_{j=1}^{I}[G_{j}+(H_{j}+lambda)W_{j}]=0 ]

[W_{j}^*=-frac{G_{j}}{H_{j}+lambda} ]

把最优解代入目标函数得到：

[Obj^*=sum_{j=1}^{I}-frac{G^2_{j}}{H_{j}+lambda}+gamma T ]

这里我们就得到了我们要得最小化目标函数值最优解。

每棵树得构建

前面我们其实是得到了一个结论：当我们已知前k-1棵树预测值时，可以很方便地计算出第k棵树预测值。现在来思考每棵树的构建方式。

前面的章节我已经介绍过决策树的构建流程，依赖于分枝算法，我们以信息增益（ID3）为例回顾下流程：

[Gain(D,a)=Ent(D)-sum_{V=1}^{V}frac{|D^v|}{|D|}Ent(D^v) ]

通过原来的信息熵减去分枝后的熵就是信息增益，我们需要求它的最大值作为分枝点。XGBoost也是这个思想，不过采用的不是信息增益，而是我们之前的目标函数(Obj^*)最优解。

假设数据集为：

1. 数据集(D={(x_{1},y_{1}),(x_{2},y_{2}),cdots,(x_{n},y_{n})})，
2. 属性集A=({a_{1},a_{2},cdots,a_{p}})其中每个数据样本(x_{i})有p个属性

[a^*=underset{ain A}{argmax};Obj^*_{old}-Obj^*_{new} ]

构造流程和决策树一样，只是分枝算法进行了替换。

总结

可以看到XGBoost算法主要依赖：

1. 利用Boost残差的思想构造多个若分类器逐步迭代优化来逐渐逼近目标值；
2. 采用泰勒二阶展开式来近似弱分类器；
3. 利用已知前k-1棵树，可以计算第k棵树的思想，作为树的分枝算法来建树。

最后说一下如果是分类问题的话，那么拟合的就是概率值，也就是要把预测值和真实值转换为类别的概率，迭代过程就是让预测概率不断接近真实概率。将(mathcal{L}(y_{i},hat y_{i}))转化为对数损失函数来做，回归就采用最小二乘。