梯度提升树的算法流程与提升树类似，只是不再使用残差作为一棵树的拟合目标，而是使用损失函数的梯度作为拟合目标。梯度提升算法利用最速下降法的近似方法，考虑经验损失函数：
\[
\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+\beta f(x_i))
\]
其中，\(N\)为样本数，\(f_{m-1}(x_i)\)为第\(m-1\)步时所有树的累加，\(\beta\)为基学习器的系数，\(f(x_i)\)为本次要训练的树，即：
\[
f(x)=\sum_{j=1}^Jc_jI(x\in R_j)
\]
简单起见，考虑一个样本，对损失函数进行一阶泰勒展开：
\[
L(y_i,f_{m-1}(x_i)+\beta f(x_i))=L(y_i,f_{m-1}(x_i))+\beta f(x_i)\frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}
\]
由于\(\beta\)是大于0的，要使\(L(y_i,f_{m-1}(x_i)+\beta f(x_i))\leq L(y_i,f_{m-1}(x_i))\)，令
\[
f(x_i)=-\frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}
\]
每一个样本点上，上式尽可能成立的\(f(x_i)\)就是我们本次要构建的树。
简言之，对损失函数\(L(y,\hat{y})\)求关于\(f(x)\)的偏导，然后带入\(f_{m-1}(x)\)：
\[
r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}
\]
就是每一步上，一棵树需要拟合的目标。
梯度提升树算法流程
输入：训练数据集\(T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)},x_i\in X \subseteq \mathbb{R}^n,y_i\in Y \subseteq \mathbb{R}\)；损失函数\(L(y,f(x))\)
输出：回归树\(\hat{f(x)}\)
初始化
\[
f_0(x)=\mathop{argmin}_c\sum_{i=1}^NL(y_i,c)
\]
对\(m=1,2,...,M\):
a. 对\(i=1,2,...,N\)，计算\[ r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)} \]
b. 对\(r_{mi}\)拟合一个回归树，得到第\(m\)棵树的叶节点区域\(R_{mj},j=1,2,...,J\)
c. 对\(j=1,2,...,J\)，计算\[ c_{mj}=\mathop{argmin}_c\sum_{x\in R_{mj}}L(y_i,f_{m-1}(x_i)+c) \]
d. 更新\(f_m(x)=f_{m-1}(x)+\sum_{j=1}^Jc_{mj}I(x\in R_{mj})\)
获得回归树：
\[
\hat{f(x)}=f_M(x)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj})
\]
同样，梯度提升树的基学习器是回归树，加法模型中每个基学习器前的系数会内化到回归树内部，因此可省略。
注意到当使用\(r_{mi}\)拟合出一个回归树后，2-c进一步使用整体损失函数对这棵回归树的值进行了优化。这就是”先局部，后整体“的思想，就是先通过逐步的局部优化获得一个结果，然后从全局的角度优化结果。决策树的生成和剪枝也是这样，先通过局部优化，如信息增益等指标选择特征，得出一个决策树；再从降低整体损失的角度，进行剪枝。
梯度提升树和提升树的关系：
提升树每一次提升都是用上次的预测结果和训练数据真实值的误差作为新的训练数据进行进一步学习，而梯度提升树把对误差的拟合替换为对损失函数梯度的拟合。提升树主要缺点有：在回归问题中，提升树的平方损失目标函数对于异常值特别敏感；对于一些损失函数，不易优化，如绝对值损失函数等。
XGBoost
XGBoost是Boosting Tree的一种实现，相比于梯度提升树，XGBoost对损失函数进行了二阶泰勒展开，同时用到了一阶和二阶导数；并且引入了适用于树模型的正则化项用于控制模型的复杂度，正则化项包含树的叶子节点个数、叶子节点分数的\(L_2\)正则。
目标函数：
\[
Obj(\Theta)=L(\Theta)+\Omega (\Theta)\\
Obj=\sum_{i=1}^nl(y_i,\hat{y_i})+\sum_{k=1}^K\Omega(f_k)
\]
可以看到，目标函数包含两个部分：训练误差和树的复杂度。其中，树的复杂度包括：a.树的深度；b.内部节点个数；c.叶子节点个数(T)；d.叶子节点分数(w)
和梯度提升树的思路一致，
\[
\begin{split}
Obj^{(t)}&=\sum_{i=1}^nl(y_i,\hat{y_{i}}^{(t)})+\Omega(f_t(x))\\
&=\sum_{i=1}^nl(y_i,\hat{y_{i}}^{(t-1)}+f_t(x_i))+\Omega(f_t)+constant
\end{split}
\]
思考如何寻找一个\(f_t\)来优化这个目标函数。
这里和梯度提升树不同，XGBoost进行了二阶泰勒展开，令\(x=(y_i,\hat{y_i}^{(t-1)}),\Delta x=f_t(x_i)\)：
\[
Obj^{(t)}\approx \sum_{i=1}^n(l(y_i,\hat{y_i}^{(t-1)})+g_if_t(x)+\frac{1}{2}h_if_t^2(x_i))+\Omega(f_t)+constant
\]
其中，\(g_i\)为一阶导，\(h_i\)为二阶导
\[
g_i=\frac{\partial l(y_i,\hat{y}^{(t-1)})}{\partial \hat{y}^{(t-1)}},\\
h_i=\frac{\partial ^2 l(y_i,\hat{y}^{(t-1)})}{{\partial \hat{y}^{(t-1)}}^2}
\]
\(l(y_i,\hat{y_i}^{(t-1)})\)为常数项；\(f_t(x)=W_{q_{(x)}}\)为决策树表征的函数，\(w\in \mathbb{R}^T\)表示树的叶子权重，\(q(x)\)表示树结构，这是上述对决策树\(f(x)=\sum_{j=1}^Jc_jI(x\in R_j)\)的另一种记法。