梯度提升决策树(Gradient Boosting Decision Trees,GBDT)

2024-01-09 14:52:11

梯度提升决策树(Gradient Boosting Decision Trees,GBDT)

? 提升树是以分类树或回归树为基本分类器的提升方法。 提升树被认为是统计学习 中性能最好的方法之一。

? 提升方法实际采用加法模型(即基函数的线性组合)与前向分步算法。 以决策树为基函数的提升方法称为提升树 (boosting tree)。 对分类问题决策树是二叉分类树, 对回归问题决策树是二叉回归树

---------------------------------------------------------------------------------------------------------------------------------------

输入:线性可分训练数据集 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 ∈ X = R n , y i ∈ Y , i = 1 , 2 , … , N x_i∈X=R^n,y_i∈Y, i = 1,2,…,N xi?X=Rn,yi?Y,i=1,2,,N;弱学习算法

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

优化问题

? 不同问题的提升树学习算法,其主要区别在于使用的损失函数不同。回归问题:平方误差损失函数;分类问题:指数损失函数。

? f m ? 1 ( x ) f_{m-1}(x) fm?1?(x) 为当前模型,通过经验风险极小化确定下一颗决策树的参数 Θ m \Theta_m Θm?
Θ ^ m = a r g ? m i n Θ m ∑ i = 1 N L ( y i , f m ( x ) ) → Θ ^ m = a r g ? m i n Θ m ∑ i = 1 N L ( y i , f m ? 1 ( x i ) + T ( x ; Θ m ) ) \hat\Theta_m=arg\ \underset{\Theta_m}{min}\sum_{i=1}^NL(y_i,f_m(x))\\ \\ →\hat\Theta_m=arg\ \underset{\Theta_m}{min}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x;\Theta_m)) Θ^m?=arg?Θm?min?i=1N?L(yi?,fm?(x))Θ^m?=arg?Θm?min?i=1N?L(yi?,fm?1?(xi?)+T(x;Θm?))
回归问题:
Θ ^ m = a r g ? m i n Θ m ∑ i = 1 N ( y i ? f m ( x ) ) 2 → Θ ^ m = a r g ? m i n Θ m ∑ i = 1 N ( y i ? f m ? 1 ( x ) ? T ( x ; Θ m ) ) 2 → Θ ^ m = a r g ? m i n Θ m ∑ i = 1 N ( r ? T ( x ; Θ m ) ) 2 , r = y ? f m ? 1 ( x ) \hat\Theta_m=arg\ \underset{\Theta_m}{min}\sum_{i=1}^N(y_i-f_{m}(x))^2\\ \\ →\hat\Theta_m=arg\ \underset{\Theta_m}{min}\sum_{i=1}^N(y_i-f_{m-1}(x)-T(x;\Theta_m))^2\\ \\ →\hat\Theta_m=arg\ \underset{\Theta_m}{min}\sum_{i=1}^N(r-T(x;\Theta_m))^2,r=y-f_{m-1}(x) Θ^m?=arg?Θm?min?i=1N?(yi??fm?(x))2Θ^m?=arg?Θm?min?i=1N?(yi??fm?1?(x)?T(x;Θm?))2Θ^m?=arg?Θm?min?i=1N?(r?T(x;Θm?))2,r=y?fm?1?(x)

分类问题:
Θ ^ m = a r g ? m i n Θ m ∑ i = 1 N e x p ( ? y i f m ( x ) ) → Θ ^ m = a r g ? m i n Θ m ∑ i = 1 N e x p [ ? y i ( f m ? 1 ( x ) + T ( x ; Θ m ) ) ] \hat\Theta_m=arg\ \underset{\Theta_m}{min}\sum_{i=1}^Nexp(-y_if_m(x))\\ \\ →\hat\Theta_m=arg\ \underset{\Theta_m}{min}\sum_{i=1}^Nexp[-y_i(f_{m-1}(x)+T(x;\Theta_m))] Θ^m?=arg?Θm?min?i=1N?exp(?yi?fm?(x))Θ^m?=arg?Θm?min?i=1N?exp[?yi?(fm?1?(x)+T(x;Θm?))]
---------------------------------------------------------------------------------------------------------------------------------------

? 提升树模型可以表示为决策树的加法模型:
f M ( x ) = ∑ m = 1 M T ( x ; Θ m ) f_M(x)=\sum_{m=1}^MT(x;\Theta_m) fM?(x)=m=1M?T(x;Θm?)
其中, T ( x ; Θ m ) T(x;\Theta_m) T(x;Θm?)表示决策树, Θ m \Theta_m Θm?为决策树的参数,M为树的个数。

? 首先确定初始提升树 f 0 ( x ) = 0 f_0(x)=0 f0?(x)=0,第m步的模型是:
f m ( x ) = f m ? 1 ( x ) + T ( x ; Θ m ) f_{m}(x)=f_{m-1}(x)+T(x;\Theta_m) fm?(x)=fm?1?(x)+T(x;Θm?)

回归问题的提升树

? 已知一个训练数据集 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 ∈ X = R n , y i ∈ Y , i = 1 , 2 , … , N x_i∈X=R^n,y_i∈Y, i = 1,2,…,N xi?X=Rn,yi?Y,i=1,2,,NX 为输入空间,Y 为输出空间。

? 如果将输入空间划分为J 个互不相交的区域 R 1 , R 2 , . . . , R J R_1,R_2,...,R_J R1?,R2?,...,RJ? ,并且在每个区域上确定输出的常量 c j c_j cj? ,那么树可以表示为:
T ( x ; Θ ) = ∑ j = 1 J c j I ( x ∈ R j ) T(x;\Theta)=\sum_{j=1}^Jc_jI(x∈R_j) T(x;Θ)=j=1J?cj?I(xRj?)
其中,参数 Θ = { ( R 1 , c 1 ) , ( R 2 , c 2 ) , . . . , ( R J , c J ) } \Theta=\{(R_1,c_1),(R_2,c_2),...,(R_J,c_J)\} Θ={(R1?,c1?),(R2?,c2?),...,(RJ?,cJ?)} 表示树的区域划分和各个区域上的常数。J 是回归树的复杂度即叶节点个数。

回归问题的前向分布算法

f 0 ( x ) = 0 f m ( x ) = f m ? 1 ( x ) + T ( x ; Θ m ) , ??? m = 1 , 2 , . . . , M f M ( x ) = ∑ m = 1 M T ( x ; Θ m ) f_0(x)=0\\ \\ f_m(x)=f_{m-1}(x)+T(x;\Theta_m),\ \ \ m=1,2,...,M\\ \\ f_M(x)=\sum_{m=1}^MT(x;\Theta_m) f0?(x)=0fm?(x)=fm?1?(x)+T(x;Θm?),???m=1,2,...,MfM?(x)=m=1M?T(x;Θm?)

第m步时,当前模型是 f m ? 1 ( x ) f_{m-1}(x) fm?1?(x) ,要求解以下的式子(回归问题采用均方误差损失函数)得到 Θ ^ m \hat\Theta_m Θ^m?
Θ ^ m = a r g ? m i n Θ m ∑ i = 1 N ( y i ? f m ( x ) ) 2 → Θ ^ m = a r g ? m i n Θ m ∑ i = 1 N ( y i ? f m ? 1 ( x ) ? T ( x ; Θ m ) ) 2 → Θ ^ m = a r g ? m i n Θ m ∑ i = 1 N ( r ? T ( x ; Θ m ) ) 2 , r = y ? f m ? 1 ( x ) \hat\Theta_m=arg\ \underset{\Theta_m}{min}\sum_{i=1}^N(y_i-f_{m}(x))^2\\ \\ →\hat\Theta_m=arg\ \underset{\Theta_m}{min}\sum_{i=1}^N(y_i-f_{m-1}(x)-T(x;\Theta_m))^2\\ \\ →\hat\Theta_m=arg\ \underset{\Theta_m}{min}\sum_{i=1}^N(r-T(x;\Theta_m))^2,r=y-f_{m-1}(x) Θ^m?=arg?Θm?min?i=1N?(yi??fm?(x))2Θ^m?=arg?Θm?min?i=1N?(yi??fm?1?(x)?T(x;Θm?))2Θ^m?=arg?Θm?min?i=1N?(r?T(x;Θm?))2,r=y?fm?1?(x)
算法流程:

输入:线性可分训练数据集 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 ∈ X = R n , y i ∈ Y , i = 1 , 2 , … , N x_i∈X=R^n,y_i∈Y, i = 1,2,…,N xi?X=Rn,yi?Y,i=1,2,,N;弱学习算法

输出:提升树 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。

? (a)按照 T ( x ; Θ ) = ∑ j = 1 J c j I ( x ∈ R j ) T(x;\Theta)=\sum_{j=1}^Jc_jI(x∈R_j) T(x;Θ)=j=1J?cj?I(xRj?)计算残差:
r m i = y i ? f m ? 1 ( x i ) , ??? i = 1 , 2 , . . . , N r_{mi}=y_i-f_{m-1}(x_i),\ \ \ i=1,2,...,N rmi?=yi??fm?1?(xi?),???i=1,2,...,N
? (b)拟合残差 r m i r_{mi} rmi?学习一个回归树,得到 T ( x ; Θ m ) T(x;\Theta_m ) T(x;Θm?)

? (c)更新 f m ( x ) = f m ? 1 ( x ) + T ( x ; Θ m ) f_m(x)=f_{m-1}(x)+T(x;\Theta_m) fm?(x)=fm?1?(x)+T(x;Θm?)

(3)得到回归问题的提升树
f M ( x ) = ∑ m = 1 M T ( x ; Θ m ) f_M(x)=\sum_{m=1}^MT(x;\Theta_m) fM?(x)=m=1M?T(x;Θm?)

梯度提升

? 提升树算法利用加法模型与前向分布算法实现学习的优化过程。当损失函数时平方损失和指数损失函数的时候,每一步的优化时很简单的。但是对于一般损失函数而言,往往每一步优化都不是容易的。

? 其关键是利用损失函数的负梯度在当前模型的值
? [ ? 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)=fm?1?(x)?
作为回归问题提升树算法中的残差的近似值,拟合一个回归树。

算法流程:

输入:线性可分训练数据集 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 ∈ X = R n , y i ∈ Y , i = 1 , 2 , … , N x_i∈X=R^n,y_i∈Y, i = 1,2,…,N xi?X=Rn,yi?Y,i=1,2,,N;损失函数 L ( y , f ( x ) ) L(y,f(x)) L(y,f(x)) ;

输出:提升树 f ^ ( x ) \hat f(x) f^?(x)

(1)初始化 f 0 ( x ) = a r g m i n c ∑ i = 1 N L ( y i , c ) f_0(x)= arg \underset{c}{min}\sum_{i=1}^NL(y_i,c) f0?(x)=argcmin?i=1N?L(yi?,c)

(2)对m=1,2,…,M。

? (a)对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)=fm?1?(x)?
? (b)拟合残差 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

? (c)对j=1,2,…,J,计算
c m j = a r g ? m i n c ∑ x i ∈ R m j L ( y i , f m ? 1 ( x i ) + c ) c_{mj}=arg\ \underset{c}{min}\sum_{x_i∈R_{mj}}L(y_i,f_{m-1}(x_i)+c) cmj?=arg?cmin?xi?Rmj??L(yi?,fm?1?(xi?)+c)
? (d)更新 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_{j=1}^Jc_{mj}I(x∈R_{mj}) fm?(x)=fm?1?(x)+j=1J?cmj?I(xRmj?)

(3)得到回归树
f ^ ( x ) = f M ( x ) = ∑ m = 1 M ∑ j = 1 J c m j I ( x ∈ R m j ) \hat f(x)=f_M(x)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x∈R_{mj}) f^?(x)=fM?(x)=m=1M?j=1J?cmj?I(xRmj?)

文章来源:https://blog.csdn.net/Gaowang_1/article/details/135479070
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。