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

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 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

塔秘 | 极简Python带你探索分类与回归的奥秘

前言 本文从分类和回归两个方面介绍了基本的监督学习方法,并用Scikit-Learn做了实例演示。 ? 为何使用人工智能和机器学习? 地球的未来在于人工智能和机...

37812
来自专栏书山有路勤为径

Optimization Algorithms

机器学习应用是一个高度依赖经验并伴随着大量迭代的过程——这一句话不得不同意,经验更重要,深有体会。你需要训练诸多模型才能找到合适的那一个。深度学习没有在大数据领...

391
来自专栏iOSDevLog

机器学习术语表机器学习术语表

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

【算法】决策树与ID3算法

小编邀请您,先思考: 1 如何构建决策树? 2 决策树适合解决什么问题? 1. 什么是决策树/判定树(decision tree)? 决策树(Decision ...

3195
来自专栏人工智能

如何使用Python超参数的网格搜索ARIMA模型

我们都知道用于时序分析和预测的ARIMA模型可能很难配置。

5445
来自专栏深度学习之tensorflow实战篇

聚类方法的区别解读:各种聚类分析呀呀呀

k 均值聚类法 快速高效,特别是大量数据时,准确性高一些,但是需要你自己指定聚类的类别数量 系统聚类法则是系统自己根据数据之间的距离来自动列出类别,所以通过系统...

2527
来自专栏企鹅号快讯

《教育统计与SPSS应用》学习笔记(8)

第8讲 回归分析 主要内容 回归分析简介 一元线性回归分析 多元线性回归分析 第一部分 回归分析简介 一、回归分析的意义 表示变量之间的不确定性关系以...

2188
来自专栏ml

数据挖掘学习笔记--AdaBoost算法(一)

声明: 这篇笔记是自己对AdaBoost原理的一些理解,如果有错,还望指正,俯谢~ 背景: AdaBoost算法,这个算法思路简单. 正文: AdaBoost...

3457
来自专栏机器之心

深度 | 利用进化方法自动生成神经网络:深度进化网络DENSER

2595
来自专栏生信小驿站

无监督学习 聚类分析③

可以看到有16个指标支持最佳聚类数目为3,5个指标支持聚类数为2,所以该方法推荐的最佳聚类数目为3.

714

扫描关注云+社区