Adaboost 演算法介绍（附常见面试题）

1. Adaboost简介

1.1 集成学习（ensemble learning）背景介绍

集成学习（ensemble learning）通过构建并结合多个学习器（learner）来完成学习任务，通常可获得比单一学习器更良好的泛化性能（特别是在集成弱学习器（weak learner）时）。

目前集成学习主要分为2大类：

一类是以bagging、Random Forest等演算法为代表的，各个学习器之间相互独立、可同时生成的并行化方法；

一类是以boosting、Adaboost等演算法为代表的，个体学习器是串列序列化生成的、具有依赖关系，它试图不断增强单个学习器的学习能力。

1.2 Adaboost背景介绍

Adaboost是Yoav Freund和Robert Schapire在1997年提出的一种集成学习（ensemble learning）演算法。

此前也Schapire也曾提出了一种boosting演算法（Schapire』s Boosting ），但实际应用效果并不好，主要原因是因为Schapire』s Boosting 对于训练集样本的选取条件十分精确而又苛刻，以至于很难找出符合条件的训练集。而Adaboost在选取样本的时候采用了基于概率分布（也可解释为基于权值）来选取样本的方法，相比Schapire』s Boosting 放宽了对于训练样本选取的要求。

2. Adaboost 演算法详解

2.1 Adaboost 步骤概览

? ① 初始化训练样本的权值分布，每个训练样本的权值应该相等（如果一共有N个样本，则每个样本的权值为1/N)

? ② 依次构造训练集并训练弱分类器。如果一个样本被准确分类，那么它的权值在下一个训练集中就会降低；相反，如果它被分类错误，那么它在下个训练集中的权值就会提高。权值更新过后的训练集会用于训练下一个分类器。

? ③ 将训练好的弱分类器集成为一个强分类器，误差率小的弱分类器会在最终的强分类器里占据更大的权重，否则较小。

2.2 Adaboost 演算法流程

给定一个样本数量为m的数据集T= ${left(x_{1}, y_{1} ight), ldots,left(x_{m}, y_{m} ight) }$ ，yi 属于标记集合{-1,+1}。

训练集的在第k个弱学习器的输出权重为 $D(k)=left(w_{k 1}, w_{k 2}, ldots w_{k m} ight) ; quad w_{1 i}=frac{1}{m} ; i=1,2 ldots m$

① 初始化训练样本的权值分布，每个训练样本的权值相同： $D(1)=left(w_{1 1}, w_{1 2}, ldots w_{1 m} ight) ; quad w_{1 i}=frac{1}{m} ; i=1,2 ldots m$

② 进行多轮迭代，产生T个弱分类器。

? for t = 1, ... , T :

? a. 使用权值分布 D(t) 的训练集进行训练，得到一个弱分类器 $G_{t}(x) : quad chi ightarrow{-1,+1}$ ? b. 计算 Gt(x) 在训练数据集上的分类误差率（其实就是被 Gt(x) 误分类样本的权值之和）: $e_{t}=Pleft(G_{t}left(x_{i} ight) eq y_{i} ight)=sum_{i=1}^{m} w_{t i} Ileft(G_{t}left(x_{i} ight) eq y_{i} ight)$

c. 计算弱分类器 Gt(x) 在最终分类器中的系数(即所占权重) $alpha_{t}=frac{1}{2} ln frac{1-e_{t}}{e_{t}}$

? d. 更新训练数据集的权值分布，用于下一轮（t+1）迭代 $D(t+1)=left(w_{t+1,1} ,w_{t+1,2} ,cdots w_{t+1, i} cdots, w_{t+1, m} ight)$ ?

for i = 1, ... , m： $w_{t+1,i}=frac{w_{t,i}}{Z_{t}} imes left{egin{array}{ll}{e^{-alpha_{t}}} & { ext （{ if } G_{t}left(x_{i} ight)=y_{i}}） \ {e^{alpha_{t}}} & { ext （{ if } G_{t}left(x_{i} ight) eq y_{i}}）end{array} ight. = frac{w_{t,i}}{Z_{t}} exp left(-alpha_{t} y_{i} G_{t}left(x_{i} ight) ight)$