Adaboost

Adaboost report

这篇文章介绍了Adaboost算法、给出了 Adaboost 的 python 实现和误差分析。

Description

Adaboost算法主要针对分类问题。Boost 方法指的是将弱分类器提升成强分类器的方法。大多数提升方法都基于改变训练样本权重来实现。AdaBoost 迭代地训练弱分类器，每次迭代会增加前一个弱分类器错误分类样本权重方式，让下一个弱分类器更关注分类错误的样本。最后，Adaboost通过加权平均的方式将弱分类器结合起来，成为一个强分类器。Adaboost 巧妙地将改变错误样本的权重和弱分类器加权平均之间的权重结合起来，算法很巧妙且有效。

Adaboost algorithm

Adaboost 算法Step-by-Step，最后输出 G(x) 作为分类器。

1. 初始化带有标签的训练数据集： $D=(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$，其中 $x_i$ 表示第 $i$ 个示例的特征向量，$y_i$ 表示其对应的标签。

2. 初始化训练示例的权重分布：$w_i=\frac{1}{n}$，其中 $i=1,2,...,n$，$n$ 是训练示例的总数。

3. 对于 $t=1\to T$，执行以下步骤：

   1. 使用训练数据 $D$ 和对应的权重 $w_i$ 训练一个弱分类器 $h_t$。
   2. 计算弱分类器 $h_t$ 的加权误差 ${\epsilon }_t={\sum }_{i=1}^n{w}_i\cdot \text{error}(h_t(x_i),y_i)$
   3. 计算弱分类器 $h_t$ 在最终集成中的权重：${\alpha }_t=\frac{1}{2}\cdot \log \left(\frac{1-{\epsilon }_t}{{\epsilon }_t}\right)$。
   4. 根据 $h_t$ 的表现重新调整每个示例的权重分布 $w_i\leftarrow w_i\cdot \exp \left(-{\alpha }_t\cdot y_i\cdot h_t(x_i)\right)$。
   5. 将权重分布 $w_i$ 进行归一化，使其总和为1：$w_i\leftarrow \frac{w_i}{{\sum }_{j=1}^n{w}_j}$。

4. 输出最终的增强集成分类器：$\text{G}(x)=\text{sign}\left({\sum }_{t=1}^T{\alpha }_t\cdot h_t(x)\right)$。

该算法迭，每个分类器都专注于在前一次迭代中被误分类的示例。最终的增强集成将所有弱分类器的预测进行组合，给予表现更好的分类器更高的权重。

Error bound

可以证明 Adaboost 的误差成指数下降，具体为：

$$\frac{1}{N}\sum _{i=1}^{n}error(G(x_i)\ne y_i)\le \prod _t{\mathbf{Z}}_t=\prod _{t=1}^T[2\sqrt{{\epsilon }_t(1-{\epsilon }_t)}]\le \exp (-2\sum _{t=1}^T{\gamma }_t^2)$$

其中 ${\mathbf{Z}}_t={\sum }_{j=1}^n{w}_j$，${\gamma }_t=0.5-{\epsilon }_t$

Results

将”diabetes_scale.txt” 以8:2的分割成训练/测试数据集后，使用上面提到的算法运行T=300 steps，得到的结果为： train acc: 0.85505, test acc: 0.77273

Error curve 结果如下，呈现出指数下降趋势。

add error bound

增加了Error bound 后的图如下，发现 Bound 与 Error 之间还是有比较大的差距。

Comparasion with SVM

使用 Libsvm 实现的SVM 与我自己实现的Adaboost使用同样的训练测试集运行后，得到的结果为：Accuracy = 74.6753% (115/154) (classification)。 可以发现 Adaboost 取得了更好的效果，但是也不能说 Adaboost 一定比 SVM 优秀。 SVM 使用支持向量分类，最后得到的模型复杂度很低，但 Adaboost 运行几轮就需要保存几个弱分类器，这可能导致复杂度比较高。同时，由于 Adaboost 算法会更关注分类错误的数据样本，这可能导致模型抗噪声能力较弱，但 SVM 使用最大化边界来决策，可能会更 Robust。Adaboost 和 SVM 都是很好的分类模型，也都有成熟的库，所以来一个问题应该都试试：）