Adaboost是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器（弱分類器），然后把這些弱分類器集合起來，構(gòu)成一個更強的最終分類器（強分類器）。

Boosting，也稱為增強學習或提升法，是一種重要的集成學習技術(shù)，能夠?qū)㈩A測精度僅比隨機猜度略高的弱學習器增強為預測精度高的強學習器，這在直接構(gòu)造強學習器非常困難的情況下，為學習算法的設(shè)計提供了一種有效的新思路和新方法。作為一種元算法框架，Boosting幾乎可以應用于所有目前流行的機器學習算法以進一步加強原算法的預測精度，應用十分廣泛，產(chǎn)生了極大的影響。而AdaBoost正是其中最成功的代表，被評為數(shù)據(jù)挖掘十大算法之一。在AdaBoost提出至今的十幾年間，機器學習領(lǐng)域的諸多知名學者不斷投入到算法相關(guān)理論的研究中去，扎實的理論為AdaBoost算法的成功應用打下了堅實的基礎(chǔ)。AdaBoost的成功不僅僅在于它是一種有效的學習算法，還在于：

1）它讓Boosting從最初的猜想變成一種真正具有實用價值的算法；

2）算法采用的一些技巧，如：打破原有樣本分布，也為其他統(tǒng)計學習算法的設(shè)計帶來了重要的啟示；

3）相關(guān)理論研究成果極大地促進了集成學習的發(fā)展。

對adaBoost算法的研究以及應用大多集中于分類問題，同時也出現(xiàn)了一些在回歸問題上的應用。就其應用adaBoost系列主要解決了： 兩類問題、多類單標簽問題、多類多標簽問題、大類單標簽問題、回歸問題。它用全部的訓練樣本進行學習。

最初的Boosting算法由Schapire于1990年提出，即一種多項式的算法，并進行了實驗和理論性的證明。在此之后，F(xiàn)reund研究出一種更高效的Boosting算法。但這兩種算法都有共同的不足即需要提前確定弱學習算法識別準確率的下限。Boosting算法可以提升任意給定學習算法的準確度，主要思想是通過一些簡單的規(guī)則整合得到一個整體，使得該整體具有的性能比任何一個部分都高。其思想受啟發(fā)于Valiant提出的PAC學習模型。

Valiant認為“學習”是一種不管模式明顯清晰或是否存在模式時都能夠獲得知識的過程，并從計算的角度定義了學習的方法，其包含學習的協(xié)議、合理信息采集機制的選擇以及可以在適當過程內(nèi)實現(xiàn)學習概念的分類。PAC學習模型的原理是指在訓練樣本的基礎(chǔ)上，算法的輸出能夠以概率靠近未知的目標進行學習分類，基本框架涉及樣本復雜度和計算復雜度。簡而言之，在PAC學習模型中，能夠在多項式個時間內(nèi)和樣本獲得特定要求的正確率即就是一個好的學習過程。該模型由統(tǒng)計模式識別、決策理論得到的一些簡單理論并結(jié)合計算復雜理論的方法而得出的學習模型。其中提出了弱學習和強學習的概念。

Adaboost算法已被證明是一種有效而實用的Boosting算法。該算法是Freund和Schapire于1995年對Boosting算法的改進得到的，其算法原理是通過調(diào)整樣本權(quán)重和弱分類器權(quán)值，從訓練出的弱分類器中篩選出權(quán)值系數(shù)最小的弱分類器組合成一個最終強分類器。基于訓練集訓練弱分類器，每次下一個弱分類器都是在樣本的不同權(quán)值集上訓練獲得的。每個樣本被分類的難易度決定權(quán)重，而分類的難易度是經(jīng)過前面步驟中的分類器的輸出估計得到的。

Adaboost算法在樣本訓練集使用過程中，對其中的關(guān)鍵分類特征集進行多次挑選，逐步訓練分量弱分類器，用適當?shù)拈撝颠x擇最佳弱分類器，最后將每次迭代訓練選出的最佳弱分類器構(gòu)建為強分類器。其中，級聯(lián)分類器的設(shè)計模式為在盡量保證感興趣圖像輸出率的同時，減少非感興趣圖像的輸出率，隨著迭代次數(shù)不斷增加，所有的非感興趣圖像樣本都不能通過，而感興趣樣本始終保持盡可能通過為止。

算法流程

該算法其實是一個簡單的弱分類算法提升過程，這個過程通過不斷的訓練，可以提高對數(shù)據(jù)的分類能力。整個過程如下所示：

1． 先通過對N個訓練樣本的學習得到第一個弱分類器；

2． 將分錯的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個新的N個的訓練樣本，通過對這個樣本的學習得到第二個弱分類器 ；

3． 將1和2都分錯了的樣本加上其他的新樣本構(gòu)成另一個新的N個的訓練樣本，通過對這個樣本的學習得到第三個弱分類器；

4． 最終經(jīng)過提升的強分類器。即某個數(shù)據(jù)被分為哪一類要由各分類器權(quán)值決定。

由Adaboost算法的描述過程可知，該算法在實現(xiàn)過程中根據(jù)訓練集的大小初始化樣本權(quán)值，使其滿足均勻分布，在后續(xù)操作中通過公式來改變和規(guī)范化算法迭代后樣本的權(quán)值。樣本被錯誤分類導致權(quán)值增大，反之權(quán)值相應減小，這表示被錯分的訓練樣本集包括一個更高的權(quán)重。這就會使在下輪時訓練樣本集更注重于難以識別的樣本，針對被錯分樣本的進一步學習來得到下一個弱分類器，直到樣本被正確分類。在達到規(guī)定的迭代次數(shù)或者預期的誤差率時，則強分類器構(gòu)建完成。 

算法特點

Aadboost 算法系統(tǒng)具有較高的檢測速率，且不易出現(xiàn)過適應現(xiàn)象。但是該算法在實現(xiàn)過程中為取得更高的檢測精度則需要較大的訓練樣本集，在每次迭代過程中，訓練一個弱分類器則對應該樣本集中的每一個樣本，每個樣本具有很多特征，因此從龐大的特征中訓練得到最優(yōu)弱分類器的計算量增大。典型的 Adaboost 算法采用的搜索機制是回溯法，雖然在訓練弱分類器時每一次都是由貪心算法來獲得局部最佳弱分類器，但是卻不能確保選擇出來加權(quán)后的是整體最佳。在選擇具有最小誤差的弱分類器之后，對每個樣本的權(quán)值進行更新，增大錯誤分類的樣本對應的權(quán)值，相對地減小被正確分類的樣本權(quán)重。且執(zhí)行效果依賴于弱分類器的選擇，搜索時間隨之增加，故訓練過程使得整個系統(tǒng)的所用時間非常大，也因此限制了該算法的廣泛應用。另一方面，在算法實現(xiàn)過程中，從檢測率和對正樣本的誤識率兩個方面向預期值逐漸逼近來構(gòu)造級聯(lián)分類器，迭代訓練生成大量的弱分類器后才能實現(xiàn)這一構(gòu)造過程。由此推出循環(huán)逼近的訓練分類器需要消耗更多的時間。