Adaboost和提升树

Adaboost 提升方法基于这样一种思想：
对于一个复杂任务来说，多个专家的综合判断比一个其中任何一个的单独判断要好
也可以理解为三个臭皮匠抵个诸葛亮

Adaboost

在学习中，通常“弱学习算法”更容易被发现，而“强学习算法”可遇而不可求。所以我们可以通过 Adaboost 算法把多个“弱学习算法”合并为一个“强学习算法”。

弱学习算法：识别错误率小于1/2(即准确率仅比随机猜测略高的学习算法)
强学习算法：识别准确率很高并能在多项式时间内完成的学习算法

给定一个二分类训练数据集

[图片上传失败...(image-ba7526-1524099262989)],(x_2,y_2),...,(x_n,y_n)})

Adaboost的算法流程如下

步骤1. 首先，初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权值：1/N。

步骤2. 进行多轮迭代，用m = 1,2, ..., M表示迭代的第多少轮

a. 使用当前加权的的训练数据集Dm学习，得到基本分类器（选取让误差率最低的阈值来设计基本分类器）：

b. 计算Gm(x)在训练数据集上的分类误差率

由上述式子可知，Gm(x)在训练数据集上的误差率em就是被Gm(x)误分类样本的权值之和。

c. 计算Gm(x)的系数，am表示Gm(x)在最终分类器中的重要程度（目的：得到基本分类器在最终分类器中所占的权重）：

由上述式子可知，em <= 1/2时，am >= 0，且am随着em的减小而增大，意味着分类误差率越小的基本分类器在最终分类器中的作用越大。

d. 更新训练数据集的权值分布（目的：得到样本的新的权值分布），用于下一轮迭代

使得被基本分类器Gm(x)误分类样本的权值增大，而被正确分类样本的权值减小。就这样，通过这样的方式，AdaBoost方法能“重点关注”或“聚焦于”那些较难分的样本上。

其中，Zm是规范化因子，使得Dm+1成为一个概率分布：

步骤3. 组合各个弱分类器

从而得到最终分类器，如下：

Adaboost 训练误差分析
Adaboost 的基本性质是它能在学习的过程中不断减少训练误差，关于这个问题有下面的定理

这里不给出证明

这一定理说明可以选择合适的Gm使Zm最小，从而减少整体的误差。

这里不给出证明

结合定理8.1和8.2我们可以得到推论

这说明 AdaBoost 的误差是指数级下降的，这一性质具有相当的吸引力。

前向分步算法

设 β 为基分类器系数， γ 为基分类器参数

前向分布加法算法

值得一提的是Adaboost也可以看作前向分步加法算法的一个特例。

提升树

提升树是以分类树或者回归树(决策树)为基础学习算法的提升方法。

提升树模型

回归问题的提升树

以下内容需要对回归树有一定了解
可参考决策树-CART回归树

回归问题的提升树采用前向分步算法

r 即为当前模型拟合数据的残差。
对于特征的每个可能取值，选择平方损失函数最小的切分点，即用 T(x; Θ) 尽可能拟合 rm

平方损失函数，m 表示第 m 步

得到树

回归树

然后更新 fm(x)

更新整体模型

梯度提升算法

对于一般损失函数，可能无法像平方误差函数一样直接推导出拟合残差rm，
梯度提升算法的核心是用损失函数的负梯度近似rm

即用

损失函数的负梯度

作为拟合残差 rm 生成回归树
在梯度提升算法中，每个新模型的建立是为了使得先前模型残差往梯度方向减少，与传统的Boost算法对正确、错误的样本进行加权有着极大的区别。

具体算法可参考 梯度树提升

参考

《统计学习方法》
决策树
http://blog.csdn.net/u012258999/article/details/42457577
http://www.cnblogs.com/liuwu265/p/4693113.html?ptvd