Lecture8 - Ensemble Learning

02-05

這一講，講給大家講講什麼是集成學習，也就是平常所說的Ensemble Learning，讀做"昂桑寶"。

集成學習說的是

他是通過構建多個學習器來完成學習任務
有時也叫做多分類系統，或者叫基於委員會的學習

按照分類器的類型是否相同：

異態集成-基本分類器的類型不同

集成後的分類器包含不同類型的個體學習器。例如，同時包含決策樹和神經網路，這樣的集成就是異態集成

同態集成-基本分類器的類型相同

此時的集成中只包含同種類型的個體學習器。例如，全是決策樹的集成，全是神經網路的集成。

好了。知道了集成學習的基本概念，我們再來看看什麼是弱學習器，什麼是強學習器。這兩個概念都是在PAC（probably approximately correct）的學習框架下，

一個概念（一個類），如果存在多項式時間的演算法可以學習他，而且正確率很高，則稱這個概念是強可學習的。
同樣，一個概念，如果存在一個多項式的學習演算法能夠學習它，學習的正確率僅僅比隨機猜想略好，那稱這個學概念是弱可學習的。
在該學習框架下，我們一定能夠通過將弱學習器進行組合，從而得到一個強學習器。

emmmm，有了強學習和弱學習的概念，那麼，我們就能知道集成學習的目的了。他就是針對這些弱學習器而言的，通過將多個弱學習器進行結合，在泛化誤差上面，往往能得到比單個弱學習器要好的效果，這也就達到了集成學習的目的。

接下來，對於集成學習按照演算法進行分類：

Bagging
Boosting

其實只要掌握以上這兩類演算法就行了，關於集成學習的內容，可以和很多model進行結合，已達到比單個model更優的泛化性能。在下面的文章中，我會慢慢講解。

Bagging：

首先來說說Bagging，Bagging就是袋裝的意思，他的訓練步驟是這樣的

首先訓練一組基分類器，每個基分類器通過一個bootstrap訓練樣本集來進行訓練，有關bootstrap在model selection這章已經講過了，就是一個又放回的採集訓練集的方法。
獲得基分類器後，

對於分類問題，bagging通過投票進行統計，選出這些基分類器的output中被投票最多的類作為result。
對於回歸問題，bagging通過求取各個基分類器的output做平均，得到最終的result。

從偏差-方差分解的角度看，Bagging 主要關注降低方差，因為它在不剪枝決策樹，神經網路等易受樣本擾動的學習器上效果更為明顯。

Boosting：

那什麼是boosting演算法呢？boosting演算法其實是一族可將弱學習器提升為強學習器的方法，這類演算法的工作機制如下：

先從初始訓練集訓練處一個基學習器，再根據對基學習器的表現對訓練樣本分布進行調整，使得先前在基學習器做錯的訓練樣本在後續受到更多的關注，然後基於調整後的樣本分布來訓練下一個基學習器，如此重複進行，直到達到預期目標值，然後將這些基學習器按照權值相加。

其中，boosting族演算法最著名的代表就是AdaBoost

關於boosting有兩個核心問題：

每一輪如何改變訓練數據的權值或概率分布？

通過提高那些在前一輪被弱分類器分錯樣例的權值，減小前一輪分對樣例的權值，來使得分類器對誤分的數據有較好的效果。

2. 通過什麼方式來組合弱分類器？

通過加法模型將弱分類器進行線性組合，比如AdaBoost通過加權多數表決的方式，即增大錯誤率小的分類器的權值，同時減小錯誤率較大的分類器的權值。而提升樹通過擬合殘差的方式逐步減小殘差，將每一步生成的模型疊加得到最終模型。（提升樹=AdaBoost+決策樹)

從偏差方差分解的角度看，Boosting演算法主要是為了降低偏差，因此，Boosting演算法能基於泛化性能相當弱的學習器構建出很強的集成。

比較：

Boosting 與 Bagging的相同點

Bagging和Boosting都是將已有的分類或回歸演算法通過一定方式組合起來，形成一個性能更加強大的分類器，更準確的說這是一種分類演算法的組裝方法。即將弱分類器組裝成強分類器的方法。

Boosting 與 Bagging的差異：

在訓練樣本的選擇上：

Bagging演算法：它是通過bootstrap方法來，有放回的從一個訓練集中選出數據，每輪的採集是相互獨立的
Boosting演算法：每一輪的訓練集不變，只是訓練集中每個樣例在分類器中的權重發生變化。而權值是根據上一輪的分類結果進行調整。

樣例權重上：

Bagging演算法：使用均勻取樣，每個樣例的權重相等
Boosting演算法：根據每輪訓練的錯誤率不斷調整樣例的權重，錯誤率越高，樣例的權重越大

預測函數上：

Bagging演算法：所有預測函數的權值相同
Boosting演算法：每個弱分類器都會有一個權重，對於那些分類誤差小的分類器，將會有更大的權重。

運算方式：

Bagging演算法：所有預測函數可以並行生成，在生成的過程中，互不干擾。
Boosting演算法：各個預測函數只能順序生成，因為後一個模型參數需要前一輪的預測結果

關於最後一點，其實這也就是目前集成學習的主流。

一種是以個體學習器見存在強依賴關係，必須串列生成的序列化方法為主的boosting演算法。
另外一種是個體學習器之間不存在強依賴關係，可同時生成的並行化方法為主的bagging演算法。

總結：

這兩種方法都是通過將若干個分類器整合為一個分類器的方法，只是整合的方式不同，最終得到的預測效果也是不一樣的。我們可以通過將現有的分類器演算法與該演算法框架（bagging或者boosting）相結合，從而得到比原先的分類器演算法性能更優越的分類器，但是這種結合在一定程度上也帶來了計算量的增加。

比如：

決策樹+bagging = 隨機森林
決策樹+adaboost = 提升樹
決策樹+Gradient boost = GBDT

其實在，計算機視覺領域，關於通過adaboost+haar做人臉檢測的方法也是相當值得學習的，在以後的article中，會專門開一個專欄來講解這些經典的問題和方法。

（好像還沒有開始講什麼是決策樹，什麼是隨機森林，什麼是GBDT，那就在下一講，我們來好好講講這些概念）