第8章 集成學(xué)習(xí)理論

主要內(nèi)容1.集成學(xué)習(xí)的概念2.Adaboost3.應(yīng)用：人臉識(shí)別11.集成學(xué)習(xí)2在機(jī)器學(xué)習(xí)中，直接建立一個(gè)高性能的分類器是很困難的。但是，如果能找到一系列性能較差的分類器，并把它們集成起來的話，也許就能得到更好的分類器。日常生活中，所謂的民主決策，便是部分的利用了這種想法。譬如選總統(tǒng)，每個(gè)人都以自己的考慮，投下自己的一票，但最后由多數(shù)人選出的總統(tǒng)，似乎應(yīng)該好于由一個(gè)人指定的總統(tǒng)?！炯蓪W(xué)習(xí)：動(dòng)機(jī)】3集成學(xué)習(xí)，就是一種把輸入送入多個(gè)學(xué)習(xí)器，再通過某種辦法把學(xué)習(xí)的結(jié)果集成起來的辦法。這每一個(gè)學(xué)習(xí)器，也就相應(yīng)的被稱為“弱學(xué)習(xí)器”。集成學(xué)習(xí)最早也叫做“CommitteeVotingMethod”，也就是因?yàn)樗屯镀钡倪^程相似?！炯蓪W(xué)習(xí)：動(dòng)機(jī)】4弱學(xué)習(xí)機(jī)（weaklearner):對(duì)一定分布的訓(xùn)練樣本給出假設(shè)（僅僅強(qiáng)于隨機(jī)猜測(cè)）強(qiáng)學(xué)習(xí)機(jī)（stronglearner):根據(jù)得到的弱學(xué)習(xí)機(jī)和相應(yīng)的權(quán)重給出假設(shè)（最大程度上符合實(shí)際情況：almostperfectexpert)弱學(xué)習(xí)機(jī)強(qiáng)學(xué)習(xí)機(jī)Boosting弱學(xué)習(xí)機(jī)和強(qiáng)學(xué)習(xí)機(jī)5ClassifierensembleΣαihi(x)hn(x)h2(x)h1(x)InputvectorClassifier1Classifier2……ClassifierNCombineClassifiersOutputx【集成學(xué)習(xí)：圖示】6Boosting思想源于三個(gè)臭皮匠，勝過諸葛亮

Findingmanyroughrulesofthumbcanbealoteasierandmoreeffectivethanfindingasingle,highlypredictionrule.【理論背景】7Boosting是一種提高任意給定學(xué)習(xí)算法準(zhǔn)確度的方法。它的思想起源于Valiant提出的PAC(ProbablyApproximatelyCorrect)學(xué)習(xí)模型（1984）提出問題（Valiant和Kearns，1984）:強(qiáng)學(xué)習(xí)算法:準(zhǔn)確率很高的學(xué)習(xí)算法弱學(xué)習(xí)算法:準(zhǔn)確率不高,僅比隨機(jī)猜測(cè)略好是否可以將弱學(xué)習(xí)算法提升為強(qiáng)學(xué)習(xí)算法【理論來源】8

同時(shí),Valiant和Kearns首次提出了PAC學(xué)習(xí)模型中弱學(xué)習(xí)算法和強(qiáng)學(xué)習(xí)算法的等價(jià)性問題（1988）,即任意給定僅比隨機(jī)猜測(cè)略好的弱學(xué)習(xí)算法,是否可以將其提升為強(qiáng)學(xué)習(xí)算法?如果二者等價(jià),那么只需找到一個(gè)比隨機(jī)猜測(cè)略好的弱學(xué)習(xí)算法就可以將其提升為強(qiáng)學(xué)習(xí)算法,而不必尋找很難獲得的強(qiáng)學(xué)習(xí)算法。【理論來源】9YES【理論來源】10Boosting由來(1)Kearns&Valiant(1984)

PAC學(xué)習(xí)模型提出問題：強(qiáng)學(xué)習(xí)算法：存在一個(gè)多項(xiàng)式時(shí)間的學(xué)習(xí)算法以識(shí)別一組概念，且識(shí)別的正確率很高。弱學(xué)習(xí)算法：識(shí)別一組概念的正確率僅比隨機(jī)猜測(cè)略好。弱學(xué)習(xí)器與強(qiáng)學(xué)習(xí)器的等價(jià)問題。如果兩者等價(jià)，只需找到一個(gè)比隨機(jī)猜測(cè)略好的學(xué)習(xí)算法，就可以將其提升為強(qiáng)學(xué)習(xí)算法。11Boosting由來(2)Kearns&Valiant(1989)證明了弱學(xué)習(xí)器和強(qiáng)學(xué)習(xí)器的等價(jià)問題。Schapire(1989)第一個(gè)提出了一個(gè)可證明的多項(xiàng)式時(shí)間的Boosting算法。Schapire,etc.(1993)第一次把Boosting算法思想用于實(shí)際應(yīng)用：OCR。Freund&Schapire，ICML,1996AdaBoost算法。12我們一般選定加權(quán)平均的方法來構(gòu)造集成學(xué)習(xí)的最終學(xué)習(xí)器。但是里面的每一個(gè)Classifieri怎樣做呢？有一些研究，是針對(duì)每個(gè)學(xué)習(xí)器都不同構(gòu)的情況，比如識(shí)別一個(gè)人，一個(gè)學(xué)習(xí)器考慮臉，另一個(gè)考慮步態(tài)，另一個(gè)考慮指紋。這種研究通常稱為InformationFusion，不在我們今天討論的范疇。我們今天討論的，是用同樣的學(xué)習(xí)算法來構(gòu)造不同的弱學(xué)習(xí)器的方法?！炯蓪W(xué)習(xí)：如何構(gòu)造？】13辦法就是改變訓(xùn)練集。通常的學(xué)習(xí)算法，根據(jù)訓(xùn)練集的不同，會(huì)給出不同的學(xué)習(xí)器。這時(shí)就可以通過改變訓(xùn)練集來構(gòu)造不同的學(xué)習(xí)器。然后再把它們集成起來?！炯蓪W(xué)習(xí)：如何構(gòu)造？】14在原來的訓(xùn)練集上隨機(jī)采樣，可以得到新的訓(xùn)練集?！倦S機(jī)采樣】15采樣時(shí)，我們可以給訓(xùn)練集里的每個(gè)元素不同的權(quán)。權(quán)值可以通過上一次訓(xùn)練的結(jié)果來確定?！編?quán)的采樣】16通過給訓(xùn)練數(shù)據(jù)賦以不同的權(quán)，實(shí)際上使得每個(gè)學(xué)習(xí)器關(guān)注訓(xùn)練集中的某一部分，這也符合我們最初民主投票的想法。直觀上，每個(gè)學(xué)習(xí)器關(guān)注訓(xùn)練集中的某一部分，很多個(gè)訓(xùn)練集應(yīng)該可以覆蓋訓(xùn)練集中的大部分，只要巧妙的選擇加權(quán)平均的權(quán)，就可以得到更好的學(xué)習(xí)效果?！編?quán)的采樣:討論】17【用多個(gè)學(xué)習(xí)器覆蓋樣本空間】18集成學(xué)習(xí)實(shí)際上代表了一種與傳統(tǒng)不同的思維理念。傳統(tǒng)的機(jī)器學(xué)習(xí)一般都自認(rèn)為是單模型的，對(duì)于模型的分析總是在整體上完成。Rosenblatt：PerceptronRumelhart:BPVapnik:SVM但是，所有這些模型其實(shí)都可以看作是一種加權(quán)平均的多模型?！炯蓪W(xué)習(xí)：評(píng)述】19所以，當(dāng)然應(yīng)該考慮研究一般的多模型。實(shí)際上，從90年代開始，對(duì)集成學(xué)習(xí)的研究取得了一系列突破進(jìn)展。在算法上，集成學(xué)習(xí)的典型代表AdaBoost算法，已經(jīng)成為與SVM并立的方法。而且，集成學(xué)習(xí)比SVM更為一般，可能可以有更廣闊的前景。【集成學(xué)習(xí)：評(píng)述】20泛化：generalization泛化能力越強(qiáng)，處理新數(shù)據(jù)的能力越好【泛化能力】泛化能力是機(jī)器學(xué)習(xí)關(guān)注的基本問題之一提高泛化能力是永遠(yuǎn)的追求21集成學(xué)習(xí)（EnsembleLearning）是一種機(jī)器學(xué)習(xí)范式，它使用多個(gè)（通常是同質(zhì)的）學(xué)習(xí)器來解決同一個(gè)問題

問題…...…...

問題集成學(xué)習(xí)中使用的多個(gè)學(xué)習(xí)器稱為個(gè)體學(xué)習(xí)器當(dāng)個(gè)體學(xué)習(xí)器均為決策樹時(shí)，稱為“決策樹集成”當(dāng)個(gè)體學(xué)習(xí)器均為神經(jīng)網(wǎng)絡(luò)時(shí)，稱為“神經(jīng)網(wǎng)絡(luò)集成”…………【集成學(xué)習(xí)】22由于集成學(xué)習(xí)技術(shù)可以有效地提高學(xué)習(xí)系統(tǒng)的泛化能力，因此它成為國際機(jī)器學(xué)習(xí)界的研究熱點(diǎn)，并被國際權(quán)威T.G.Dietterich稱為當(dāng)前機(jī)器學(xué)習(xí)四大研究方向之首[T.G.Dietterich,AIMag97]問題：對(duì)20維超立方體空間中的區(qū)域分類左圖中縱軸為錯(cuò)誤率從上到下的四條線分別表示：平均神經(jīng)網(wǎng)絡(luò)錯(cuò)誤率最好神經(jīng)網(wǎng)絡(luò)錯(cuò)誤率兩種神經(jīng)網(wǎng)絡(luò)集成的錯(cuò)誤率令人驚奇的是，集成的錯(cuò)誤率比最好的個(gè)體還低

[L.K.Hansen&P.Salamon,TPAMI90]【集成學(xué)習(xí)的重要性】23集成學(xué)習(xí)技術(shù)已經(jīng)在行星探測(cè)、地震波分析、Web信息過濾、生物特征識(shí)別、計(jì)算機(jī)輔助醫(yī)療診斷等眾多領(lǐng)域得到了廣泛的應(yīng)用只要能用到機(jī)器學(xué)習(xí)的地方，就能用到集成學(xué)習(xí)【集成學(xué)習(xí)的應(yīng)用】24期望結(jié)果個(gè)體1(精度33.3%)個(gè)體2(精度33.3%)個(gè)體3(精度33.3%)集成(精度33.3%)投票個(gè)體必須有差異期望結(jié)果個(gè)體1(精度33.3%)個(gè)體2(精度33.3%)個(gè)體3(精度33.3%)集成(精度0%)投票個(gè)體精度不能太低個(gè)體學(xué)習(xí)器越精確、差異越大，集成越好【如何構(gòu)建好的集成】25既然多個(gè)個(gè)體的集成比單個(gè)個(gè)體更好，那么是不是個(gè)體越多越好?更多的個(gè)體意味著：在預(yù)測(cè)時(shí)需要更大的計(jì)算開銷，因?yàn)橐?jì)算更多的個(gè)體預(yù)測(cè)更大的存儲(chǔ)開銷，因?yàn)橛懈嗟膫€(gè)體需要保存?zhèn)€體的增加將使得個(gè)體間的差異越來越難以獲得【個(gè)體越多越好嗎？】26分類器設(shè)計(jì)的重采樣技術(shù)也被稱為“自適應(yīng)的權(quán)值重置和組合（arcing,adaptivereweightingandcombining）；這類方法的主要思想是利用同一個(gè)訓(xùn)練樣本集合構(gòu)造多個(gè)分類器，然后以某種方式將這些分類器組合成一個(gè)分類器；主要方法包括：bagging算法和boosting算法【分類設(shè)計(jì)的重采樣技術(shù)】27從大小為n的原始數(shù)據(jù)集D中獨(dú)立隨機(jī)地抽取n’個(gè)數(shù)據(jù)(n’<=n)，形成一個(gè)自助數(shù)據(jù)集；重復(fù)上述過程，產(chǎn)生出多個(gè)獨(dú)立的自助數(shù)據(jù)集；利用每個(gè)自助數(shù)據(jù)集訓(xùn)練出一個(gè)“分量分類器”；最終的分類結(jié)果由這些“分量分類器”各自的判別結(jié)果投票決定?；舅枷耄簩?duì)訓(xùn)練集有放回地抽取訓(xùn)練樣例，從而為每一個(gè)基本分類器都構(gòu)造出一個(gè)跟訓(xùn)練集相當(dāng)大小但各不相同的訓(xùn)練集，從而訓(xùn)練出不同的基本分類器；該算法是基于對(duì)訓(xùn)練集進(jìn)行處理的集成方法中最簡單、最直觀的一種?！綛agging算法】28boosting算法同樣是利用訓(xùn)練樣本集合構(gòu)造多個(gè)分量分類器，它只要求這個(gè)分量分類器是一個(gè)弱分類器—準(zhǔn)確率比平均性能好即可。2類問題，3個(gè)分量分類器的訓(xùn)練算法：在數(shù)量為n的原始樣本集D中隨機(jī)選取n1個(gè)樣本構(gòu)成D1，利用D1訓(xùn)練出一個(gè)分類器C1；在樣本集D-D1中選擇被C1正確分類和錯(cuò)誤分類的樣本各一半組成樣本集D2，用D2訓(xùn)練出一個(gè)分類器C2；將樣本集D-D1-D2中所有C1和C2分類結(jié)果不同的樣本組成樣本集D3，訓(xùn)練出一個(gè)分類器C3；【Boosting算法】29對(duì)新的樣本x進(jìn)行分類，如果C1和C2判別結(jié)果相同，則將x判別為此類別，否則以C3的結(jié)果作為x的類別；原始樣本集分量分類器組合分類器【Boosting的分類算法】30Boosting算法：首先給每一個(gè)訓(xùn)練樣例賦予相同的權(quán)重，然后訓(xùn)練第一個(gè)基本分類器并用它來對(duì)訓(xùn)練集進(jìn)行測(cè)試，對(duì)于那些分類錯(cuò)誤的測(cè)試樣例提高其權(quán)重（實(shí)際算法中是降低分類正確的樣例的權(quán)重），然后用調(diào)整后的帶權(quán)訓(xùn)練集訓(xùn)練第二個(gè)基本分類器，然后重復(fù)這個(gè)過程直到最后得到一個(gè)足夠好的學(xué)習(xí)器?！綛oosting算法步驟】31【Bagging算法和Boosting算法比較】32Step1:原始訓(xùn)練集輸入，帶有原始分布Step2:給出訓(xùn)練集中各樣本的權(quán)重Step3:將改變分布后的訓(xùn)練集輸入已知的弱學(xué)習(xí)機(jī)，弱學(xué)習(xí)機(jī)對(duì)每個(gè)樣本給出假設(shè)Step4:對(duì)此次的弱學(xué)習(xí)機(jī)給出權(quán)重Step5:轉(zhuǎn)到Step2,直到循環(huán)到達(dá)一定次數(shù)或者某度量標(biāo)準(zhǔn)符合要求Step6:將弱學(xué)習(xí)機(jī)按其相應(yīng)的權(quán)重加權(quán)組合形成強(qiáng)學(xué)習(xí)機(jī)【Boosting算法流程描述】33樣本的權(quán)重沒有先驗(yàn)知識(shí)的情況下，初始的分布應(yīng)為等概分布，也就是訓(xùn)練集如果有N個(gè)樣本，每個(gè)樣本的分布概率為1/N每次循環(huán)一后提高錯(cuò)誤樣本的分布概率，分錯(cuò)樣本在訓(xùn)練集中所占權(quán)重增大，使得下一次循環(huán)的弱學(xué)習(xí)機(jī)能夠集中力量對(duì)這些錯(cuò)誤樣本進(jìn)行判斷。弱學(xué)習(xí)機(jī)的權(quán)重準(zhǔn)確率越高的弱學(xué)習(xí)機(jī)權(quán)重越高循環(huán)控制：損失函數(shù)達(dá)到最小在強(qiáng)學(xué)習(xí)機(jī)的組合中增加一個(gè)加權(quán)的弱學(xué)習(xí)機(jī)，使準(zhǔn)確率提高，損失函數(shù)值減小?！綛oosting算法核心思想】34【簡單問題演示(Boosting訓(xùn)練過程)】35要求事先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限解決方案：Adaboost【Boosting算法存在問題】36訓(xùn)練集:Bagging:隨機(jī)選擇,各輪訓(xùn)練集相互獨(dú)立Boosting:各輪訓(xùn)練集并不獨(dú)立,它的選擇與前輪的學(xué)習(xí)結(jié)果有關(guān)預(yù)測(cè)函數(shù):Bagging:沒有權(quán)重;可以并行生成Boosting:有權(quán)重;只能順序生成Bagging和boosting的區(qū)別【總結(jié)】37在大多數(shù)應(yīng)用中，準(zhǔn)確率比運(yùn)算速度更為重要，因?yàn)橛?jì)算機(jī)的性價(jià)比提高很快。

bagging和boosting都可以有效地提高分類的準(zhǔn)確性。在大多數(shù)數(shù)據(jù)集中，boosting的準(zhǔn)確性比bagging高。在有些數(shù)據(jù)集中，boosting會(huì)引起退化。---OverfitBagging和boosting方法的要求：最基本的是分類方法的不穩(wěn)定性。即：訓(xùn)練集的小變動(dòng)能夠使得分類模型顯著變動(dòng)?！究偨Y(jié)】382.AdaBoost39adaboost的實(shí)現(xiàn)過程示例：圖中，“+”和“-”分別表示兩種類別，在這個(gè)過程中，我們使用水平或者垂直的直線作為分類器，來進(jìn)行分類?！続casestudy】40

第一步：根據(jù)分類的正確率，得到一個(gè)新的樣本分布D2-，一個(gè)子分類器h1其中劃圈的樣本表示被分錯(cuò)的。在右邊的圖中，比較大的“+”表示對(duì)該樣本做了加權(quán)。

【Acasestudy】41第二步：根據(jù)分類的正確率，得到一個(gè)新的樣本分布D3，一個(gè)子分類器h2【Acasestudy】42第三步：得到一個(gè)子分類器h3【Acasestudy】43整合所有子分類器：因此可以得到整合的結(jié)果，從結(jié)果中看，即使簡單的分類器，組合起來也能獲得很好的分類效果?！続casestudy】44AdaboostBaseSetting二元分類問題訓(xùn)練數(shù)據(jù):(x1,y1),…,(xm,ym)wherexi∈X,yi∈Y={-1,+1}Dt(i):樣本xi在第t次迭代的權(quán)重D1(i)=1/mht(X)：弱學(xué)習(xí)器Ct訓(xùn)練得到的判別函數(shù)ht:X->{-1,+1}εt：ht(X)的錯(cuò)誤率45Adaboost基本思路1.訓(xùn)練一系列弱學(xué)習(xí)器h1,h2,…,hT。2.在訓(xùn)練過程中，注重那些分類錯(cuò)誤的樣本。3.把訓(xùn)練出來的一系列弱學(xué)習(xí)器組合起來，每個(gè)弱學(xué)習(xí)器ht(X)都有一個(gè)相應(yīng)的權(quán)重46AdaBoost算法47為什么每次迭代都要把分錯(cuò)的點(diǎn)的權(quán)值變大呢？這樣有什么好處呢？不這樣不行嗎?注意到算法最后的表到式為這里面的a表示的權(quán)值，是由得到的。而a是關(guān)于誤差的表達(dá)式，到這里就可以得到比較清晰的答案了，所有的一切都指向了誤差。提高錯(cuò)誤點(diǎn)的權(quán)值，當(dāng)下一次分類器再次分錯(cuò)了這些點(diǎn)之后，會(huì)提高整體的錯(cuò)誤率，這樣就導(dǎo)致a變的很小，最終導(dǎo)致這個(gè)分類器在整個(gè)混合分類器的權(quán)值變低。也就是說，這個(gè)算法讓優(yōu)秀的分類器占整體的權(quán)值更高，而差的分類器權(quán)值更低。AdaBoost算法48AdaBoost算法(2)弱學(xué)習(xí)器Ct的權(quán)重αt由第t次迭代決定訓(xùn)練樣本的分布權(quán)重Dt(i)在每一次迭代都會(huì)更新弱學(xué)習(xí)器Ct的選擇：如果某次迭代的訓(xùn)練誤差大于1/2，則拋棄，算法停止49AdaBoost算法(3)算法在每次迭代都會(huì)更新樣本的分布權(quán)重，在下一次迭代前會(huì)進(jìn)行一次訓(xùn)練樣本的重采樣。如何進(jìn)行重采樣？可根據(jù)概率分布Dt(i)來采樣。5050Adaboost算法重點(diǎn)—樣本權(quán)重思想：提高分錯(cuò)樣本的權(quán)重

采用什么樣的函數(shù)形式？

51Adaboost算法重點(diǎn)—弱學(xué)習(xí)機(jī)權(quán)重思想：錯(cuò)誤率越低，該學(xué)習(xí)機(jī)的權(quán)重應(yīng)該越大采用什么樣的函數(shù)形式？52OverviewTheAdaBoostAlgorithmHowandwhyAdaBoostworks?AdaBoostforFaceDetection【Outline】53AdaBoostAdaptiveAlearningalgorithmBuildingastrongclassifierfromalotofweakeronesBoosting【Introduction】54...weakclassifiersslightlybetterthanrandomstrongclassifier【AdaBoostConcept】55WeakerClassifiers...weakclassifiersslightlybetterthanrandomstrongclassifierEachweakclassifierlearnsbyconsideringonesimplefeatureT

most

beneficialfeaturesforclassificationshouldbeselectedHowtodefinefeatures?selectbeneficialfeatures?trainweakclassifiers?manage(weight)trainingsamples?associateweighttoeachweakclassifier?56TheStrongClassifiers...weakclassifiersslightlybetterthanrandomstrongclassifierHowgoodthestrongonewillbe?57TheAdaBoostAlgorithmGiven:Initialization:For:Findclassifierwhichminimizeserrorwrt

Dt

,i.e.,

Weightclassifier:

Updatedistribution:

58TheAdaBoostAlgorithmGiven:Initialization:For:Findclassifierwhichminimizeserrorwrt

Dt

,i.e.,

Weightclassifier:

Updatedistribution:

Outputfinalclassifier:59BoostingillustrationWeakClassifier160BoostingillustrationWeightsIncreased61BoostingillustrationWeakClassifier262BoostingillustrationWeightsIncreased63BoostingillustrationWeakClassifier364BoostingillustrationFinalclassifierisacombinationofweakclassifiers65HowandwhyAdaBoostworks?66TheAdaBoostAlgorithmGiven:Initialization:For:Findclassifierwhichminimizeserrorwrt

Dt

,i.e.,

Weightclassifier:

Updatedistribution:

Outputfinalclassifier:WhatgoaltheAdaBoostwantstoreach?67T