Adaboost
2021-9-30
| 2023-8-6
0  |  阅读时长 0 分钟
type
status
date
slug
summary
tags
category
icon
password
Property

原理

回顾boosting

notion image
Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.，如此重复进行，直到弱学习器数达到事先指定的数目，最终将这个弱学习器通过集合策略进行整合，得到最终的强学习器。
不过有几个具体的问题Boosting算法没有详细说明：
  1. 如何计算学习误差率?
  1. 如何得到弱学习器权重系数?
  1. 如何更新样本权重D?
  1. 使用何种结合策略？
只要是boosting大家族的算法，都要解决这4个问题。
 
那么Adaboost是怎么解决的呢？
 

Adaboost算法的基本思路

假设我们的训练集样本是
训练集的在第个弱学习器的输出权重为
Adaboost的分类问题：
如何计算学习误差率?
分类问题的误差率很好理解和计算。由于多元分类是二元分类的推广，这里假设是二元分类问题，输出为，则第个弱分类器 在训练集上的加权误差率为：
接着我们看弱学习器权重系数，对于二元分类问题，第个弱分类器的权重系数为
为什么这样计算弱学习器权重系数？
从上式可以看出，如果分类误差率越大，则对应的弱分类器权重系数越小，也就是说误差率小的弱分类器权重系数越大
如何更新样本权重D?
假设第个弱分类器的样本集权重系数为，则对应的第个弱分类器的样本集权重系数为：
这里是规范化因子（规范化因子只是为了保证想加之和为1）：
从计算公式可以看出，如果第个样本分类错误，则 ，导致样本的权重在第个弱分类器中增大；如果分类正确，则权重在第个弱分类器中减少。
权值代表了这个样本在当前轮迭代之前被误分类的次数度量，被误分类的次数越多，权值就越大，在当前轮就会越被重视。如何被重视呢？这里采用的就是用的权值乘以损失函数，当然也有其他可行的方法。因为我们的目标是极小化损失函数，这样做自然对大权值的样本误分类的惩罚高。
使用何种结合策略？
Adaboost分类采用的是加权表决法，最终的强分类器为
 
Adaboost的回归问题:
由于Adaboost的回归问题有很多变种，这里以Adaboost R2算法为准。
如何计算学习误差率?
对于第个弱学习器，计算它在训练集上的最大误差
然后计算每个样本的相对误差：
这里是误差损失为线性时的情况，如果用平方误差，则
如果用的是指数误差，则
最终得到第个弱学习器的误差率
如何得到弱学习器权重系数？如何更新样本权重D?
这里有：
对于更新更新样本权重D，第个弱学习器的样本集权重系数为
这里 是规范化因子
使用何种结合策略？
和分类问题稍有不同，采用的是对加权的弱学习器取权重中位数对应的弱学习器作为强学习器的方法，最终的强回归器为
其中 是所有 的中位数值对应序号对应的弱学习器
 

AdaBoost分类问题的损失函数优化

分类Adaboost的弱学习器权重系数公式和样本权重更新公式其实可以从Adaboost的损失函数推导出来。
从另一个角度讲， Adaboost是模型为加法模型，学习算法为前向分步学习算法，损失函数为指数函数的分类问题。
模型为加法模型好理解，我们的最终的强分类器是若干个弱分类器加权平均而得到的
 
前向分步学习算法也好理解，我们的算法是通过一轮轮的弱学习器学习，利用前一个强学习器的结果和当前弱学习器来更新当前的强学习器的模型。也就是说，第轮的强学习器为
而第轮的强学习器为
上两式一比较可以得到
可见强学习器的确是通过前向分步学习算法一步步而得到的
 
Adaboost损失函数为指数函数，即定义损失函数为
利用前向分步学习算法的关系可以得到损失函数为
令, 它的值不依赖于 ，因此与最小化无关，仅仅依赖于，随着每一轮迭代而改变。
将这个式子带入损失函数，损失函数转化为
首先，我们求 ，
注：时，有，同理有
基于上式， 可以得到
将带入损失函数，并对求导，使其等于0：
注意到：
将的表达式带入上面导数为0 的表达式得到：
就得到了
其中， 即为我们前面的分类误差率。
最后看样本权重的更新：
利用 和 ，即可得：
这样就得到了样本权重更新公式
注意到：
即仅仅是比多了一个规范化因子的分母而已。也就是说，是规范化后的表达式，即可以得到：

AdaBoost二元分类问题算法流程

输入为样本集 ，输出为{-1, +1}，弱分类器算法, 弱分类器迭代次数
输出为最终的强分类器
1) 初始化样本集权重为
2) 对于 :
a.使用具有权重 的样本集来训练数据，得到弱分类器 ，对于每一步的基本分类器都根据最小分类误差率来选择
b.计算 的分类误差率
c.计算弱分类器的系数
d.更新样本集的权重分布
这里 是规范化因子
3) 构建最终分类器为：
对于Adaboost多元分类算法，其实原理和二元分类类似，最主要区别在弱分类器的系数上。比如Adaboost SAMME算法，它的弱分类器的系数
其中为类别数。从上式可以看出，如果是二元分类，R=2，则上式和我们的二元分类算法中的弱分类器的系数一致。

Adaboost回归问题的算法流程

AdaBoost回归算法变种很多，下面的算法为Adaboost R2回归算法过程
输入为样本集，弱学习器算法, 弱学习器迭代次数
输出为最终的强学习器
1) 初始化样本集权重为
2) 对于 :
a) 使用具有权重的样本集来训练数据，得到弱学习器
b) 计算训练集上的最大误差
c) 计算每个样本的相对误差:
  • 如果是线性误差，则
  • 如果是平方误差，则
  • 如果是指数误差，则
d) 计算回归误差率
c) 计算弱学习器的系数
d) 更新样本集的权重分布为
这里 是规范化因子
3) 构建最终强学习器为：
其中， 是所有 的中位数值乘以对应序号对应的弱学习器。在回归的时候，弱回归器的系数不是，而是 ，在分类的时候弱回归器的系数才是

Adaboost算法的正则化

为了防止Adaboost过拟合，我们通常也会加入正则化项，这个正则化项我们通常称为步长(learning rate),，定义为
对于前面的弱学习器的迭代
如果我们加上了正则化项，则有
的取值范围为 ，对于同样的训练集学习效果，较小的 意味着需要更多的弱学习器的迭代次数。通常用步长和迭代最大次数一起来决定算法的拟合效果。每次不会严格按照减少训练样本损失的路线走，从而减少过拟合。

Adaboost小结

理论上任何学习器都可以用于Adaboost，但一般来说，使用最广泛的Adaboost弱学习器是决策树和神经网络。对于决策树，Adaboost分类用了CART分类树，而Adaboost回归用了CART回归树
 
Adaboost的主要优点有：
  • Adaboost作为分类器时，分类精度很高
  • 在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活
  • 作为简单的二元分类器时，构造简单，结果可理解
  • 不容易发生过拟合
Adaboost的主要缺点有：
  • 对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性
 

补充：

为什么极小化指数损失函数等价于最小化分类误差？

对于通用的指数损失函数：
对指数损失函数求偏导可以得到：
令上式等于0，可以得到:
因此可以得到：
这意味着达到了贝叶斯最优错误率。若指数损失函数最小化，则分类错误率也将最小化；这就说明指数损失函数是分类任务原本0/1损失函数的一致的替代损失函数

弱分类器不必有太高精度, 如果太高反而适得其反会使得整个adaboost提前终止

弱分类器如果精度太高，那么误分类的样本就会很少，要知道Adaboost后面的弱学习器是基于前面弱学习器的分类误差情况来调整的，如果前面的误分类样本少，后面的弱学习器可以调整权重的样本就不多，那么再建立一个弱学习器和前面的弱学习器区别就会很小，这样会导致Adaboost提前终止。
另外，弱分类器如果精度太高，后续的弱分类器基本一样，还有可能导致过拟合，因此单个弱学习器的精度不用太高。算法精度由整体保证即可。
 
 

代码

scikit-learn中Adaboost类库比较直接，就是AdaBoostClassifier和AdaBoostRegressor两个
AdaBoostClassifier使用了两种Adaboost分类算法的实现，SAMME和SAMME.R；而AdaBoostRegressor则使用了Adaboost.R2
对Adaboost调参时，主要要对两部分内容进行调参，第一部分是对我们的Adaboost的框架进行调参， 第二部分是对选择的弱分类器进行调参。两者相辅相成。
 
AdaBoostClassifier和AdaBoostRegressor框架参数：
base_estimator
AdaBoostClassifier和AdaBoostRegressor都有，即弱分类学习器或者弱回归学习器。理论上可以选择任何一个分类或者回归学习器，不过需要支持样本权重。常用的一般是CART决策树或者神经网络MLP。默认是决策树，即AdaBoostClassifier默认使用CART分类树DecisionTreeClassifier，而AdaBoostRegressor默认使用CART回归树DecisionTreeRegressor。
另外有一个要注意的点是，如果选择的AdaBoostClassifier算法是SAMME.R，则弱分类学习器还需要支持概率预测，也就是在scikit-learn中弱分类学习器对应的预测方法除了predict还需要有predict_proba。
algorithm
这个参数只有AdaBoostClassifier有。主要原因是scikit-learn实现了两种Adaboost分类算法，SAMME和SAMME.R。两者的主要区别是弱学习器权重的度量，SAMME使用了二元分类Adaboost算法的扩展，即用对样本集分类效果作为弱学习器权重，而SAMME.R使用了对样本集分类的预测概率大小来作为弱学习器权重。由于SAMME.R使用了概率度量的连续值，迭代一般比SAMME快，因此AdaBoostClassifier的默认算法algorithm的值也是SAMME.R。一般使用默认的SAMME.R就够了，但是要注意的是使用了SAMME.R， 则弱分类学习器参数base_estimator必须限制使用支持概率预测的分类器。SAMME算法则没有这个限制
loss
这个参数只有AdaBoostRegressor有，Adaboost.R2算法需要用到。有线性‘linear’, 平方‘square’和指数 ‘exponential’三种选择, 默认是线性，一般使用线性就足够了。这个值对第k个弱分类器的中第个样本的误差的处理，即：
  • 如果是线性误差，则
  • 如果是平方误差，则
  • 如果是指数误差，则
为训练集上的最大误差
n_estimators
AdaBoostClassifier和AdaBoostRegressor都有，就是弱学习器的最大迭代次数，或者说最大的弱学习器的个数。一般来说n_estimators太小，容易欠拟合，n_estimators太大，又容易过拟合，一般选择一个适中的数值。默认是50。在实际调参的过程中，常常将n_estimators和参数learning_rate一起考虑。
learning_rate
daBoostClassifier和AdaBoostRegressor都有，即每个弱学习器的权重缩减系数，加上了正则化项，强学习器的迭代公式为 的取值范围为。对于同样的训练集拟合效果，较小意味着需要更多的弱学习器的迭代次数。通常用步长和迭代最大次数一起来决定算法的拟合效果。所以这两个参数n_estimators和learning_rate要一起调参。一般来说，可以从一个小一点的ν开始调参，默认是1。
 
AdaBoostClassifier和AdaBoostRegressor弱学习器参数:
使用不同的弱学习器，对应的弱学习器参数各不相同。这里仅仅讨论默认的决策树弱学习器的参数。即CART分类树DecisionTreeClassifier和CART回归树DecisionTreeRegressor
 
重要几个的参数：
  • 划分时考虑的最大特征数max_features：可以使用很多种类型的值，默认是"None"，意味着划分时考虑所有的特征数；如果是"log2"意味着划分时最多考虑 个特征；如果是"sqrt"或者"auto"意味着划分时最多考虑 个特征。如果是整数，代表考虑的特征绝对数。如果是浮点数，代表考虑特征百分比，即考虑（百分比xN）取整后的特征数。其中N为样本总特征数。一般来说，如果样本特征数不多，比如小于50，用默认的"None"就可以了，如果特征数非常多，可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间。
  • 决策树最大深max_depth：默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。
  • 内部节点再划分所需最小样本数min_samples_split：这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。 默认是2，如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。
  • 叶子节点最少样本数min_samples_leaf：这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。 默认是1，可以输入最少的样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，推荐增大这个值。
  • 叶子节点最小的样本权重和min_weight_fraction_leaf：这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。 默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时就要注意这个值了。
  • 最大叶子节点数max_leaf_nodes：通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到。
 
notion image
 
相关文章 :
数据分析
  • Scikit-Learn
    • 集成学习梯度提升树(GBDT)
    目录