Adaboost

什么是 AdaBoost 算法？

Adaboost（Adaptive Boosting）是一种基于 Boosting 的算法，用于提高一组弱分类器的性能。它通过组合多个简单的模型（通常称为弱学习器）来创建一个强大的总体模型。Adaboost 算法本身是通过改变数据分布来实现的，它根据每次训练集中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据送给下层分类器进行训练，最后将每次得到的分类器融合起来，作为最后的决策分类器。

算法原理：

输入：训练数据集

\[T = \{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\}\]

其中，每个样本点由实例与标记组成。实例 $x_i \in X=R^n$，$y_i \in Y = \{+1, -1\}$

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

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

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

对 $m=1,2,\ldots,M$
使用具有权值分布 $D_m$ 的训练数据学习，得到基本分类器

$\(G_m(x) : X \rightarrow \{-1, +1\}$\)
计算 $G_m(x)$ 在训练数据集上的分类误差率

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

其中，$I$ 是一个指示函数，如果样本 $x_i$ 被错误分类，则值为 1，否则为 0。
计算 $G_m(x)$ 的系数

$\(\alpha_m = \frac{1}{2} \log \frac{1 - e_m}{e_m}$\)

这里的对数是自然对数
更新训练数据集的权值分布

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

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

这里，$Z_m$ 是规范化因子，它使 $D_{m+1}$ 成为一个概率分布。

$\(Z_m = \sum_{i=1}^{N} w_{mi} \exp(-\alpha_m y_i G_m(x_i))$\)
构建基本分类器的线性组合

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

得到最终分类器

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

说明

步骤（1）假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设保证第一步能够在原始数据上学习基本分类器$G_1(x)$。
步骤（2）AdaBoost 反复学习基本分类器，在每一轮 m=1,2,...,M 顺次地执行下列操作：
使用当前分布 $D_m$ 加权的训练数据集，学习基本分类器 $G_m(x)$。
计算基本分类器 $G_m(x)$ 在加权训练数据集上的分类误差率：

\[e_m = P(G_m(x_i) \neq y_i) = \sum_{G_m(x_i) \neq y_i} w_{mi}\]

这里，$w_{mi}$ 表示第 m 轮中第 i 个实例的权值，

\[\sum_{i=1}^{N} w_{mi} = 1\]

这表明，$G_m(x)$ 在加权的训练数据集上的分类误差率是被 $G_m(x)$ 误分类样本的权值之和，由此可以看出数据权值分布 $D_m$与基本分类器 $G_m(x)$ 的分类误差率的关系。
计算基本分类器 $G_m(x)$ 的系数 $α_m$。$α_m$ 表示 $G_m(x)$ 在最终分类器中的重要性。由前面的 $α_m$ 的计算公式可知，当 $e_m ≤1/2$时，$α_m≥0$，并且 $α_m$ 随着 $e_m$ 的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。
更新训练数据的权值分布为下一轮作准备，前面算法计算 $w_{m+1,i}$ 可以写成

\[w_{m+1,i} = \begin{cases} \frac{w_{mi}}{Z_m} \exp(-\alpha_m), & \text{if } G_m(x_i) = y_i \\ \frac{w_{mi}}{Z_m} \exp(\alpha_m), & \text{if } G_m(x_i) \neq y_i \end{cases} \]

由此可知，被基本分类器 $G_m(x)$ 误分类的样本的权值得以扩大，而被正确分类的样本的权值却得以缩小。两相比较，误分类的样本的权值被放大了。

\[e^{2\alpha_m} = \frac{1 - e_m}{e_m}\]

倍。因此，误分类样本在下一轮学习中起到更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是AdaBoost的一个特点。
步骤（3）线性组合 f(x) 实现 M 个基本分类器的加权表决。系数 $α_m$ 表示了基本分类器 $G_m(x)$ 的重要性，这里，所有 $α_m$ 之和并不为1。f(x) 的符号决定实例 x 的类，f(x) 的绝对值表示分类的确信度。利用基本分类器的线性组合构建最终分类器是 AdaBoost 的另一个特点。

下面是使用 sklearn 实现 adaboost 算法的一个简单示例。

from sklearn.ensemble import AdaBoostClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# 创建一个虚拟的二分类数据集
X, y = make_classification(n_samples=1000, n_features=20, n_informative=2, n_redundant=0, random_state=42)

# 将数据分为训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 创建AdaBoost实例
# 默认情况下，AdaBoostClassifier 使用决策树作为弱学习器
ada = AdaBoostClassifier(n_estimators=50, learning_rate=1, random_state=42)

# 训练模型
ada.fit(X_train, y_train)

# 预测测试集
y_pred = ada.predict(X_test)

# 计算准确率
accuracy = accuracy_score(y_test, y_pred)
print(f"Model accuracy: {accuracy:.2f}")

在这个例子中，首先使用 make_classification 函数生成了一个虚拟的二分类数据集。然后，数据集被分成训练集和测试集。接着创建一个 AdaBoostClassifier 实例，指定了弱学习器的数量（n_estimators），并对其进行训练。最后，模型在测试集上进行预测，计算并打印出准确率。

aaa

AdaBoost 算法的理论解释？

AdaBoost 算法被描述为当模型是加法模型、损失函数是指数函数、学习算法是前向分布算法时的二分类学习方法。

前向分布算法

考虑加法模型

\[f(x) = \sum_{m=1}^{M} \beta_m b(x; \gamma_m)\]

其中，$b(x; \gamma_m) $ 为基函数，$\gamma_m$ 为基函数的参数，$\beta_m$ 为基函数的系数。

显然，上面构建的基本分类器的线性组合（adaboost）

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

是一个加法模型。

在给定训练数据及损失函数 $L(y, f(x))$ 的条件下，学习加法模型 $f(x)$ 就是损失函数极小化问题。

\[\min_{\beta_m, \gamma_m} \sum_{i=1}^{N} L \left( y_i, \sum_{m=1}^{M} \beta_m b(x_i; \gamma_m) \right)\]

通常这是一个复杂的优化问题，前向分布算法求解这一优化问题的想法是：如果能够从前到后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化复杂度。具体地，每步只需优化如下损失函数：

\[\min_{\beta, \gamma} \sum_{i=1}^{N} L \left( y_i, \beta b(x_i; \gamma) \right)\]

给定训练数据集 $T = \{ (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) \}, \quad x_i \in \mathbb{R}^n, \quad y_i \in \{+1, -1\}$，学习加法模型 $f(x) $ 的前项分布算法如下：

输入：训练数据集集 $T = \{ (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) \}$；损失函数 $L(y,f(x))$；基函数集$\{b(x; \gamma)\}$；

输出：加法模型f(x)。

初始化 $f_0(x)=0$
对 $m=1,2,\ldots,M$
极小化损失函数

$\((\beta_m, \gamma_m) = \arg \min_{\beta, \gamma} \sum_{i=1}^{N} L(y_i, f_{m-1}(x_i) + \beta b(x_i; \gamma))$\)

得到参数$\beta_m,\gamma_m$
更新

$\(f_m(x) = f_{m-1}(x) + \beta_m b(x; \gamma_m)$\)
得到加法模型

$\(f(x) = f_M(x) = \sum_{m=1}^{M} \beta_m b(x; \gamma_m)$\)

这样，前向分步算法将同时求解 m=1 到 M 所有参数 $\beta_m, \gamma_m$ 的优化问题简化为逐步求解各个$\beta_m, \gamma_m$ 的优化问题。

前向分步算法与AdaBoost

AdaBoost 算法是前向分布加法算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数是指数函数。

Adaboost 每轮训练都有错误分类的样本，但为何算法却能快速收敛？

每轮训练结束后，AdaBoost 会对样本的权重进行调整，调整的结果是越到后面被错误分类的样本权重会越高。而后面的分类器为了达到较低的带权分类误差，会把样本权重高的样本分类正确。这样造成的结果是，虽然每个弱分类器可能都有分错的样本，然而整个 AdaBoost 却能保证对每个样本进行正确分类，从而实现快速收敛。

Adaboost 使用m个基学习器和Bagging加权平均使用m个学习器之间有什么不同？

Adaboost 的 m 个基学习器是有顺序关系的，第 k 个基学习器根据前 k-1个学习器得到的误差更新数据分布，再进行学习，每一次的数据分布都不同，是使用同一个学习器在不同的数据分布上进行学习。

加权平均的 m 个学习器是可以并行处理的，在同一个数据分布上，学习得到 m 个不同的学习器进行加权。

Adaboost和随机森林有什么区别？

AdaBoost 和随机森林都是集成学习方法，但它们在集成构建方式、基学习器、以及对数据的处理方法等方面有着根本的区别。

基学习器：AdaBoost 通常使用一系列的弱学习器，比如简单的决策树（通常是一个节点的决策树，也称为决策桩）。
学习方式：AdaBoost 是顺序学习的，每一个学习器都是在前一个学习器的基础上，增加其对错误分类样本的关注，逐渐改进模型。
权重调整：AdaBoost 通过调整数据点的权重来关注难以正确分类的样本。每一轮迭代后，被错分的样本权重会增加，从而在下一轮训练中强制学习器更加注意这些样本。
输出：AdaBoost 的最终模型是基于每个弱学习器的性能来加权的。

aaa

随机森林

基学习器：随机森林使用的是多个决策树，这些决策树通常比 AdaBoost 中使用的决策树要复杂得多。
学习方式：随机森林是并行学习的，每一棵树都是独立构建的，并且在构建过程中引入了随机性。
样本抽样：随机森林通过自举抽样来训练每一棵树。
输出：随机森林的最终模型是基于多数投票（分类问题）或平均预测（回归问题）的。

AdaBoost 算法的优缺点？

优点：

1、Adaboost 是一种有很高精度的分类器；

2、在 Adaboost 的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。

3、作为简单的二元分类器时，构造简单，结果可理解。

4、不容易发生过拟合

缺点：

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

aaa

Keys	Action
`?`	Open this help
`n`	Next page
`p`	Previous page
`s`	Search