提升树和梯度提升树
集成学习主要分为boosting、bagging、stacking，随机森林属于bagging，而本文介绍的提升算法属于boosting，同为该类的还有Adaboost。提升方法实际采用加法模型（基函数的线性组合）与前向分布算法。
注：阅读前请熟悉CART回归树的构建过程。
1. 提升树
根据《统计学习方法》中提升树的定义，提升树是以分类树或回归树为基本分类器的提升方法。以决策树为基函数的提升方法称为提升树。提升树可以表示为决策树的加法模型。即
，其中$M$为决策树的个数，$\Theta$为决策树的参数（若是回归树，参数就是在哪个维度哪个点进行分裂）。
首先确定初始的提升树$f_0(x) = 0$，第$m$步的模型表达式是：
意思就是前一次的模型的值与第$m$步训练出来的决策树的和。
在第$m$步，
$L$为损失函数，在第$m$步时，$f_{m-1}(x) + T(x;\Theta_m)$即为$x$的预测值。$f_{m-1}(x)$的值已经确定（常数）。
在回归问题中，$L$为二次函数，
$r = y - f_{m-1}(x)$，为残差（真实值-预测值）。当$L$最小即$L = 0$，$r = T$，即这一棵树在拟合残差。在第$m$步，训练的这棵树是在拟合$f_{m-1}(x)$与$y$的差值即残差，以此不停的迭代。
个人想法：当在构建回归树时，采用了贪心的构建算法，因此，针对相同的$y$值，构建无数次都是同一棵树。因此，在提升树算法中，我们通过损失函数看到了，回归树是在拟合残差，即每一步输入到回归树中的y值是$y - f_{m-1}(x)$。
2. 梯度提升算法
针对提升树的优化问题，当损失函数是二次函数时，可以看到很好优化，但当损失函数为其他形式时，没有更好的优化方法，或者说优化比较困难。因此，$Fridemam$提出了梯度提升算法来优化提升树。回归问题和分类问题的区别是损失函数定义的不同。
针对回归问题的梯度提升算法，介绍如下：
（1）初始化
（2）对$m = 1,2,…M$
1）对$i = 1,2,3,…,N$ 计算
2）针对$r_{mi}$拟合一个回归树，得到第$m$棵树的叶子结点$R_{mj},j = 1,2,…,J$
3）对每个叶子结点$j = 1,2,…,J$，根据损失函数计算该叶子节点的权值（和1一样的问题，只有一个根节点的树）
4）更新$f_m(x) = f_{m-1}(x) + \sum_{j=1}^J c_{mj}I(x\in R_{mj})$
（3）得到最终的梯度提升树。
3. 梯度提升树（GBDT）
当梯度提升的损失函数为二次函数时，恰好，损失函数负梯度 == 伪残差。
还有就是，当损失函数为二次函数，第一步初始化的值是所有$y$值的均值。原因如下：
令$p(c) = \sum_{i=1}^N (y_i-c)^2$，$\partial p/ \partial c = -2\sum_{i=1}^N(y_i-c) = 0$，$c = (y_1 + y_2 + … + y_N) / N$。即初始化时，
与梯度下降不同的是，梯度提升是在函数空间求梯度，把函数作为参数来看待。而梯度下降是在参数空间求梯度。
当损失函数为二次函数，每个叶子结点最后的权值是划到该叶子结点所有y值的均值。(和初始化问题一样)。
4. XGBoost
xgboost与梯度提升树不同的是目标函数中加入了正则项，以及使用了二阶导数（目标函数泰勒展开式中用到了），结果更为精确，同时支持分布式并行计算（特征维度），在大规模机器学习中速度很快。本章介绍xgboost的推导，以及xgboost框架中是如何构建一棵xgboost树的。二阶泰勒展开：