分步实现机器学习 VI - AdaBoost 指南

Ryukkkk

5.00/5 (1投票)

2019年5月20日

CPOL

2分钟阅读

6558

易于实现的机器学习

引言

AdaBoost 是一种**Boosting** 方法，其原理是结合多个弱分类器可以在复杂的环境中获得更准确的结果。

AdaBoost 模型

AdaBoost 模型由弱分类器、权重更新和分类组成。

弱分类器

AdaBoost 结合弱分类器，采用特定策略获得强分类器，如图所示。在每次迭代中，被错误分类的样本的权重会增加，以引起分类器的“注意”。例如，在图 (a) 中，虚线是分类平面，有两个蓝色样本和一个红色样本被错误分类。然后在图 (b) 中，这两个蓝色样本和一个红色样本的权重被增加。在每次迭代调整权重后，我们可以组合所有弱分类器以获得最终的强分类器。

权重更新

在每次迭代中，有两种类型的权重需要更新，即每个样本的权重 $w_{i}$ 和每个弱分类器的权重 $\alpha_{m}$ 。初始状态如下

$w_{i}=\frac{1}{N}$

$\alpha_{m}=\frac{1}{M}$

其中 N 和 M 分别是样本数量和弱分类器的数量。

AdaBoost 在每次迭代中训练一个弱分类器，记为 $G_{m}\left(x\right)$ ，其训练误差计算如下：

$e_{m}=\sum_{i=1}^{N}w_{mi}I\left(G_{m}(x_{i})\ne y_{i}\right)$

然后，通过以下公式更新弱分类器的权重：

$\alpha_{m}=\frac{1}{2}\ln\frac{1-e_{m}}{e_{m}}$

通过以下公式更新样本权重：

$w_{mi}=\frac{w_{mi}\cdot \exp\left(-\alpha_{m}y_{i}G_{m}\left(x_{i}\right)\right)}{Z_{m}}$

其中

$Z_{m}=\sum_{i=1}^{N}w_{mi}\exp\left(-\alpha_{m}y_{i}G_{m}\left(x_{i}\right)\right)$

从以上公式可以看出：

训练误差是错误分类样本权重的总和。
当 e_m 小于 0.5 时，a_m 大于 0，这意味着弱分类器的训练误差越小，它在最终分类器中发挥的作用就越大。
权重更新可以写成：
$w_{mi}=\left\{ \begin{aligned} \frac{w_{mi}}{Z_{m}}e^{-\alpha_{m}},G_{m}\left(x_{i}\right)=y_{i}\\ \frac{w_{mi}}{Z_{m}}e^{\alpha_{m}},G_{m}\left(x_{i}\right)\ne y_{i} \end{aligned} \right.$

这意味着正确分类的样本权重降低，而错误分类的样本权重增加。

AdaBoost 的训练过程代码如下所示：

def train(self, train_data, train_label):
        if self.norm_type == "Standardization":
            train_data = preProcess.Standardization(train_data)
        else:
            train_data = preProcess.Normalization(train_data)

        train_label = np.expand_dims(train_label, axis=1)
        sample_num = len(train_data)

        weak_classifier = []

        # initialize weights
        w = np.ones([sample_num, 1])
        w = w/sample_num

        # predictions
        agg_predicts = np.zeros([sample_num, 1]) # aggregate value of prediction

        # start train
        for i in range(self.iterations):
            base_clf, error, base_prediction = self.baseClassifier(train_data, train_label, w)
            alpha = self.updateAlpha(error)
            weak_classifier.append((alpha, base_clf))

            # update parameters in page of 139 Eq.(8.4)
            expon = np.multiply(-1 * alpha * train_label, base_prediction)
            w = np.multiply(w, np.exp(expon))
            w = w/w.sum()

            # calculate the total error rate
            agg_predicts += alpha*base_prediction
            error_rate = np.multiply(np.sign(agg_predicts) != train_label, 
                         np.ones([sample_num, 1]))
            error_rate = error_rate.sum()/sample_num

            if error_rate == 0:
                break
            self.classifier_set = weak_classifier
        return weak_classifier

分类

将所有弱分类器组合起来得到一个强分类器。分类规则是每个弱分类器结果的加权和，公式如下：

$G\left(x\right)=sign\left(\sum_{m=1}^{M}\alpha_{m}G_{m}\left(x\right)\right)$

结论与分析

AdaBoost 可以被视为使用前向步进算法的具有指数损失函数的加性模型。在 AdaBoost 中，弱分类器的类型可以是不同的，也可以是相同的。在本文中，我们使用 5 个 SVM 分类器作为弱分类器，检测性能如下所示：

可以看出，准确率提高了约 5%，而运行时间是单个 SVM 的约 5 倍。

本文相关的代码和数据集可以在 MachineLearning 中找到。