Boosting算法特征如下：通过将一些表现效果一般（可能仅仅优于随机猜测）的模型通过特定方法进行组合来获得一个表现效果较好的模型。从抽象的角度来看，Boosting算法是借助convex loss function在函数空间进行梯度下降的一类算法。Gradient Boost和Adaboost就是其中比较常见的两种。
Adaboost 是 Boosting 算法中有代表性的一个。由 Yoav Freund 和 Robert Schapire 提出，两人因此获得了哥德尔奖。

示例

二元分类问题，例如如何划分红球和篮球。显然这个问题用一个线性分类器的话很难取得最好的效果。有没有办法通过组合一系列和正方形平行的线（每条线都相当于一个线性分类器）来获得一个比较好的分类效果呢？
第一步：先矮子里拔将军，选择一条平行于四边且最不坏的线段。下图第一排中间的小图里，直线把图分为左边（红点）和右边（蓝点）两类，被错分的点只有3个，这似乎是能得到的最好的结果了。然后我们想去找第二条线（第二个线性分类器）。如果只是基于现有的这些点的话那么说不定得到的线段还是和之前那条差不多，那多个线段（线性分类器）就没有意义了。所以我们要稍微调整一下某些点在分类结果里的重要性，提升他们的权重。我们在这里提升了那三个被错分的点的权重。
第二步：我们找到了一条新的线段，因为之前提升了把蓝点和蓝点分在一起的重要性，所以这条线段没有选择平行于上下两边把上面4个点（1红3蓝）和下面7个点（5红2蓝）分开，而是选择尽可能多地把蓝点归在一起。然而这次不同的是我们分错的是右边那4个红点，于是我们放大那4个红点，提升他们的权重。
alt text
不断重复这一过程。

最终我们得到了多个线性分类器，把这些线性分类器的结果做一个线性组合，我们就得到了整个集成模型的结果。每个线性分类器的结果的系数（权重）取决于它的表现，表现越好，权重越高。比如第一条线段的分类错误就优于第二条线段，那么它获得的权重也就会更大。集成模型的效果非常好。
alt text
资料来源：Mehryar Mohris Foundations of Machine Learning的上课讲义
顺带一提，第一条线段的分类正确率是8/11，第二条线段的分类正确率是7/11，第三条线段的分类正确率是8/11，确实要好于随机猜测（以1/2为界）。
把 AdaBoost 和一开始对 Boosting 算法的定义比较看看，我们确实通过组合一系列表现一般的模型获得了一个表现优秀的模型。另外值得注意的是在训练过程中，每个新的模型都会基于前一个模型的表现结果进行调整（调整过程是和bagging类算法的主要区别），这也就是为什么 AdaBoost 是自适应（adaptive）的原因。

算法数学原理

原始的 Adaboost 算法用于解决二分类问题，因此对于一个训练集
$$ T = {\left(x_1, y_1\right), \left(x_2, y_2\right), …, \left(x_n, y_n\right)} $$
其中 (x_i \in \mathcal{X} \subseteq \mathbb{R}^n, y_i \in \mathcal{Y} = {-1, +1})，首先初始化训练集的权重
$$ \begin{equation} \begin{split} D_1 =& \left(w_{11}, w_{12}, …, w_{1n}\right) \ w_{1i} =& \dfrac{1}{n}, i = 1, 2, …, n \end{split} \end{equation} $$
根据每一轮训练集的权重 (D_m)，对训练集数据进行抽样得到 (T_m)，再根据 (T_m) 训练得到每一轮的基学习器 (h_m)。通过计算可以得出基学习器 (h_m) 的误差为 (\epsilon_m)，根据基学习器的误差计算得出该基学习器在最终学习器中的权重系数
$$ \alpha_m = \dfrac{1}{2} \ln \dfrac{1 - \epsilon_m}{\epsilon_m} $$
更新训练集的权重
$$ \begin{equation} \begin{split} D_{m+1} =& \left(w_{m+1, 1}, w_{m+1, 2}, …, w_{m+1, n}\right) \ w_{m+1, i} =& \dfrac{w_{m, i}}{Z_m} \exp \left(-\alpha_m y_i h_m\left(x_i\right)\right) \end{split} \end{equation} $$
其中 (Z_m) 为规范化因子
$$ Z_m = \sum_{i = 1}^{n} w_{m, i} \exp \left(-\alpha_m y_i h_m \left(x_i\right)\right) $$
从而保证 (D_{m+1}) 为一个概率分布。最终根据构建的 (M) 个基学习器得到最终的学习器：
$$ h_f\left(x\right) = \text{sign} \left(\sum_{m=1}^{M} \alpha_m h_m\left(x\right)\right) $$

代码实现

# Importing necessary libraries
from sklearn.datasets import load_iris
from sklearn.model_selection 
import train_test_split
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
# 加载 Iris 数据集。
iris = load_iris()
X, y = iris.data, iris.target
# 将数据集分为训练集和测试集。
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# 定义 max_depth=1 的基础决策树分类器来创建弱学习器。
base_classifier = DecisionTreeClassifier(max_depth=1)
# 使用基分类器（决策树）定义 AdaBoost 分类器，并指定要使用的估计器（增强轮数）的数量
adaboost_classifier = AdaBoostClassifier(estimator=base_classifier, n_estimators=50, random_state=42)
# 在训练数据上训练 AdaBoost 分类器。
adaboost_classifier.fit(X_train, y_train)
# 预测测试数据的标签。
y_pred = adaboost_classifier.predict(X_test)
# 最后，我们计算 AdaBoost 分类器在测试集上的准确率。
accuracy = accuracy_score(y_test, y_pred)
print("Accuracy:", accuracy)

reference

精通梯度提升算法