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

提升树模型

提升树方法实际采用加法模型(即基函数的线性组合)与前向分步算法,以决策树为基函数的的提升方法称为提升树(boosting tree)。对分类问题决策树是二叉分类树,对回归问题决策树是二叉回归树。提升树可以表示为决策树的加法模型:\[f_M(x) = \sum _{m=1} ^M T(x;\Theta_m)\]其中\(T(x;\Theta_m)\)表示决策树;\(\Theta_m\)为决策树的参数;\(M\)为树的个数。

提升树算法

提升树算法采用前向分步算法。首先确定初始提升树\(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;\Theta_m))\]

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

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

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

已知一个训练数据集\(T=\{(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)\}, \quad x_i \in \mathcal{X} \subseteq R ^n\), \(\mathcal{X}\) 为输入空间,\(y_i \in \mathcal{Y} \subseteq R\)\(\mathcal{Y}\)为输出空间。 在之前的CATR中已经讨论了回归树的问题。如果将输入空间\(\mathcal{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\]其损失变为\[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\]这里,\[r=y-f_{m-1}(x) \tag{1}\]是当前模型拟合数据的残差(residual)。所以对回归问题的提升树算法来说,只需简单地拟合当前模型的残差。这样算法是相当简单的。现将回归问题的提升树算法叙述如下。

算法1 (回归问题的提升树算法)

  • 输入: 训练数据集\(T=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}\), \(x_i \in \mathcal{X} \subseteq R^n\), \(y_i \in \mathcal{Y} \subseteq R\)
  • 输出: 提升树\(f_M(x)\)

  • 1 初始化\(f_0(x) = 0\)
  • 2 对\(m = 1, 2, ..., M\)
  • 2.a 按式1计算残差 \[r_{mi} = y_i - f_{m-1}(x_i), \quad i = 1, 2, ..., N\]
  • 2.b 拟合残差\(r_{mi}\)学习一个回归树,得到\(T(x;\Theta_m)\)
  • 2.c 更新\(f_m(x) = f_{m-1}(x) + T(x; \Theta_m)\)
  • 3 得到回归问题的提升树 \[f_M(x) = \sum _{m=1} ^M T(x, \Theta _m)\]

梯度提升

提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时,每一步优化是很简单的。但对于一般损失函数而言,往往每一步优化并不那么容易。针对这一问题, Freidman提出了梯度提升(gradient boosting)算法。这是利用最速下降法的近似方法,其关键是利用损失函数的负梯度在当前模型的值\[-\left[ \frac {\partial L(y,f(x_i))} {\partial f(x_i)} \right]_{f(x) = f_{m-1}(x)}\] 作为回归问题提升树算法残差的近似值,拟合一棵树。

算法2 (梯度提升算法)

  • 输入: 训练数据集\(T=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}\), \(x_i \in \mathcal{X} \subseteq R^n\), \(y_i \in \mathcal{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\)
  • 2.a 对\(i = 1, 2, ...,N\), 计算 \[r_mi = -\left[ \frac {\partial L(y,f(x_i))} {\partial f(x_i)} \right]_{f(x) = f_{m-1}(x)}\]
  • 2.b 对\(r_{mi}\)拟合一个回归树,得到第\(m\)棵树的叶结点区域\(R_{mj}\)\(j = 1, 2, ..., J\)
  • 2.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)\]
  • 2.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)\)