从提升树出发，——》回归提升树、二元分类、多元分类三个GBDT常见算法。
提升树
梯度提升树
回归提升树
二元分类
多元分类
面经
提升树
在说GBDT之前，先说说提升树（boosting tree）。说到提升（boosting），总是绕不过AdaBoost。
AdaBoost是利用前一轮迭代的误差率来更新训练集的权重，校正前一轮迭代被错误分类的样本，通俗一点的理解就是将重心放在分错的样本上。提升树也是boosting家族的成员，意味着提升树也采用加法模型（基学习器线性组合）和前向分步算法。
下面一个一个进行解释，提升树的基学习器是什么，加法模型和前向分步算法又是怎么用的。
提升树通常以决策树作为基学习器，对分类问题决策树是二叉分类树，回归问题就是二叉回归树。
加法模型，就是说提升树可以表示为以下形式：这里我们约定 $ T(x;Θ_m ) $表示第m棵决策树；$ Θ_m $表示决策树的参数；$ M $为树的个数。强分类器$f_M (x)$可以由多个弱分类器$T(x;Θ_m )$线性相加而成。
$$f_M (x)=\sum_{m=1}^MT(x;Θ_m ) $$
提升树的前向分步算法。第m步的模型可以写成：
$$f_m (x)=f_{m-1} (x)+ T(x;Θ_m )$$
然后得到损失函数
$$L(f_m (x),y)=L(f_{m-1} (x)+ T(x;Θ_m ),y)$$
迭代的目的是构建$T(x;Θ_m )$，使得本轮损失$L(f_m (x),y)$最小。思想其实并不复杂，但是问题也很明显，对于不同的任务会有不同的损失函数，当损失函数是平方损失和指数损失函数时，每一步的优化还是简单的。但是对于一般损失函数而言，每一步的优化并不容易。
梯度提升树
下面关于GBDT的理解来自论文greedy function approximation: a gradient boosting machine
损失函数的数值优化可以看成是在函数空间，而不是在参数空间。
损失函数$L(y,F)$包含平方损失$(y-F)^2$，绝对值损失$|y-F|$用于回归问题，负二项对数似然$log(1+e^{-2yF} )$,y∈{-1,1}用于分类。
关注点是预测函数的加性扩展。
最关键的点在于损失函数的数值优化可以看成是在函数空间而不是参数空间。怎么理解呢？
首先，我们已经知道强分类器是由多个弱分类器线性相加而成，那么可以写成如下形式：
$$F(x;\{β_m,a_m \}_1^M )=\sum_{m=1}^Mβ_m h(x;a_m )$$
这里的$h(x;a_m )$指代回归树，例如CART。$a_m$是模型参数，这里指代每个节点的分裂特征（变量），最佳分割点，节点的预测值。$M$就是有多少个弱分类器。
然后，我们来回顾一下参数空间的数值优化。假设预测函数为$F(x;P)$，那么损失函数就可以写成：
$$ ϕ(P)=L(y,F(x,P))$$
优化以后得到的参数最优解为：
$$P^~=argmin_P ϕ(P) $$
回想一下SGD（随机梯度下降）的优化方式，从山顶上选择梯度下降最快的方向挪动最优步长。我们是不是可以把最优参数表达成这个形式？
$$P^~=\sum_{m=0}^Mp_m $$
$$p_m=-ρ_m g_m$$
从初始值$p_0$开始，$m$对应每一步更新迭代，负梯度$-g_m$就是最速下降方向，$ρ_m$就是在这个最速下降方向上进行线搜索得到的最优步长。
好了，现在我们说说函数空间的优化方法。
将预测函数$F(x)$对应参数$P$，最优解变成了：
$$F(x)=\sum_{m=0}^Mf_m (x)$$
相当于在函数空间上作梯度下降。每一步梯度下降：
$$f_m(x)=-ρ_m g_m(x)$$
$$g_m (x)=[\frac{-∂ϕ(F(x))}{∂F(x)} ]_{F(x)=F_{m-1} (x) }$$
$$F_{m-1}(x)=\sum_{i=0}^{m-1}f_i(x)$$
现在把这个思想代入到gradient boosting，我们之前已经得到预测函数为：
$$F(x;\{β_m,a_m \}_1^M )=\sum_{m=1}^Mβ_m h(x;a_m ) $$
需要做的事情是得到预测函数的最优解，就是：
$$\{\textbf{β}_m, \textbf{a}_m \}_1^M= argmin_{\{β_m,a_m\}_1^M} L(y,\sum_{m=1}^Mβ_m h(x;a_m ))= argmin_{β_m,a_m} L(y,F_{m-1} (x)+β_mh_m (x;a_m))$$
已知最速梯度下降方向为$g_m (x)=[\frac{-∂ϕ(F(x))}{∂F(x) }]_{F(x)=F_{m-1} (x) }$，每一个$h_m (x;a_m)$都建立在最速梯度下降的方向，我们可以得到：
$$\textbf{a}_m=argmin_{β_m,a_m} [-g_m (x)-β_mh_m (x;a_m) ]^2$$
可以认为是用$h_m (x;a)$去拟合伪标签$\tilde{y}=-g_m (x)$。这里为什么用最小二乘，我的理解是GBDT构造的树全是回归树，因此用最小二乘。
然后进行线搜索确定最优步长$ρ_m$：
$$\textbf{ρ}_m= argmin_{ρ_m} L(y,F_{m-1}(x)+ρ_mh_m (x;\textbf{a}_m))$$
$$F_m (x)=F_{m-1} (x)+ \textbf{ρ}_m h_m (x;\textbf{a}_m) $$
ok,现在来整理整个算法流程：
初始化：$F_0 (x)=argmix_ρ\sum_{i=1}^NL(y_i,ρ)$ ,$N$表示样本量
For $m=1$ to $M$ do：end for
$\tilde{y}=-[\frac{∂ϕ(F(x))}{∂F(x)} ]_{F(x)=F_(m-1) (x) }，i=1,2,……,N$
$\textbf{a}_m=argmin_{β,a}\sum_{i=1}^N [\tilde{y}-βh_m (x_i;a) ]^2$
$\textbf{ρ}_m= argmin_ρ\sum_{i=1}^N L(y_i,F_{m-1} (x_i)+ρh_m (x_i;\textbf{a}_m ))$
$F_m (x)=F_{m-1} (x)+\textbf{ρ}_m h_m (x;\textbf{a}_m)$
回归提升树当基学习器$h(x;a)$是一个包含J个节点的回归树时，可以写成：
$$h(x;a)=h(x;\{c_j,R_j\}_1^J)=\sum_{j=1}^Jc_jI(X∈R_j)$$