梯度下降决策树(Gradient Boosting Decision Tree)是Boosting算法中的一种，本文对其进行简单的推导，并与xgboost对比。
GBDT
假设存在K个树，则输出为：
假设已学习了t-1个树，现在要学习第t个树，$\hat{y_i}$为样本$x_i$的$t-1$颗树的学习结果，$y_i$为样本标记，损失函数为任意可微函数，则优化目标为：
现在只考虑一个样本，将(2)式在$\hat{y_i}$点泰勒展开：
若令$f_t(x_i)= -\frac {\partial l}{\partial \hat{y_i}} |_{\hat{y_i}}$，则函数值下降。所以将负梯度值作为下一颗树的输入，训练回归树。
具体过程如下
训练过程中为了防止过拟合，可以人为设置树的深度等参数。
XGboost
可以参考原论文