內建學習與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 ) 的表達式推導完畢。