机器学习算法系列(8)：XgBoost

在数据建模中，经常采⽤用Boosting⽅方法通过将成百上千个分类准确率较低的树模型组合起来，成为⼀一个准确率很⾼高的预测模型。这个模型会不不断地迭代，每次迭代就⽣生成⼀一颗新的树。但在数据集较复杂的时候，可能需要⼏几千次迭代运算，这将造成巨⼤大的计算瓶颈。针对这个问题。华盛顿⼤大学的陈天奇博⼠士开发的XGBoost（eXtremeGradientBoosting）基于C++通过多线程实现了了回归树的并⾏行行构建，并在原有GradientBoosting算法基础上加以改进，从⽽而极⼤大地提升了了模型训练速度和预测精度。在Kaggle的希格斯⼦子信号识别竞赛，XGBoost因为出众的效率与较⾼高的预测准确度在⽐比赛论坛中引起了了参赛选⼿手的⼴广泛关注，在1700多⽀支队伍的激烈烈竞争中占有⼀一席之地。随着它在Kaggle社区知名度的提⾼高，最近也有队伍借助XGBoost在⽐比赛中夺得第⼀一。其次，因为它的效果好，计算复杂度不不⾼高，也在⼯工业界中有⼤大量量的应⽤用。因为BoostingTree本身是⼀一种有监督学习算法，要讲BoostingTree，先从监督学习讲起。在监督学习中有⼏几个逻辑上的重要组成部件，粗略略地可以分为：模型、参数、⽬目标函数和优化算法。模型指的是给定输⼊入xi如何去预测输出yi。我们⽐比较常⻅见的模型如线性模型（包括线性回归和LogisticRegression）采⽤用线性加和的⽅方式进⾏行行预测ˆyi=∑jwjxij这⾥里里的预测值y可以由不不同的解释，⽐比如我们可以把它作为回归⽬目标的输出，或者进⾏行行sigmoid变换得到概率（即⽤用11+e−ˆyi来预测正例例的概率），或者作为排序的指标等。⽽而⼀一个线性模型根据y的解释不不通（以及设计对应的⽬目标函数）⽤用到回归、分类或者排序等场景。参数就是我们根据模型要从数据⾥里里头学习的东⻄西，⽐比如线性模型中的线性系数：机器器学习算法系列列（8）：XgBoost⼀一、XGBoost简介⼆二、监督学习的三要素2.1模型2.2参数Θ=wj|j=1,2,···,d模型和参数本身指定了了给定输⼊入我们如何预测，但是没有告诉我们如何去寻找⼀一个⽐比较好的参数，这个时候就需要⽬目标函数函数登场了了。⼀一般地⽬目标函数包含两项：⼀一项是损失函数，它说明了了我们的模型有多拟合数据；另⼀一项是正则化项，它惩罚了了复杂模型。1）L(Θ)：损失函数L=∑ni=1lyi,ˆyi，常⻅见的损失函数有：平⽅方损失：lyi,ˆyi=yi−ˆyi2Logistic损失：lyi,ˆyi=yiln1+e−yi+1−yiln1+eyi2）Ω(Θ)：正则化项，之所以要引⼊入它是因为我们的⽬目标是希望⽣生成的模型能准确地预测新的样本（即应⽤用于测试数据集），⽽而不不是简单地拟合训练集的结果（这样会导致过拟合）。所以需要在保证模型“简单”的基础上最⼩小化训练误差，这样得到的参数才具有好的泛化性能。⽽而正则化项就是⽤用于惩罚复杂模型，避免模型过分拟合训练数据。常⽤用的正则有L1正则与L2正则L1正则（lasso）：Ω(w)=λ||w||1L2正则：Ω(w)=λ||w||2这样⽬目标函数的设计来⾃自于统计学习⾥里里⾯面的⼀一个重要概念叫做Bias-variancetradeoff（偏差-⽅方差权衡），⽐比较感性的理理解，Bias可以理理解为假设我们有⽆无限多数据的时候，可以训练出最好的模型所拿到的误差。⽽而Variance是因为我们只有有限数据，其中随机性带来的误差。⽬目标中误差函数⿎鼓励我们的模型尽量量去拟合训练数据，这样相对来说最后的模型会有⽐比较少的Bias。⽽而正则化项则⿎鼓励更更加简单的模型。因为当模型简单之后，有限数据拟合出来结果的随机性⽐比较⼩小，不不容易易过拟合，使得最后模型的预测更更加稳定。上⾯面三个部分包含了了机器器学习的主要成分，也是机器器学习⼯工具划分模型⽐比较有效的办法。其实这⼏几部分之外，还有⼀一个优化算法，就是给定⽬目标函数之后怎么学的问题。有时候我们往往只知道“优化算法”，⽽而没有仔细考虑⽬目标函数的设计问题，⽐比如常⻅见的例例⼦子如决策树的学习算法的每{}2.3⽬目标函数：误差函数+正则化项()()()()()()()2.4优化算法⼀一步去优化基尼系数，然后剪枝，但是没有考虑到后⾯面的⽬目标是什什么。⽽而这些启发式优化⽅方法背后往往隐含了了⼀一个⽬目标函数，理理解了了⽬目标函数本身也有利利于我们设计相应的学习算法。在介绍XGBoost之前，⾸首先得了了解⼀一下回归树和树集成的概念，其实在AdaBoost算法中已经详细讲述过这⼀一部分了了。BoostingTree最基本的组成部分叫做回归树（regressiontree），下⾯面就是⼀一个回归树的例例⼦子。它把输⼊入根据输⼊入的属性分配到各个叶⼦子节点，⽽而每个叶⼦子节点上⾯面都会有⼀一个实数分数。具体地，下图给出了了⼀一个判断⽤用户是否会喜欢电脑游戏的回归树模型，每个树叶的得分对应了了该⽤用户有多可能喜欢电脑游戏（分值越⼤大可能性越⼤大）。上图中的回归树只⽤用到了了⽤用户年年龄和性别两个信息，过于简单，预测的准确性⾃自然有限。⼀一个回归树往往过于简单⽆无法有效地预测，因此⼀一个更更加强有⼒力力的模型叫做treeensemble。三、回归树与树集成3.1回归树3.2树集成在上图中使⽤用两个回归树对⽤用户是否喜欢电脑游戏进⾏行行了了预测，并将两个回归树的预测结果加和得到单个⽤用户的预测结果。在实际的预测模型建⽴立过程中，我们通过不不断地增加新的回归树，并给每个回归树赋予合适的权重，在此基础上综合不不同的回归树得分获得更更为准确的预测结果，这也就是树集成的基本思路路。在预测算法中，随机森林林和提升树都采⽤用了了树集成的⽅方法，但是在具体地模型构造和参数调整的⽅方法有所差别。在这个树集成模型中，我们可以认为参数对应了了树的结构，以及每个叶⼦子节点上⾯面的预测分数。那么我们如何来学习这些参数。在这⼀一部分，答案可能千奇百怪，但是最标准的答案始终是⼀一个：定义合理理的⽬目标函数，然后去尝试优化这个⽬目标函数。决策树学习往往充满了了启发式算法，如先优化基尼系数，然后再剪枝，限制最⼤大深度等等。其实这些启发式算法背后往往隐含了了⼀一个⽬目标函数，⽽而理理解⽬目标函数本身也有利利于我们设计学习算法。对于treeensemble，我们可以把某⼀一个迭代后集成的模型写成为：ˆyi=K∑k=1fkxi,fk∈F其中每个f是⼀一个在函数空间(F)⾥里里⾯面的函数，⽽而F对应了了所有regressiontree的集合。我们设计的⽬目标函数也需要遵循前⾯面的主要原则，包含两部分四、XGBoost的推导过程4.1XGBoost的⽬目标函数与泰勒勒展开()Obj(Θ)=n∑i=1lyi,ˆyi+K∑k=1Ωfk其中第⼀一部分是训练损失，如上⾯面所述的平⽅方损失或者LogisticLoss等，第⼆二部分是每棵树的复杂度的和。因为现在我们的参数可以认为是在⼀一个函数空间⾥里里⾯面，我们不不能采⽤用传统的如SGD之类的算法来学习我们的模型，因此我们会采⽤用⼀一种叫做additivetraining的⽅方式。即每次迭代⽣生成⼀一棵新的回归树，从⽽而使预测值不不断逼近真实值（即进⼀一步最⼩小化⽬目标函数）。每⼀一次保留留原来的模型不不变，加⼊入⼀一个新的函数f到模型⾥里里⾯面：其中ˆyi(t−1)就是前t−1轮的模型预测，ft(xi)为新t轮加⼊入的预测函数。这⾥里里⾃自然就涉及⼀一个问题：如何选择在每⼀一轮中加⼊入的f(xi)呢？答案很直接，选取的f(xi)必须使得我们的⽬目标函数尽量量最⼤大地降低（这⾥里里应⽤用到了了Boosting的基本思想，即当前的基学习器器重点关注以前所有学习器器犯错误的那些数据样本，以此来达到提升的效果）。先对⽬目标函数进⾏行行改写，表示如下：如果我们考虑平⽅方误差作为损失函数，公式可改写为：更更加⼀一般的，对于不不是平⽅方误差的情况，我们可以采⽤用如下的泰勒勒展开近似来定义⼀一个近似的⽬目标函数，⽅方便便我们进⾏行行下⼀一步的计算。()()泰勒勒展开⼀一般表达式为：⽤用泰勒勒展开来近似我们原来的⽬目标：⾸首先定义得到如果移除掉常数项，我们会发现这个⽬目标函数有⼀一个⾮非常明显的特点，它只依赖于每个数据点的在误差函数上的⼀一阶导数和⼆二阶导数。可能有⼈人会问，这个⽅方式似乎⽐比我们之前学过的决策树学习难懂。为什什么要花这么多⼒力力⽓气来做推导呢？这是因为，这样做⾸首先有理理论上的好处，它会使我们可以很清楚地理理解整个⽬目标是什什么，并且⼀一步⼀一步推导出如何进⾏行行树的学习。然后这⼀一个抽象的形式对于⼯工程商实现机器器学习⼯工具也是⾮非常有帮助的。因为它包含所有可以求到的⽬目标函数，也就是说有了了这个形式，我们写出来的代码可以⽤用来求解包括回归、分类和排序的各种问题，正式的推导可以使得机器器学习的⼯工具更更加⼀一般化。到⽬目前为⽌止我们讨论了了⽬目标函数中训练误差的部分。接下来我们讨论如何定义树的复杂度。我们先对于f的定义做⼀一下细化，把树拆分成结构部分q和叶⼦子权重部分w。其中结构部分q把输⼊入映射到叶⼦子的索引号上⾯面去，⽽而w给定了了每个索引号对应的叶⼦子分数是什什么。4.2决策树的复杂度当我们给定了了如上定义之后，我们可以定义⼀一棵树的复杂度如下。这个复杂度包含了了⼀一棵树⾥里里⾯面节点的个数，以及每个树叶⼦子节点上⾯面输出分数的L2范数平⽅方。当然这不不是唯⼀一的⼀一种定义⽅方式，不不过这⼀一定义⽅方式学习出的树效果⼀一般都⽐比较不不错。下图给出了了复杂度计算的⼀一个例例⼦子。接下来是最关键的⼀一步，在这种新的顶⼀一下，我们可以把⽬目标函数进⾏行行如下改写，其中I被定义为每个叶⼦子上⾯面样本集合Ij={i|q(xi)=j}4.3⽬目标函数的最⼩小化这⼀一⽬目标包含了了T个互相独⽴立的单变量量⼆二次函数我们可以定义那么这个⽬目标函数可以进⼀一步改写成如下的形式，假设我们已经知道树的结构q，我们可以通过这个⽬目标函数来求解出最好的w，以及最好的w对应的⽬目标函数最⼤大的增益可以观察到上式是由T个相互独⽴立的单变量量⼆二次函数再加上L1范数构成。这样的特性意味着单个树叶的权重计算与其他树叶的权重⽆无关，所以我们可以⾮非常⽅方便便计算第j个树叶的权重，以及⽬目标函数。由此，我们将⽬目标函数转换为⼀一个⼀一元⼆二次⽅方程求最⼩小值的问题（在此式中，变量量为wj，函数本质上是关于wj的⼆二次函数），略略去求解步骤，最终结果如下所示：乍⼀一看⽬目标函数的计算与回归树的结构q函数没有什什么关系，但是如果我们仔细回看⽬目标函数的构成，就会发现其中Gj和Hj的取值是由第j个树叶上数据样本所决定的。⽽而第j个树上所具有的数据样本则是由树结构q函数决定的。也就是说，⼀一旦回归树的结构q确定，那么相应的⽬目标函数就能够根据上式计算出来。那么回归树的⽣生成问题也就转换为找到⼀一个最优的树结构q，使得它具有最⼩小的⽬目标函数。计算求得的Obj代表了了当指定⼀一个树的结构的时候，⽬目标函数上⾯面最多减少多少。我们可以把它叫做结构分数（structurescore）。可以把它认为是类似于基尼系数⼀一样更更加⼀一般的对于树结构进⾏行行打分的函数。下⾯面是⼀一个具体的打分函数计算的例例⼦子，它根据决策树的预测结果得到各样本的梯度数据，然后计算出实际的结构分数。这个分数越⼩小，代表这个树的结构越好：在前⾯面分析的基础上，当寻找到最优的树结构时，我们可以不不断地枚举不不同树的结构，利利⽤用这个打分函数来寻找⼀一个最优结构的树，加⼊入到我们的模型中，然后再重复这样的操作。不不过枚举所有树结构这个操作不不太可⾏行行，在这⾥里里XGBoost采⽤用了了常⽤用的贪⼼心法，即每⼀一次尝试区队已有的叶⼦子加⼊入⼀一个分割。对于⼀一个剧透的分割⽅方案，我们可以获得的增益可以由如下公式计算得到：这个公式形式上跟ID3算法（采⽤用信息熵计算增益）或者CART算法（采⽤