Boosting，顾名思义，这是一个增强算法，而它增强的对象，就是机器学习中我们所熟知的学习器。在Valiant引入的PAC（Probably Approximately Correct，又称可能近似正确）中，学习器可被分为强学习器和弱学习器。其中，在处理二分类问题时，弱学习器被视为只比随机分类更好一点（即准确率略高于0.5）的分类器，而强分类器的准确率在90%以上。但是强学习器的获取要比弱学习器困难得多，而1989年Kearns&Valiant1提出了一个经典的理论问题：强可学习性和弱可学习性问题是否等价。如果该问题的答案是肯定的，那么就意味着所有的弱学习器都有被提升为强学习器的潜力。幸运的是，这问题答案在后来被Schapire证明是肯定的。由此，就有了弱学习器的增强过程。
Boosting的基本想法就是给样本赋权，利用权值改变纠正弱学习器的错误。每一轮都会加入新的弱学习器，每轮过后，都会生成一个新的样本分布，那些被分错的样本，其关注度会有所增加。T轮过后，将所有的分类器结合，形成性能提升巨大的强学习器。后来关于Boosting类算法的改进，基本上也都是基于改变调整样本权值和分类器结合方式来的。
输入：样本分布D；基学习算法L；学习轮数T； D 1 = D f o r t = , . . . T : h t = L ( D t ) ; ε t = P x ∽ D t ( h t ( x ) ≠ f ( x ) ) ; D t + 1 = A d j u s t _ D i s t r i b u t i o n ( D t , ε t ) . e n d 输出： H ( x ) = C o m b i n e _ O u t p u t s ( { h 1 ( x ) , . . . , h t ( x ) } ) . \begin{gathered} \fbox{ 输入：样本分布D；基学习算法L；学习轮数T； }\\ D_1=D \\ for\enspace t=,...T:\qquad\\ h_t=L(D_t);\\ \qquad\qquad\qquad \varepsilon _t=P_{x\backsim D_t}(h_t(x)\ne\ f(x));\\ \qquad\qquad\qquad\qquad\qquad D_{t+1}=Adjust\_Distribution(D_t,\varepsilon _t).\\ \!end\qquad\qquad\qquad \\ \fbox{ 输出： }\\ H(x)=Combine\_Outputs(\{h_1(x),...,h_t(x)\}). \end{gathered} 输入：样本分布D；基学习算法L；学习轮数T； D1=Dfort=,...T:ht=L(Dt);εt=Px∽Dt(ht(x)= f(x));Dt+1=Adjust_Distribution(Dt,εt).end 输出： H(x)=Combine_Outputs({h1(x),...,ht(x)}).
在Boosting过程的基础上，Freund&Schapire2于1997年提出了Adaboost（Adaptive Boosting，又称自适应增强）算法，其经典版在2000年由Friedman3提出。
算法流程
输入训练数据集
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
(
x
N
,
y
N
)
}
D = \{ ( x_1 , y_1 ) , ( x_2 , y_2 ) , ( x _N , y_N ) \}
D={(x1,y1),(x2,y2),(xN,yN)}其中，
x
i
∈
X
,
y
i
∈
=
−
1
,
1
x_i∈X,y_i∈=-1,1
xi∈X,yi∈=−1,1迭代总次数为T
1、初始化权重分布，
D
1
=
(
w
1
,
1
,
w
1
,
2
,
.
.
.
,
w
1
,
i
)
,
w
1
,
i
=
1
N
,
i
=
1
,
2
,
.
.
.
,
N
D_1=(w_{1,1},w_{1,2},...,w_{1,i}),w_{1,i}=\frac{1}{N},i=1,2,...,N
D1=(w1,1,w1,2,...,w1,i),w1,i=N1,i=1,2,...,N
2、迭代t=1,2,…,T
a.在分布D_t下从D中训练分类器h_t(x)
b.计算分类器h_t的错误率
ε
t
=
∑
i
=
1
N
w
t
,
i
I
(
h
t
(
x
)
≠
y
i
)
\varepsilon _t=\sum\limits_{i=1}^{N} w_{t,i}I\big(h_t(x)\ne y_i\big)
εt=i=1∑Nwt,iI(ht(x)=yi)
c.计算h_t的权重
α
t
=
1
2
l
n
(
1
−
ε
t
ε
t
)
\alpha_t=\frac{1}{2}ln(\frac{1-\varepsilon_t}{\varepsilon_t})
αt=21ln(εt1−εt)
d.更新权重分布，其中Z_t为满足分布条件的归一化因子
w
t
+
1
,
i
=
w
t
,
i
Z
t
e
x
p
(
−
α
t
y
i
h
t
(
x
i
)
)
w_{t+1,i}=\frac{w_{t,i}}{Z_t}exp\big(-\alpha_ty_ih_t(x_i)\big)
wt+1,i=Ztwt,iexp(−αtyiht(xi))
Z
t
=
∑
i
=
1
N
w
t
,
i
e
x
p
(
−
α
t
y
i
h
t
(
x
i
)
)
Z_t= \sum\limits_{i=1}^{N}w_{t,i}exp(-\alpha_ty_ih_t(x_i))
Zt=i=1∑Nwt,iexp(−αtyiht(xi))
3、整合分类器
H
(
x
)
=
s
i
g
n
(
∑
i
=
1
T
α
t
h
t
(
x
)
)
H(x)=sign\big(\sum\limits_{i=1}^{T}\alpha_th_t(x)\big)
H(x)=sign(i=1∑Tαtht(x))
此方法是通过重赋值的策略，在每一轮根据相应的分布对训练样本赋权来完成的，而对于不能利用样本权值学习的算法，可以采用重采样的方法，即每一轮根据相应的分布对训练样本进行采样。
对于算法性能，经过证明，Adaboost最终的集成分类器的错误率存在着上界，同时，在迭代之中，错误率呈指数趋势减少，说明Adaboost在降低误差，将弱分类器训练整合为强学习器方面有着很好的表现。不过，这又引出一个问题，Adaboost会过拟合吗？答案是会的。Grove&Schuurmans4在1998年证明了在足够多轮之后，Adaboost也会过拟合，所以其只是在通常情况下不会过拟合。对于多少轮后会过拟合，Grove&Schuurmans提出了一个学习轮数T的上界。
存在问题
虽然Adaboost有着很好的泛化性能，但是由于其采用的是对样本重赋权来实现纠错，其对噪声很敏感。在学习噪声数据时，Adaboost仍然会尽力去拟合这些噪声，并且由于不断错误分类，还会使得噪声数据的权重不断加大，降低分类器预测能力。一个比较好的解决办法是直接为样本的权重设定一个上界，具体改进可参考Domingo&Watanabe5于2000年提出的MadaBoost算法。
多分类问题
以上讨论的是针对于二分类问题的Adaboost，以下我们开始讨论Adaboost在多分类问题中的应用。Adaboost在多分类问题上应用所面对的最大问题，便是对弱分类器的约束过强。在二分类问题中，我们对弱分类器的要求是其分类准确率要比0.5略大，但是在多分类中，1/N，N>2，这明显达不到要求。关于这一点，比较常用的解法是将多分类任务分解为多个二分类任务，包括有“一对其余”和“一对一”分解。“一对其余”就是将N类多分类任务分成N个二分类任务，第i个二分类任务仅判断其是否属于i类。代表算法有Schapire&Singer6的Adaboost.MH。“一对一”方法则将N个多分类任务分成N*(N-1)/2个二分类任务，第i个二分类任务仅判断其是属于第i类还是第j类。代表算法有Freund&Schapire的Adaboost.M2。
参考资料
-
Ehrenfeucht A, Haussler D, Kearns M, et al. A general lower bound on the number of examples needed for learning[J]. Information and Computation, 1989, 82(3): 247-261. ↩︎
-
Freund Y, Schapire R E. A decision-theoretic generalization of on-line learning and an application to boosting[J]. Journal of computer and system sciences, 1997, 55(1): 119-139. ↩︎
-
Friedman J, Hastie T, Tibshirani R. Special invited paper. additive logistic regression: A statistical view of boosting[J]. Annals of statistics, 2000: 337-374. ↩︎
-
Grove A J, Schuurmans D. Boosting in the limit: Maximizing the margin of learned ensembles[C]//AAAI/IAAI. 1998: 692-699. ↩︎
-
Domingo C, Watanabe O. MadaBoost: A modification of AdaBoost[C]//COLT. 2000: 180-189 ↩︎
-
Allwein E L, Schapire R E, Singer Y. Reducing multiclass to binary: A unifying approach for margin classifiers[J]. Journal of machine learning research, 2000, 1(Dec): 113-141. ↩︎