机器学习经典算法 - Bagging & Boosting

Ensemble Learning

集成学习通过整合多个不同模型来实现对复杂问题的更准确建模，其实现方式多样，但共同的特征是：从总体数据集的多个子集中发掘出针对该子集具有分类能力，但不一定在其他子集当中同样有效的特征，通过该特征分别实现数据集的分类，再将结果进行集成。

Bagging & Boosting 是集成学习的典型代表。最简单的 Ensemble Learning 就是通过将数据随机划分多个子集，在每个子集上进行拟合，再将最终结果进行平均化，这种方法也被称为 Bagging，或者称为 Bootstrap aggregation，其实现优化的原理在于其可以通过平均化差异使得最终的模型可以有效的防止异常数据的影响。

Boosting

在此重点介绍以 AdaBoost (Adaptive Boosting) 为代表的 Boosting 算法，Boosting 算法想解决的核心问题就在于是否可以通过一系列的 Weak Learner 的组合来实现一个更高性能的 Learner 模型，这个过程中的性能增强也就是 Boosting 这个名称的由来。AdaBoost 算法中涉及到的两个重要的概念是 Weak learner 和样本权重：

Weak Learner：被定义为对于服从任意分布 D 的样本，其分类准确率仅需高于随机猜测的结果，在实际算法中 Weak Learner 可以是任意已知的监督学习方法，如 SVM，线性回归，逻辑回归，甚至是深度神经网络，但最常用的是决策树

What weak learner you should choose is then a trade off between 3 factors:

The bias of the model. A lower bias is almost always better, but you don't want to pick something that will overfit (yes, boosting can and does overfit)

The training time for the weak learner. Generally we want to be able to learn a weak learner quickly, as we are going to be building a few hundred (or thousand) of them.

The prediction time for our weak learner. If we use a model that has a slow prediction rate, our ensemble of them is going to be a few hundred times slower!

样本权重：在实际问题中，很可能存在的情况是某些样本相对另一些样本来说出现的可能性更大，此时仅仅采用平均化的方式过于简化，在实际的 Boosting 算法中一般采用加权平均的方式

The observation weight might come in as domain knowledge for example, we may know, based on past experience, that we are more likely to encounter a training example j compared to example k. Therefore we should assign a larger weight to example j, since it is the one that will have a greater influence on our function approximation process.

对于样本给予权重的一个好处是我们可以在计算分类器的误差的同时也将样本权重考虑在内。具体地，对于一个包含 N 个样本的样本集 (x_i, y_i)，x_i 为包含多个特征的向量，y_i 的取值为 -1 或 1，假设对于任意一个分类器 G 来说，其针对任意输入 x_i 对应的预测值为 G(x_i) ∈ {-1, 1}，此时在不考虑样本权重时可以通过统计被错误分类的样本数量来计算误差值：

error = ΣI(y_i ≠ G(x_i)), i = 1, 2, ... , N

在考虑权重后，这一误差值则可以改进为：

error = Σw_iI(y_i ≠ G(x_i)) / Σw_i, i = 1, 2, ... , N

AdaBoost 算法实现

AdaBoost 算法的实现过程为：

首先初始化各个样本的权重值，令 w_i = 1 / N
对于 m = 1 到 M，循环执行：
- 在考虑样本权重 w_i 的前提下训练一个分类器 G_m(x)
- 计算考虑权重的误差值 err_m = Σw_iI(y_i ≠ G(x_i)) / Σw_i, i = 1, 2, ... , N
- 计算 α_m = log((1 - err_m) / err_m)
- 对于 i = 1, 2, ... , N，更新权重 w_i = w_i ⋅ e^{α_mI(y_i ≠ G(x_i))}
G(x) = sign[α_mG_m(x)], m = 1, 2, ... , M

上述计算过程中 α_m 和 err_m 的关系如下图所示，其中：

当 err_m < 0.5，也即若分类器的误差表现高于随机猜测时，α_m > 0，且误差 err_m 越小，α_m 越大，也即当前这个分类器 G_m(x) 的准确率越高
样本权重更新过程中，当 G_m(x) 无法准确分类样本 x_i 时，w_i 会变大，后续的分类器 G_m+1(x) 就会对这个样本更加重视，反之亦然

The AdaBoost algorithm trains multiple weak classifiers on training data, and then combines those weak classifiers into a single boosted classifier. The combination is done through a weighted sum of the weak classifiers with weights dependent on the weak classifier accuracy.

The relationship between α and error

注意事项

尽管 Boosting 在对抗过拟合方面有先天的优势，当采用深度神经网络作为 Weak learner 时，这一优势将不再明显。另外，当数据中存在 pink noise 也即 uniform noise 时，Boosting 仍然无法避免过拟合。

机器学习经典算法 - Bagging & Boosting