1、boosting decision tree（提升树模型）
提升树模型其实是采用了加法模型的前向分布式算法，以决策树为基函数的提升方法称为提升树（boosting tree）
提升树模型
f_m = \sum_{i=1}^m T(x_i,\Theta_m)
其中$T(x_i,\Theta_m)$表示第$i$个决策树，$\Theta_m$为决策树的参数。
回归问题采用以下前向分布式算法
f_0 = 0
f_m = f_{m-1}+T(x_i,\Theta_m)
在前向分布式算法中，如果已经知道了$f_{m-1}$，那么就可以根据损失函数最小化求解出第$m$个树的参数$\Theta_{m}$：
\Theta_m = arg min_{\Theta_{m}} (L(y,f_{m-1}(x_i)+T(x_i,\Theta_{m})))
通过求解所有的$i$个树模型即可求得提升树。
如果提升树的损失函数为平方误差时,即损失函数的表达式为：$L(y,f(x)) = (y-f(x))^2$
那么提升树的损失函数跟第$i$个树的关系是：
L(y,f_{m-1}(x)+T(x,\Theta_{m})) = [y-f_{m-1}(x)-T(x,\Theta_{m})]^2
=(r_{i}-T(x,\Theta_{m}))^2
其中$r_{i}=y-f_{m-1}(x)$为当前数据的残差，所以对于回归问题的提升树算法来说，只需要简单的你和当前模型的残差。
2、gradient boosting decision tree（梯度提升树模型）
提升树利用加法模型与前向分布式算法实现学习器的游湖过程，当损失函数是平方损失函数和指数损失函数时，每一步优化都是很简单的，但是对于一般损失函数而言，往往每一步优化都不是那么容易，针对这一问题，大牛（Freidman）提出了梯度提升算法，这是利用最速下降法的近似方法，其关键就是利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差近似值，这样拟合一个回归树。
梯度提升树相对于回归问题提升树最大的区别便是：
对于回归问题梯度提升树：
r_{mi} = y-f_{m-1}(x)
而对于梯度提升树：残差用下述方程替代
r_{mi} = \frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}
gbdt算法可以总结如下：
输入：训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$；损失函数$L(y,f(x_i))$
输出：回归树$\hat f(x)$
1.初始化
f_{0} = arg min(\sum_{1}^N L(y_i,c))
2.对于$m=1,2,...,M$
(a)对于$i=1,2,...,N$，计算
r_{mi} = \frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}
(b)对于$r_{mi}$拟合一个回归树，得到第m颗树的叶节点区域$R_{mj}$，$j=1,2,...,J$
(c)对于$j=1,2,..J$，计算
c_{mj} = arg min_{c} \sum_{x_i \in R_{mj}} L(y_i,f_{m-1}(x_i)+c)
(d)更新$f_m(x) = f_{m-1}+\sum_{j=1}^J c_{mj}I(x \in R_{mj})$
(3)得到回归树：
\hat f(x) = \sum_{m=1}^M \sum_{j=1}^J c_{mj}I(x \in R_{mj})
3、xgboost
xgboost和xgboost有很大的相似点。我将在下面介绍xgboost如何构建树的模型
xgboost和gbdt最大的不同点在于目标函数的定义，xgboost的目标如下所示：
L(y,f_m(x)) = \sum_{i=1}^N l(y_i,f_{m-1}(x_i)+f_m(x_i))+\Omega(f_m(x_i))+constant
首先xgboost的目标函数是三项组成，分别是自定义损失函数，正则项，以及一个常数项。
xgboost实现的过程中是用泰勒展开公示求解原来的目标函数
泰勒二阶展开如下所示：
f(x+\Delta x) \approx f(x)+f^{'}(x)\Delta x + \frac{1}{2}f^{''}(x)\Delta x^2
因此损失函数的二阶展开式可以表示成如下形式：
L(y,f_m(x)) = \sum_{i=1}^N \left(l(y_i,f_{m-1}(x_i))+g_i f_m(x_i)+h_i f_m^2(x)\right) + \Omega(f_m(x))+constant
其中
g_i = \partial_{f_{m-1}(x)} l(y_i,f_{m-1}(x_i))
h_i = \partial_{f_{m-1}(x)}^2 l(y_i,f_{m-1}(x))
分别表示$l(y_i,f_{m-1}(x_i)) $的一阶导和二阶导
$\Omega(f_m(x))$表示正则项，以及树的复杂度，用下述公示来表示：
\Omega(f_m(x)) = \gamma T+\frac{1}{2}\lambda f_m^2(x)
因此上述的loss可以表示为如下形式：
L(y,f_m(x)) = \sum_{i=1}^N \left(l(y_i,f_{m-1}(x_i))+g_i f_m(x_i)+h_i f_m^2(x)\right) + \gamma T+\frac{1}{2}\lambda f_m^2(x)+constant
最终可以化简为：
L(y,f_m(x)) = \sum_{i=1}^N \left(l(y_i,f_{m-1}(x_i))+g_i f_m(x_i)+h_i f_m^2(x)\right) + \gamma T+\frac{1}{2}\lambda f_m^2(x)+constant
\frac {\partial L(y,f_m(x))}{w_{mj}} = \sum_{i \in I_j}g_i+ sum_{i \in I_j}hi f_m(x) + \lambda f_m{x}
当倒数为0时可以求得：
f_m(x) = \frac{\sum_{i \in I_j}g_i}{\sum_{i \in I_j}hi+\lambda}
上述的$f_m(x)$即为每轮新建的函数表达式。
