文章目录

• AdaBoost 算法
• • Boosting 的基本思路
  • AdaBoost 算法
• 提升树
• • 提升树模型
  • 提升树算法
  • 梯度提升
• References

Boosting 是一种常用的机器学习方法，应用广泛且有效。在分类问题中，它通过改变训练样本的权重学习多个弱分类器，由这些弱学习器的预测结果通过加权投票的方式组合，得到最终的预测结果。在每一次所谓的提升（boosting）迭代中，修改每一个训练样本应用于新一轮学习器的权重。

初始化时,将所有弱学习器的权重都设置为 wi=1/Nw_i = 1/Nwi​=1/N ,因此第一次迭代仅仅是通过原始数据训练出一个弱学习器。在接下来的连续迭代中，样本的权重逐个地被修改，学习算法也因此要重新应用这些已经修改的权重。在给定的一个迭代中,，那些在上一轮迭代中被预测为错误结果的样本的权重将会被增加，而那些被预测为正确结果的样本的权重将会被降低。随着迭代次数的增加，那些难以预测的样例的影响将会越来越大，每一个随后的弱学习器都将会被强迫更加关注那些在之前被错误预测的样例。

AdaBoost 算法

Boosting 的基本思路

Boosting 基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断要比其中任何一个专家单独的判断好。实际上就是“三个臭皮匠顶个诸葛亮”的道理。

在概率近似正确（probably approximately correct，PAC）学习的框架中，对于一个概念（一个类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；如果存在一个多项式的学习算法能够学习它，但学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。

发现弱学习算法通常要比发现强学习算法容易得多，那么如何具体实施提升，便成为 Boosting 所要解决的问题。这其中最具代表性的算法就是 AdaBoost 算法。

Boosting 从弱学习算法出发，反复学习，得到一系列弱分类器，然后组合这些弱分类器，构成一个强分类器。大多数的 Boosting 都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

这样，对于 Boosting 来说，就有两个问题需要回答：

1. 在每一轮如何改变训练数据的权值或概率分布；
2. 如何将弱分类器组合成一个强分类器。

关于第一个问题，AdaBoost 的做法是，在上一轮迭代中被预测为错误结果的样本的权重将会被增加，被预测为正确结果的样本的权重将会被降低，这样没有得到正确分类的数据，由于其权值的增大将受到后一轮的弱分类器的更大关注。

至于第二个问题，AdaBoost 采取加权多数表决的方法，具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用；减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

AdaBoost 算法

假设给定一个二分类的训练数据集
T={(x1,y1),(x2,y2),⋯,(xN,yN)}T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\} T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}其中，xi∈X=Rnx_i\in \mathcal{X}=\mathbb{R}^nxi​∈X=Rn，yi∈Y={+1,−1}，i=1,2,...,Ny_i\in \mathcal{Y}=\{+1,-1\}，i=1,2,...,Nyi​∈Y={+1,−1}，i=1,2,...,N。AdaBoost 利用以下算法，从训练数据中学习一系列弱分类器或基本分类器，并将这些弱分类器线性组合成为一个强分类器。

输入：训练数据集 TTT；弱学习算法

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

1. 初始化训练数据的权值分布 D1=(w11,⋯,w1i,⋯,w1N),w1i=1N,i=1,2,...,ND_1=(w_{11},\cdots,w_{1i},\cdots,w_{1N}),\quad w_{1i}=\frac{1}{N},\quad i=1,2,...,ND1​=(w11​,⋯,w1i​,⋯,w1N​),w1i​=N1​,i=1,2,...,N

2. 对 m=1,2,⋯,Mm=1,2,\cdots,Mm=1,2,⋯,M，
   
   （a）使用具有权值分布 DmD_mDm​ 的训练数据集学习，得到基本分类器： Gm(x):X→{+1,−1}G_m(x):\mathcal{X} \to \{+1,-1\}Gm​(x):X→{+1,−1} （b）计算 Gm(x)G_m(x)Gm​(x) 在训练数据集上的分类误差率： em=∑i=1NP(Gm(xi)≠yi)=∑i=1NwmiI(Gm(xi)≠yi)e_m=\sum_{i=1}^N P(G_m(x_i)\neq y_i)=\sum_{i=1}^N w_{mi} I(G_m(x_i)\neq y_i)em​=i=1∑N​P(Gm​(xi​)=yi​)=i=1∑N​wmi​I(Gm​(xi​)=yi​)（c）计算 Gm(x)G_m(x)Gm​(x) 的系数 αm=12log⁡1−emem\alpha_m=\frac{1}{2}\log \frac{1-e_m}{e_m}αm​=21​logem​1−em​​ （d）更新训练数据集的权值分布 Dm+1=(wm+1,1,⋯,wm+1,i,⋯,wm+1,N)D_{m+1}=(w_{m+1,1},\cdots,w_{m+1,i},\cdots,w_{m+1,N})Dm+1​=(wm+1,1​,⋯,wm+1,i​,⋯,wm+1,N​) wm+1,i=wmiZmexp⁡(−αmyiGm(xi)),i=1,2,...,Nw_{m+1,i}=\frac{w_{mi}}{Z_m} \exp (-\alpha_m y_i G_m(x_i)),\quad i=1,2,...,Nwm+1,i​=Zm​wmi​​exp(−αm​yi​Gm​(xi​)),i=1,2,...,N 这里，ZmZ_mZm​ 是规范化因子，且 Zm=∑i=1Nwmiexp⁡(−αmyiGm(xi))Z_m=\sum_{i=1}^N w_{mi} \exp (-\alpha_m y_i G_m(x_i))Zm​=i=1∑N​wmi​exp(−αm​yi​Gm​(xi​)) 它使 Dm+1D_{m+1}Dm+1​ 成为一个概率分布。

3. 构建基本分类器的线性组合 f(x)=∑m=1MαmGm(x)f(x)=\sum_{m=1}^M \alpha_m G_m(x)f(x)=m=1∑M​αm​Gm​(x) 得到最终分类器 G(x)=sign(f(x))G(x)=\text{sign}(f(x))G(x)=sign(f(x))

对 AdaBoost 算法作如下说明：

1. 步骤 1 假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设保证第一步能够在原始数据上学习基本分类器 G1(x)G_1(x)G1​(x)。
2. 步骤 2 中反复学习基本分类器：
   
   （b）∑i=1Nwmi=1\sum_{i=1}^N w_{mi}=1∑i=1N​wmi​=1。这表明，Gm(x)G_m(x)Gm​(x) 在加权的训练数据集上的分类误差率是被 Gm(x)G_m(x)Gm​(x) 误分类样本的权值之和。
   
   （c）当 em≤1/2e_m \le 1/2em​≤1/2 时，αm≥0\alpha_m \ge 0αm​≥0，并且 αm\alpha_mαm​ 随着 eme_mem​ 的减小而增大。
   
   （d）更新权值的公式可以写为 wm+1,i={wmiZme−αm,Gm(xi)=yiwmiZmeαm,Gm(xi)≠yiw_{m+1,i}= \left\{ \begin{aligned} &\frac{w_{mi}}{Z_m} e^{-\alpha_m},\ & G_m(x_i)=y_i \\ & \frac{w_{mi}}{Z_m} e^{\alpha_m},\ & G_m(x_i)\neq y_i \end{aligned} \right.wm+1,i​=⎩⎨⎧​​Zm​wmi​​e−αm​, Zm​wmi​​eαm​, ​Gm​(xi​)=yi​Gm​(xi​)=yi​​
   由此可知，被基本分类器误分类样本的权值得以扩大，而被正确分类的样本的权值得以缩小。结合（c）中的系数，误分类样本的权值被放大 e2αm=(1−em)/eme^{2\alpha_m}=(1-e_m)/e_me2αm​=(1−em​)/em​ 倍。

下面的示例展示了如何训练一个包含 100 个弱学习器的 AdaBoost 分类器：

from sklearn.model_selection import cross_val_score
from sklearn.datasets import load_iris
from sklearn.ensemble import AdaBoostClassifieriris = load_iris()
clf = AdaBoostClassifier(n_estimators=100)
scores = cross_val_score(clf, iris.data, iris.target)
scores.mean()

提升树

提升树是以分类树或回归树为基本分类器的 Boosting。提升树被认为是机器学习中性能最好的方法之一。

提升树模型

以决策树为基函数的 Boosting 称为提升树。提升树模型可以表示为决策树的加法模型：
fM(x)=∑m=1MT(x;Θm)f_M(x)=\sum_{m=1}^M T(x;\Theta_m) fM​(x)=m=1∑M​T(x;Θm​)其中， T(x;Θm)T(x;\Theta_m)T(x;Θm​) 表示决策树，Θm\Theta_mΘm​ 为决策树的参数，MMM 为树的个数。

提升树算法

提升树采用前向分步算法。首先确定初始提升树 f0(x)=0f_0(x)=0f0​(x)=0，第 mmm 步的模型是
fm(x)=fm−1(x)+T(x;Θm)f_m(x)=f_{m-1}(x)+T(x;\Theta_m) fm​(x)=fm−1​(x)+T(x;Θm​)通过经验风险最小化确定第 mmm 步决策树的参数 Θm\Theta_mΘm​：
Θ^m=arg min⁡Θm∑i=1NL(yi,fm−1(x)+T(xi;Θm))\hat{\Theta}_m=\argmin_{\Theta_m} \sum_{i=1}^N L(y_i,f_{m-1}(x)+T(x_i;\Theta_m)) Θ^m​=Θm​argmin​i=1∑N​L(yi​,fm−1​(x)+T(xi​;Θm​)) 由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。

下面讨论针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括用平方误差损失函数的回归问题、用指数损失函数的分类问题，以及用一般损失函数的一般决策问题。

对于二分类问题，提升树只需将 AdaBoost 算法中的基本分类器限制为二类分类树即可。下面叙述回归问题的提升树。

已知一个训练数据集 T={(x1,y1),(x2,y2),⋯,(xN,yN)},xi∈X=Rn，yi∈Y=RT=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\},\ x_i\in \mathcal{X}=\mathbb{R}^n，y_i\in \mathcal{Y}=\mathbb{R}T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}, xi​∈X=Rn，yi​∈Y=R。在决策树中我们已经讨论了回归树的问题。如果将输入空间 X\mathcal{X}X 划分为 JJJ 个互不相交的区域 R1,R2,⋯,RJR_1,R_2,\cdots,R_JR1​,R2​,⋯,RJ​，并且在每个区域上确定输出的常量 cjc_jcj​，那么树可表示为
T(x;Θ)=∑j=1JcjI(x∈Rj)T(x;\Theta)=\sum_{j=1}^J c_j I(x \in R_j) T(x;Θ)=j=1∑J​cj​I(x∈Rj​)其中，参数 Θ={(R1,c1),(R2,c2),⋯,(RJ,cJ)}\Theta=\{(R_1,c_1),(R_2,c_2),\cdots,(R_J,c_J)\}Θ={(R1​,c1​),(R2​,c2​),⋯,(RJ​,cJ​)} 表示树的区域划分和各区域上的常数，JJJ 是回归树的复杂度即叶结点的个数。

回归问题提升树当采用平方误差损失函数时，
L(y,f(x))=(y−f(x))2L(y,f(x))=(y-f(x))^2 L(y,f(x))=(y−f(x))2其损失变为L(y,fm−1(x)+T(x;Θm))=(y−fm−1(x)−T(x;Θm))2=(r−T(x;Θm))2\begin{aligned} L(y,f_{m-1}(x)+T(x;\Theta_m))&=(y-f_{m-1}(x)-T(x;\Theta_m))^2 \\&=(r-T(x;\Theta_m))^2 \end{aligned}L(y,fm−1​(x)+T(x;Θm​))​=(y−fm−1​(x)−T(x;Θm​))2=(r−T(x;Θm​))2​
这里 r=y−fm−1(x)r=y-f_{m-1}(x)r=y−fm−1​(x) 是当前模型拟合数据的残差（residual）。所以，对回归问题的提升树算法来说，只需简单地拟合当前模型的残差。

梯度提升

提升树利用加法模型与前向分布算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。针对这一问题，提出梯度提升（gradient boosting）算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值
−[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)-\left[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\right]_{f(x)=f_{m-1}(x)} −[∂f(xi​)∂L(y,f(xi​))​]f(x)=fm−1​(x)​作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

下图展示了应用损失函数为最小二乘损失，基学习器个数为 500 的 GradientBoostingRegressor 来处理 sklearn.datasets.load_diabetes 数据集的结果。左图表示每一次迭代的训练误差和测试误差。每一次迭代的训练误差保存在提升树模型的 train_score_ 属性中，每一次迭代的测试误差能够通过 staged_predict 方法获取，该方法返回一个生成器，用来产生每一个迭代的预测结果。类似下面这样的图表，可以用于决定最优的树的数量，从而进行提前停止。右图表示每个特征的重要性，它 可以通过 feature_importances_ 属性来获取。

import matplotlib.pyplot as plt
import numpy as np
from sklearn import datasets, ensemble
from sklearn.inspection import permutation_importance
from sklearn.metrics import mean_squared_error
from sklearn.model_selection import train_test_splitdiabetes = datasets.load_diabetes()
X, y = diabetes.data, diabetes.targetX_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.1, random_state=13
)params = {"n_estimators": 500,"max_depth": 4,"min_samples_split": 5,"learning_rate": 0.01,"loss": "squared_error",
}reg = ensemble.GradientBoostingRegressor(**params)
reg.fit(X_train, y_train)mse = mean_squared_error(y_test, reg.predict(X_test))train_score = reg.train_score_test_score = np.zeros((params["n_estimators"],), dtype=np.float64)
for i, y_pred in enumerate(reg.staged_predict(X_test)):test_score[i] = mean_squared_error(y_test, y_pred)fig = plt.figure(figsize=(6, 6))
plt.title("Deviance")
plt.plot(np.arange(params["n_estimators"]) + 1, test_score, "r-", label="Test Set Deviation"
)
plt.plot(np.arange(params["n_estimators"]) + 1, train_score, "b-", label="Train Set Deviation"
)
plt.legend(loc="upper right")
plt.xlabel("Boosting Iterations")
plt.ylabel("Deviance")
fig.tight_layout()
plt.show()

feature_importance = reg.feature_importances_
sorted_idx = np.argsort(feature_importance)pos = np.arange(sorted_idx.shape[0]) + 0.5
fig = plt.figure(figsize=(12, 6))
plt.subplot(1, 2, 1)
plt.barh(pos, feature_importance[sorted_idx], align="center")
plt.yticks(pos, np.array(diabetes.feature_names)[sorted_idx])
plt.title("Feature Importance (MDI)")result = permutation_importance(reg, X_test, y_test, n_repeats=10, random_state=42, n_jobs=2
)
sorted_idx = result.importances_mean.argsort()
plt.subplot(1, 2, 2)
plt.boxplot(result.importances[sorted_idx].T,vert=False,labels=np.array(diabetes.feature_names)[sorted_idx],
)
plt.title("Permutation Importance (test set)")
fig.tight_layout()
plt.show()

References

[1] 《机器学习方法》，李航，清华大学出版社。
[2] sklearn 中文文档，https://www.sklearncn.cn/5/。