AdaBoost & AdaRank 算法
1. AdaBoost
實習了三個多月，把ML的算法都忘得差不多了，最近寫論文用到了AdaBoost和AdaRank，這里重新復習總結了下，主要參考了：http://blog.csdn.net/haidao2009/article/details/7514787 。
AdaBoost 是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器，即弱分類器，然后把這些弱分類器集合起來，構造一個更強的最終分類器。(很多博客里說的三個臭皮匠賽過諸葛亮)
算法本身是改變數據分布實現的，它根據每次訓練集之中的每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權值。將修改權值的新數據 送給下層分類器進行訓練，然后將每次訓練得到的分類器融合起來，作為最后的決策分類器。完整的adaboost算法如下：
下面我們舉一個簡單的例子來看看adaboost的實現過程：
圖中，“+”和“-”分別表示兩種類別，在這個過程中，我們使用水平或者垂直的直線作為分類器，來進行分類。
第一步：
根據分類的正確率，得到一個新的樣本分布D2，一個子分類器h1 其中劃圈的樣本表示被分錯的。在右邊的途中，比較大的“+”表示對該樣本做了加權。
也 許你對上面的?1，ɑ1怎么算的也不是很理解。下面我們算一下，不要嫌我啰嗦，我最開始就是這樣思考的，只有自己把算法演算一遍，你才會真正的懂這個算法 的核心，后面我會再次提到這個。算法最開始給了一個均勻分布 D 。所以h1 里的每個點的值是0.1。ok，當劃分后，有三個點劃分錯了，根據算法誤差表達式
得到 誤差為分錯了的三個點的值之和，所以?1=(0.1+0.1+0.1)=0.3，而ɑ1 根據表達式
的可以算出來為0.42. 然后就根據算法 把分錯的點權值變大。如此迭代，最終完成adaboost算法。
第二步：
根據分類的正確率，得到一個新的樣本分布D3，一個子分類器h2
第三步：
得到一個子分類器h3
第四步：
整合所有子分類器：
因此可以得到整合的結果，從結果中看，及時簡單的分類器，組合起來也能獲得很好的分類效果，在例子中所有的。
關于若分類器：
獲得不同若分類器的方式有如下幾種：
- 不同的弱學習算法得到不同學習器的參數估計、非參數估計。
- 使用相同的若學習算法，但用不同的參數，eg：K-Means的k，神經網絡不同的隱含層。
- 相同輸入對象的不同表示，不同的表示可以凸顯事務的不同特征。
一些思考：
到這里，也許你已經對adaboost算法有了大致的理解。但是也許你會有個問題，為什么每次迭代都要把分錯的點的權值變大呢？這樣有什么好處呢？不這樣 不行嗎? 這就是我當時的想法，為什么呢？我看了好幾篇介紹adaboost 的博客，都沒有解答我的疑惑，也許大牛認為太簡單了，不值一提，或者他們并沒有意識到這個問題而一筆帶過了。然后我仔細一想，也許提高錯誤點可以讓后面的 分類器權值更高。然后看了adaboost算法，和我最初的想法很接近，但不全是。 注意到算法最后的表到式為
，這里面的a 表示的權值，是由
得到的。而a是關于誤差的表達式，到這里就可以得到比較清晰的答案了，所有的一切都指向了誤差。提高錯誤點的權值，當下一次分類器再次分錯了這些點之后， 會提高整體的錯誤率，這樣就導致 a 變的很小，最終導致這個分類器在整個混合分類器的權值變低。也就是說，這個算法讓優秀的分類器占整體的權值更高，而挫的分類器權值更低。這個就很符合常理 了。到此，我認為對adaboost已經有了一個透徹的理解了。
總結：
我們可以總結下adaboost算法的一些實際可以使用的場景：
1）用于二分類或多分類的應用場景
2）用于做分類任務的baseline
無腦化，簡單，不會overfitting，不用調分類器
3）用于特征選擇（feature selection)
4）Boosting框架用于對badcase的修正
只需要增加新的分類器，不需要變動原有分類器
由于adaboost算法是一種實現簡單，應用也很簡單的算法。Adaboost算法通過組合弱分類器而得到強分類器，同時具有分類錯誤率上界隨著訓練增加而穩定下降，不會過擬合等的性質，應該說是一種很適合于在各種分類場景下應用的算法。
來自：http://my.oschina.net/supersonic/blog/379438