幾種Boost算法的比較(Discrete AdaBoost, Real AdaBoost, LogitBoost, Gentle Adaboost)
關于boost算法
boost算法是基于 PAC學習理論 （probably approximately correct）而建立的一套集成學習算法(ensemble learning)。其根本思想在于通過多個簡單的弱分類器，構建出準確率很高的強分類器，PAC學習理論證實了這一方法的可行性。下面關于幾種 Boost算法的比較，是基于文章《Additive Logistic Regression a Statistical View of Boosting》整理的。
幾種boost算法步驟
通常使用最多的應該是離散的Adaboost算法(Discrete AdaBoost),主要因為它的簡單卻不俗的表現，Discrete Adaboost算法的步驟如下：
可以看出，Discrete AdaBoost的每一個弱分類的輸出結果是1或-1，并沒有屬于某個類的概率，略顯粗糙。如果讓每個弱分類器輸出樣本屬于某個類的概率，則可以得到Real AdaBoost算法，其步驟如下：
Real Adaboost每個弱分類器輸出樣本屬于某類的概率后，通過一個對數函數將0-1的概率值映射到實數域，最后的分類器是所有映射函數的和。
將Real Adaboost算法每次迭代的兩部合并，直接產生一個映射到實數域的函數，則就成了Gentle AdaBoost， 其算法步驟如下：
Gentle AdaBoost則在每次迭代時，基于最小二乘去做一個加權回歸，最后所有回歸函數的和作為最終的分類器。
LogitBoost算法則和Gentle AdaBoost算法有點相像，不過其每次進行回歸擬合的變量z是在不斷更新的，Gentle AdaBoost使用的是y。LogitBoost算法步驟如下：
4種boost算法的原理差異
上面4中boost算法，其大體結構都是比較相似的，那么是如何推導出每種算法的具體形式的呢？
首先是關于損失函數（或代價函數），通常見到比較多的是均方誤差和似然函數，而上面的算法中，Discrete AdaBoost、Real AdaBoost和Gentle AdaBoost算法都是采用對數損失函數，具體形式如下：
\begin{aligned} J(F) = Ee^({-yF(x)}) \end{aligned}
其表達的意義實質上與分類錯誤個數是相同的。
而Logit Boost算法則采用最大化對數似然函數來推導的。
第二點是具體優化方法，Discrete AdaBoost與Real AdaBoost主要通過類似梯度下降的方法來優化，而Gentle AdaBoost與Logit Boost都是采用類似牛頓迭代的方式優化的。
算法的效果差異
在前面提到的參考文章中，對幾種算法的效果進行了大量比較，大致如下;
- 整體效果而言，效果由好到差的順序為Logit Boost，Gentle AdaBoost， Real AdaBoost， Discrete AdaBoost
- 若弱分類器采用樹樁模型（也就是只要2個葉子節點的決策樹），Discrete AdaBoost的結果比其他3種算法結果差了很多，大概是由于系統偏差過大導致的泛化誤差較大
- 若弱分類器采用多層的決策樹（4或8個葉子節點），Discrete AdaBoost的結果能有較大提升，而其他3種算法則差異不大。
平時我們所用的AdaBoost算法大多是Discrete AdaBoost，從這里可以看出Discrete AdaBoost算法模型相對比較簡單，需要弱分類器的精確度稍高，因此在具體應用時最好將每個弱分類器的葉子節點控制在4個或8個。關于Boost算法 還有很多比較有趣的結論，這里不多講，可以參考上面的那篇Paper。