TASK9 Boosting

Boosting

PAC学习（概率近似正确学习）

PAC总结理论

同等条件下，模型越复杂泛化误差越大。同一模型在样本满足一定条件的情况下，其数量越大，模型泛化误差越小，因此还可以说模型越复杂越吃样本。
某个训练样本对正确目标的映射，而称为‘概念’，用符号 c c c表示，即存在一个映射，使得 c ( x ) = y c(x)= y c(x)=y，这只是某一个结果，并不是集合。
所有我们希望所有训练目标的映射集合为‘概念类’，用符号 C C C表示。
模型经过训练后得到的所有结果映射集合，称为‘假设空间’，用符号H表示。
首先PAC学习理论对机器学习算法结果有两个概念

• 可分的：
  训练样本通过学习算法后，得出的假设空间，c属于H，我们称为可分的
• 不可分的：
  训练样本通过学习算法后，得出的假设空间，c不属于H，我们称为不可分的

当然在学习算法中，我们都希望学习算法尽可能有更多的c属于H中，为什么只是尽可能多，而不是要求精确呢？因为在机器学习算法中，会受到很多因素的制约，所以并不会百分百地对应到。
当选择学习算法时候，我们希望以比较大的把握学得比较好的模型。要判断哪些学习算法能选用，这就需要符合PAC可学习性

PAC可学习性：

首先学习算法得出的‘假设’必须满足以下的两个条件（PAC辨识）才算上“近似”正确对应目的概念 c c c：

• 近似正确：泛化误差E(h)足够小

  E ( h ) E(h) E(h)越小越好，最好泛化误差能能于0，但一般是不可能的。那我们就把 E ( h ) E(h) E(h)限定在一个很小的数 ϵ \epsilon ϵ之内，即只要假设 h h h满足
  E ( h ) ≤ ϵ E(h)≤\epsilon E(h)≤ϵ我们就认为 h h h是正确的。

• 可能正确

  不指望选择的假设h百分之百是近似正确的（按上段所述，即E(h)≤ϵ），只要很可能是近似正确的就可以，即我们给定一个值 δ \delta δ，假设 h h h满足 P ( h 近 似 正 确 ) ≥ 1 − δ P(h_{近似正确})≥1−δ P(h近似正确​)≥1−δ

满足以上两点的学习算法，就是能以较大概率学得目标概念 c c c的近似。

PAC可学习：

当学习算法能从假设空间H中PAC辨识概念类 C C C，则称概念类对假设空间 H H H而言是PAC可学习的。

PAC学习中一个关键因素是假设空间H的复杂度， H H H包含了学习算法所有可能输出的假设。在实际问题中概念类C往往是不等于 H H H的，因为我们对概念类，往往一概不知。当H越大，其包含任意目标概念的可能性越大，但从中找到某个具体目标概念的难度也越大。 ∣ H ∣ |H| ∣H∣有限时候，我们称H为“有限假设空间”，否则称为“无限假设空间”

可分与不可分

• 可分情形:

  在可分情形下，如何找到满足误参数的假设呢？
  训练集D中，样例都可以通过目标概念c，映射结果，而c存在假设空间H中，那么我们通过保留D中一致的假设，剔除与D不一致的假设，知道H只剩下一个假设位置，这个假设就是目标概念。前提是训练集D足够大。

• 不可分情形：
  对比较困难的学习问题，目标概念c通常不存在于H中，也就是说，H中的任意一个假设都会在训练集上出现或多或少的错误，有Hoeffding不等式知：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FtLGPZ4e-1618833719794)(./Hoeffdro不等式.png)]

从而我们知道，对于任意 ϵ \epsilon ϵ，只要样本数量 m m m足够小， ∣ E ( h ) − E ^ ( h ) ∣ > ϵ |E(h)−\hat E(h)|> \epsilon ∣E(h)−E^(h)∣>ϵ 发生的可能性就非常大，此时我们不能用经验误差近似泛化误差，但是反之，当样本数量 m m m足够大时， ∣ E ( h ) − E ^ ( h ) ∣ > ϵ |E(h)−\hat E(h)|> \epsilon ∣E(h)−E^(h)∣>ϵ发生的可能性就非常小，此时我们可以用经验误差近似泛化误差。¹

强学习与弱学习

在概率近似正确PAC学习的框架下：

• 弱学习：识别错误率小于1/2（即准确率仅比随机猜测略高的学习算法）
• 强学习：识别准确率很高并能在多项式时间内完成的学习算法
  值得注意的是，在PAC学习的框架下，强可学习和弱可学习是等价的，也就是说一个概念是强可学习的充分必要条件是这个概念是弱可学习的。这样一来，问题便是：在学习中，如果已经发现了弱可学习算法，能否将他提升至强可学习算法。因为，弱可学习算法比强可学习算法容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器(又称为基本分类器)，然后通过一定的形式去组合这些弱分类器构成一个强分类器。大多数的Boosting方法都是通过改变训练数据集的概率分布(训练数据不同样本的权值)，针对不同概率分布的数据调用弱分类算法学习一系列的弱分类器。

故而，Boosting解决的两个主要问题就是：

• 每一轮学习应该如何改变数据的概率分布
• 如何将各个弱分类器组合起来

Boosting的算法就是这样的思想：先从初始训练集训练出一个基学习器，再基学习器的表现对训练样本进行调整，使得先前出错的样本在后续训练中得到更多关注，调整样本分布后训练下一个基学习器，直到基学习器数目达到阈值，最后将这些基学习器融合。

Adaboost²

Adaboost的优化目标是：最小化指数损失函数：
l e x p ( H ∣ D ) = E x ∼ d [ s − f ( x ) H ( x ) ] l_{exp}(H|D) = E_{x\sim d}[s^{-f(x)H(x)}] lexp​(H∣D)=Ex∼d​[s−f(x)H(x)]
对 H ( x ) H(x) H(x)求偏导得
∂ l e x p ( H ∣ D ) ∂ H ( X ) = − e − H ( x ) P ( f ( x ) = 1 ∣ x ) + e H ( x ) P ( f ( x ) = − 1 ∣ x ) \frac{\partial l_{exp}(H|D)}{\partial H(X)}= -e^{-H(x)}P(f(x)=1|x) + e^{H(x)}P(f(x)=-1|x) ∂H(X)∂lexp​(H∣D)​=−e−H(x)P(f(x)=1∣x)+eH(x)P(f(x)=−1∣x)
令上式为0，则：
H ( x ) = 1 2 l n P ( f ( x ) = 1 ∣ x ) P ( f ( x ) = − 1 ∣ x ) H(x)=\frac{1}{2}ln\frac{P(f(x)=1|x)}{P(f(x)=-1|x)} H(x)=21​lnP(f(x)=−1∣x)P(f(x)=1∣x)​

Adaboost sklearn实战³

引入数据科学相关工具包：

import numpy as np
import pandas as pd 
import matplotlib.pyplot as plt
plt.style.use("ggplot")
%matplotlib inline
import seaborn as sns

加载训练数据：

wine = pd.read_csv("https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data",header=None)
wine.columns = ['Class label', 'Alcohol', 'Malic acid', 'Ash', 'Alcalinity of ash','Magnesium', 'Total phenols','Flavanoids', 'Nonflavanoid phenols', 
                'Proanthocyanins','Color intensity', 'Hue','OD280/OD315 of diluted wines','Proline']

数据查看

print("Class labels",np.unique(wine["Class label"]))
wine.head()

Class labels [2 3]

	Class label	Alcohol	Malic acid	Ash	Alcalinity of ash	Magnesium	Total phenols	Flavanoids	Nonflavanoid phenols	Proanthocyanins	Color intensity	Hue	OD280/OD315 of diluted wines	Proline
59	2	12.37	0.94	1.36	10.6	88	1.98	0.57	0.28	0.42	1.95	1.05	1.82	520
60	2	12.33	1.10	2.28	16.0	101	2.05	1.09	0.63	0.41	3.27	1.25	1.67	680
61	2	12.64	1.36	2.02	16.8	100	2.02	1.41	0.53	0.62	5.75	0.98	1.59	450
62	2	13.67	1.25	1.92	18.0	94	2.10	1.79	0.32	0.73	3.80	1.23	2.46	630
63	2	12.37	1.13	2.16	19.0	87	3.50	3.10	0.19	1.87	4.45	1.22	2.87	420

数据概览

wine.describe()

	Class label	Alcohol	Malic acid	Ash	Alcalinity of ash	Magnesium	Total phenols	Flavanoids	Nonflavanoid phenols	Proanthocyanins	Color intensity	Hue	OD280/OD315 of diluted wines	Proline
count	178.000000	178.000000	178.000000	178.000000	178.000000	178.000000	178.000000	178.000000	178.000000	178.000000	178.000000	178.000000	178.000000	178.000000
mean	1.938202	13.000618	2.336348	2.366517	19.494944	99.741573	2.295112	2.029270	0.361854	1.590899	5.058090	0.957449	2.611685	746.893258
std	0.775035	0.811827	1.117146	0.274344	3.339564	14.282484	0.625851	0.998859	0.124453	0.572359	2.318286	0.228572	0.709990	314.907474
min	1.000000	11.030000	0.740000	1.360000	10.600000	70.000000	0.980000	0.340000	0.130000	0.410000	1.280000	0.480000	1.270000	278.000000
25%	1.000000	12.362500	1.602500	2.210000	17.200000	88.000000	1.742500	1.205000	0.270000	1.250000	3.220000	0.782500	1.937500	500.500000
50%	2.000000	13.050000	1.865000	2.360000	19.500000	98.000000	2.355000	2.135000	0.340000	1.555000	4.690000	0.965000	2.780000	673.500000
75%	3.000000	13.677500	3.082500	2.557500	21.500000	107.000000	2.800000	2.875000	0.437500	1.950000	6.200000	1.120000	3.170000	985.000000
max	3.000000	14.830000	5.800000	3.230000	30.000000	162.000000	3.880000	5.080000	0.660000	3.580000	13.000000	1.710000	4.000000	1680.000000

通过数据概览，我们可以发现所有的数据都没有缺失值。

但大部分指标存在异常值，有许多的指标在 3 σ 3\sigma 3σ范围之外。

Proline的方差波动很明显，或许这个特征很敏感。

数据预处理

仅仅考虑2，3类葡萄酒，去除1类

wine = wine[wine['Class label'] != 1]
y = wine['Class label'].values
X = wine[['Alcohol','OD280/OD315 of diluted wines']].values

将分类标签变成二进制编码：

from sklearn.preprocessing import LabelEncoder
le = LabelEncoder()
y = le.fit_transform(y)

按8：2分割训练集和测试集

from sklearn.model_selection import train_test_split
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2,random_state=1,stratify=y)  # stratify参数代表了按照y的类别等比例抽样

模型训练

使用单一决策树建模

from sklearn.tree import DecisionTreeClassifier
tree = DecisionTreeClassifier(criterion='entropy',random_state=1,max_depth=1)
from sklearn.metrics import accuracy_score
tree = tree.fit(X_train,y_train)
y_train_pred = tree.predict(X_train)
y_test_pred = tree.predict(X_test)
tree_train = accuracy_score(y_train,y_train_pred)
tree_test = accuracy_score(y_test,y_test_pred)
print('Decision tree train/test accuracies %.3f/%.3f' % (tree_train,tree_test))

Decision tree train/test accuracies 0.916/0.875

使用sklearn实现Adaboost(基分类器为决策树)

'''
AdaBoostClassifier相关参数：
base_estimator：基本分类器，默认为DecisionTreeClassifier(max_depth=1)
n_estimators：终止迭代的次数
learning_rate：学习率
algorithm：训练的相关算法，{'SAMME'，'SAMME.R'}，默认='SAMME.R'
random_state：随机种子
'''
from sklearn.ensemble import AdaBoostClassifier
ada = AdaBoostClassifier(base_estimator=tree,n_estimators=500,learning_rate=0.1,random_state=1)
ada = ada.fit(X_train,y_train)
y_train_pred = ada.predict(X_train)
y_test_pred = ada.predict(X_test)
ada_train = accuracy_score(y_train,y_train_pred)
ada_test = accuracy_score(y_test,y_test_pred)
print('Adaboost train/test accuracies %.3f/%.3f' % (ada_train,ada_test))

Adaboost train/test accuracies 1.000/0.917

结果可视化

# 画出单层决策树与Adaboost的决策边界：
x_min = X_train[:, 0].min() - 1
x_max = X_train[:, 0].max() + 1
y_min = X_train[:, 1].min() - 1
y_max = X_train[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1),np.arange(y_min, y_max, 0.1))
f, axarr = plt.subplots(nrows=1, ncols=2,sharex='col',sharey='row',figsize=(12, 6))
for idx, clf, tt in zip([0, 1],[tree, ada],['Decision tree', 'Adaboost']):
    clf.fit(X_train, y_train)
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    axarr[idx].contourf(xx, yy, Z, alpha=0.3)
    axarr[idx].scatter(X_train[y_train==0, 0],X_train[y_train==0, 1],c='blue', marker='^')
    axarr[idx].scatter(X_train[y_train==1, 0],X_train[y_train==1, 1],c='red', marker='o')
    axarr[idx].set_title(tt)
axarr[0].set_ylabel('Alcohol', fontsize=12)
plt.tight_layout()
plt.text(0, -0.2,s='OD280/OD315 of diluted wines',ha='center',va='center',fontsize=12,transform=axarr[1].transAxes)
plt.show()

从上面的决策边界图可以看到：Adaboost模型的决策边界比单层决策树的决策边界要复杂的多。也就是说，Adaboost试图用增加模型复杂度而降低偏差的方式去减少总误差，但是过程中引入了方差，可能出现国拟合，因此在训练集和测试集之间的性能存在较大的差距，这就简单地回答的刚刚问题。值的注意的是：与单个分类器相比，Adaboost等Boosting模型增加了计算的复杂度，在实践中需要仔细思考是否愿意为预测性能的相对改善而增加计算成本，而且Boosting方式无法做到现在流行的并行计算的方式进行训练，因为每一步迭代都要基于上一部的基本分类器。

参数解释⁴

参数	含义	默认参数
base_estimator	基分类器	默认是深度为1的决策树分类器
n_estimators	基分类器个数	默认50个
learning_rate	学习率	默认是1
algorithm	训练算法	默认='SAMME.R
random_state	随机种子

【注】algorithm如果为“ SAMME”，则使用SAMME离散提升算法。SAMME.R算法通常比SAMME收敛更快，从而以更少的提升迭代次数实现了更低的测试误差。

---

1. PAC学习理论 ↩︎

2. 周志华《机器学习》 ↩︎

3. Datawhale ↩︎

4. Sklearn ↩︎