GBDT 算法的原理推导
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∑MT(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Θmmini=1∑NL(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∑KckI(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∑MT(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)=argcmini=1∑NL(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=argcminxi∈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∑JcmjI(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∑Mj=1∑JcmjI(x∈Rmj)(11-17)