adaboost算法
基本思想是，對于一個複雜的問題，單獨用一個分類算法判斷比較困難，那麼我們就用一組分類器來進行綜合判斷，得到結果，“三個臭皮匠頂一個諸葛亮”
專業的說法，
強可學習（strongly learnable），存在一個多項式算法可以學習，并且準确率很高
弱可學習（weakly learnable），存在一個多項式算法可以學習，但準确率略高于随機猜測
并且可以證明強可學習和弱可學習是等價的
那麼發現一個弱可學習算法是很容易的，如果将弱可學習算法boosting到強可學習算法？
adaboost就是這樣的算法，通過反複學習，得到一組弱分類器，通過組合這些弱分類器得到強分類器
問題就是如果得到一組弱分類器？
當然你可以用不同的分類算法來訓練
也可以用不同的訓練集，比如bagging，對訓練集進行m次随機抽樣，得到m個新的訓練集
adaboost采用的方法是，用相同的算法和訓練集，但改變每個訓練樣本的weight，因為在求解分類器時的目标函數是，權重誤差最小，是以不同的權值會得到不同的分類器參數
具體的規則，是每輪分類後， 增大分錯的樣本的權值，減小分對樣本的權值，所有樣本權值和為1
這樣下一輪分類器求解，就會更關注上一輪分錯的這樣樣本點，達到分而治之的目的
需要注意，可以想到，這個算法對離群值比較敏感，容易overfitting
并且每個弱分類器也有個weight，代表該分類器的誤差率，最終用權重多數表決的方式來得到最終結果
具體算法，
1. 初始化訓練樣本的權值，平均分布，每個樣本的機率相同
2. 反複疊代學習得到m個弱分類器，對于第m個弱分類器，
2.1 對于訓練集，以權重誤差最小為目标，求出分類器，gm
2.2 算出，該弱分類器的權重誤差
2.3 算出該弱分類器的權值，log函數，可見誤差越小，權值越高，即在最終強分類器中的作用越大
2.4 關鍵的一步，更新訓練樣本的權值
其中，第一個式子其實是，
指數分布，小于0，取值在(0,1)，大于0，取值大于1
是以意思就是，當gm(x)=y的時候，即判斷正确的樣本，減小權值
判斷錯誤的樣本，增權重值
之是以要除以zm，是因為所有權值的和要為1，用zm來進行規範化
3. 上面我們就得到m個弱分類器，如何組合出強分類器，
很簡單的，權重多數表決
其中sign函數，取值-1(x<0)，0，1(x>0)
本文章摘自部落格園，原文釋出日期： 2014-08-26