AdaBoost階段小結(jié)

1、提綱提綱n前期調(diào)研前期調(diào)研nadaboostadaboost原理原理n一些問題一些問題前期調(diào)研前期調(diào)研npacpac學(xué)習(xí)模型學(xué)習(xí)模型2-3 機(jī)器學(xué)習(xí)中，訓(xùn)練樣本再大也不能代表某類事機(jī)器學(xué)習(xí)中，訓(xùn)練樣本再大也不能代表某類事物本身，所以從訓(xùn)練樣本中學(xué)習(xí)得到物本身，所以從訓(xùn)練樣本中學(xué)習(xí)得到“規(guī)則規(guī)則”不能對某類事物完全適用，總有失效的情況出不能對某類事物完全適用，總有失效的情況出現(xiàn)，所以機(jī)器學(xué)習(xí)的目標(biāo)是現(xiàn)，所以機(jī)器學(xué)習(xí)的目標(biāo)是概率逼近正確學(xué)習(xí)概率逼近正確學(xué)習(xí)! ! 1984年年 valiant提出提出pac（probably probably approximately correctapproxi

2、mately correct）學(xué)習(xí)模型文中提出）學(xué)習(xí)模型文中提出強(qiáng)學(xué)習(xí)和弱學(xué)習(xí)兩個概念強(qiáng)學(xué)習(xí)和弱學(xué)習(xí)兩個概念。nvaliant的貢獻(xiàn)的貢獻(xiàn) valiant指出弱學(xué)習(xí)轉(zhuǎn)換為強(qiáng)學(xué)習(xí)的可行性！ 實際運用中，人們根據(jù)生產(chǎn)經(jīng)驗可以較為容易的找到弱學(xué)習(xí)方法，但是很多情況下要找到強(qiáng)學(xué)習(xí)方法是不容易的。有時候人們傾向于通過先找到弱學(xué)習(xí)然后把它轉(zhuǎn)換為強(qiáng)學(xué)習(xí)的方式獲取強(qiáng)學(xué)習(xí)方法，而valiant證明了這種方式的可行性。n怎樣實現(xiàn)弱學(xué)習(xí)轉(zhuǎn)為強(qiáng)學(xué)習(xí)怎樣實現(xiàn)弱學(xué)習(xí)轉(zhuǎn)為強(qiáng)學(xué)習(xí) 核心思想：通過組合使弱學(xué)習(xí)互補(bǔ)。 學(xué)習(xí)是不適定問題，在有限的樣本上，不同的學(xué)習(xí)方法得到不同的“規(guī)則”，并在不同的情況下失效，沒有一種學(xué)習(xí)算法總是在

3、任何領(lǐng)域產(chǎn)生最好的分類效果。 例如：學(xué)習(xí)算法a在a情況下失效，學(xué)習(xí)算法b在b情況下失效，那么在a情況下可以用b算法，在b情況下可以用a算法解決。這說明通過某種合適的方式把各種算法組合起來，可以提高準(zhǔn)確率。 為實現(xiàn)弱學(xué)習(xí)互補(bǔ)，面臨兩個問題： （1）怎樣獲得不同的弱分類器？ （2）怎樣組合弱分類器？n怎樣獲得不同的弱分類器怎樣獲得不同的弱分類器u使用不同的弱學(xué)習(xí)算法得到不同基學(xué)習(xí)器 參數(shù)估計、非參數(shù)估計u使用相同的弱學(xué)習(xí)算法，但用不同的超參數(shù) k-mean不同的k，神經(jīng)網(wǎng)絡(luò)不同的隱含層u相同輸入對象的不同表示 不同的表示可以凸顯事物不同的特征u使用不同的訓(xùn)練集 裝袋（bagging） 提升（boo

4、sting） n怎樣組合弱分類器怎樣組合弱分類器u多專家組合一種并行結(jié)構(gòu)，所有的弱分類器都給出各自的預(yù)測結(jié)果，通過“組合器”把這些預(yù)測結(jié)果轉(zhuǎn)換為最終結(jié)果。 eg.投票（voting）及其變種、混合專家模型u多級組合 一種串行結(jié)構(gòu)，其中下一個分類器只在前一個分類器預(yù)測不夠準(zhǔn)（不夠自信）的實例上進(jìn)行訓(xùn)練或檢測。 eg. 級聯(lián)算法（cascading）n小結(jié)小結(jié) 通過前期調(diào)研我比較關(guān)注是boosting原理。 bagging在給定樣本上隨機(jī)抽取（有放回）訓(xùn)練子集，在每個訓(xùn)練子集上用不穩(wěn)定的學(xué)習(xí)算法訓(xùn)練分類不同弱分類器。boosting在前一個弱分類器錯分的實例在后續(xù)的弱分類器上得到更大的重視。從訓(xùn)練

5、子集的獲取方式上看： bagging靠“運氣”，boosting有“依據(jù)”！ 所謂不穩(wěn)定學(xué)習(xí)算法是指訓(xùn)練集很小的變化會引起所產(chǎn)生的分類器變化很大，即學(xué)習(xí)算法高方差。例如，決策樹。adaboostadaboost原理原理nadaboost的由來的由來？nadaboostadaboost的核心思想的核心思想“關(guān)注”被錯分的樣本，“器重”性能好的弱分類器n怎么實現(xiàn)怎么實現(xiàn) （1）不同的訓(xùn)練集調(diào)整樣本權(quán)重 （2）“關(guān)注”增加錯分樣本權(quán)重 （3）“器重”好的分類器權(quán)重大 （4）樣本權(quán)重間接影響分類器權(quán)重原始adaboost1995年freund 提出adaboost算法，1999年schapire在一篇

6、會議論文上對freund的adaboost重新表述，基本原理不變但是更易理解，下面以schapire的版本介紹adaboost。given: m examples (x1, y1), , (xm, ym) where xix, yiy=-1, +1initialize d1(i) = 1/mfor t = 1 to tpr()tti dtiih xy1. train learner ht with min error ttt1ln212. compute the hypothesis weight iitiittttyxheyxhezididtt)(if)(if)()(13. for each

7、 example i = 1 to mttttxhxh1)(sign)(outputthe weight adapts. the bigger t becomes the smaller t becomes.zt is a normalization factor.boost example if incorrectly predicted.linear combination of models.schapire adaboost algorithmnadaboost的收斂性證明 整個證明的核心： ，不等左邊是最終強(qiáng)分類器的錯誤率證明過程： 至此，看到adaboost的錯誤率上限，接下來的目

8、標(biāo)就是使這個上限盡可能小！n怎么使 盡量小看到 是關(guān)于 的函數(shù)，要使 最小顯然需要研究 ！在原始的adaboost算法中采用貪婪算法，每次的 都是最小的保證 收斂到滿意的結(jié)果。在原始adaboost算法中h值域是-1，1，問題是怎么找到最佳的 )(exp()(ittiiittxhyxdztztztth、tth、t這時候 前面證明原始adaboost算法的收斂性，但是原始adaboost的收斂速度是不是就是最好的，有沒有更快的？有，schapire提出了real adaboost收斂更快！再次明確一下目標(biāo)： 使盡量小！對于原始的adaboost，前文討論過其h是“定死”的，失去了“討價還價”的余

9、地，進(jìn)而確定了 的選擇方法，所以在real adaboost不在“定死”)(exp()(ittiiittxhyxdztreal adaboost algorithmh 不再“定死”到這里介紹完adaboost原理，接下來就是我學(xué)習(xí)中的一些困惑。？一些問題uadaboost泛化能力的證明uadaboost中對h選擇u接下來學(xué)習(xí)的方向uadaboost泛化能力的證明 目前對adaboost泛化能力的證明是各家各言，沒有定論。 freund的證明已經(jīng)被實踐推翻； schapire的證明被人證明是有缺陷的； 我比較關(guān)注的是freund和schapire的證明，他們都用到一個概念叫vc維度。我查了很多文

10、獻(xiàn)，都沒能理解這個概念，所以目前我對adaboost泛化能力的證明無能為力。uadaboost對h的選擇 是h和alpha的二元函數(shù)，為什么考慮的時候都考慮alpha，沒考慮h？ 在原始的adaboost算法中用錯誤率最小來確定h至少還有個說法，在real adaboost中直接把h和alpha整合成一個參數(shù)h了，那么real adaboost算法中對alpha的討論又有什么意義呢？ tzu接下來學(xué)習(xí)的方向 不管是變種adaboost其功能都是把弱學(xué)習(xí)提升為強(qiáng)學(xué)習(xí)，直觀上我的感覺是adaboost性能好壞取決于弱學(xué)習(xí)？ 那么我們應(yīng)該怎么選擇弱學(xué)習(xí)方法？我在文獻(xiàn)中看到有決策樹、神經(jīng)網(wǎng)絡(luò)、svm、k-mean。等，adaboost作者用的是c4.5決策樹。viola第一個用adaboost做人臉檢測，他采