Adaboost 算法总结

Adaboost 是 boosting 算法的其中之一。它既可以作为分类,也可以作为回归。一般我们都是提它怎么用于分类,对它应用在回归比较少提到,其实它也是可以用于回归的。今天我不想写太多 Adaboost 的原理,主要是写一下 Adaboost 如何用于分类和回归问题。

Adaboost 二元分类问题的算法流程

输入为样本集 \( (x_1, y_1) ,…, (x_n, y_n) \),输出为 {+1,-1}。

弱分类器迭代次数为 K。输出为最终的强分类器 \(f(x)\)

1) 初始化样本集权重为:

$$D(1) = (w_{11}, w_{12},…, w_{1m});$$

$$w_{1i} = \frac{1}{m}; i = 1,2,…,m$$

2)对于 \(k = 1, 2, 3 … K\):

a) 使用具有权重 \(D_k\) 的样本集来训练数据,得到弱分类器 \(G_{k}(x)\)

b) 计算 \(G_{k}(x)\) 的分类误差率

$$e_{k} = P(G_k(x_i) \neq y_i); i = 1,2,…,m$$

c) 计算弱分类器的系数

$$\alpha_k = \frac{1}{2} log \frac{1 - e_k}{e_k}$$

d) 更新样本集的权重分布

$$w_{k+1,i} = \frac{w_{ki}}{Z_k} exp(- \alpha_k y_i G(x_i))$$

这里 \(Z_k\) 是规范因子:

$$Z_k = \sum_{i=1}^m w_{ki} exp(-\alpha_k y_i G_k(x_i)) \,\, i = 1,2,…,m$$

3) 构建最终的分类器为:

$$f(x) = sign \sum_{k=1}^K \alpha_k G_k(K)$$

对于 Adaboost 多元分类算法,其实原理和二分类很类似,最主要的区别是在弱分类器的系数上,比如 Adaboost SAMME 算法,它的弱分类器的系数:

$$ \alpha_k = \frac{1}{2} log \frac{1 - e_k}{e_k} + log(R - 1)$$

其中 R 为类别数,从上式可以看出,如果是二元分类,R = 2,则上式和我们的二元分类算法中的弱分类器的系数一致。

Adaboost 回归问题的算法流程

AdaBoost回归算法变种很多,下面的算法为Adaboost R2 回归算法过程。

输入为样本集 \( (x_1, y_1) ,…, (x_n, y_n) \),

最终输出为强学习器 \(f(x)\)

1) 初始化样本集权重为:

$$D(1) = (w_{11}, w_{12},…, w_{1m});$$

$$w_{1i} = \frac{1}{m}; i = 1,2,…,m$$

2)对于 \(k = 1, 2, 3 … K\):

a) 使用具有权重 \(D_k\) 的样本集来训练数据,得到弱分类器 \(G_{k}(x)\)

b) 计算训练集上的最大误差

$$E_k = max|y_i - G_k(x_i)|; i = 1, 2, 3 … m$$

c) 计算每个样本的相对误差:

如果是线性误差,则 \(e_{ki} = \frac{|y_i - G_k(x_i)|}{E_k}\)

如果是平方误差,则 \(e_{ki} = \frac{(y_i - G_k(x_i))^2}{E_k}\)

如果是指数误差,则 \(e_{ki} = 1 - exp(\frac{-y_i + G_k(x_i)}{E_k})\)

d) 计算回归误差率

$$e_k = \sum_{i=1}^m w_{ki}e_{ki}$$

e) 计算弱学习器的系数

$$\alpha_k = \frac{e_k}{1 - e_k}$$

f) 更新样本集的权重分布为

$$w_{k+1, j} = \frac{w_{ki}}{Z_k} \alpha_k^{1 - e_{ki}}$$

这里 \(Z_k\) 是规范化因子:

$$ Z_k = \sum_{i=1}^m w_{ki} \alpha_k ^{1 - e_{ki}}$$

3) 构建最终的强学习器:

$$f(x) = \sum_{k=1}^K = (ln \frac{1}{\alpha_k}) G_k(x)$$

Adaboost算法的正则化

为了防止 Adaboost 过拟合,我们通常也会加入正则化项,这个正则化项我们通常称为步长(learning rate)。定义为 ν,对于前面的弱学习器的迭代:

$$f_k(x) = f_{k-1}(x) + \alpha_k G_k (x)$$

如果我们加上了正则项,则有:

$$f_k(x) = f_{k-1}(x) + \nu \alpha_k G_k(x)$$

ν 的取值范围为 \(0<ν≤10<ν≤1\)。对于同样的训练集学习效果,较小的 ν 意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

Adaboost 小结

理论上任何学习器都可以用于 Adaboost。但一般来说,使用最广泛的 Adaboost 弱学习器是决策树和神经网络。对于决策树,Adaboost分类用了 CART 分类树,而 Adaboost 回归用了 CART 回归树。

这里对Adaboost算法的优缺点做一个总结。

Adaboost的主要优点有:

  1. Adaboost作为分类器时,分类精度很高
  2. 在Adaboost的框架下,可以使用各种回归分类模型来构建弱学习器,非常灵活。
  3. 作为简单的二元分类器时,构造简单,结果可理解。
  4. 不容易发生过拟合

Adaboost的主要缺点有:

  1. 对异常样本敏感,异常样本在迭代中可能会获得较高的权重,影响最终的强学习器的预测准确性。