提升树是以分类树或者回归树为基本分类器的提升方法。提升方法采用的加法模型和前向分布算法。提升树模型可以表示为决策树的加法模型：
梯度提升树采用的是前向分布算法。第m步骤的模型为：
则，通过经验风险极小化来确定下一棵数的参数$W_m$,
一阶的GBDT
考虑一阶泰勒展开，对$obj(m)= \Sigma_{n=1}^N L(y_n,f_{m-1}(x_n)+T(x_n;W_m)$在$f_{m-1}(x)$处展开有：
对近似一阶展开最小化，可知：$L(y_n,f_{m-1}(x_n))$,$\frac{\partial L(y_n,f(x_n))}{\partial f _{m-1}(x_n) }$都是constant，因为为了最小化(4)，只要求：
这个就得到了梯度提升树的算法，新的一颗树是通过拟合负梯度得到的。
需要注意的是，当$L(y,f_m(x))$选为平方函数的时候，上述的负梯度即残差。
二阶的GBDT
考虑二阶展开，有：
可以缩写为：
由于函数中的常量在优化过程中不起影响，因此可以省略，(7)可以进一步写为：
在更一般的机器学习的目标函数中，会通过添加一个正则项，来达到一个最小化结构化误差的作用，因此(8)进一步写为：
最常见的一个二阶的GBDT模型为Xgboost模型。
Xgboost
这里假设一棵决策树，叶子节点个数为$M$,该决策树是由叶子节点上的值组成的向量$\omega \in R^M$，以及一个将一个特征向量映射到叶子节点的索引函数$q:R^d \rightarrow \{1,2,…,M\}$ 组成的。因此一个决策树可以重新写为：$T(x)=\omega_{q(x)}$
此时正则项定义为：$\Omega(T) = \gamma M + \frac{1}{2} \lambda \Sigma_{j=1}^M\omega^2$来定义。此时为叶子j定义一个样本集合为：$I_j = \{n|q(x_n)=j\}$
上面的目标函数可以重新写为：
定义$G_n = \Sigma_{n \in I_j}g_n,H_n=(\Sigma_{n \in I_j}h_n)$,那么上面的目标函数可以写为：
对于一个单变量二次方程式:
假设树的结构是固定的，那么每个叶子的最佳权重为：
如果给定一个树的结果，可以用上面的公式计算出得分，并且为每个叶子赋值。但是问题是，如何找到一个合适的结构。
xgb中的方法是贪婪的
树从深度0开始
对树的每一个叶子节点，尝试增加一个划分。目标函数的变化程度为：
对于每一个节点，遍历所有的特征：
- 对于每一个特征，根据特征值对样本进行排序
- 使用线性扫描的方法去决定特征的最佳划分
- 选择所有特征中最佳的特征
回到GBDT，生成的树要加到原来的模型上：
这里$\epsilon$被称为步长或者收缩，一般设置为0.1左右。这个意味着在每一步没有做最好的优化，保留了后面的轮数，有助于防止过拟合。
除了步长外，xgb还有其他的防止过拟合的措施：
Early Stopping：本质是在某项指标达标后就停止训练，也就是设定了训练的轮数
Subsampling：无放回抽样，具体含义是每轮训练随机使用部分训练样本，其实这里是借鉴了随机森林的思想
colsample_bytree: 训练的过程中，使用的特征以一定的比例从所有的特征中采样。
max_depth: 树的深度，树越深越容易过拟合
min_child_weight: 值越大，越容易欠拟合。
参考
[李航《统计学习方法》]: