Boosting Tree提升树

1. Boosting基本概念

提升（Boosting）方法是一种常用的统计学习方法，应用广泛且有效。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。
提升方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。实际上，就是“三个臭皮匠顶个诸葛亮”的道理。
历史上，Kearns和Valiant首先提出了“强可学习（strongly learnable）”和“弱可学习（weakly learnable）”的概念。指出：在概率近似正确（probably approximately correct，PAC）学习的框架中，一个概念（一个类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。非常有趣的是Schapire后来证明强可学习与弱可学习是等价的，也就是说，在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。
这样一来，问题便成为，在学习中，如果已经发现了“弱学习算法”，那么能否将它提升（boost）为“强学习算法”。大家知道，发现弱学习算法通常要比发现强学习算法容易得多。那么如何具体实施提升，便成为开发提升方法时所要解决的问题。关于提升方法的研究很多，有很多算法被提出。最具代表性的是AdaBoost算法（AdaBoost algorithm）。
Boosting算法的两个核心问题：
（1）在每一轮如何改变训练数据的权值或概率分布？
AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器“分而治之”。
（2）如何将弱分类器组合成一个强分类器？
弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。
提升树是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中性能最好的方法之一。提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法。以决策树为基函数的提升方法称为提升树（boosting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。下面让我们深入理解提升树的具体算法吧！

2. 前向分步加法模型

2.1 加法模型
考虑加法模型（Additive Model）如下：

其中， 为基函数， 为基函数的参数， 为基函数的系数。显然上式是一个加法模型。
2.2 前向分布算法
在给定训练数据及损失函数 的条件下，学习加法模型 成为经验风险极小化，即损失函数极小化的问题：

通常这是一个复杂的优化问题。前向分布算法（forward stagewise algorithm）求解这一优化问题的想法是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近上面要优化的目标函数，那么就可以简化优化的复杂度。
具体地，每步只需优化如下损失函数：

给定训练数据集 。损失函数和基函数的集合 ，学习加法模型 的前向分步算法如下：
前向分步算法步骤如下：
输入：训练数据集 ；损失函数；基函数集
输出：加法模型f(x)
（1）初始化f0(x)=0
（2）对 m=12…M
（a）极小化损失函数：

得到参数
（b）更新：

（3）得到加法模型：

这样，前向分步算法将同时求解从m=1到M的所有参数 ， 的优化问题简化为逐次求解各个 ， 的优化问题。

3. 提升树

提升树是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中性能最好的方法之一。
3.1 提升树模型
提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法。以决策树为基函数的提升方法称为提升树（boosting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。提升树模型可以表示为决策树的加法模型：

其中， 表示决策树； 为决策树的参数；M为树的个数。
3.2 提升树算法
提升树算法采用前向分步算法。首先确定初始提升树 ，第m步的模型是：

其中， 为当前模型，通过经验风险极小化确定下一棵决策树的参数 :

由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。
下面讨论针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括用平方误差损失函数的回归问题，用指数损失函数的分类问题，以及用一般损失函数的一般决策问题。
3.2.1 二叉分类提升树
对于二分类问题，提升树算法只需将AdaBoost算法中的基本分类器限制为二类分类树即可，可以说这时的提升树算法是AdaBoost算法的特殊情况，这里不再细述。下面叙述回归问题的提升树。
3.2.2 二叉回归提升树
已知一个训练数据集 ，x为输入空间， , y为输出空间。如果将输入空间x划分为J个互不相交的区域 ,并且在每个区域上确定输出的常量 ，那么树可表示为：

其中，参数 表示树的区域划分和各区域上的常数。J是回归树的复杂度即叶结点个数。
回归问题提升树使用以下前向分步算法：



在前向分步算法的第m步，给定当前模型 ，需求解：

得到 ，即第m棵树的参数。
采用平方误差损失函数时， ，其损失变为：

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

4. 回归提升树示例