原理

与传统决策树不同的是，传统的决策树中每次决策是Heuristic（启发式）的（比如信息增益），而这里，每次决策都是Objective（目标性质的，与目标函数相关）。

Boosting Tree Model

提升树（Boosting tree）是以分类树或回归树为基本分类器的提升方法。提升数被认为是统计学习中性能最好的方法之一。

提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树（boosting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。提升树模型可以表示为决策树的加法模型：

\[f_M(x) = \sum_{m=1}^M T(x;\theta_m)\]

其中，\(T(x,\theta_m)\)表示决策树；\(\theta_m\)为决策树的参数；M为树的个数。

Boosting Tree algorithm

提升树算法采用前向分布算法。首先确定初始提升树\(f_0(x)=0\)，第m步的模型是

\[f_m(x) = f_{m-1}(x)+T(x; \theta_m)\]

其中，f_{m-1}(x)为当前模型，通过经验风险极小化确认下一棵决策树的参数\(\theta_m\)，

\[\hat{\theta}_m =arg min_{\theta_m} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + T(x_i; \theta_m))\]

由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。

下面讨论针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括平方误差损失函数的回归问题，用指数损失函数的分类问题，以及用一般损失函数的一般决策问题。

对于二类分类问题，提升树算法只需将基本分类器限制为二分类即可，可以说这时的提升树算法是AdaBoost算法的特殊情况，这里不再细述。

下面叙述回归问题的提升树。

已知一个训练数据集\(T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}, x_i \in X \subseteq R^n\)，X为输入空间，\(y_i \in Y \subseteq R\)，Y为输出空间。在决策树中已经讨论了回归树的问题。如果将输入空间X划分为J个互不相交的区域\(R_1, R_2,...,R_J\)，并且在每个区域上确定输出的常量\(c_j\)，那么树可以表示为

\[T(x; \theta) = \sum_{j=1}^J c_j I(x \in R_j)\]

其中，参数\(\theta={(R_1,c_1),(R_2,c_2),...,(R_J,c_J)}\)表示树的区域划分和各区域上的常数，J是回归树的复杂度即叶结点个数。

回归问题提升树使用以下向前分步算法：

\[f_0(x)=0\] \[f_m(x)=f_{m-1}(x)+T(x;\theta_m), m=1,2,...,M\] \[f_M(x)=\sum_{m-1}^M T(x;\theta_m)\]

在前向分布算法的第m步，给定当前模型\(f_{m-1}(x)\)，需求解

\[\hat{\theta}_m = arg min_{\theta_m} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + T(x_i; \theta_m))\]

得到\(\hat{\theta}_m\)，即第m棵树的参数。

当采用平方误差损失函数时，

\[L(y,f(x)) = (y-f(x))^2\]

其损失变为

\[\begin{align} &L(y,f_{m-1}(x) + T(x;\theta_m)) \\ &=[y-f_{m=1}(x)-T(x;\theta_m)]^2 \\ &=[r-T(x;\theta_m)]^2\\ \end{align}\]

这里，

\[r=y-f_{m-1}(x)\]

是当前模型拟合数据的残差（residual）。所以，对回归问题的提升树算法来说，只需简单地拟合当前模型的残差。这样，算法是相当简单的。

回归问题的提升树算法：

输入：训练数据集\(T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}, x_i \in X \subseteq R^n, y_i \in Y \subseteq R\);

输出：提升树\(f_M(x)\)

(1) 初始化\(f_0(x)=0\)

(2) 对m=1,2,…,M

(a) 计算残差

\[r_{mi}=y_i-f_{m-1}(x_i), i=1,2,...,N\]

(b) 拟合残差\(r_{mi}\)学习一个回归树，得到\(T(x;\theta_m)\)

(c) 更新\(f_m(x)=f_{m-1}(x)+T(x;\theta_m)\)

(3) 得到回归问题提升树

\[f_M(x)=\sum_{m-1}^M T(x;\theta_m)\]

Gradient Boosting Decision Tree(GBDT)

提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对于一般损失函数而言，往往每一步优化并不那么容易。针对这一问题，Freidman提出了梯度提升（gradient boosting）算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值

\[-[\frac{\partial L(y, f(x_1))}{\partial f(x_1)}]_{f(x)=f_{m-1}(x)}\]

作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

梯度提升算法：

输入：训练数据集\(T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)},x_i \in X \subseteq R_n, y_i \in Y \subseteq R\)；损失函数L(y,f(x));

输出：回归树\(\hat{f}(x)\)

(1) 初始化

\[f_0(x) = arg min_c \sum_{i=1}^N L(y_i,c)\]

(2) 对m=1,2,…,M

(a) 对i=1,2,…,N，计算

\[r_{mi} = -[\frac{\partial L(y, f(x_1))}{\partial f(x_1)}]_{f(x)=f_{m-1}(x)}\]

(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}(x) + \sum_{j-1}^J c_{mj} I(x \in R_{mj})\)

(3) 得到回归树

\[\hat{f}(x) = f_M(x) = \sum_{m-1}^M \sum_{j=1}^J c_{mj} I(x \in R_{mj}\]

算法第1步初始化，估计使损失函数极小化的常数值，它是只有一个根结点的树。第2(a)步计算损失函数的负梯度在当前模型的值，将它作为残差的估计，对于平方损失函数，它就是通常所说的残差；对于一般损失函数，它就是残差的近似值。第2(b)步估计回归树叶结点区域，以拟合残差的近似值。第2(c)步利用线性搜索估计叶结点区域的值，使损失函数极小化。第2(d)步更新回归树。第3步得到输出的最终模型\(\hat{f}(x)\)。