adaboost

Boosting，也稱為增強學習或提升法，是一種重要的集成學習技術，能夠將預測精度僅比隨機猜度略高的弱學習器增強為預測精度高的強學習器，這在直接構造強學習器非常困難的情況下，為學習算法的設計提供了一種有效的新思路和新方法。作為一種元算法框架，Boosting幾乎可以應用於所有目前流行的機器學習算法以進一步加強原算法的預測精度，應用十分廣泛，產生了極大的影響。而AdaBoost正是其中最成功的代表，被評為數據挖掘十大算法之一。在AdaBoost提出至今的十幾年間，機器學習領域的諸多知名學者不斷投入到算法相關理論的研究中去，紮實的理論為AdaBoost算法的成功應用打下了堅實的基礎。AdaBoost的成功不僅僅在於它是一種有效的學習算法，還在於1)它讓Boosting從最初的猜想變成一種真正具有實用價值的算法；2)算法採用的一些技巧，如:打破原有樣本分佈，也為其他統計學習算法的設計帶來了重要的啓示；3)相關理論研究成果極大地促進了集成學習的發展。 ^[1] 

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

最初的Boosting算法由Schapire於1990年提出，即一種多項式的算法，並進行了實驗和理論性的證明[28]。在此之後，Freund研究出一種更高效的Boosting算法。但這兩種算法都有共同的不足即需要提前確定弱學習算法識別準確率的下限。Boosting算法可以提升任意給定學習算法的準確度，主要思想是通過一些簡單的規則整合得到一個整體，使得該整體具有的性能比任何一個部分都高。其思想受啓發於Valiant提出的PAC(ProbablyApproximatelyCorrect)學習模型。Valiant認為“學習”是一種不管模式明顯清晰或是否存在模式時都能夠獲得知識的過程，並從計算的角度定義了學習的方法，其包含學習的協議、合理信息採集機制的選擇以及可以在適當過程內實現學習概念的分類[29]。PAC學習模型的原理是指在訓練樣本的基礎上，算法的輸出能夠以概率靠近未知的目標進行學習分類，基本框架涉及樣本複雜度和計算複雜度。簡而言之，在PAC學習模型中，能夠在多項式個時間內和樣本獲得特定要求的正確率即就是一個好的學習過程。該模型由統計模式識別、決策理論得到的一些簡單理論並結合計算複雜理論的方法而得出的學習模型。其中提出了弱學習和強學習的概念。

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

Adaboost算法在樣本訓練集使用過程中，對其中的關鍵分類特徵集進行多次挑選，逐步訓練分量弱分類器，用適當的閾值選擇最佳弱分類器，最後將每次迭代訓練選出的最佳弱分類器構建為強分類器。其中，級聯分類器的設計模式為在儘量保證感興趣圖像輸出率的同時，減少非感興趣圖像的輸出率，隨着迭代次數不斷增加，所有的非感興趣圖像樣本都不能通過，而感興趣樣本始終保持儘可能通過為止。 ^[2] 

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

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

2. 將分錯的樣本和其他的新數據一起構成一個新的N個的訓練樣本，通過對這個樣本的學習得到第二個弱分類器 ；

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

4. 最終經過提升的強分類器。即某個數據被分為哪一類要由各分類器權值決定。

由Adaboost算法的描述過程可知，該算法在實現過程中根據訓練集的大小初始化樣本權值，使其滿足均勻分佈，在後續操作中通過公式來改變和規範化算法迭代後樣本的權值。樣本被錯誤分類導致權值增大，反之權值相應減小，這表示被錯分的訓練樣本集包括一個更高的權重。這就會使在下輪時訓練樣本集更注重於難以識別的樣本，針對被錯分樣本的進一步學習來得到下一個弱分類器，直到樣本被正確分類[36]。在達到規定的迭代次數或者預期的誤差率時，則強分類器構建完成。 ^[2] 

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