提升方法
- 提升方法 AdaBoost 算法
- AdaBoost算法的训练误差分析
- AdaBoost算法的解释
- 提升树
提升(boosting)方法是一种常用的统计学习方法,应用广泛且有效。在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提高分类的性能。
提升方法 AdaBoost 算法
- 提升方法基于这样一种思想:对于一个复杂任务来说,将多个专家的判断进行适当的综合所得出的判断,要比其中任何一个专家单独的判断好。实际上,就是“三个臭皮匠顶个诸葛亮”的道理。
- 对于分类问题而言,给定一个训练样本集,求比较粗糙的分类规则(弱分类器)要比求精确的分类规则(强分类器)容易得多。提升方法就是从弱学习算法出发,反复学习,得到一系列弱分类器(又称为基本分类器),然后组合这些弱分类器,构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。
- 这样,对提升方法来说,有两个问题需要回答:一是在每一轮如何改变训练数据的权值或概率分布;二是如何将弱分类器组合成一个强分类器。关于第1个问题,AdaBoost的做法是,提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。这样一来,那些没有得到正确分类的数据,由于其权值的加大而受到后一轮的弱分类器的更大关注。于是,分类问题被一系列的弱分类器“分而治之”。至于第2个问题,即弱分类器的组合,AdaBoost采取加权多数表决的方法。具体地,加大分类误差率小的弱分类器的权值,使其在表决中起较大的作用,减小分类误差率大的弱分类器的权值,使其在表决中起较小的作用。
- 现在叙述 AdaBoost 算法。假设给定一个二类分类的训练数据集
其中,每个样本点由实例与标记组成。实例 ,标记 , 是实例空间, 是标记集合。
输出:最终分类器
1>>
初始化训练数据的权值分布
2>>
对
a>>
使用具有权值分布 的训练数据集学习,得到基本分类器
假设训练数据集具有均匀的权值分布,即每个训练样本在基本分类器的学习中作用相同。
b>>
计算 在训练数据集上的分类错误率
在加权的训练数据集上的分类误差率是被 误分类样本的权值之和,由此可以看出数据权值分布 与基本分类器 的分类误差率的关系。
c>>
计算 的系数
这里的对数是自然对数。当 时, ,并且 随着 的减小而增大,所以分类误差率越小的基本分类器在最终分类器中的作用越大。
d>>
更新训练数据集的权值分布
这里 是规范化因子
它使 成为一个概率分布。
也可以写成
由此可知,被基本分类器 误分类样本的权值得以扩大,而被正确分类样本的权值却得以缩小。两相比较,误分类样本的权值被放大 倍。因此,误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据,而不断改变训练数据权值的分布,使得训练数据在基本分类器的学习中起不同的作用,这是AdaBoost的一个特点。
3>>
构建基本分类器的线性组合
得到最终分类器
线性组合 实现 M 个基本分类器的加权表决。系数 表示了基本分类器 的重要性,这里,所有 之和并不为1。 的符号决定实例 的类, 的绝对值表示分类的确信度。利用基本分类器的线性组合构建最终分类器是 AdaBoost 的另一特点。
AdaBoost算法的训练误差分析
- AdaBoost 最基本的性质是它能在学习过程中不断减少训练误差,即在训练数据集上的分类误差率。AdaBoost 算法最终分类器的训练误差界为
证明:
当 时, ,因而 。因此可直接推导出前半部分。
现推导后半部分如下
这一定理说明,可以在每一轮选取适当的 使得 最小,从而使训练误差下降最快。
- 二类分类问题 AdaBoost 的训练误差界
这里 。
证明:
至于不等式
可先由 和 在点 的泰勒展开式推出 进而得到。
- 二类分类问题,如果存在 ,对所有 有 ,则
这表明在此条件下 AdaBoost 的训练误差是以指数速率下降的。
- AdaBoost 具有
适应性
,即它能适应弱分类器各自的训练误差率。这也是它的名称(适应的提升)的由来,Ada 是Adaptive 的简写。
AdaBoost算法的解释
- AdaBoost 算法还有另一个解释,即可以认为 AdaBoost 算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二类分类学习方法。
- 考虑加法模型
其中, 为基函数, 为基函数的参数, 为基函数的系数。
在给定训练数据及损失函数 的条件下,学习加法模型 成为经验风险极小化即损失函数极小化问题:
通常这是一个复杂的优化问题。前向分步算法
(forward stagewise algorithm)求解这一优化问题的想法是:因为学习的是加法模型,如果能够从前向后,每一步只学习一个基函数及其系数,逐步逼近优化目标函数式,那么就可以简化优化的复杂度。具体地,每步只需优化如下损失函数:
-
前向分步算法
输入:训练数据集 ,损失函数 ;基函数集 ;
输出:加法模型 。
1>>
初始化
2>>
对
a>>
极小化损失函数
得到参数
b>>
更新
3>>
得到加法模型
这样,前向分步算法将同时求解从 到 所有参数 的优化问题简化为逐次求解各个 的优化问题。
AdaBoost 算法是前向分歩加法算法的特例。这时,模型是由基本分类器组成的加法模型,损失函数是指数函数。
提升树
-
提升树是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中性能最好的方法之一。
- 以决策树为基函数的提升方法称为提升树(boosting tree)。对分类问题决策树是二叉分类树,对回归问题决策树是二叉回归树。
- 提升树模型可以表示为决策树的加法模型
其中, 表示决策树; 为决策树的参数; 为树的个数。
- 提升树算法采用前向分步算法。首先确定初始提升树 ,第 步的模型是
其中, 为当前模型,通过经验风险极小化确定下一颗决策树的参数 ,
由于树的线性组合可以很好地拟合训练数据,即使数据中的输入与输出之间的关系很复杂也是如此,所以提升树是一个高功能的学习算法。
- 已知一个训练数据集 ,,。在决策树部分已经讨论了回归树问题。如果将输入空间 划分为 个互不相交的区域 ,并且在每个区域上确定输出的常量 ,那么树可以表示为
其中,参数 表示树的区域划分和各区域上的常数。 是回归树的复杂度即叶结点个数。
回归问题提升树使用以下前向分步算法:
在前向分步算法的第 m 步,给定当前模型 ,需求解
得到 ,即第 m 棵树的参数。
当采用平方误差损失函数时,
其损失变为
这里, 是当前模型拟合数据的残差
(residual)。所以,对回归问题的提升树算法来说,只需简单地拟合当前模型的残差。这样,算法是相当简单的。
- 回归问题的提升树算法
输入:训练数据集 ,,;
输出:提升树 。
1>>
初始化
2>>
对
a>>
计算残差
b>>
拟合残差 学习一个回归树,得到
c>>
更新
3>>
得到回归提升树
- 提升树利用加法模型与前向分歩算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时,每一步优化是很简单的。但对一般损失函数而言,往往每一步优化并不那么容易。针对这一问题,Freidman提出了
梯度提升(gradient boosting)算法
。这是利用最速下降法的近似方法,其关键是利用损失函数的负梯度在当前模型的值
作为回归问题提升树算法中的残差的近似值,拟合一个回归树。
-
梯度提升算法
输入:训练数据集 ,,;损失函数 ;
输出:回归树 。
1>>
初始化
估计使损失函数极小化的常数值,它是只有一个根结点的树。
2>>
对
a>>
对 ,计算
计算损失函数的负梯度在当前模型的值,将它作为残差的估计。对于平方损失函数,它就是通常所说的残差;对于一般损失函数,它就是残差的近似值。
b>>
对 拟合一个回归树,得到第 m 棵树的叶结点区域 ,
估计回归树叶结点区域,以拟合残差的近似值。
c>>
对 ,计算
利用线性搜索估计叶结点区域的值,使损失函数极小化。
d>>
更新
3>>
得到回归树