机器学习算法（三）：Adaboost算法_机器学习第3关:adaboost算法流程

作者：花生_TL007 | 2024-03-23 04:51:06

踩

机器学习第3关:adaboost算法流程

Boosting算法

集成学习

集成学习的一般结构：先产生一组个体学习器，再使用某种策略将它们结合起来。个体学习器通常由一个现有的算法从训练数据中产生。集成学习既可以包含相同类型的个体学习器，也可以包含不同类型的个体学习器。

集成学习通过将多个学习器进行结合，常可以获得比一般学习器显著优越的泛化性能。这对弱分类器（指泛化性能略优于随机猜测的学习器）尤为明显，因此集成学习的很多理论研究都是针对弱分类器进行的。虽然从理论上来说使用弱分类器集成足以获得好的性能，但在实践中出于种种考虑，人们往往会使用比较强的学习器。

假设基分类器的错误率相互独立，随着集成中基分类器数目的增大，集成的错误率将指数级下降，最终趋向于0。事实上，它们显然不可能相互独立。要获得好的集成效果，个体学习器应『好而不同』，即个体学习器要有一定的准确性，并且要有多样性，即学习器之间要有差异。这两者之间也是存在冲突的。在准确性很高之后，要增加多样性就需要牺牲准确性。事实上，如何产生并结合『好而不同』的个体学习器，恰是集成学习研究的核心。

根据个体学习器的生成方式，目前集成学习方法大致可以分为两大类。个体学习器之间存在强依赖关系，必须串行生成序列化方法。以及个体学习器之间不存在强依赖关系，可同时生成并行化方法。前者的代表是Boosting，后者的代表是Bagging和随机森林算法。关于这两类算法，将使用两篇博客来介绍。

强可学习与弱可学习

强可学习：在概率近似正确学习的框架中，一个概念（一个类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的。

弱可学习：一个概念，如果存在一个多项式的学习算法能够正确学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。

后来证明强可学习与弱可学习是等价的。也就是说，在概率近似正确学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

通常发现弱可学习算法通常要比发现强可学习算法容易的多。集成学习就是从弱学习算法出发，反复学习，得到一系列弱分类器，然后组合这些弱分类器，构成一个强分类器。

Boosting算法简介

提升方法基于这样一种思想：对于复杂的任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。

它改变训练数据分布的方法是：提高那些前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。对于将一系列弱分类器组合称强分类器的方法是：加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

Adaboost作为提升方法的典型代表，把多个不同的决策树用一种非随机的方式组合起来，表现出惊人的性能。其优点如下：

具有很高的精度；
Adaboost提供的是一种框架，可以使用各种方法来构建子分类器；
当使用简单分类器时，计算出的结果是可以理解的，而且弱分类器的构造特别简单；
简单，不用做特征筛选
不用担心overfitting

算法的具体过程

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

T={ $(x_1,y_1),(x_2,y_2),...,(x_N,y_N)$ }

其中，每个样本点由实例与标记组成。算法的具体过程如下：

输入：训练数据集T；弱学习算法

输出：最终分类器 $G(x)$

(1) 初始化训练数据的权值分布

D_{1} = (w_{11}, . . ., w_{1 i}, . . ., w_{1 N}), w_{1 i} = \frac{1}{N}, i = 1, 2, . . ., N

$D_1=(w_{11},...,w_{1i},...,w_{1N}), w_{1i}= \frac{1}{N},i=1,2,...,N$

(2) 对 $m=1,2,...,M$

(a) 使用具有权值分布 $D_m$ 的训练数据集学习，得到基本分类器

G_{m} (x) : X \to (- 1, + 1)

$G_m(x): X \rightarrow (-1,+1)$

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

e_{m} = P (G_{m} (x_{i}) \neq y_{i}) = \sum_{i = 1}^{N} w_{m i} I (G_{m} (x_{i}) \neq y_{i})

$e_m = P(G_m(x_i) \neq y_i) = \sum_{i=1} ^{N} w_{mi} I(G_m(x_i) \neq y_i)$

α_{m} = \frac{1}{2} l o g_{e} \frac{1 - e_{m}}{e_{m}}

$\alpha_m = \frac{1}{2} log_e \frac{1-e_m}{e_m}$

(d) 更新训练数据的权值分布

D_{m + 1} = (w_{m + 1, 1}, . . ., w_{m + 1, i}, . . ., w_{m + 1, N})

$D_{m+1} = (w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N})$

w_{m + 1, i} = \frac{w_{m i}}{Z_{m}} e x p (- α_{m} y_{i} G_{m} (x_{i})), i = 1, 2, . . ., N

$w_{m+1,i} = \frac{w_{mi}}{Z_m} exp(- \alpha_m y_i G_m(x_i)),i=1,2,...,N$

其中， $Z_m$ 是规范化因子

Z_{m} = \sum_{i = 1}^{N} w_{m i} e x p (- α_{m} y_{i} G_{m} (x_{i}))

$Z_m = \sum_{i=1} ^{N} w_{mi} exp(- \alpha_m y_i G_m(x_i))$

它使 $D_{m+1}$ 成为一个概率分布。

(3) 构建基本分类器的线性组合

f (x) = \sum_{m = 1}^{M} α_{m} G_{m} (x)

$f(x) = \sum_{m=1} ^{M} \alpha_m G_m(x)$

得到最终分类器

G (x) = s i g n (f (x)) = s i g n (\sum_{m = 1}^{M} α_{m} G_{m} (x))

$G(x) = sign(f(x)) = sign(\sum_{m=1} ^{M} \alpha_m G_m(x))$

算法解释

在此对算法过程中的一些关键点做一些解释：

在计算分类器 $G_m(x)$ 的系数 $\alpha_m$ 时，当 $e_m \leq \frac{1}{2}$ 时， $\alpha_m \geq 0$ ，表示该分类器的效果要比随机预测的好时，才会在最终的分类器中发挥正的效果。并且 $\alpha_m$ 随着 $e_m$ 的减小而增大。
为什么在每次迭代时，都是将错误分类点的权值增大？提高错误点的权值，当下一次分类器再次错分了这些点时，会提高整体的错误率，这样会导致分类器的 $\alpha_m$ 变小，最终导致这个分类器在整个混合分类器的权值变低。通过权值的改变，也使得每一次学习到的弱分类器具有较为显著的差异。
在更新训练数据的概率分布时，我们可以将式子写成如下形式：

$w_{m + 1, i} = {\begin{aligned} \frac{w_{m i}}{Z_{m}} e^{- α_{m}}, G_{m} (x_{i}) = y_{i} \\ \frac{w_{m i}}{Z_{m}} e^{α_{m}}, G_{m} (x_{i}) \neq y_{i} \end{aligned}$ $w _{m+1,i}=\left\{ \begin{aligned} \frac{w_{mi}}{Z_m}e^{-\alpha_m}, G_m(x_i)=y_i \\ \frac{w_{mi}}{Z_m}e^{\alpha_m}, G_m(x_i) \neq y_i \end{aligned} \right.$
由上式可知，误分类样本的权值被放大 $e^{2\alpha_m} = \frac{e_m}{1-e_m}$ 倍。不改变所给训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是Adaboost算法的一个特点。
注意到，这里所有 $\alpha_m$ 的和并不为1。
对于无法接受带权样本的基学习算法，则可以通过重采样法来处理。即在每一轮学习中，根据样本分布对训练数据重新进行采样，再用重新采样的数据集对基学习器进行训练。
Boosting主要关注偏差降低，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。