第九章集成学习 Ensemble Learning

Bagging、adboost算法

集成学习概述

Ensemble Learning 集成学习

集成学习(ensemble learning)通过构建并结合多个学习器来提升性能。

Ensemble Learning: Combine multiple models into one!
集成学习：将多个模型组合为一个！

Applications: classification, clustering, collaborative filtering, anomaly detection
应用: 分类、聚类、协同过滤、异常检测

Motivations of ensemble methods 集成方法的动机

Ensemble model improves accuracy and robustness over single model methods.
与单一模型方法相比，集成模型提高了准确性和健壮性。

Applications 应用:

distributed computing 分布式计算
privacy-preserving applications 隐私保护应用
large-scale data with reusable models 具有可重用模型的大规模数据
multiple sources of data 多种数据来源

Efficiency: a complex problem can be decomposed into multiple sub-problems that are easier to understand and solve (divide-and-conquer approach)
效率：一个复杂的问题可以分解为多个子问题，更容易理解和解决（分而治之法）

Ensemble Philosophy 集成哲学

Build many models and combine them
构建多个模型并将其组合

Only through averaging do we get at the truth!
只有通过平均才能得出真相！

It’s too hard (impossible?) to build a single model that works best
建立一个最有效的模型太难了（不可能了？）

Two types of approaches:
两种类型的方法：

Models that don’t use randomness
不使用随机性的模型
Models that incorporate randomness
包含随机性的模型

Ensemble Approaches 集成方法

★ Bagging

Bagging

Main Assumption:
主要假设：

Combining many unstable predictors to produce a ensemble (stable) predictor.
将许多不稳定的预测器组合在一起，生成一个集合（稳定）预测器。
Unstable Predictor: small changes in training data produce large changes in the model.
不稳定预测：训练数据的微小变化会导致模型的巨大变化。
- e.g. Neural Nets, trees
  例如神经网络、树
- Stable: SVM (sometimes), Nearest Neighbor.
  稳定：支持向量机（有时），最近邻。

Hypothesis Space
假设空间

Variable size (nonparametric):
可变大小（非参数）：
- Can model any function if you use an appropriate predictor (e.g. trees)
  如果使用适当的预测器（例如树），可以对任何函数进行建模

The Bagging Algorithm 算法

从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行m轮抽取，得到m个训练集。（k个训练集之间是相互独立的）每次使用一个训练集得到一个模型，m个训练集共得到m个模型。对分类问题采用投票的方式得到分类结果，对回归问题计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

Given data: $D={(x_1,y_1 ),...,(x_N,y_N )}$

For $m = 1 : M$

Obtain bootstrap sample $D_m$ from the training data $D$
从训练数据 $D$ 中获取 bootstrap 样本 $D_m$
Build a model $G_m (x)$ from bootstrap data $D_m$
从 bootstrap 数据 $D_m$ 建立模型 $G_m (x)$

The Bagging Model 模型

Regression 回归：均值

y^=1M∑m=1MGm(X)\hat{y}=\frac{1}{M}\sum_{m=1}^M G_m(X)

Classification 分类：投票

Vote over classifier outputs $G_1 (X),…,G_M (X)$

Bagging Details 细节

Bootstrap sample of N instances is obtained by drawing N examples at random, with replacement.
bootstrap 样本是随机抽取的。

On average each bootstrap sample has 63% of instances.
每个 bootstrap 样本有 63% 的实例。

Encourages predictors to have uncorrelated errors. This is why it works.

对于一个样本，它在某一次含 $m$ 个样本的训练集的随机采样中，每次被采集到的概率是 $1 / m$ ，不被采集到的概率为 $(1 - 1 / m)$ ，如果 $m$ 次采样都没有被采集中的概率是 $1-1/m)^m$ ,当 $m \to \infty$ ， $1-1/m)^m→1/e≅0.368$ 。

Usually set $\approx 30$ , Or use validation data to pick $M$
通常设置 $\approx 30$ ，或者使用验证集决定 $M$ 。

The models $G_m (x)$ need to be unstable. Usually full length (or slightly pruned) decision trees.
$G_m (x)$ 模型需要不稳定，通常是全长（或稍微修剪过的）决策树。

★ Boosting

Boosting 思想

训练多个弱分类器，最后组装成一个强分类器。

Boosting 算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习器1的学习误差率求得弱学习器1的权重，并根据该权重更新训练样本的权重，使得弱学习器1学习误差率高的训练样本点的权重变高，这些误差率高的样本在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2，如此重复，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。

重赋权：每次训练完成后，提高错误分类的样本的权重。

重采样：每次训练前，根据样本分布抽一个训练集。

利用“重采样法”实现重启动，避免训练过程过早停止。

Main Assumption: Combining many weak predictors (e.g. tree stumps or 1-R predictors) to produce an ensemble predictor
主要假设：组合许多弱预测器（例如树桩或1-R预测器）以产生集合预测器

The weak predictors or classifiers need to be stable
弱预测因子或分类器需要稳定

Hypothesis Space 假设空间
Variable size (nonparametric): Can model any function if you use an appropriate predictor (e.g. trees)
可变大小（非参数）：如果使用适当的预测器（例如树），可以对任何函数进行建模

Boosting 特征 (Boosting Characteristics)

iterative
迭代的
successive classifiers depends upon its predecessors
连续分类器依赖于它的前一个分类器
look at errors from previous classifier step to decide how to focus on next iteration over data
查看上一个分类器步骤中的错误，以决定如何关注数据的下一次迭代

早期 Boosting 算法 (Early Boosting Algorithms)

Schapire (1989)

first provable boosting algorithm 第一个可证明的boosting算法
call weak learner three times on three modified distributions 在三个修改后的分布上对弱学习者进行三次调用
get slight boost in accuracy 精确度略有提高
apply recursively 递归应用

Freund (1990)

“optimal” algorithm that “boosts by majority”

“多数提升”的“最优”算法

Drucker, Schapire & Simard (1992)

first experiments using boosting 首次使用 boosting 的实验
limited by practical drawbacks 受到实际缺陷的限制

Freund & Schapire (1995) – AdaBoost

strong practical advantages over previous boosting algorithms

与以前的 boosting 算法相比具有强大的实用优势

Boosting 算法

Train a set of weak hypotheses: $h_1, …., h_T$ .
训练一组弱猜想 $h_1, …., h_T$

The combined hypothesis $H$ is a weighted majority vote of the $T$ weak hypotheses.
组合假设 $H$ 是弱猜想 $T$ 的加权多数票

Each hypothesis $h_t$ has a weight $α_t$ .
每一个猜想有权值

H(x)=sign(∑t=1Tαtht(x))H(x)=sign(\sum\limits_{t=1}^T\alpha_t h_t(x))

During the training, focus on the examples that are misclassified.
在训练过程中，重点关注分类错误的样本。

At round $t$ , example $x_i$ has the weight $D_t(i)$ .

Binary classification problem 二分类问题

Training data: $x_1,y_1 ),…,(x_m,y_m )$ , where $x_i∈X,y_i∈Y=\{-1,+1\}$
训练数据

$D_t(i)$ : the weight of $x_i$ at round $t$ . $D_1(i)=1/m$ .
一轮中的权重

A learner $L$ that finds a weak hypothesis $ht:X→Yh_t: X \to Y$ given the training set and $D_t$
找到一个弱猜想

The error of a weak hypothesis $h_t$ :
弱猜想的错误率

εt=Pr⁡i∼Dt[ht(xi)≠yi]=∑i:ht(xi)≠yiDt(i)\varepsilon_{t}=\operatorname*{Pr}_{i\sim D_{t}}[h_{t}(x_{i})\neq y_{i}]=\sum_{i:h_{t}(x_{i})\neq y_{i}}D_{t}(i)

Bagging 和 Boosting 的区别

1）样本选择上：
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

2）样例权重：
Bagging：使用均匀取样，每个样例的权重相等
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。

3）预测函数：
Bagging：所有预测函数的权重相等。
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。

4）并行计算：
Bagging：各个预测函数可以并行生成
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

这两种方法都是把若干个分类器整合为一个分类器的方法，只是整合的方式不一样，最终得到不一样的效果，将不同的分类算法套入到此类算法框架中一定程度上会提高了原单一分类器的分类效果，但是也增大了计算量。

★ AdaBoost

介绍 (Introduction)

Linear classifier with all its desirable properties
具有所有所需特性的线性分类器
Has good generalization properties
具有良好的泛化性能
Is a feature selector with a principled strategy (minimisation of upper bound on empirical error)
是一个具有原则性策略的特征选择器（最小化经验误差上限）
Close to sequential decision making
接近顺序决策

AdaBoost 定义 (AdaBoost Definition)

Is an algorithm for constructing a “strong” classifier as linear combination of simple “weak” classifiers $h_t(x)$ .
是一种使用弱分类器的线性组合构造“强”分类器的算法

=\sum_{t=1}^T\alpha_t h_t(x)

$h t (x)$ - “weak” or basis classifier, hypothesis, ”feature”
弱分类器

$H (x)$ = $s i g n (f (x))$ – “strong” or final classifier/hypothesis
强分类器

The main idea of AdaBoost 主要思想

to use the weak learner to form a highly accurate prediction rule by calling the weak learner repeatedly on different distributions over the training examples.
通过在训练示例的不同分布上重复调用弱学习器来使用弱学习器形成高度准确的预测规则。

initially, all weights are set equally, but each round the weights of incorrectly classified examples are increased so that those observations that the previously classifier poorly predicts receive greater weight on the next iteration.
最初，所有权重都被设置为相等，但每一轮错误分类的例子的权重都会增加，使得先前分类器预测不佳的那些观察结果在下一次迭代中获得更大的权重。

AdaBoost 算法 (The AdaBoost Algorithm)

Input – a training set: S = {(x1, y1); … ;(x_m,y_m)}

xi∈"X", X instance space
yi∈"Y", Y finite label space
in binary case Y = {-1,+1}

Each round, t=1,…,T, AdaBoost calls a given weak or base learning algorithm – accepts as input a sequence of training examples (S) and a set of weights over the training example (D_t (i) )

The weak learner computes a weak classifier (ht), : ht : X → R

Once the weak classifier has been received, AdaBoost chooses a parameter (α_t∈R ) – intuitively measures the importance that it assigns to ht*.*

AdaBoost Analysis 分析

the weights D_t (i) are updated and normalised on each round. The normalisation factor takes the form

Zt=∑i=1mDt(i)e−αtyiht(xi)Z_t=\sum_{i=1}^m D_t(i)e^{-\alpha_t y_i h_t(x_i)}

and it can be verified that Z_t measures exactly the ratio of the new to the old value of the exponential sum

∑i=1mexp(−yi∑j=1tαjhj(xi))\sum_{i=1}^m\text{exp}(-y_i\sum_{j=1}^t\alpha_j h_j(x_i))

on each round, so that $πtZt\pi_tZ_t$ is the final value of this sum. We will see below that this product plays a fundamental role in the analysis of AdaBoost.

AdaBoost Training Error

Theorem:

run Adaboost

let $εt=1/2−γt\varepsilon_t=1/2 -\gamma_t$

then the training error:

Hfinal≤∏t2εt(1−εt)=∏t1−4γt2≤exp⁡(−2∑tγt2)∀t:γt≥γ>0⇒Hfinal≤e−2γ2T\begin{aligned} &H_{final}\leq\prod_t2\sqrt{\varepsilon_t(1-\varepsilon_t)}=\prod_t\sqrt{1-4\gamma_t^2}\leq\exp(-2\sum_t\gamma_t^2) \\ &\forall t:\gamma_t\geq\gamma>0\Rightarrow H_{\textit{final}}\leq e^{-2\gamma^2T} \end{aligned}

AdaBoost Pros and Contras 优缺点

Pros:

Very simple to implement
Fairly good generalization
The prior error need not be known ahead of time

Contras:

Suboptimal solution
Can over fit in presence of noise

Boosting Example

AdaBoost Summary

Other Variations of Boosting

Gradient Boosting
- Can use any cost function
Stochastic (Gradient) Boosting
- Bootstrap Sample: Uniform random sampling (with replacement)
- Often outperforms the non-random version
XGBoost

Gradient Boosting

略

eXtreme Gradient Boosting

略