GBDT(Gradient Boosting Decision Tree)是一种迭代的决策树算法，由多棵决策树组成，所有树的结论累加起来作为最终答案，我们根据其名字(Gradient Boosting Decision Tree)来展开推导过程。决策树(Decision Tree)我们已经不再陌生，在之前介绍到的机器学习之决策树(C4.5算法)、机器学习之分类与回归树(CART)、机器学习之随机森林中已经多次接触，在此不再赘述。但Boosting和Gradient方法是什么含义呢，又如何跟Decision Tree相结合?首先我们来了解集成学习中的Boosting概念。
集成学习不是单独的机器学习方法，而是通过构建并结合多个机器学习器来完成任务，集成学习可以用于分类问题集成、回归问题集成、特征选取集成、异常点检测集成等方面。其思想是对于训练数据集，我们通过训练若干个个体学习器，通过一定的结合策略形成一个强学习器，以达到博采众长的目的。在机器学习之随机森林中我们已经用到集成学习中的bagging方法，此处我们详细介绍集成学习中的Boosting方法。
从上图可以看出，Boosting算法的工作机制是从训练集用初始权重训练出一个弱学习器1，根据弱学习器的学习误差率来更新训练样本的权重，使得之前弱学习器1中学习误差率高的训练样本点权重变高。然后这些误差率高的点在弱学习器2中得到更高的重视，利用调整权重后的训练集来训练弱学习器2。如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。了解Boosting方法后，我们便可将Boosting方法和Decision Tree相结合便可得到Boosting Decision Tree。
**提升树(Boosting Decision Tree)**由于输出样本是连续值，因此我们通过迭代多棵回归树来共同决策。在机器学习之分类与回归树(CART)中我们已经详细推导分类树与回归树的构建过程，在此不再赘述。
我们利用平方误差来表示损失函数，其中每一棵回归树学习的是之前所有树的结论和残差，拟合得到一个当前的残差回归树。其中残差=真实值-预测值，提升树即是整个迭代过程生成的回归树的累加。
我们通过以下例子来详解算法过程，希望通过训练提升树来预测年龄。训练集是4个人，A、B、C、D年龄分别是14、16、24、26。样本中有购物金额、上网时长、经常到百度知道提问等特征。提升树的过程如下
我们能够直观的看到，预测值等于所有树值的累加，如A的预测值=树1左节点(15)+树2左节点(-1)=14。因此给定当前决策树模型ft-1(x)，只需拟合决策树的残差，便可迭代得到提升树，算法过程如下
我们介绍了Boosting Decision Tree的基本思路，但是没有解决损失函数拟合方法的问题。针对这个问题，Freidman提出用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。了解Boosting Decision Tree方法后，我们便可将Gradient与Boosting Decision Tree相结合得到Gradient Boosting Decision Tree的负梯度拟合。
Boosting Decision Tree迭代过程中，假设我们前一轮迭代得到的强学习器是 f t − 1 ( x ) f_{t-1}(x) ft−1(x)，损失函数是 L ( y , f t − 1 ( x ) ) L(y,f_{t-1}(x)) L(y,ft−1(x))，我们本轮迭代的目标是找到一个回归树模型的弱学习器 h t ( x ) h_t(x) ht(x)，让本轮的损失 L ( y , f t ( x ) ) = L ( y , f t − 1 ( x ) + h t ( x ) ) L(y,f_t(x))=L(y,f_{t-1}(x)+h_t(x)) L(y,ft(x))=L(y,ft−1(x)+ht(x))最小。也就是说，本轮迭代找到的决策树，要让样本的损失函数尽量变得更小。
我们利用损失函数 L ( y i , f ( x i ) ) L(y_i,f(x_i)) L(yi,f(xi))的负梯度来拟合本轮损失函数的近似值，进而拟合一个CART回归树。其中第t轮的第i个样本的损失函数的负梯度表示为
r t i = − [ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f t − 1 ( x ) r_{ti}=-\left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right]_{f(x)=f_{t-1}(x)} rti=−[∂f(xi)∂L(yi,f(xi))]f(x)=ft−1(x)
利用 ( x i , r t i ) i = 1 , 2 , 3 , … , m (x_i,r_{ti})i=1,2,3,…,m (xi,rti)i=1,2,3,…,m，我们可以拟合一棵CART回归树，得到第t棵回归树，其对应的叶节点区域为 R t j , j = 1 , 2 , 3 , … , J R_{tj},j=1,2,3,…,J Rtj,j=1,2,3,…,J，其中 J J J为叶子节点的个数。
针对每一个叶子节点中的样本，我们求出使损失函数最小，也就是拟合叶子节点最好的输出值 c t j c_{tj} ctj。其中决策树中叶节点值已经生成一遍，此步目的是稍加改变决策树中叶节点值，希望拟合的误差越来越小。
c t j = arg min ⎵ c ∑ x i ∈ R t j L ( y i , f t − 1 ( x i ) + c ) c_{tj}=\underset{c}{\underbrace{\arg\min}} \sum_{x_i \in R_{tj}}L(y_i,f_{t-1}(x_i)+c) ctj=c
argminxi∈R
