『机器学习笔记 』GBDT原理-Gradient Boosting Decision Tree

『机器学习笔记 』GBDT原理-Gradient Boosting Decision Tree1.背景1.1GradientBoosting1.2提升树-boostingtree回归问题提升树算法2GradientBoostingDecisionTree2.1函数空间的数值优化2.2算法Shrinkage总结附录参考资料相似算法:1.背景决策树是一种基本的分类与回归方法。决策树模型具有分类速度快,模型…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

1. 背景

决策树是一种基本的分类回归方法。决策树模型具有分类速度快,模型容易可视化的解释,但是同时是也有容易发生过拟合,虽然有剪枝,但也是差强人意。

提升方法boosting)在分类问题中,它通过改变训练样本的权重(增加分错样本的权重,减小分队样本的的权重),学习多个分类器,并将这些分类器线性组合,提高分类器性能。boosting数学表示为:
f ( x ) = w 0 + ∑ m = 1 M w m ϕ m ( x ) f(x) = w_0 + \sum\limits_{m=1}^M w_m \phi_m(x) f(x)=w0+m=1Mwmϕm(x)

其中w是权重, ϕ \phi ϕ是弱分类器的集合,可以看出最终就是基函数的线性组合。

于是决策树与boosting结合产生许多算法,主要有提升树、GBDT等。本文主要是GBDT学习笔记。

1.1 Gradient Boosting

Gradient Boosting是一种Boosting的方法,它主要的思想是,每一次建立模型是在之前建立模型损失函数的梯度下降方向。损失函数是评价模型性能(一般为拟合程度+正则项),认为损失函数越小,性能越好。而让损失函数持续下降,就能使得模型不断改性提升性能,其最好的方法就是使损失函数沿着梯度方向下降(讲道理梯度方向上下降最快)。

Gradient Boost是一个框架,里面可以套入很多不同的算法。

1.2 提升树-boosting tree

以决策树为基函数的提升方法称为提升树,其决策树可以是分类树OR回归树。提升树模型可以表示为决策树的加法模型。
f M ( x ) = ∑ m = 1 M T ( x ; Θ m ) f_M(x) = \sum\limits_{m=1}^M T(x;\Theta_m) fM(x)=m=1MT(x;Θm)
其中, T ( x ; Θ m ) 表 示 决 策 树 , T(x;\Theta_m)表示决策树, T(x;Θm) Θ m \Theta_m Θm表示树的参数,M为树的个数。

回归问题提升树算法

输入:训练数据集$T={(x_1,y_1),(x_2,y_2),···,(x_N,y_N)}, x_i \in \chi = R^n, y_i \in \gamma, \ i=1,2,···,N ; ; \gamma$为输出空间。

输出:提升树 f M ( x ) f_M(x) fM(x)

  1. 初始化 f 0 ( x ) = 0 f_0(x)=0 f0(x)=0

  2. 对于 m = 1 , 2 , . . . M m=1,2,…M m=1,2,...M:

    1. 计算残差(后一棵树拟合前一颗树残差):

      r m i = y i − f m − 1 ( x i ) r_{mi} = y_i – f_{m-1}(x_i) rmi=yifm1(xi)

    2. 拟合残差学习一个回归树,得到 T ( x ; Θ m ) T(x;\Theta_m) T(x;Θm)

    3. 更新 f m ( x ) = f m − 1 ( x ) + T ( x ; Θ m ) f_m(x) = f_{m-1}(x) + T(x;\Theta_m) fm(x)=fm1(x)+T(x;Θm)

  3. M次迭代之后得到提升树:

    f M ( x ) = ∑ m = 1 M T ( x ; Θ m ) f_M(x) = \sum\limits_{m=1}^M T(x;\Theta_m) fM(x)=m=1MT(x;Θm)

2 Gradient Boosting Decision Tree

提升树的学习优化过程中,损失函数平方损失和指数损失时候,每一步优化相对简单,但对于一般损失函数优化的问题,Freidman提出了Gradient Boosting算法,其利用了损失函数的负梯度在当前模型的值
− [ ∂ L ( y , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f m − 1 ( x ) -[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)} [f(xi)L(y,f(xi))]f(x)=fm1(x)
作为回归问题提升树算法的残差近似值,去拟合一个回归树。

2.1 函数空间的数值优化

优化目标是使得损失函数最小,(N是样本集合大小):
F ∗ ( x ) = arg ⁡ min ⁡ ρ ∑ i = 1 N L ( y i , ρ ) F^*(x)=\underset{\rho}{\arg\min}\sum^N_{i=1}\mathcal{L}(y_i, \rho) F(x)=ρargmini=1NL(yi,ρ)
GBDT是一个加法模型: f m ( x ) f_m(x) fm(x)是每一次迭代学习的到树模型。
F ^ ( x ) = F M ( x ) = ∑ m = 1 M f m ( x ) \hat{F}(x) = F_M(x) = \sum\limits_{m=1}^M f_m(x) F^(x)=FM(x)=m=1Mfm(x)
对于其每一步迭代:
f m ( x ) = − ρ m g m ( x ) f_m(x) = -\rho_m g_m(x) fm(x)=ρmgm(x)
其中
g m ( x ) = [ ∂ ϕ ( F ( x ) ) ∂ F ( x ) ] F ( x ) = F m − 1 ( x ) ϕ ( F ( x ) ) = E y [ L ( y , F ( x ) ) ∣ x ] , F m − 1 ( x ) = ∑ i = 0 m − 1 f i ( x ) g_m(x) = [\frac{\partial \phi(F(x))}{\partial F(x)}]_{F(x) = F_{m-1}(x)} \\ \phi(F(x)) = E_y[L(y,F(x))|x], F_{m-1}(x) = \sum_{i=0}^{m-1} f_i(x) gm(x)=[F(x)ϕ(F(x))]F(x)=Fm1(x)ϕ(F(x))=Ey[L(y,F(x))x],Fm1(x)=i=0m1fi(x)
其实 L ( y , F ( x ) ) L(y, F(x)) L(y,F(x))就是损失函数, ϕ ( F ( x ) ) \phi(F(x)) ϕ(F(x))是当前x下的损失期望, g m ( x ) g_m(x) gm(x)是当前x下的函数梯度。最终 f m ( x ) f_m(x) fm(x)学习的是损失函数在函数空间上的负梯度。

对于权重 ρ m \rho_m ρm通过线性搜索求解(这也是后面算法改进的点):
ρ m = arg ⁡ min ⁡ ρ E y , x L ( y , F m − 1 ( x ) − ρ ∗ g m ( x ) ) \rho_m = \arg \min_{\rho} E_{y,x} L(y, F_{m-1}(x) – \rho *g_m(x)) ρm=argρminEy,xL(y,Fm1(x)ρgm(x))
理解:每一次迭代可以看做是采用梯度下降法对最优分类器 F ∗ ( x ) F^*(x) F(x)的逐渐比较,每一次学习的模型 f m ( x ) f_m(x) fm(x)是梯度,进过M步迭代之后,最后加出来的模型就是最优分类器的一个逼近模型,所以 f m ( x i ) f_m(x_i) fm(xi)使用单步修正方向 − g m ( x i ) -g_m(x_i) gm(xi)
− g m ( x i ) = g m ( x ) = [ ∂ L ( F ( x ) ) ∂ F ( x ) ] F ( x ) = F m − 1 ( x ) -g_m(x_i) = g_m(x) = [\frac{\partial L(F(x))}{\partial F(x)}]_{F(x) = F_{m-1}(x)} gm(xi)=gm(x)=[F(x)L(F(x))]F(x)=Fm1(x)
这里的梯度变量是函数,是在函数空间上求解(这也是后面XGBoost改进的点),注意以往算法梯度下降是在N维的参数空间的负梯度方向,变量是参数。这里的变量是函数,更新函数通过当前函数的负梯度方向来修正模型,是它更优,最后累加的模型近似最优函数。

2.2 算法

输入:训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋅ ⋅ ⋅ , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),···,(x_N,y_N)\} T={
(x1,y1),(x2,y2),,(xN,yN)}
,$ x_i \in \chi = R^n , , y_i \in \gamma={-1,+1}, \ i=1,2,···,N $;

输出:回归树 f M ( x ) f_M(x) fM(x)

  1. 初始化

    f 0 ( x ) = a r g min ⁡ c ∑ i = 1 N L ( y i , c ) f_0(x) = arg \min\limits_c \sum\limits_{i=1}^N L(y_i,c) f0(x)=argcmini=1NL(yi,c)

  2. 对m=1,2,…M

    1. 对i=1,2,…,N,计算

      r m i = − [ ∂ L ( y , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f m − 1 ( x ) r_{mi}= -[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)} rmi=[f(xi)L(y,f(xi))]f(x)=fm1(x)

    2. r m i r_{mi} rmi拟合一颗回归树,得到第m棵树的叶结点区域 R m j ,   j = 1 , 2 , . . . J R_{mj}, \ j=1,2,…J Rmj, j=1,2,...J,即一棵由J个叶子节点组成的树。

    3. j = 1 , 2 , . . . J j=1,2,…J j=1,2,...J,计算

      c m j = a r g min ⁡ c ∑ x i ∈ R m j L ( y i , f m − 1 ( x i ) + c ) c_{mj}=arg \min\limits_c \sum\limits_{x_i \in R_{mj} } L(y_i, f_{m-1}(x_i) + c) cmj=argcminxiRmjL(yi,fm1(xi)+c)

      2.2,2.3这一步相当于回归树递归在遍历所有切分变量j和切分点s找到最优j,s,然后在每个节点区域求最优的c。参考回归树生成算法

    4. 更新 f m ( x ) = f m − 1 ( x ) + ∑ j = 1 J c m j I ( x ∈ R m j ) f_m(x)=f_{m-1}(x) + \sum\limits_{j=1}^J c_{mj} I(x \in R_{mj}) fm(x)=fm1(x)+j=1JcmjI(xRmj)

  3. 得到回归树

    f ^ ( x ) = f M ( x ) = ∑ m = 1 M f m ( x ) = ∑ m = 1 M ∑ j = 1 J c m j I ( x ∈ R m j ) \hat{f}(x) = f_M(x) = \sum\limits_{m=1}^M f_m(x) = \sum\limits_{m=1}^M \sum\limits_{j=1}^J c_{mj}I(x \in R_{mj}) f^(x)=fM(x)=m=1Mfm(x)=m=1Mj=1JcmjI(xRmj)

算法1步获得使得损失函数最小的常数估计值,是一个只有根节点的树。在2.1步计算损失函数的负梯度在当前模型的值,将它作为残差估计。在2.2步估计回归树的叶结点区域,来拟合残差的近似值。在2.3步利用线性搜索估计回归树叶结点区域的值,使损失函数最小化。2.4更新回归树。第3步获得输出的最终模型。

Shrinkage

Shrinkage的思想认为,每次走一小步逐渐逼近结果的效果,要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树,它认为每棵树只学到了真理的一小部分,累加的时候只累加一小部分,通过多学几棵树弥补不足。

数学方程对比:

  • 之前: f m ( x ) = f m − 1 ( x ) + ∑ j = 1 J c m j I ( x ∈ R m j ) f_m(x)=f_{m-1}(x) + \sum\limits_{j=1}^J c_{mj} I(x \in R_{mj}) fm(x)=fm1(x)+j=1JcmjI(xRmj)
  • Shrinkage: f m ( x ) = f m − 1 ( x ) + s t e p ∗ ∑ j = 1 J c m j I ( x ∈ R m j ) f_m(x)=f_{m-1}(x) +step* \sum\limits_{j=1}^J c_{mj} I(x \in R_{mj}) fm(x)=fm1(x)+stepj=1JcmjI(xRmj)

Shrinkage仍然以残差作为学习目标,但对于残差学习的结果,只累加一小部分,step一般取值0.001-0.01(非gradient的step),使得各个树的残差是渐变而不是陡变的,即将大步切成了小步。Shrinkage能减少过拟合发生也是经验证明的,目前还没有看到从理论的证明。

总结

原始的boosting算法开始时,为每一个样本赋上一个权重值。在每一步训练中得到的模型,会使得数据点的估计有对有错,在每一步结束后,增加分错的点的权重,减少分对的点的权重,这样使得某些点如果老是被分错,那么就会被“严重关注”,也就被赋上一个很高的权重。然后等进行了N次迭代(由用户指定),将会得到N个简单的分类器(basic learner),然后我们将它们组合起来(比如说可以对它们进行加权、或者让它们进行投票等),得到一个最终的模型。

那么GBDT算法中并未有权重的改变,哪里有boosting思想 ?

Gradient Boosting与Boosting区别在于,每一计算的是为了减少上一次的残差,下一个模型主要在残差减少的梯度方上建立模型,使得残差往梯度方向上减少。

虽然不同,但是GBDT算法会更关注那些梯度比较大的样本,和Boosting思想类似。

附录

CSDN原文:http://blog.csdn.net/shine19930820/article/details/65633436
公众号:百川NLP

在这里插入图片描述

参考资料

相似算法:

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/185669.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 用户 不在 sudoers 文件中。此事将被报告。

    用户 不在 sudoers 文件中。此事将被报告。文章目录背景解决方案背景普通linux用户使用sudo命令执行只有root用户才可以执行的命令时出现了该错误,如下图示:简单说明一下操作。命令$ll/etc/sudoers表示查看文件的属性,属性包括有:文件拥有者、文件所属组以及其他用户组对该文件拥有的读写权限和文件的类型等,上图的/etc/sudoers文件表示拥有者和所属组都是root且只能读取,其他用户组的没有任何读写权限。命…

  • javascript uint8数组和uint32之间的转换

    javascript uint8数组和uint32之间的转换低位在前,高位在后functionintTobytes(value){vara=newUint8Array(4)a[3]=(value>>24)&0xFFa[2]=(value>>16)&0xFFa[1]=(value>>8)&0xFFa[0]=value

  • 数据库的唯一索引_数据库唯一索引是什么

    数据库的唯一索引_数据库唯一索引是什么唯一索引是不允许表中任何两行具有相同索引值的索引。  当现有的数据中存在重复的键值时,大多数数据库不允许把新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复键值的新数据。主键索引数据库表经常有一列或列组合,其值唯一标识表中的每一行。该列称为表的主键。在数据库关系图中为表定义主键将自动创建主键索引,主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键

  • asp.net类似于js中的setTimeOut()的函数作用?

    asp.net类似于js中的setTimeOut()的函数作用?

    2021年11月17日
  • 新人学习EJB!ejb到底是什么?[通俗易懂]

    1. 我们不禁要问,什么是”服务集群”?什么是”企业级开发”? 既然说了EJB是为了”服务集群”和”企业级开发”,那么,总得说说什么是所谓的”服务集群”和”企业级开发”吧!这个问题其实挺关键的,因为J2EE中并没有说明白,也没有具体的指标或者事例告诉广大程序员什么时候用EJB什么时候不用。于是大家都产生一些联想,认为EJB”分布式运算”指得是”负载均衡”提高系统的运行效率

  • 五、工厂模式—旅行的钱怎么来 #和设计模式一起旅行#

    君子爱财,取之有道!—— 出自《增广贤文》### 故事背景上一篇我和MM相约好了,去旅行了,但是旅行是需要Money的啊,作为有个搬砖的码农,没钱啊,怎么呢!不能穷游啊,真是愁人啊 !哎 ,办法总归困难多,这一篇就是写写如何通过工厂拿到钱,然后开始我们的旅行,为一路上能胡吃海喝打下基础!下面开始我们的造钱之旅!“` public class Client{publi…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号