写完公式发现原来可以写的这么复杂，简单点说就是，对于回归树$h$，如果$x$被归到某个叶子节点$R_j$，那么$x$在这个$h$中得到的预测值就是叶子节点$R_j$的值$c_j$。一般用叶子节点上 $\{x_i∈R_j \}_1^J$的$\{\tilde{y}_i\}_1^J$平均值近似节点$R_j$的值
$$c_j=ave_{x_i∈R_j}\tilde{y}_i $$
$\{R_j\}_1^J$是不相交的区域，集合覆盖预测值的空间。$\{c_j\}_1^J$可以认为是回归树$h$的系数。什么意思？我们回想一下线性回归，预测函数是$θ^T x$，这个$θ$就是模型系数。同样的，也可以这么理解$\{c_j\}_1^J$，是回归树$h$的系数。
ok，现在我们已经得到了回归提升树的预测函数：
$$F_m (x)=F_{m-1} (x)+ρ_m \sum_{j=1}^Jc_{m,j}I(x∈R_j)$$
令$γ_{m,j}=ρ_mc_{m,j}$，这个值是叶子节点的最理想的常数更新值，也可以认为兼顾了下降方向和下降步长。
综上，整理一下回归提升树的整个算法流程：
输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2),……,(x_N,y_N)\}$，迭代次数$M$
1. 初始化：$F_0 (x)=argmin_ρ\sum_{i=1}^NL(y,ρ)$ ,$N$表示样本量
2. For $m=1$ to $M$ do：
(a) 计算损失函数在当前模型$F_{m-1} (x)$的负梯度值：
$$\tilde{y}=-[\frac{∂ϕ(F(x))}{∂F(x)}]_{F(x)=F_{m-1}(x) }=y_i-F_{m-1}(x_i)，i=1,2,……,N$$
(b) 根据$\tilde{y}_i$学习得到了第$m$棵回归树，对应的叶节点区域为$\{R_j \}_1^J$
(c) $γ_{m,j}=argmin_γ\sum_{x_i∈R_{m,j}}L(y_i,F_{m-1}(x_i)+γ)$
(d) 得到本轮最佳拟合决策树为：
$$h_m(x;a)=\sum_{j=1}^Jγ_{m,j}I(x∈R_{m,j})$$
(e) 得到本次迭代得到的强学习器:
$$F_m(x)=F_{m-1}(x)+\sum_{j=1}^Jγ_{m,j}I(x∈R_{m,j})$$
3.结束迭代之后的强学习器为:
$$F_M(x)=\sum_{m=1}^M\sum_{j=1}^Jγ_{m,j}I(x∈R_{m,j})$$
当当当~看到第3点，我们发现损失函数在当前模型$F_{m-1}(x)$的负梯度值刚刚好是$y-F_{m-1}(x)$，也就是我们常说的残差！看到这里有没有很激动？这不就是我们常说的GBDT是在拟合前几轮迭代的残差吗？
下面给出证明：
令当前的预测函数模型为$F_{m-1}(x)$，下一棵要学习的回归树为$h_m (x;a)$，则下一步要学习的预测函数为：
$$F_m(x)=F_{m-1}(x)+h_m(x;a_m)$$
回归提升树的损失函数为平方损失：
$$Loss=L(F_m(x),y)=\frac{1}{2}(F_m(x)-y)^2$$
对$F_m (x)$求关于$a_m$的偏导：
$$\frac{∂Loss}{∂a_m}=(F_m(x)-y)=F_{m-1}(x)+h_m(x;a_m)-y$$
我们要使经验风险极小化，令偏导为0：
$$h_m(x;a_m)=y-F_{m-1}(x)$$
也就是说，构建的回归树要去拟合前面的残差，得证。可以这么理解，GBDT是在函数空间的梯度下降求最优值，当损失函数为平方损失时，恰好去拟合了残差。
下面给一个简单的例子方便理解，现在要通过购物金额和上网时长来预测年龄。假设有5个训练样本，标签分别14,17,13,25,27。第m轮迭代，通过前几轮的残差构建决策树，得到预测函数$F_m (x)$的预测年龄分别为16,15,12,19,29，计算残差-2,2,1,6,-2。第m+1轮迭代，就去学习这个残差，通俗一点说就是以残差作为第i+1轮迭代构建决策树的标签。
二元分类
我们使用负二项对数似然作为损失函数：
$$L(y,F)=log(1+exp(-2yF)),y∈\{1,1\}$$
其中，$F(x)=\frac{1}{2}log[\frac{P(y=1|x)}{P(y=-1|x)}]$
看这个公式有没有很熟悉？是的，这个负二项对数似然可以推到逻辑回归的损失函数。
我们知道逻辑回归的预测函数为:
$$P(y=1|x)=\frac{1}{1+exp(-θ^Tx)},y∈\{0,1\}$$
我们知道这里的负样本y=-1对应于逻辑回归里的负样本y=0，所以有：
$$F(x)=\frac{1}{2}log[\frac{P(y=1|x)}{P(y=-1|x)}]=\frac{1}{2}log[\frac{P(y=1|x)}{P(y=0|x)}]=\frac{1}{2}θ^Tx$$
将上式代入$L(y,F)$，可得$L(y,F)=log(1+exp(-2yF))=log(1+exp(-yθ^Tx)),y∈\{-1,1\}$
当y=1时，$L(y,F)= log(1+exp(-θ^T x))=y log(1+exp(-θ^T x) )=ylog(P(y=1|x))$
当y=-1时，$L(y,F)=log(1+exp(θ^T x) )=log(1-P(y=1|x))$
令$y$←0，$L(y,F)=(1-y)log(1-P(y=1|x))$
结合在一起，可以写成：
$$L(y,F)=ylog(P(y=1|x))+(1-y)log(1-P(y=1|x))，y∈\{0,1\}$$
与逻辑回归损失函数一致，得证。
预测函数$F_{m-1} (x)$的当前负梯度值，也可以说是伪响应$\tilde{y}$为：
$$\tilde{y}=-[\frac{∂L(F(x),y)}{∂F(x)}]_{F(x)=F_{m-1}(x)}=\frac{2y}{1+exp(2yF_{m-1}(x))}$$
我们仍然将回归树作为基学习器，进行线搜索得到最优叶子节点值：
$$γ_{m,j}=argmin_y\sum_{x∈R_{m,j}}log(1+(-2y(F_{m-1}(x)+γ)))$$
一看这个公式就知道计算量不是一般的大，我们用[Newton-Raphson近似][2]，得到:
$$γ_{m,j}=\frac{\sum_{x∈R_{m,j}}\tilde{y}_i}{\sum_{x∈R_{m,j}}|\tilde{y}_i|(2-|\tilde{y}|)}$$
总结一下算法流程如下：
1. 初始化：$F_0 (x)=argmix_ρ\sum_{i=1}^NL(y,ρ)$ ,$N$表示样本量
2. For $m=1$ to $M$ do：3. end For
(a) $\tilde{y}_i=\frac{2y_i}{1+exp(2y_iF_{m-1}(x_i))},i=1,2,……,N$
(b) 根据$\tilde{y}_i$学习得到了第m棵回归树，对应的叶节点区域为$\{R_j\}_1^J$
(c) $γ_{m,j}=\frac{\sum_{x∈R_{m,j}}\tilde{y}_i}{\sum_{x∈R_{m,j}}|\tilde{y}_i|(2-|\tilde{y_i}|)}$
(d) $F_m (x)=F_{m-1} (x)+\sum_{j=1}^Jγ_{m,j} I(x∈R_{m,j})$
最后，我们得到了预测函数$F_M(x)$，用来进行概率估计：
$$P(y=1|x)=p=\frac{e^{2F(x)}}{1+e^{2F(x)}}=\frac{1}{1+e^{-2F(x)}}$$
$$P(y=-1|x)=1-p=\frac{1}{1+e^{2F(x)}}$$
有了概率之后，我们可以对样本进行分类。
多元分类
我们使用多分类log损失作为损失函数：
$$L(y,F)=-\sum_{k=1}^{K}y_klogp_k(x)$$
对应的概率$p_k(x)$为（就是softmax）：
$$p_k (x)=\frac{e^{F_k (x)}}{\sum_{l=1}^Ke^{F_l (x)}}$$
对于多分类问题，在构建基学习器时，我们要为每个类别k创建一棵回归树$F_k (x)，k=1,2,……，K$
$$\tilde{y}_{i,k}=y_{i,k}-p_{k,m-1} (x_i)$$
因此，每次迭代m，以概率角度来计算当前残差。
叶子节点值近似为：
$$γ_{m,j}=\frac{K-1}{K}\frac{\sum_{x∈R_{m,j}}\tilde{y}_i}{\sum_{x∈R_{m,j}}|\tilde{y}_i|(2-|\tilde{y}|)}$$
面经
GBDT为什么是在拟合前面几轮的残差？请公式推导。