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

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

相关文章

来自专栏机器之心

ECCV 2018 | 微软亚洲研究院与北京大学共同提出用于物体检测的可学习区域特征提取模块

作者:Jiayuan Gu、Han Hu、Liwei Wang、Yichen Wei、Jifeng Dai

482
来自专栏ArrayZoneYour的专栏

机器学习的Boosting技术(以AdaBoost为例)

Boosting(提升,提高)是一种集成技术,它通过综合多个弱分类器来获得一个强的分类器。

2678
来自专栏深度学习

RF(随机森林)、GBDT、XGBoost算法简介

一、概念 RF、GBDT和XGBoost都属于集成学习(Ensemble Learning),集成学习的目的是通过结合多个基学习器的预测结果来改善单个学习器的泛...

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

RF(随机森林)、GBDT、XGBoost面试级整理

由于本文是基于面试整理,因此不会过多的关注公式和推导,如果希望详细了解算法内容,敬请期待后文。   RF、GBDT和XGBoost都属于集成学习(Ens...

6284
来自专栏机器学习算法与Python学习

机器学习(33)之局部线性嵌入(LLE)【降维】总结

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 前言 局部线性嵌入(Locally ...

3718
来自专栏大数据文摘

斯坦福深度学习课程第七弹:RNN,GRU与LSTM

1413
来自专栏算法channel

数据降维处理:PCA之特征值分解法例子解析

请点击上面公众号,免费订阅。 《实例》阐述算法,通俗易懂,助您对算法的理解达到一个新高度。包含但不限于:经典算法,机器学习,深度学习,LeetCode 题解,...

2817
来自专栏PPV课数据科学社区

【V课堂】R语言十八讲(十七)—主成分分析

理解主成分分析这个模型前,可能需要一定的线性代数的知识,当然若没有基本也能看下去,只是可能比较困弄清楚,但这篇短文会尽可能给你的写得浅显易懂,不涉及太多公式推导...

2586
来自专栏人工智能LeadAI

深度学习与TensorFlow: VGG论文笔记

马毅老师曾说过:”如果你没有看过近30年的经典论文,你是做不出成果的”.现如今深度学习如此火热,一些关键节点发布的文章更应该好好的阅读,因此我想在未来的一段时间...

913
来自专栏机器学习算法与Python学习

干货 | 卷积神经网络入门这一篇就够了

【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 先明确一点就是,Deep Learning是全部深度学习算法...

32210

扫码关注云+社区