GBDT 算法:原理篇

GBDT 是常用的机器学习算法之一,因其出色的特征自动组合能力和高效的运算大受欢迎。 这里简单介绍一下 GBDT 算法的原理,后续再写一个实战篇。

1、决策树的分类

决策树分为两大类,分类树和回归树。

分类树用于分类标签值,如晴天/阴天/雾/雨、用户性别、网页是否是垃圾页面;

回归树用于预测实数值,如明天的温度、用户的年龄、网页的相关程度;

两者的区别:

  • 分类树的结果不能进行加减运算,晴天 晴天没有实际意义;
  • 回归树的结果是预测一个数值,可以进行加减运算,例如 20 岁 3 岁=23 岁。
  • GBDT 中的决策树是回归树,预测结果是一个数值,在点击率预测方面常用 GBDT,例如用户点击某个内容的概率。

2、GBDT 概念

GBDT 的全称是 Gradient Boosting Decision Tree,梯度提升决策树。

要理解 GBDT,首先就要理解这个 B(Boosting)。

Boosting 是一族可将弱学习器提升为强学习器的算法,属于集成学习(ensemble learning)的范畴。Boosting 方法基于这样一种思想:对于一个复杂任务来说,将多个专家的判断进行适当的综合所得出的判断,要比其中任何一个专家单独的判断要好。通俗地说,就是"三个臭皮匠顶个诸葛亮"的道理。

基于梯度提升算法的学习器叫做 GBM(Gradient Boosting Machine)。理论上,GBM 可以选择各种不同的学习算法作为基学习器。GBDT 实际上是 GBM 的一种情况。

为什么梯度提升方法倾向于选择决策树作为基学习器呢?(也就是 GB 为什么要和 DT 结合,形成 GBDT) 决策树可以认为是 if-then 规则的集合,易于理解,可解释性强,预测速度快。同时,决策树算法相比于其他的算法需要更少的特征工程,比如可以不用做特征标准化,可以很好的处理字段缺失的数据,也可以不用关心特征间是否相互依赖等。决策树能够自动组合多个特征。

不过,单独使用决策树算法时,有容易过拟合缺点。所幸的是,通过各种方法,抑制决策树的复杂性,降低单颗决策树的拟合能力,再通过梯度提升的方法集成多个决策树,最终能够很好的解决过拟合的问题。由此可见,梯度提升方法和决策树学习算法可以互相取长补短,是一对完美的搭档。

至于抑制单颗决策树的复杂度的方法有很多,比如限制树的最大深度、限制叶子节点的最少样本数量、限制节点分裂时的最少样本数量、吸收 bagging 的思想对训练样本采样(subsample),在学习单颗决策树时只使用一部分训练样本、借鉴随机森林的思路在学习单颗决策树时只采样一部分特征、在目标函数中添加正则项惩罚复杂的树结构等。

演示例子:

考虑一个简单的例子来演示 GBDT 算法原理。

下面是一个二分类问题,1 表示可以考虑的相亲对象,0 表示不考虑的相亲对象。

特征维度有 3 个维度,分别对象 身高,金钱,颜值

对应这个例子,训练结果是 perfect 的,全部正确, 特征权重可以看出,对应这个例子训练结果颜值的重要度最大,看一下训练得到的树。

Tree 0:

Tree 1:

3、原理推导

3.1 目标函数

监督学习的关键概念:模型(model)、参数(parameters)、目标函数(objective function)

模型就是所要学习的条件概率分布或者决策函数,它决定了在给定特征向量时如何预测出目标。

参数就是我们要从数据中学习得到的内容。模型通常是由一个参数向量决定的函数。

目标函数通常定义为如下形式:

其中,L 是损失函数,用来衡量模型拟合训练数据的好坏程度;Ω称之为正则项,用来衡量学习到的模型的复杂度。

对正则项的优化鼓励算法学习到较简单的模型,简单模型一般在测试样本上的预测结果比较稳定、方差较小(奥坎姆剃刀原则)。也就是说,优化损失函数尽量使模型走出欠拟合的状态,优化正则项尽量使模型避免过拟合。

3.2 加法模型

GBDT 算法可以看成是由 K 棵树组成的加法模型:

如何来学习加法模型呢?

解这一优化问题,可以用前向分布算法(forward stagewise algorithm)。因为学习的是加法模型,如果能够从前往后,每一步只学习一个基函数及其系数(结构),逐步逼近优化目标函数,那么就可以简化复杂度。这一学习过程称之为 Boosting。具体地,我们从一个常量预测开始,每次学习一个新的函数,过程如下:

在第 t 步,这个时候目标函数可以写为:

举例说明,假设损失函数为平方损失(square loss),则目标函数为:

其中,称

之为残差(residual)。因此,使用平方损失函数时,GBDT 算法的每一步在生成决策树时只需要拟合前面的模型的残差。

3.3 泰勒公式

定义:

泰勒公式简单的理解,就是函数某个点的取值可以用参考点取值和 n+1 阶导数的来表示,而且这个公式是有规律的比较好记。

根据泰勒公式把函数

点处二阶展开,可得到如下等式:

则等式(1) 可转化为:

假设损失函数为平方损失函数,把对应的一阶导数和二阶导数代入等式(4) 即得等式(2)。

由于函数中的常量在函数最小化的过程中不起作用,因此我们可以从等式(4) 中移除掉常量项,得:

3.4 GBDT 算法

一颗生成好的决策树,假设其叶子节点个数为

决策树的复杂度可以由正则项

来定义,即决策树模型的复杂度由生成的树的叶子节点数量和叶子节点对应的值向量的 L2 范数决定。

定义集合

为所有被划分到叶子节点的训练样本的集合。等式(5) 可以根据树的叶子节点重新组织为 T 个独立的二次函数的和:

定义

,则等式(6) 可写为:

因为一元二次函数最小值处,一阶导数等于 0:

此时,目标函数的值为

综上,为了便于理解,单颗决策树的学习过程可以大致描述为: 1. 枚举所有可能的树结构 q 2. 用等式(8) 为每个 q 计算其对应的分数 Obj,分数越小说明对应的树结构越好 3. 根据上一步的结果,找到最佳的树结构,用等式(7) 为树的每个叶子节点计算预测值

然而,可能的树结构数量是无穷的,所以实际上我们不可能枚举所有可能的树结构。通常情况下,我们采用贪心策略来生成决策树的每个节点。

1. 从深度为 0 的树开始,对每个叶节点枚举所有的可用特征 2. 针对每个特征,把属于该节点的训练样本根据该特征值升序排列,通过线性扫描的方式来决定该特征的最佳分裂点,并记录该特征的最大收益(采用最佳分裂点时的收益) 3. 选择收益最大的特征作为分裂特征,用该特征的最佳分裂点作为分裂位置,把该节点生长出左右两个新的叶节点,并为每个新节点关联对应的样本集 4. 回到第 1 步,递归执行到满足特定条件为止

3.5 收益的计算

如何计算每次分裂的收益呢?假设当前节点记为 C,分裂之后左孩子节点记为 L,右孩子节点记为 R,则该分裂获得的收益定义为当前节点的目标函数值减去左右两个孩子节点的目标函数值之和:

根据等式(8) 可得:

其中,

项表示因为增加了树的复杂性(该分裂增加了一个叶子节点)带来的惩罚。

最后,总结一下 GBDT 的学习算法: 1. 算法每次迭代生成一颗新的决策树 ; 2. 在每次迭代开始之前,计算损失函数在每个训练样本点的一阶导数和二阶导数 ; 3. 通过贪心策略生成新的决策树,通过等式(7) 计算每个叶节点对应的预测值 4. 把新生成的决策树

添加到模型中:

保持简单

易经中说道"易则易知,简则易从",就是越是简易的东西,越是容易被理解和得到执行。很多机器学习模型都会尽量让学习到的模型尽量简单,尽量减少参数,越是简单的模型,通用性越好,也是这个道理。

Xgboost 和 GBDT 的区别:

GBDT:

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

Xgboost:

它有以下几个优良的特性:

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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

陈龙的专栏

1 篇文章1 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT派

对数几率回归 —— Logistic Regression

首先,在引入LR(Logistic Regression)模型之前,非常重要的一个概念是,该模型在设计之初是用来解决0/1二分类问题,虽然它的名字中有回归二字,...

1092
来自专栏数据科学与人工智能

【知识】图解机器学习

每当提到机器学习,大家总是被其中的各种各样的算法和方法搞晕,觉得无从下手。确实,机器学习的各种套路确实不少,但是如果掌握了正确的路径和方法,其实还是有迹可循的,...

2075
来自专栏技术与生活

深度学习之卷积

今日休假,把卷积神经网络梳理下。先从一些基本概念入手,什么是卷积?为什么叫这么个名字? 搜索了一遍,网上有很多人已经表述的非常好了,这里用自己理解的语言重述下。

792
来自专栏AI科技评论

开发 | 手把手教你用 TensorFlow 实现卷积神经网络(附代码)

AI科技评论按:本文作者徐凯文,原文载于作者个人博客,已获授权。 在知乎上看到一段介绍卷积神经网络的文章,感觉讲的特别直观明了,我整理了一下。首先介绍原理部分。...

3728
来自专栏算法channel

TensorFlow 指标列,嵌入列

一般地,机器学习、深度学习 feed 进来的数据要求为数值型。如果某列取值为字符型,需要做数值转换,今天就来总结下 TensorFlow 中的指标列和嵌入列。

1323
来自专栏专知

【干货】​深度学习中的线性代数

【导读】近日,机器学习专业学生 Niklas Donges 撰写了一篇关于深度学习需要的数学基础相关知识。线性代数对于理解机器学习和深度学习内部原理至关重要,这...

34710
来自专栏大数据挖掘DT机器学习

深度学习CTPN算法的解读与tensorflow实现

作者github地址和tensorflow版本地址: 在公众号 datadw 里 回复 CTPN 即可获取。 本文将对CTPN这篇文章的思路做一个详细的介绍...

6934
来自专栏AI研习社

看完立刻理解 GAN!初学者也没关系

前言 GAN 从 2014 年诞生以来发展的是相当火热,比较著名的 GAN 的应用有 Pix2Pix、CycleGAN 等。本篇文章主要是让初学者通过代码了...

3135
来自专栏AI研习社

手把手教你用 TensorFlow 实现卷积神经网络(附代码)

在知乎上看到一段介绍卷积神经网络的文章,感觉讲的特别直观明了,我整理了一下。首先介绍原理部分。 通过一个图像分类问题介绍卷积神经网络是如何工作的。下面是卷积神经...

3426
来自专栏人工智能LeadAI

零基础入门深度学习 | 第四章:卷积神经网络

无论即将到来的是大数据时代还是人工智能时代,亦或是传统行业使用人工智能在云上处理大数据的时代,作为一个有理想有追求的程序员,不懂深度学习这个超热的技术,会不会感...

4667

扫码关注云+社区