赞
踩
标签(空格分隔): 机器学习 集成学习 GBM GBDT XGBoost
梯度提升(Gradient boosting)是一种用于回归、分类和排序任务的机器学习技术1,属于Boosting算法族的一部分。Boosting是一族可将弱学习器提升为强学习器的算法,属于集成学习(ensemble learning)的范畴。Boosting方法基于这样一种思想:对于一个复杂任务来说,将多个专家的判断进行适当的综合所得出的判断,要比其中任何一个专家单独的判断要好。通俗地说,就是“三个臭皮匠顶个诸葛亮”的道理。梯度提升同其他boosting方法一样,通过集成(ensemble)多个弱学习器,通常是决策树,来构建最终的预测模型。
Boosting、bagging和stacking是集成学习的三种主要方法。不同于bagging方法,boosting方法通过分步迭代(stage-wise)的方式来构建模型,在迭代的每一步构建的弱学习器都是为了弥补已有模型的不足。Boosting族算法的著名代表是AdaBoost,AdaBoost算法通过给已有模型预测错误的样本更高的权重,使得先前的学习器做错的训练样本在后续受到更多的关注的方式来弥补已有模型的不足。与AdaBoost算法不同,梯度提升方法在迭代的每一步构建一个能够沿着梯度最陡的方向降低损失(steepest-descent)的学习器来弥补已有模型的不足。经典的AdaBoost算法只能处理采用指数损失函数的二分类学习任务2,而梯度提升方法通过设置不同的可微损失函数可以处理各类学习任务(多分类、回归、Ranking等),应用范围大大扩展。另一方面,AdaBoost算法对异常点(outlier)比较敏感,而梯度提升算法通过引入bagging思想、加入正则项等方法能够有效地抵御训练数据中的噪音,具有更好的健壮性。这也是为什么梯度提升算法(尤其是采用决策树作为弱学习器的GBDT算法)如此流行的原因,有种观点认为GBDT是性能最好的机器学习算法,这当然有点过于激进又固步自封的味道,但通常各类机器学习算法比赛的赢家们都非常青睐GBDT算法,由此可见该算法的实力不可小觑。
基于梯度提升算法的学习器叫做GBM(Gradient Boosting Machine)。理论上,GBM可以选择各种不同的学习算法作为基学习器。现实中,用得最多的基学习器是决策树。为什么梯度提升方法倾向于选择决策树(通常是CART树)作为基学习器呢?这与决策树算法自身的优点有很大的关系。决策树可以认为是if-then规则的集合,易于理解,可解释性强,预测速度快。同时,决策树算法相比于其他的算法需要更少的特征工程,比如可以不用做特征标准化,可以很好的处理字段缺失的数据,也可以不用关心特征间是否相互依赖等。决策树能够自动组合多个特征,它可以毫无压力地处理特征间的交互关系并且是非参数化的,因此你不必担心异常值或者数据是否线性可分(举个例子,决策树能轻松处理好类别A在某个特征维度x的末端,类别B在中间,然后类别A又出现在特征维度x前端的情况)。不过,单独使用决策树算法时,有容易过拟合缺点。所幸的是,通过各种方法,抑制决策树的复杂性,降低单颗决策树的拟合能力,再通过梯度提升的方法集成多个决策树,最终能够很好的解决过拟合的问题。由此可见,梯度提升方法和决策树学习算法可以互相取长补短,是一对完美的搭档。至于抑制单颗决策树的复杂度的方法有很多,比如限制树的最大深度、限制叶子节点的最少样本数量、限制节点分裂时的最少样本数量、吸收bagging的思想对训练样本采样(subsample),在学习单颗决策树时只使用一部分训练样本、借鉴随机森林的思路在学习单颗决策树时只采样一部分特征、在目标函数中添加正则项惩罚复杂的树结构等。现在主流的GBDT算法实现中这些方法基本上都有实现,因此GBDT算法的超参数还是比较多的,应用过程中需要精心调参,并用交叉验证的方法选择最佳参数。
本文对GBDT算法原理进行介绍,从机器学习的关键元素出发,一步一步推导出GBDT算法背后的理论基础,读者可以从这个过程中了解到GBDT算法的来龙去脉。对于该算法的工程实现,本文也有较好的指导意义,实际上对机器学习关键概念元素的区分对应了软件工程中的“开放封闭原则”的思想,基于此思想的实现将会具有很好的模块独立性和扩展性。
先复习下监督学习的关键概念:模型(model)、参数(parameters)、目标函数(objective function)
模型就是所要学习的条件概率分布或者决策函数,它决定了在给定特征向量
参数就是我们要从数据中学习得到的内容。模型通常是由一个参数向量决定的函数。例如,线性模型的参数可以表示为:
目标函数通常定义为如下形式:
目标函数之所以定义为损失函数和正则项两部分,是为了尽可能平衡模型的偏差和方差(Bias Variance Trade-off)。最小化目标函数意味着同时最小化损失函数和正则项,损失函数最小化表明模型能够较好的拟合训练数据,一般也预示着模型能够较好地拟合真实数据(groud true);另一方面,对正则项的优化鼓励算法学习到较简单的模型,简单模型一般在测试样本上的预测结果比较稳定、方差较小(奥坎姆剃刀原则)。也就是说,优化损失函数尽量使模型走出欠拟合的状态,优化正则项尽量使模型避免过拟合。
从概念上区分模型、参数和目标函数给学习算法的工程实现带来了益处,使得机器学习的各个组成部分之间耦合尽量松散。
GBDT算法可以看成是由K棵树组成的加法模型:
上述加法模型的目标函数定义为:
如何来学习加法模型呢?
解这一优化问题,可以用前向分布算法(forward stagewise algorithm)。因为学习的是加法模型,如果能够从前往后,每一步只学习一个基函数及其系数(结构),逐步逼近优化目标函数,那么就可以简化复杂度。这一学习过程称之为Boosting。具体地,我们从一个常量预测开始,每次学习一个新的函数,过程如下:
那么,在每一步如何决定哪一个函数
在第
举例说明,假设损失函数为平方损失(square loss),则目标函数为:
泰勒公式:设
n 是一个正整数,如果定义在一个包含a 的区间上的函数f 在a 点处n+1 次可导,那么对于这个区间上的任意x 都有:f(x)=∑n=0Nf(n)(a)n!(x−a)n+Rn(x) ,其中的多项式称为函数在a 处的泰勒展开式,Rn(x) 是泰勒公式的余项且是(x−a)n 的高阶无穷小。—-维基百科
根据泰勒公式把函数
由于函数中的常量在函数最小化的过程中不起作用,因此我们可以从等式(4)中移除掉常量项,得:
由于要学习的函数仅仅依赖于目标函数,从等式(5)可以看出只需为学习任务定义好损失函数,并为每个训练样本计算出损失函数的一阶导数和二阶导数,通过在训练样本集上最小化等式(5)即可求得每步要学习的函数
一颗生成好的决策树,假设其叶子节点个数为
决策树的复杂度可以由正则项
定义集合
综上,为了便于理解,单颗决策树的学习过程可以大致描述为:
1. 枚举所有可能的树结构
2. 用等式(8)为每个
3. 根据上一步的结果,找到最佳的树结构,用等式(7)为树的每个叶子节点计算预测值
然而,可能的树结构数量是无穷的,所以实际上我们不可能枚举所有可能的树结构。通常情况下,我们采用贪心策略来生成决策树的每个节点。
1. 从深度为0的树开始,对每个叶节点枚举所有的可用特征
2. 针对每个特征,把属于该节点的训练样本根据该特征值升序排列,通过线性扫描的方式来决定该特征的最佳分裂点,并记录该特征的最大收益(采用最佳分裂点时的收益)
3. 选择收益最大的特征作为分裂特征,用该特征的最佳分裂点作为分裂位置,把该节点生长出左右两个新的叶节点,并为每个新节点关联对应的样本集
4. 回到第1步,递归执行到满足特定条件为止
在上述算法的第二步,样本排序的时间复杂度为
如何计算每次分裂的收益呢?假设当前节点记为
最后,总结一下GBDT的学习算法:
1. 算法每次迭代生成一颗新的决策树
2. 在每次迭代开始之前,计算损失函数在每个训练样本点的一阶导数
3. 通过贪心策略生成新的决策树,通过等式(7)计算每个叶节点对应的预测值
4. 把新生成的决策树
通常在第四步,我们把模型更新公式替换为:
[1] Gradient Boosting 的更多内容
[2] XGBoost是一个优秀的GBDT开源软件库,有多种语言接口
[3] Pyramid是一个基于Java语言的机器学习库,里面也有GBDT算法的介绍和实现
[4] Friedman的论文《Greedy function approximation: a gradient boosting machine》是比较早的GBDT算法文献,但是比较晦涩难懂,不适合初学者,高阶选手可以进一步学习
[5] “A Gentle Introduction to Gradient Boosting“是关于Gradient Boosting的一个通俗易懂的解释,比较适合初学者或者是已经对GBDT算法原理印象不深的从业者
[6] 关于GBDT算法调参的经验和技巧可以参考这两篇博文:《GBM调参指南》、
《XGBoost调参指南》,作者使用的算法实现工具来自于著名的Python机器学习工具scikit-learn
[7] GBDT算法在搜索引擎排序中的应用可以查看这篇论文《Web-Search Ranking with Initialized Gradient Boosted Regression Trees 》,这篇论文提出了一个非常有意思的方法,用一个已经训练好的随机森林模型作为GBDT算法的初始化,再用GBDT算法优化最终的模型,取得了很好的效果
备注:CSDN对公式的渲染总有一个竖线在后面,影响了美观。本文最初发布在作业部落,原文链接:https://www.zybuluo.com/yxd/note/611571
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。