数据挖掘面试题之梯度提升树

GBDT是机器学习面试中的常客,但是,要准确地说出它的原理却并不容易,除了掌握DT基本知识外,还要掌握加法模型、前向分步算法、梯度提升思想,本文是对这些知识点的一个简单总结,请各路大神指正。

为了提高写作效率,文中公式都是手写,美观不足,但清晰准确是没问题的。

01

从加法模型说开去

首先,我们需要具备一些基本的机器学习知识,这里简单列出,以作为下面讨论的基础:

1、机器学习的大致流程就是确定模型集H、定义经验损失函数(一般是基于单个样本点进行定义)、利用给定的数据集{(x_i,y_i)},从模型集中寻找最佳的模型(一般就是寻找最佳的模型参数)。

2、决策树是一种模型,它的主要思想是将输入空间划分为不同的子区域,然后给每个子区域确定一个值,如果是分类树,这个值就是类别,如果是回归树,这个树就是一个实值。如下图所示:

图1.PNG

3、GBDT中的DT是回归树,不是分类树,也就是说,只有回归树才有所谓的梯度提升。

所谓加法模型,也是一种模型集H,它的一般形式如下:

图2.PNG

f_m(x)叫做基函数,基函数可以有各种各样的形式,自然也会有自己的参数,待会儿我们讨论GBDT时,它就是二叉回归决策树。β_m是基函数的系数,一般假设大于0。

有了模型,还需定义该模型的经验损失函数,如下所示:

图3.PNG

现在,我们的问题转变成了通过极小化经验损失函数来确定各个系数β_m和各个基函数f_m(x)。

问题是:How?

此时,我们既不知道基函数的具体形式,也不知道损失函数的具体形式,只有N个样本点,很显然,我们无法往下进行。

02

前向分步算法横空出世

这就是前向分步算法一显身手的地方,前向分布算法说:“我可以提供一套框架,不管基函数和损失函数是什么形式,只要你的模型是加法模型,就可以按照我的框架的指导,去求解。”

也就是说,前向分步算法提供了一种学习加法模型的普遍性方法,不同形式的基函数、不同形式的损失函数都可以用这种普遍性方法去求出加法模型的最优化参数,它是一种元算法。

它的思路是:加法模型中一共有M个基函数以及与之相应的M个系数,可以从前往后,每次学习一个基函数及其系数。

其学习步骤如下:

图4.PNG

前向分步算法中最核心的就是第2步中的第1小步,即如何求出f_m和β_m?

03

梯度提升顺利接盘

梯度提升思想正是为了解决上面的问题。它的主要思想是先求f_m,再求β_m。观察式子:

图5.PNG

我们要最小化的式子由N部分相加而成,如果能够最小化每一部分,自然也就最小化了整个式子。考察其中任一部分,并将其进行泰勒一阶展开(这是关键所在!):

图6.PNG

由于β是大于0的,若:

图7.PNG

不难得出:

图8.PNG

这说明,我们已经成功地降低了在第i个样本点上的预测损失。同理,我们可以降低在每一个样本点上的预测损失。条件就是:

图9.PNG

这个条件其实告诉了我们如何去寻找f_m,即能够使得在每一个样本点上上式尽可能成立的f_m就是我们要找的。这是一个回归问题,很容易解决。

我们已经有了f_m,下面优化求解β,很显然,这是一个一维搜索问题,如下:

图10.PNG

在上面的泰勒一阶展开时,有一个条件就是βf(x_i)要足够小,显然,执行一维搜索后得到的β会满足这个条件。

04

这时才是学习梯度提升树的最佳时机

以上是加法模型的一般学习方法,对不同的基函数,不同的损失函数,不同的问题(分类还是回归),都可以套用上面的方法来求解,只是具体的表现形式会有所变化。

比如当加法模型解决的问题是二类分类问题,基函数是基本分类器,损失函数为指数损失函数时,按照上面的方法求解,其过程就和AdaBoost是完全一样的。

当用加法模型解决的问题是回归问题,基函数是二叉决策回归树时,加法模型本身会得到简化,基函数前面的系数可以省去,因为对每一个系数,我们都可以把它内化到二叉决策回归树内部去,这时的加法模型变成了这样:

![Uploading end_421067.PNG . . .]

简化了加法模型,消除了β,在求解第2步第1小步时,过程也得到了简化,详情请参考《统计学习方法》P151-152:

end.PNG

在上面的图中,有一点值得注意,就是我们用r_mi拟合出一个回归树之后,进一步用整体损失函数对这棵回归树的值进行了优化。这样的思想在机器学习中很常见,我管它叫做“先局部、后整体”思想,就是先通过逐步的局部优化得出一个结果,然后再从全局的角度来优化这个结果。

举个例子,决策树的生成和剪枝,先通过局部优化(用信息增益等指标选择特征)得出一个决策树,再从降低整体损失的角度,进行剪枝。

Note:注重总结机器学习各种模型中的思想,就可以达到触类旁通的境界。

更进一步,当损失函数是平方误差时,求解过程就更加的简单了,详情请见《统计学习方法》P148。

05

总结一下

本文首先介绍了机器学习中一类模型——加法模型,然后介绍了求解优化该类模型的前向分步算法,又进一步介绍了该算法中最核心步骤求解所用的梯度提升思想。然后,从一般到个别,展示了当加法模型运用到不同问题中(分类和回归),当基函数采用不同的具体形式(基本分类器和二叉决策回归树),当损失函数采用不同的具体形式(指数损失函数和平方损失函数)时,其具体化的求解步骤。

可以看出GBDT作为求解回归问题的加法模型,具有形式简单(消除了β),求解便捷(见上面的《统计学习方法》图)的特点,这也是为什么它十分流行的原因。

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2018-02-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ATYUN订阅号

从自编码器到变分自编码器(其一)

AiTechYun 编辑:yuxiangyu 自编码器是一种无监督学习技术,利用神经网络进行表征学习。也就是说,我们设计一个在网络中施加“瓶颈”,迫使原始输入压...

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

手把手教你实现SVM算法

什么是机器学习 (Machine Learning) 机器学习是研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断...

33510
来自专栏机器学习与自然语言处理

深度学习在文本分类中的应用

近期阅读了一些深度学习在文本分类中的应用相关论文(论文笔记),同时也参加了CCF 大数据与计算智能大赛(BDCI)2017的一个文本分类问题的比赛:让AI当法...

5036
来自专栏SIGAI学习与实践平台

深入浅出聚类算法

聚类问题是机器学习中无监督学习的典型代表,在数据分析、模式识别的很多实际问题 中得到了应用。在本文中,SIGAI 将为大家深入浅出的介绍聚类问题的定义以及各种典...

1241
来自专栏人工智能LeadAI

GBDT(梯度提升决策树)总结笔记

数据:对于输入数据 $$$x_i \in R^d$$$,训练数据里的第i个样本。 模型:如何对于给定的 $$$x_i$$$预测 $$$\hat{y}_i$$$。

1243
来自专栏专知

概率论之概念解析:极大似然估计

【导读】本文是数据科学家Jonny Brooks-Bartlett概率论基础概念系列博客中的“极大似然估计”一章,主要讲解了极大似然估计的若干概念。分别介绍了参...

3097
来自专栏用户2442861的专栏

深度学习概述:从感知机到深度网络

http://www.cnblogs.com/xiaowanyer/p/3701944.html

731
来自专栏CDA数据分析师

三分钟看懂机器学习中应该注意哪些问题?

本文简单谈谈机器学习中应该注意的一些问题。仅供大家参考学习和讨论。 1. 特征预处理 机器学习中的输入数据必须是数值类型的,但是现实问题中不免会有一些类别类型的...

18410
来自专栏WD学习记录

机器学习 学习笔记(20)深度前馈网络

深度前馈网络(deep feedforward network),也叫做前馈神经网络(feedforward neural network)或者多层感知机(mu...

2323
来自专栏IT派

笔记 | 吴恩达Coursera Deep Learning学习笔记

作者:Lisa Song 微软总部云智能高级数据科学家,现居西雅图。具有多年机器学习和深度学习的应用经验,熟悉各种业务场景下机器学习和人工智能产品的需求分析...

3688

扫码关注云+社区