一個有情懷的公眾號 Adaptive Boosting(AdaBoost)是一種迭代算法,其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器(弱分類器),然后把這些弱分類器集合起來,構(gòu)成一個最強的最終分類器(強分類器)。 1 Motivation of Boosting 我們先來看一個簡單的識別蘋果的例子,老師展示20張圖片,讓6歲孩子們通過觀察,判斷其中哪些圖片的內(nèi)容是蘋果。從判斷的過程中推導(dǎo)如何解決二元分類問題的方法。 顯然這是一個監(jiān)督式學(xué)習(xí),20張圖片包括它的標簽都是已知的。首先,學(xué)生Michael回答說:所有的蘋果應(yīng)該是圓形的。根據(jù)Michael的判斷,對應(yīng)到20張圖片中去,大部分蘋果能被識別出來,但也有錯誤。其中錯誤包括有的蘋果不是圓形,而且圓形的水果也不一定是蘋果。如下圖所示: 上圖中藍色區(qū)域的圖片代表分類錯誤。顯然,只用“蘋果是圓形的”這一個條件不能保證分類效果很好。我們把藍色區(qū)域(分類錯誤的圖片)放大,分類正確的圖片縮小,這樣在接下來的分類中就會更加注重這些錯誤樣本。 然后,學(xué)生Tina觀察被放大的錯誤樣本和上一輪被縮小的正確樣本,回答說:蘋果應(yīng)該是紅色的。根據(jù)Tina的判斷,得到的結(jié)果如下圖所示: 上圖中藍色區(qū)域的圖片一樣代表分類錯誤,即根據(jù)這個蘋果是紅色的條件,使得青蘋果和草莓、西紅柿都出現(xiàn)了判斷錯誤。那么結(jié)果就是把這些分類錯誤的樣本放大化,其它正確的樣本縮小化。同樣,這樣在接下來的分類中就會更加注重這些錯誤樣本。 接著,學(xué)生Joey經(jīng)過觀察又說:蘋果也可能是綠色的。根據(jù)Joey的判斷,得到的結(jié)果如下圖所示: 上圖中藍色區(qū)域的圖片一樣代表分類錯誤,根據(jù)蘋果是綠色的條件,使得圖中藍色區(qū)域都出現(xiàn)了判斷錯誤。同樣把這些分類錯誤的樣本放大化,其它正確的樣本縮小化,在下一輪判斷繼續(xù)對其修正。 后來,學(xué)生Jessica又發(fā)現(xiàn):上面有梗的才是蘋果。得到如下結(jié)果: 經(jīng)過這幾個同學(xué)的推論,蘋果被定義為:圓的,紅色的,也可能是綠色的,上面有梗。從一個一個的推導(dǎo)過程中,我們似乎得到一個較為準確的蘋果的定義。雖然可能不是非常準確,但是要比單一的條件要好得多。也就是說把所有學(xué)生對蘋果的定義融合起來,最終得到一個比較好的對蘋果的總體定義。這種做法就是我們本節(jié)課將要討論的演算法。這些學(xué)生代表的就是簡單的hypotheses gtgt,將所有g(shù)tgt融合,得到很好的預(yù)測模型G。例如,二維平面上簡單的hypotheses(水平線和垂直線),這些簡單gtgt最終組成的較復(fù)雜的分類線能夠較好地將正負樣本完全分開,即得到了好的預(yù)測模型。 所以,上個蘋果的例子中,不同的學(xué)生代表不同的hypotheses gt;最終得到的蘋果總體定義就代表hypothesis G;而老師就代表演算法A,指導(dǎo)學(xué)生的注意力集中到關(guān)鍵的例子中(錯誤樣本),從而得到更好的蘋果定義。其中的數(shù)學(xué)原理,我們下一部分詳細介紹。 2 Diversity by Re-weighting ![]() ![]() ![]() ![]() ![]() 這種算法叫做Weightd Base Algorithm,目的就是最小化bootstrap-weighted error。 ![]() 其實,這種weightd base algorithm我們之前就介紹過類似的算法形式。例如在soft-margin SVM中,我們引入允許犯錯的項,同樣可以將每個點的error乘以權(quán)重因子un。加上該項前的參數(shù)C,經(jīng)過QP,最終得到0≤αn≤Cun,有別于之前介紹的0≤αn≤C。這里的un相當于每個犯錯的樣本的懲罰因子,并會反映到αn的范圍限定上。 同樣在logistic regression中,同樣可以對每個犯錯誤的樣本乘以相應(yīng)的un,作為懲罰因子。un表示該錯誤點出現(xiàn)的次數(shù),un越大,則對應(yīng)的懲罰因子越大,則在最小化error時就應(yīng)該更加重視這些點。 ![]() 其實這種example-weighted learning,我們在機器學(xué)習(xí)基石課程第8次筆記中就介紹過class-weighted的思想。二者道理是相通的。 知道了u的概念后,我們知道不同的u組合經(jīng)過base algorithm得到不同的gt。那么如何選取u,使得到的gt之間有很大的不同呢?之所以要讓所有的gt差別很大,是因為上節(jié)課aggregation中,我們介紹過gt越不一樣,其aggregation的效果越好,即每個人的意見越不相同,越能運用集體的智慧,得到好的預(yù)測模型。 為了得到不同的gt,我們先來看看gt和g(t+1)是怎么得到的: ![]() ![]() ![]() ![]() 乍看上面這個式子,似乎不好求解。但是,我們對它做一些等價處理,其中分式中分子可以看成gt作用下犯錯誤的點,而分母可以看成犯錯的點和沒有犯錯誤的點的集合,即所有樣本點。其中犯錯誤的點和沒有犯錯誤的點分別用橘色方塊和綠色圓圈表示: ![]() ![]() ![]() ![]() ![]() ![]() 3 Adaptive Boosting Algorithm ![]() ![]() ![]() ![]() 值得注意的是上述的結(jié)論是建立在?t≤1/2的基礎(chǔ)上,如果?t≥1/2,那么就做相反的推論即可。關(guān)于?t≥1/2的情況,我們稍后會進行說明。 ![]() ![]() 但是,上述步驟還有兩個問題沒有解決,第一個問題是初始的u應(yīng)為多少呢?一般來說,為了保證第一次Ein最小的話,設(shè)u=1/N即可。這樣最開始的g就能由此推導(dǎo)。第二個問題,最終的G(x)應(yīng)該怎么求?是將所有的g(t)合并uniform在一起嗎?一般來說并不是這樣直接uniform求解,因為g(t+1)是通過gt得來的,二者在Ein上的表現(xiàn)差別比較大。所以,一般是對所有的g(t)進行l(wèi)inear或者non-linear組合來得到G(t)。 ![]() 接下來的內(nèi)容,我們將對上面的第二個問題進行探討,研究一種算法,將所有的gt進行l(wèi)inear組合。方法是計算gt的同時,就能計算得到其線性組合系數(shù)αt,即aggregate linearly on the fly。這種算法使最終求得g(t+1)的時候,所有gt的線性組合系數(shù)α也求得了,不用再重新計算α了。這種Linear Aggregation on the Fly算法流程為: ![]() 如何在每次迭代的時候計算αt呢?我們知道αt與?t是相關(guān)的:?t越小,對應(yīng)的αt應(yīng)該越大,?t越大,對應(yīng)的αt應(yīng)該越小。又因為?t與?t是正相關(guān)的,所以,αt應(yīng)該是?t的單調(diào)函數(shù)。我們構(gòu)造αt為: ![]() αt這樣取值是有物理意義的,例如當?t=1/2時,error很大,跟擲骰子這樣的隨機過程沒什么兩樣,此時對應(yīng)的?t=1,αt=0,即此gt對G沒有什么貢獻,權(quán)重應(yīng)該設(shè)為零。而當?t=0時,沒有error,表示該gt預(yù)測非常準,此時對應(yīng)的?t=∞,αt=∞,即此gt對G貢獻非常大,權(quán)重應(yīng)該設(shè)為無窮大。 ![]() 這種算法被稱為Adaptive Boosting。它由三部分構(gòu)成:base learning algorithm A,re-weighting factor ?t和linear aggregation αt。這三部分分別對應(yīng)于我們在本節(jié)課開始介紹的例子中的Student,Teacher和Class。 ![]() 綜上所述,完整的adaptive boosting(AdaBoost)Algorithm流程如下: ![]() 從我們之前介紹過的VC bound角度來看,AdaBoost算法理論上滿足: ![]() ![]() 對這個VC bound中的第一項Ein(G)來說,有一個很好的性質(zhì):如果滿足?t≤?<1 ,則經(jīng)過t="">1>Ein(G)能減小到等于零的程度。而當N很大的時候,其中第二項也能變得很小。因為這兩項都能變得很小,那么整個Eout(G)就能被限定在一個有限的上界中。 其實,這種性質(zhì)也正是AdaBoost算法的精髓所在。只要每次的?t≤?<1>1>g比亂猜的表現(xiàn)好一點點,那么經(jīng)過每次迭代之后,矩g的表現(xiàn)都會比原來更好一些,逐漸變強,最終得到Ein=0且Eout很小。 ![]() 4 Adaptive Boosting in Action 上一小節(jié)我們已經(jīng)介紹了選擇一個“弱弱”的算法A(?t≤?<1>1>Ein=0。我們稱這種形式為decision stump模型。下面介紹一個例子,來看看AdaBoost是如何使用decision stump解決實際問題的。 如下圖所示,二維平面上分布一些正負樣本點,利用decision stump來做切割。 ![]() 第一步: ![]() 第二步: ![]() 第三步: ![]() 第四步: ![]() 第五步: ![]() 可以看到,經(jīng)過5次迭代之后,所有的正負點已經(jīng)被完全分開了,則最終得到的分類線為: ![]() 另外一個例子,對于一個相對比較復(fù)雜的數(shù)據(jù)集,如下圖所示。它的分界線從視覺上看應(yīng)該是一個sin波的形式。如果我們再使用AdaBoost算法,通過decision stump來做切割。在迭代切割100次后,得到的分界線如下所示。 ![]() 可以看出,AdaBoost-Stump這種非線性模型得到的分界線對正負樣本有較好的分離效果。 課程中還介紹了一個AdaBoost-Stump在人臉識別方面的應(yīng)用: ![]() 5 Summary 本節(jié)課主要介紹了Adaptive Boosting。首先通過講一個老師教小學(xué)生識別蘋果的例子,來引入Boosting的思想,即把許多“弱弱”的hypotheses合并起來,變成很強的預(yù)測模型。然后重點介紹這種算法如何實現(xiàn),關(guān)鍵在于每次迭代時,給予樣本不同的系數(shù)u,宗旨是放大錯誤樣本,縮小正確樣本,得到不同的小矩g。并且在每次迭代時根據(jù)錯誤?值的大小,給予不同gt不同的權(quán)重。最終由不同的gt進行組合得到整體的預(yù)測模型G。實際證明,Adaptive Boosting能夠得到有效的預(yù)測模型。 |
|
來自: 太極混元天尊 > 《學(xué)習(xí)資料》