關(guān)于Adaboost，我以前推薦的是Ensemble Based Systems in Decision Making，在這個(gè)wiki中AdaBoost詞條下的external links中就有，它沒(méi)有給出為什么AdaBoost的推導(dǎo)，不過(guò)它本身是一篇很好的介紹，下面是Pattern Recognition and Machine Learning第14.3節(jié)中的介紹。

Boosting是一個(gè)將多個(gè)基分類(lèi)器結(jié)合產(chǎn)生一個(gè)committee形式分類(lèi)器的方法，它的分類(lèi)效果會(huì)比任何單個(gè)基分類(lèi)器要好的多。這里我們描述一個(gè)廣泛使用的boosting算法AdaBoost，它是’adaptive boosting’的縮寫(xiě)(不能用漢語(yǔ)拼音的方法去讀，其實(shí)這是一個(gè)很可怕的習(xí)慣)。Boosting可以在基分類(lèi)器就比隨機(jī)亂猜好一點(diǎn)的情況下，得到一個(gè)好的分類(lèi)效果，所以有時(shí)基分類(lèi)器被稱(chēng)為弱分類(lèi)器(weak learners)。

         Boosting與committee方法相比，比如bagging，主要區(qū)別在于，Boosting是基分類(lèi)器是順序?qū)W習(xí)的，并且每一個(gè)基分類(lèi)器所訓(xùn)練的數(shù)據(jù)集樣本是加權(quán)的，樣本權(quán)重是由前面分類(lèi)器的在該樣本上的分類(lèi)效果所決定的。特別是，被一個(gè)基分類(lèi)器所分類(lèi)錯(cuò)誤的點(diǎn)會(huì)給更高的權(quán)重。當(dāng)所有的分類(lèi)器都訓(xùn)練好了，它們的預(yù)測(cè)是通過(guò)加權(quán)投票的方式結(jié)合起來(lái)，如圖14.1所示。

         考慮一個(gè)二分類(lèi)問(wèn)題，訓(xùn)練數(shù)據(jù)集由輸入向量x₁,…,x?_N組成，每一個(gè)向量對(duì)應(yīng)一個(gè)二值的目標(biāo)值t₁,…,t_N。其中t_N屬于{-1, 1}。每個(gè)數(shù)據(jù)點(diǎn)給定一個(gè)相應(yīng)的權(quán)重w_n，所有的樣本權(quán)重被初始化為1/N。假設(shè)我們有一個(gè)方法可以通過(guò)加權(quán)數(shù)據(jù)學(xué)習(xí)一個(gè)給定的函數(shù)y(x)，y(x)屬于{-1,1}，訓(xùn)練一個(gè)基分類(lèi)器。在算法的每一步，AdaBoost學(xué)習(xí)一個(gè)新的分類(lèi)器，這個(gè)分類(lèi)器通過(guò)上一次訓(xùn)練的分類(lèi)器加權(quán)后的數(shù)據(jù)進(jìn)行學(xué)習(xí)，加權(quán)是將錯(cuò)誤的樣本賦以更高的權(quán)重的過(guò)程。最后，當(dāng)適合個(gè)數(shù)的基分類(lèi)器被訓(xùn)練后，它們通過(guò)不同基分類(lèi)器加以不同的權(quán)重的方法結(jié)合起來(lái)進(jìn)行預(yù)測(cè)。AdaBoost的標(biāo)準(zhǔn)形式如下：

         我們看到第一個(gè)基分類(lèi)器y₁(x)是通過(guò)全部相等的權(quán)重w_n⁽¹⁾訓(xùn)練的，它采用的是訓(xùn)練一個(gè)單分類(lèi)器的標(biāo)準(zhǔn)過(guò)程。從14.18中我們可以看到隨后的迭代中，對(duì)于分類(lèi)錯(cuò)誤的數(shù)據(jù)點(diǎn)增加權(quán)重系數(shù)w_?n^(m)，分類(lèi)正確的數(shù)據(jù)點(diǎn)權(quán)重減小。隨后的分類(lèi)器所以被迫更關(guān)注于以前分類(lèi)器分類(lèi)錯(cuò)誤的樣本，隨后分類(lèi)器再分類(lèi)錯(cuò)誤的樣本會(huì)被賦以更高的權(quán)重。量epsilon_m表示每個(gè)基分類(lèi)器錯(cuò)誤率的一個(gè)度量方法。所以我們看到權(quán)重系數(shù)由14.17定義的alpha_m會(huì)對(duì)分類(lèi)更準(zhǔn)確的分類(lèi)器賦以更高的權(quán)重，最后通過(guò)14.19將輸出結(jié)果結(jié)合起來(lái)。

         Adaboost算法示例在圖14.2中，一個(gè)30個(gè)數(shù)據(jù)點(diǎn)的toy子數(shù)據(jù)集做為例子。這個(gè)簡(jiǎn)單的分類(lèi)器對(duì)應(yīng)決策樹(shù)的一種形式稱(chēng)之為’decision stumps’，比如，一個(gè)決策樹(shù)只有一個(gè)結(jié)點(diǎn)。所以每個(gè)基分類(lèi)器分類(lèi)一個(gè)與其對(duì)應(yīng)的特征，當(dāng)特征值超過(guò)了某個(gè)閾值，就把它分類(lèi)成某個(gè)類(lèi)別。也就是分類(lèi)器只關(guān)心一個(gè)維，即與坐標(biāo)軸平等的維。

         下面是圖14.2圖注的翻譯：boosting算法的一個(gè)例子，每一個(gè)基分類(lèi)器包含x軸或是y軸坐標(biāo)的閾值。每一幅圖顯示了當(dāng)前有多少個(gè)基分類(lèi)器已經(jīng)訓(xùn)練了，還顯示了最新訓(xùn)練的基分類(lèi)器的決策邊界(黑色的點(diǎn)線)和ensemble結(jié)合的決策邊界。每一數(shù)據(jù)點(diǎn)由一個(gè)圈描述，它的半徑表示當(dāng)訓(xùn)練最新基分類(lèi)器時(shí)，這個(gè)數(shù)據(jù)點(diǎn)的權(quán)重。所以，例如，我們看到由m=1基分類(lèi)器分類(lèi)錯(cuò)誤的數(shù)據(jù)點(diǎn)在m=2基分類(lèi)器學(xué)習(xí)時(shí)賦予更高的權(quán)重。