GBDT介绍
GBDT(Gradient Boosting Decision Tree)在数据分析和预测中的效果很好。它是一种基于决策树的集成算法。其中Gradient Boosting 是集成方法boosting中的一种算法，通过梯度下降来对新的学习器进行迭代。而GBDT中采用的就是CART决策树。
Boosting
Boosting指把多个弱学习器相加，产生一个新的强学习器，经典的例子有：adaboost, GBDT, xgboost等。如果每一个弱学习器用 $f_i(x)$ 来表示的话，那么Boosting的强学习器就可以表示为$F(x)=\sum f_i(x)$。 接下来，我们就介绍一下Gradient Boosting是如何产生强学习器的：
Gradient Boosting
首先，举个例子。例如我们给定的特征x和对应的结果y是：
$$
x=(1,2,3)\
y=(11,12,13)
$$
我们假设给定的第一个弱学习器为$f_1(x)=x$，显然，这个学习器很弱。产生的结果$f_1(x)=(1,2,3)$ 。那我们如何来改进这个学习器呢？Boosting的思想就是，我们可以给这个弱学习器再加另一个学习器，来提高效果。经过观察我们发现，如果给第一个学习器加上一个常数10，那这个学习器就完美了。于是我们就有了
$$
f_2(x)=10,\
F(x)=f_1(x)+f_2(x)=(11,12,13)
$$
这就完美地拟合了数据。而这个常数10就是对应的$y-x$，即对应的残差。于是，一个很朴素的思想就出来了，即每次新的学习器的学习目标就是由残差产生。所以，我们假设已有n-1个弱学习器$f_i(x)$组合而成的强学习器：
$$
F_{n-1}(x)=\sum_{i=1}^{n-1} f_i(x)
$$
而学习器$f_n(x)$就把$y-F_{n-1}(x)$看做新的y，即学习的目标，进行学习。之后，我们就可以得到一个新的更强的学习器：
$$
F_n(x)=F_{n-1}(x)+f_n(x)
$$
而其实残差呢，本质上就是二次损失函数$L(y,F)=\frac{1}{2}(y-F(x))^2$的导数的负数，即：
$$
y-F(x)=-\frac{1}{2}\times\frac{\part(y-F(x))^2}{\part F(x)}=-\frac{\part L(y,F(x))}{\part F(x)}
$$
也就是对应二次损失函数的负梯度，这也就是Gradient boosting的梯度下降的思想。并且，我们也可以将这里的二次损失函数替换成其他的损失函数，来减少异常点对于模型的影响。例如可以使用如下的Huber损失函数：
$$
L(y,F)=\left{\begin{array} a\frac{1}{2}|y-F(x)| &|y-F(x)|<\delta
\ \delta(|y-F(x)|-\delta/2) &|y-F(x)|\geq\delta
\end{array}\right.
$$
GBDT
而GBDT则是把CART决策树作为每次弱分类器学习的方法，GBDT具体的算法如下（截图来自《The Elements of Statistical Learning》）：
