集成学习与Adaboost算法

 本文简要介绍了集成学习，说明了Boosting和Bagging的主要特点。接着，基于周志华的《机器学习》中关于Adaboost算法，详细推导了Adaboost算法，并给出了关键步骤的解释，更方便初学者的理解。

集成学习

 集成学习通过构建并结合多个学习器来完成学习任务，有是也称为多分类器系统，基于委员会的学习等。

 上图显示出集成学习的一般结构：先产生一组“个体学习器”,再用某种策略将它们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生，例如BP神经网络等。此时，集成中只包含同种类型的个体学习器，这样的集成是

同质

的，同质集成中的个体学习器也称

基学习器

，相应的学习算法称为

基学习算法

，集成也可包含不同类型的个体学习器，例如同时包含决策树和神经网络，这样的集成是

异质

的。异质集成不再有基学习算法，相应的个体学习器不再称为基学习器，常称为

组件学习器

。

 以二分类问题 y∈{−1,+1} y ∈ { − 1 , + 1 } 和真实函数 f f ，假定基本分类器的错误率为ϵϵ,即对每个基分类器 hi h i ,有:

P(hi(x)≠f(x))=ϵ(1) (1) P ( h i ( x ) ≠ f ( x ) ) = ϵ

 假设集成通过简单投票法结合 T T 个基分类器，若有超过半数的基分类器正确，则集成分类就正确：

H(x)=sign(∑i=1Thi(x))(2)(2)H(x)=sign(∑i=1Thi(x))

说明：

• f f 是真实函数，产生的结果范围是{−1,+1}{−1,+1}，分类结果是真实的，准确的。
• hi(x) h i ( x ) 是基分类器，产生的结果范围是 {−1,+1} { − 1 , + 1 } ，可能与真实结果有偏差。
• H(x) H ( x ) 是集成分类器，举例来说，如果超过一半的基分类器的分类结果是+1，则集成分类器的结果是+1。
• 对于式 (2) ( 2 ) ，设 A=∑i=1T(hi(x)) A = ∑ i = 1 T ( h i ( x ) ) ,分析如下，如果 A>0 A > 0 表明 T T 个基分类器分类结果为+1+1的较多，结果是集成分类器分类结果是 +1 + 1 ；如果 A=0 A = 0 ，表明 T T 个基分类器中，分类结果为+1+1的 −1 − 1 的一样多。如果 A<0 A < 0 ，表明 T T 个基分类器中，分类结果为−1−1的基分类器数量较多，集成分类器的结果为 −1 − 1 。函数是符号函数，在 ⋅<0,⋅=0,⋅>0 · < 0 , · = 0 , · > 0 时分别取值为 −1,0,1 − 1 , 0 , 1 。

 假设基分类器的错误率相互独立，则由

hoeffding

不等式可知，集成的错误率为：

P(H(x)≠f(x))=∑k=0T/2CkT(1−ϵ)kϵT−k≤e−12T(1−2ϵ)2(3) (3) P ( H ( x ) ≠ f ( x ) ) = ∑ k = 0 T / 2 C T k ( 1 − ϵ ) k ϵ T − k ≤ e − 1 2 T ( 1 − 2 ϵ ) 2

 上式可以看出，随着集成中个体分类器数目 T​ T ​ 的增大，集成的错误率将成指数级下降，最终趋于零。

 

hoeffding

不等式为：

随机变量xi,xi∈{0,1},x¯¯¯=1n(x1+x2+⋯+xn)则有P(|x¯¯¯−E(x¯¯¯)|≥t) ≤e−2nt2 随 机 变 量 x i , x i ∈ { 0 , 1 } , x ¯ = 1 n ( x 1 + x 2 + ⋯ + x n ) 则 有 P ( | x ¯ − E ( x ¯ ) | ≥ t )   ≤ e − 2 n t 2

 式 (3) ( 3 ) 中， t=12−ϵ t = 1 2 − ϵ , n=T n = T

P(H(x)≠f(x))=P(|H(x)−f(x)|≥t)≤e−2nt2=e−2T(12−ϵ)2=e−12T(1−2ϵ)2 P ( H ( x ) ≠ f ( x ) ) = P ( | H ( x ) − f ( x ) | ≥ t ) ≤ e − 2 n t 2 = e − 2 T ( 1 2 − ϵ ) 2 = e − 1 2 T ( 1 − 2 ϵ ) 2

 根据个体学习器的生产方式，目前的集成学习方法大致可以分为两大类，即个体学习器间存在强依赖关系，必须串行生成的序列化方法，以及个体学习器间不存在依赖关系，可同时生成的并行化方法；前者的代表是Boosting，后者代表的是Bagging和随机森林。

Boosting

 Boosting是一族可将弱学习器提升为强学习器的方法，这族算法的工作机制类似：先从初始训练集训练处一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值T,最终将这T个基学习器进行加权结合。

 Boosting族算法最著名的代表是Adaboost。

 Adaboost算法有多种推导方式，比较容易理解的是基于“加性模型”，即基学习器的线性组合：

H(x)=∑t=1Tαtht(x)(4) (4) H ( x ) = ∑ t = 1 T α t h t ( x )

 Adaboost的推导主要有三个方面的内容：损失函数的定义， αt α t 的求解和 ht(x) h t ( x ) 的求解。

损失函数：

 这里选用指数损失函数来替换0/1损失函数来作为优化目标，理由如下：

 指数损失函数的形式为：

lexp(H|D)=Ex∼D[e−f(x)H(x)](5) (5) l e x p ( H | D ) = E x ∼ D [ e − f ( x ) H ( x ) ]

 上式中：

• f(x) f ( x ) 是真实函数，函数值范围是 {−1,+1} { − 1 , + 1 } ;
• H(x) H ( x ) 是基学习器，函数值范围是 {−1,+1} { − 1 , + 1 } ，结果可能存在误差
• D D 指某种分布;
• x∼Dx∼D 的意思是， x x 服从DD分布；
• lexp(H|D) l e x p ( H | D ) 的含义是在分布为 D D 的前提下，以HH为自变量的损失函数。

 自然的，我们希望获得公式 (5) ( 5 ) 的最小化，考虑公式 (5) ( 5 ) 对 H(x) H ( x ) 求一阶偏导：

∂lexp(H|D)∂H(x)=∂Ex∼D[e−f(x)H(x)]∂H(x)=−e−H(x)Ex∼Df(x)=−e−H(x)[1⋅P(f(x)=1|x)+(−1)P(f(x)=−1|x)]=−e−H(x)P(f(x)=1|x)+e−H(x)P(f(x)=−1|x)(6) (6) ∂ l e x p ( H | D ) ∂ H ( x ) = ∂ E x ∼ D [ e − f ( x ) H ( x ) ] ∂ H ( x ) = − e − H ( x ) E x ∼ D f ( x ) = − e − H ( x ) [ 1 ⋅ P ( f ( x ) = 1 | x ) + ( − 1 ) P ( f ( x ) = − 1 | x ) ] = − e − H ( x ) P ( f ( x ) = 1 | x ) + e − H ( x ) P ( f ( x ) = − 1 | x )

 令式 (4) ( 4 ) 等于0 ，则有：

∂lexp(H|D)∂H(x)e−H(x)P(f(x)=1|x)(eH(x))2H(x)=−e−H(x)P(f(x)=1|x)+eH(x)P(f(x)=−1|x)=0=eH(x)P(f(x)=−1|x)=P(f(x)=1|x)P(f(x)=−1|x)=12lnP(f(x)=1|x)P(f(x)=−1|x)⇒⇒⇒(6) (6) ∂ l e x p ( H | D ) ∂ H ( x ) = − e − H ( x ) P ( f ( x ) = 1 | x ) + e H ( x ) P ( f ( x ) = − 1 | x ) = 0 ⇒ e − H ( x ) P ( f ( x ) = 1 | x ) = e H ( x ) P ( f ( x ) = − 1 | x ) ⇒ ( e H ( x ) ) 2 = P ( f ( x ) = 1 | x ) P ( f ( x ) = − 1 | x ) ⇒ H ( x ) = 1 2 l n P ( f ( x ) = 1 | x ) P ( f ( x ) = − 1 | x )

因此，有：

sign(H(x))=sign(12lnP(f(x)=1|x)P(f(x)=−1|x))={1,P(f(x)=1|x)>P(f(x)=−1|x)−1,P(f(x)=1|x)<P(f(x)=−1|x)=argminy∈−1,1P(f(x)=y|x)(7) (7) s i g n ( H ( x ) ) = s i g n ( 1 2 l n P ( f ( x ) = 1 | x ) P ( f ( x ) = − 1 | x ) ) = { 1 , P ( f ( x ) = 1 | x ) > P ( f ( x ) = − 1 | x ) − 1 , P ( f ( x ) = 1 | x ) < P ( f ( x ) = − 1 | x ) = arg ⁡ min y ∈ − 1 , 1 ⁡ P ( f ( x ) = y | x )

 这意味着， sign(H(x)) s i g n ( H ( x ) ) 达到了贝叶斯最优错误率，换言之，若指数损失函数最小化，则分类错误率也将最小化，这说明指数损失函数是分类任务原本0/1损失函数的一致性的替代损失函数，由于这个替代函数有更好的数学性质，如连续可微，所以替代0/1损失函数。

αt α t 的求解

 在adaboost算法中，第一个基分类器 h1 h 1 是通过直接将基学习算法用于初始数据分布而得，此后迭代地生成 ht h t 和 αt α t 当基分类器 ht h t 基于分布 D D 产生后，该分类器的权重αtαt应是的 αtht α t h t 最小化指数损失函数。

lexp(αtht|Dt)=Ex∼Dt[e−f(x)αtht(x)]=Ex∼Dt[e−αtI(f(x)=ht(x)+eαtI(f(x)≠ht(x))]=e−αtPx∼Dt(f(x)=ht(x))+eαtPx∼Dt(f(x)≠ht(x))=e−αt(1−ϵt)+eαtϵt(8) (8) l e x p ( α t h t | D t ) = E x ∼ D t [ e − f ( x ) α t h t ( x ) ] = E x ∼ D t [ e − α t I ( f ( x ) = h t ( x ) + e α t I ( f ( x ) ≠ h t ( x ) ) ] = e − α t P x ∼ D t ( f ( x ) = h t ( x ) ) + e α t P x ∼ D t ( f ( x ) ≠ h t ( x ) ) = e − α t ( 1 − ϵ t ) + e α t ϵ t

 上式中， I(⋅) I ( ⋅ ) 是指示函数，在 ⋅ ⋅ 为真和假时分别取值为1,0， ϵt=Px∼Dt(ht(x)≠f(x)) ϵ t = P x ∼ D t ( h t ( x ) ≠ f ( x ) ) ,考虑指数损失函数的导数：

∂lexp(αtht|Dt)∂αt=−e−αt(1−ϵt)+eαtϵt(9) (9) ∂ l e x p ( α t h t | D t ) ∂ α t = − e − α t ( 1 − ϵ t ) + e α t ϵ t

 使上式为零，可解得：

αt=12ln(1−ϵtϵt)(10) (10) α t = 1 2 l n ( 1 − ϵ t ϵ t )

 式 (10) ( 10 ) 即为 αt α t 的求解结果。

ht(x) h t ( x ) 的求解：

 adaboost算法在获得 Ht−1 H t − 1 之后样本分布将进行调整，使下一轮的基学习器 ht h t 能纠正 Ht−1 H t − 1 的一些错误，理想的 ht h t 能纠正 Ht−1 H t − 1 的全部错误，即最小化为：

lexp(Ht−1+ht|Dt)=Ex∼Dt[e−f(x)(Ht−1(x)+ht(x))]=Ex∼Dt[e−f(x)(Ht−1(x)e−f(x)ht(x)](11) (11) l e x p ( H t − 1 + h t | D t ) = E x ∼ D t [ e − f ( x ) ( H t − 1 ( x ) + h t ( x ) ) ] = E x ∼ D t [ e − f ( x ) ( H t − 1 ( x ) e − f ( x ) h t ( x ) ]

 注意到 f2(x)=h2t(x)=1 f 2 ( x ) = h t 2 ( x ) = 1 ,因为 f(x)∈{−1,+1},ht(x)∈{−1,+1} f ( x ) ∈ { − 1 , + 1 } , h t ( x ) ∈ { − 1 , + 1 } ,上式使用 e−f(x)ht(x) e − f ( x ) h t ( x ) 的泰勒展开式近似为：

lexp(Ht−1+ht|Dt)=Ex∼Dt[e−f(x)(Ht−1(x)(1−f(x)ht(x)+f2(x)h2t(x)2)]=Ex∼Dt[e−f(x)(Ht−1(x)(1−f(x)ht(x)+12)](12) (12) l e x p ( H t − 1 + h t | D t ) = E x ∼ D t [ e − f ( x ) ( H t − 1 ( x ) ( 1 − f ( x ) h t ( x ) + f 2 ( x ) h t 2 ( x ) 2 ) ] = E x ∼ D t [ e − f ( x ) ( H t − 1 ( x ) ( 1 − f ( x ) h t ( x ) + 1 2 ) ]

 上式中 ex e x 的泰勒展开式为： ex=1+x+x22!+⋯+xnn!+o(xn) e x = 1 + x + x 2 2 ! + ⋯ + x n n ! + o ( x n )

 于是，理想的基学习器：

ht(x)=argminhlexp(Ht−1+h|D)=argminhEx∼D[e−f(x)Ht−1(x)(1−f(x)h(x)+12)]=argmaxhEx∼D[e−f(x)Ht−1(x)f(x)h(x)]=argmaxhEx∼D[e−f(x)Ht−1(x)Ex∼D[e−f(x)Ht−1(x)]f(x)h(x)](13) (13) h t ( x ) = arg ⁡ min h ⁡ l e x p ( H t − 1 + h | D ) = arg ⁡ min h ⁡ E x ∼ D [ e − f ( x ) H t − 1 ( x ) ( 1 − f ( x ) h ( x ) + 1 2 ) ] = arg ⁡ max h ⁡ E x ∼ D [ e − f ( x ) H t − 1 ( x ) f ( x ) h ( x ) ] = arg ⁡ max h ⁡ E x ∼ D [ e − f ( x ) H t − 1 ( x ) E x ∼ D [ e − f ( x ) H t − 1 ( x ) ] f ( x ) h ( x ) ]

 上式中， Ex∼D[e−f(x)Ht−1(x)] E x ∼ D [ e − f ( x ) H t − 1 ( x ) ] 是一个常数，令 Dt D t 为一个分布：

Dt(x)=D(x)e−f(x)Ht−1(x)Ex∼D[e−f(x)Ht−1(x)](14) (14) D t ( x ) = D ( x ) e − f ( x ) H t − 1 ( x ) E x ∼ D [ e − f ( x ) H t − 1 ( x ) ]

 则根据数学期望的定义，这等价于:

ht(x)=argmaxhEx∼D[e−f(x)Ht−1(x)Ex∼D[e−f(x)Ht−1(x)]f(x)h(x)]=argmaxhEx∼Dt[f(x)h(x)](15) (15) h t ( x ) = arg ⁡ max h ⁡ E x ∼ D [ e − f ( x ) H t − 1 ( x ) E x ∼ D [ e − f ( x ) H t − 1 ( x ) ] f ( x ) h ( x ) ] = arg ⁡ max h ⁡ E x ∼ D t [ f ( x ) h ( x ) ]

 因为, f(x),h(x)∈{−1,+1} f ( x ) , h ( x ) ∈ { − 1 , + 1 } ，有：

f(x)h(x)=1−2I(f(x)≠h(x))(16) (16) f ( x ) h ( x ) = 1 − 2 I ( f ( x ) ≠ h ( x ) )

 这是因为：

f(x) f ( x )	h(x) h ( x )	f(x)h(x) f ( x ) h ( x )	I(f(x)≠h(x)) I ( f ( x ) ≠ h ( x ) )
-1	-1	1
-1	+1	-1	1
+1	+1	1
+1	-1	-1	1

 所以有， f(x)h(x)=1−2I(f(x)≠h(x)) f ( x ) h ( x ) = 1 − 2 I ( f ( x ) ≠ h ( x ) )

 则理想的基学习器为:

ht(x)=argmaxhEx∼Dt[f(x)h(x)]=argminhEx∼Dt[I(f(x)≠h(x))](17) (17) h t ( x ) = arg ⁡ max h ⁡ E x ∼ D t [ f ( x ) h ( x ) ] = arg ⁡ min h ⁡ E x ∼ D t [ I ( f ( x ) ≠ h ( x ) ) ]

 由此可见，理想的 ht h t 将在分布 Dt D t 下最小化分类误差。因此，弱分类器将基于分布 Dt D t 来训练，且针对 Dt D t 的分类误差应小于0.5，这在一定程度上类似”残差逼近”的思想，考虑到 Dt D t 和 Dt+1 D t + 1 的关系，有：

Dt+1(x)=D(x)e−f(x)Ht(x)Ex∼D[e−f(x)Ht(x)]=D(x)e−f(x)Ht−1(x)e−f(x)αtht(x)Ex∼D[e−f(x)Ht(x)]=D(x)e−f(x)Ht−1(x)e−f(x)αtht(x)Ex∼D[e−f(x)Ht−1(x)]Ex∼D[e−f(x)Ht−1(x)]Ex∼D[e−f(x)Ht(x)]=Dt(x)e−f(x)αtht(x)Ex∼D[e−f(x)Ht−1(x)]Ex∼D[e−f(x)Ht(x)](18) (18) D t + 1 ( x ) = D ( x ) e − f ( x ) H t ( x ) E x ∼ D [ e − f ( x ) H t ( x ) ] = D ( x ) e − f ( x ) H t − 1 ( x ) e − f ( x ) α t h t ( x ) E x ∼ D [ e − f ( x ) H t ( x ) ] = D ( x ) e − f ( x ) H t − 1 ( x ) e − f ( x ) α t h t ( x ) E x ∼ D [ e − f ( x ) H t − 1 ( x ) ] E x ∼ D [ e − f ( x ) H t − 1 ( x ) ] E x ∼ D [ e − f ( x ) H t ( x ) ] = D t ( x ) e − f ( x ) α t h t ( x ) E x ∼ D [ e − f ( x ) H t − 1 ( x ) ] E x ∼ D [ e − f ( x ) H t ( x ) ]

 至此， ht(x) h t ( x ) 的表达式推导完毕。