首页 > 编程语言 >GBDT 算法的原理推导

GBDT 算法的原理推导

时间:2024-11-01 12:18:24浏览次数:3  
标签:11 varTheta 推导 梯度 模型 tag 算法 GBDT fm

GBDT的全称为梯度提升决策树(gradient boosting decision tree),其基模型(弱分类器)为CART决策树,针对分类问题的基模型为二叉分类树,对应梯度提升模型就叫GBDT;针对回归问题的基模型为二叉回归树,对应的梯度提升模型叫做GBRT(gradient boosting regression tree)。

我们先来用一个通俗的说法来理解GBDT。假设某人月薪10k,我们首先用一个树模型拟合了6k,发现有4k的损失,然后再用一棵树模型拟合了2k,这样持续拟合下去,拟合值和目标值之间的残差会越来越小。将每一轮迭代,也就是每一棵树的预测值加起来,就是模型最终的预测结果。使用多棵决策树组合就是提升树模型,使用梯度下降法对提升树模型进行优化的过程就是梯度提升树模型。

一个提升树模型的数学表达式为:
f M ( x ) = ∑ m = 1 M T ( x ; Θ m ) (11-1) f_M(x) = \sum_{m=1}^{M} T(x; \varTheta_m) \tag{11-1} fM​(x)=m=1∑M​T(x;Θm​)(11-1)

其中 T ( x ; Θ m ) T(x; \varTheta_m) T(x;Θm​)为决策树表示的基模型, Θ m \varTheta_m Θm​为决策树参数, M M M为决策树棵数。

当确定初始提升树模型 f 0 ( x ) = 0 f_0(x)=0 f0​(x)=0时,第 m m m的模型表示为:
f m ( x ) = f m − 1 ( x ) + T ( x ; Θ m ) (11-2) f_m(x) = f_{m-1}(x) + T(x; \varTheta_m) \tag{11-2} fm​(x)=fm−1​(x)+T(x;Θm​)(11-2)

其中 f m − 1 ( x ) f_{m-1}(x) fm−1​(x)为当前迭代模型,根据前向分步算法,可以使用经验风险最小化来确定下一棵决策树的参数 Θ m \varTheta_m Θm​:
Θ ^ m = arg ⁡ min ⁡ Θ m ∑ i = 1 N L ( y i , f m − 1 ( x i ) + T ( x i ; Θ m ) ) (11-3) \hat{\varTheta}_m = \arg\min_{\varTheta_m} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + T(x_i; \varTheta_m)) \tag{11-3} Θ^m​=argΘm​min​i=1∑N​L(yi​,fm−1​(xi​)+T(xi​;Θm​))(11-3)

以梯度提升回归树为例,一棵回归树可以表示为:
T ( x ; Θ ) = ∑ k = 1 K c k I ( x ∈ R j ) (11-4) T(x; \varTheta) = \sum_{k=1}^K c_k I(x \in R_j) \tag{11-4} T(x;Θ)=k=1∑K​ck​I(x∈Rj​)(11-4)

根据加性模型,第0步、第 m m m步和最终模型可以表示为:
f 0 ( x ) = 0 (11-5) f_0(x) = 0 \tag{11-5} f0​(x)=0(11-5)

f m ( x ) = f m − 1 ( x ) + T ( x ; Θ m ) (11-6) f_m(x) = f_{m-1}(x) + T(x; \varTheta_m) \tag{11-6} fm​(x)=fm−1​(x)+T(x;Θm​)(11-6)

f M ( x ) = ∑ m = 1 M T ( x ; Θ m ) (11-7) f_M(x) = \sum_{m=1}^{M} T(x; \varTheta_m) \tag{11-7} fM​(x)=m=1∑M​T(x;Θm​)(11-7)

在已知 f m − 1 ( x ) f_{m-1}(x) fm−1​(x)的情况下,求解式(11-3)可得到当前迭代步的模型参数。假设回归树的损失函数为平方损失:
L ( y , f ( x ) ) = ( y − f ( x ) ) 2 (11-8) L(y, f(x)) = (y - f(x))^2 \tag{11-8} L(y,f(x))=(y−f(x))2(11-8)

对应到GBRT中,损失可推导为:
L ( y , f m − 1 ( x ) + T ( x ; Θ m ) ) = [ y − f m − 1 ( x ) − T ( x ; Θ m ) ] 2 (11-9) L(y, f_{m-1}(x) + T(x; \varTheta_m)) = [y - f_{m-1}(x) - T(x; \varTheta_m)]^2 \tag{11-9} L(y,fm−1​(x)+T(x;Θm​))=[y−fm−1​(x)−T(x;Θm​)]2(11-9)

令:
r = y − f m − 1 ( x ) (11-10) r = y - f_{m-1}(x) \tag{11-10} r=y−fm−1​(x)(11-10)

所以式(11-9)可表示为:
L ( y , f m − 1 ( x ) + T ( x ; Θ m ) ) = [ r − T ( x ; Θ m ) ] 2 (11-11) L(y, f_{m-1}(x) + T(x; \varTheta_m)) = [r - T(x; \varTheta_m)]^2 \tag{11-11} L(y,fm−1​(x)+T(x;Θm​))=[r−T(x;Θm​)]2(11-11)

正如本节开头的例子,提升树模型每一次迭代都是在拟合一个残差函数。当损失函数如本例中的均方损失一样时,式(11-3)是容易求解的。但大多数情况下,一般损失函数很难直接优化求解,因而就有了基于负梯度求解提升树模型的梯度提升树模型。梯度提升树以梯度下降的方法,使用损失函数的负梯度在当前模型的值作为回归提升树中残差的近似值:
r m i = − [ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f m − 1 ( x ) (11-12) r_{mi} = -\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]_{f(x)=f_{m-1}(x)} \tag{11-12} rmi​=−[∂f(xi​)∂L(yi​,f(xi​))​]f(x)=fm−1​(x)​(11-12)

所以,综合提升树模型、前向分步算法和梯度提升,给定训练集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } D=\{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\} D={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}, x i ∈ X x_i \in X xi​∈X, y i ∈ Y ⊆ R n y_i \in Y \subseteq \mathbb{R}^n yi​∈Y⊆Rn,GBDT算法的一般流程可归纳为如下步骤。

(1) 初始化提升树模型:
f 0 ( x ) = arg ⁡ min ⁡ c ∑ i = 1 N L ( y i , c ) (11-13) f_0(x) = \arg\min_c \sum_{i=1}^N L(y_i, c) \tag{11-13} f0​(x)=argcmin​i=1∑N​L(yi​,c)(11-13)

(2) 对 m = 1 , 2 , ⋯   , M m=1, 2, \cdots, M m=1,2,⋯,M,有

(a) 对每个样本 i = 1 , 2 , ⋯   , N i=1, 2, \cdots, N i=1,2,⋯,N,计算负梯度拟合的残差:
r m i = − [ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f m − 1 ( x ) (11-14) r_{mi} = -\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]_{f(x)=f_{m-1}(x)} \tag{11-14} rmi​=−[∂f(xi​)∂L(yi​,f(xi​))​]f(x)=fm−1​(x)​(11-14)

(b) 将上一步得到的残差作为样本新的真实值,并将数据 ( x i , r m i ) (x_i, r_{mi}) (xi​,rmi​), i = 1 , 2 , ⋯   , N i=1, 2, \cdots, N i=1,2,⋯,N作为下一颗树的训练数据,得到一棵新的回归树 f m ( x ) f_m(x) fm​(x),其对应的叶子结点区域为 R m j R_{mj} Rmj​, j = 1 , 2 , ⋯   , J j=1, 2, \cdots, J j=1,2,⋯,J。其中 J J J为回归树 T T T的叶子结点的个数。

© 对叶子区域 j = 1 , 2 , ⋯   , J j=1, 2, \cdots, J j=1,2,⋯,J计算最优拟合值:
c m j = arg ⁡ min ⁡ c ∑ x i ∈ R m j L ( y i , f m − 1 ( x i ) + c ) (11-15) c_{mj} = \arg\min_c \sum_{x_i \in R_{mj}} L(y_i, f_{m-1}(x_i) + c) \tag{11-15} cmj​=argcmin​xi​∈Rmj​∑​L(yi​,fm−1​(xi​)+c)(11-15)

(d) 更新提升树模型:
f m ( x ) = f m − 1 ( x ) + ∑ j = 1 J c m j I ( x ∈ R m j ) (11-16) f_m(x) = f_{m-1}(x) + \sum_{j=1}^J c_{mj} I(x \in R_{mj}) \tag{11-16} fm​(x)=fm−1​(x)+j=1∑J​cmj​I(x∈Rmj​)(11-16)

(3) 得到最后的梯度提升树:
f ( x ) = f M ( x ) = ∑ m = 1 M ∑ j = 1 J c m j I ( x ∈ R m j ) (11-17) f(x) = f_M(x) = \sum_{m=1}^M \sum_{j=1}^J c_{mj} I(x \in R_{mj}) \tag{11-17} f(x)=fM​(x)=m=1∑M​j=1∑J​cmj​I(x∈Rmj​)(11-17)

标签:11,varTheta,推导,梯度,模型,tag,算法,GBDT,fm
From: https://blog.csdn.net/u013172930/article/details/143428457

相关文章

  • 聚类算法——Kernel K-Means (核K-均值聚类)聚类算法详解
    KernelK-Means聚类算法详解目录引言聚类算法概述K-Means算法回顾KernelK-Means算法概述KernelK-Means的工作原理核心思想与标准K-Means的区别KernelK-Means的算法步骤初始化计算核矩阵簇分配质心更新迭代与收敛数学基础目标函数核技巧(KernelTrick)特征映......
  • 聚类算法——Spherical K-Means聚类算法详解
    SphericalK-Means聚类算法详解聚类分析是数据挖掘和机器学习中的重要任务之一,其目的是将数据集中的对象分组,使得同一组内的对象相似度高,而不同组之间的对象相似度低。K-Means聚类算法是最经典和最广泛使用的聚类算法之一。然而,K-Means算法在处理高维稀疏数据或基于余弦相......
  • 【粒子群优化算法】基于Schwefel‘s P2.21函数的PSO算法变体性能分析(附完整算法Python
    基于Schwefel'sP2.21函数的PSO算法变体性能分析(附完整算法Python代码)摘要1.引言1.1研究目的2.算法与测试函数2.1Schwefel'sP2.21函数2.2PSO算法变体2.2.1标准PSO(SPSO)2.2.2自适应PSO(APSO)2.2.3改进的带变异PSO(IPSOM)2.2.4混合PSO(HPSO)3.实验设计3.......
  • 【Matlab算法】基于MATLAB实现时间序列预测(附MATLAB完整代码)
    基于MATLAB实现时间序列预测前言正文代码实现结果图结果说明总结前言时间序列预测是许多实际应用中的重要任务,涉及领域包括经济、金融、气象等。其中,自回归集成移动平均(ARIMA)模型是一种广泛使用的时间序列预测方法,因其简单有效而备受青睐。在本文中,......
  • 数据结构与算法(二叉树)
    鲸饮未吞海,剑气已横秋。 前言  这是我学习数据结构的第五份笔记,有关二叉树的知识。后期我会继续将数据结构知识的笔记补全。 上一期笔记有栈与列队,没看过的同学可以去看看:有关栈与列队的笔记https://blog.csdn.net/hsy1603914691/article/details/143064674?spm=10......
  • 02链表算法/代码随想录
    前几天忙比赛,算法停了三天,继续开刷,不能停!!二、链表2.1删除链表中的元素两种方案无哨头:要删除节点的前一个结点指向删除节点的指向节点。头节点需要单独定义有哨头:头节点不需要单独定义实战力扣203/***Definitionforsingly-linkedlist.*publicclassLis......
  • 【SSL-RL】自监督强化学习:Plan2Explore算法
            ......
  • pairwise算法之rank svm
    众所周知,point-wise/pair-wise/list-wise是机器学习领域中重要的几种建模方法。比如,最常见的分类算法使用了point-wise,即一条样本对应一个label(0/1),根据多条正负样本,使用交叉熵(crossentropy)等方法构建损失函数,来训练模型。顾名思义,Pairwise方法是一种基于样本对比较的排......
  • 从二维图像到三维重建:由运动到结构(SfM)的完整流程推导【含数学原理及推导】
    结构从运动(SfM)-稀疏特征点的3D重建1.引言由运动到结构(StructurefromMotion,SfM)是一种从二维图像序列中恢复三维结构和相机运动的技术。在SfM中,通过分析图像中稀疏的特征点,我们可以估计出相机在拍摄过程中经历的姿态变化,并重建出场景的三维几何结构。COLMAP等常用的Sf......
  • 动态规划 01背包(算法)
    现有四个物品,小偷的背包容量为8,怎么可以偷得价值较多的物品如:物品编号:1   2   3   4 物品容量:2   3   4   5物品价值:3   4   5   8记f(k,w),当背包容量为w,可以偷k件物品,所能偷到的最大价值以f(4,8)为列,记录每......