Ensemble Learning 集成學習(中)

最近工作上有碰到「簡易版 feature用 gradient boosting」的成效 train的比「詳細版 feature用深度學習」的成效還好的情況，於是就把李宏毅老師2015年講 ensemble的課程拿出來看，想好好理解一下集成學習在做什麼，順邊把筆記記錄起來。

因為這次影片的內容較多，所以我把ensemble分成上中下篇來紀錄，這篇要介紹的是AdaBoosting的概念。

此篇筆記來自此課程：https://www.youtube.com/watch?v=tH9FH1DH5n0

Ensemble: Boosting

核心概念：Improve Weak Classifier
當我們有一些模型都沒辦法fit training data時，會使用的ensemble方式。

可以保證

• 如果有一個binary classifier在training data的error rate是低於50%。
• 那麼用boosting這種方式，就能夠在training data上得到0%的error rate。

Framework

• 首先訓練第一個分類器（weak learner）：f1(x)
• 再訓練另一個分類器：f2(x)，而且這個f2(x)是要能夠彌補f1(x)的不足，否則幫助不大。
• 再訓練另一個分類器：f3(x)，跟f2(x)是互補的，並以此類推。
• 把所有分類器串起來
• 重點是這些分類器是有順序性的，必須先找到f1(x)，才有f2(x)..。（bagging的做法是沒有順序性的）

Idea of AdaBoosting

• 要讓f2(x) 去training 那些讓f1(x)表現不好的dataset
• 若f1(x)的error rate小於50%，那麼我們就要為training data重新設定權重，使得f1(x)的error rate等於50%。(re-weighting training data)
• 假設f1(x)在四次分類中，僅答錯一次，則它的error rate就是25%，若要讓它的error rate提升到50%，那麼我們就必須提高答錯那筆資料的權重 (乘以d)，也調低答對資料的權重 (除以d)，如此error rate就會上升，並且再用這樣的權重去訓練f2(x)，那麼f2(x)就會特別注意這組f1(x)答錯的data，使得f2(x)的error rate小於50%，因此達到f1(x)和f2(x)互補的作用。

Algorithm for AdaBoost

• 這邊老師在解釋公式的推導，重點在於每個iter的weight是如何算出來的，我並沒有看懂公式，但總之最終的weight(u)，是從d這個推導而來的，而d又是從error rate(ε)得出來。
• d的公式如下圖

• 有n筆training data，n筆label (y)，n個weight (u)
• y = 1, 0、u1 = 1 (相同的weights)
• t = iter，每一次的訓練都會更新一次training data的u，而每一筆資料都有自己的u，u要怎麼更新可以用最下面那一列來表示。

How to aggregate

• 我們可以把每個function加起來，最後得出的是正的就是1，負的就是0，但其實有更好的做法。
• 在每個function前面加上權重 α，權重求法就是d的公式，若error rate (ε)越低，則α越高，反之亦然，可以參考下圖右下角。

Top Example

這邊直接用一個假想的範例來跑一次AdaBoost，我覺得清楚很多。

t=1

• 當t=1時, 先用decision stump找到一個weak classifier。
• decision stump：假設data是二維的，直接切一刀，藍色是正，紅色是負的，會讓function夠weak
• 如下圖，分類錯誤的是紅色圈起來的三個點，經過加權後（將ε1, d1, α1帶入上面的公式），就可以得出右邊的結果。

• t=2
• 用新的weight透過decision stump再找一個weak classifier。
• 同樣會切一刀，但會切在比較右邊一點的位置，因為這個weak classifier會想辦法讓第一個classifier判斷錯誤的點回答正確。
• 錯誤的3筆data要乘上d2，剩下的data除上d2。

• t=3
• 每個classifier的weight就是alpha值。
• 同樣的步驟重複一次。(這邊可以直接參考圖片)

Aggregate

• 最終的classifier：sign(Σ αt*ft(x))
• 上面的式子等於將weight乘以function，得出的結果再取正負號。
• 如下圖所示，這3個weak classifier將二維的平面切分成6塊，且分類如下圖所標示。
• 雖然3個weak classifier的error rate都不是0，但final classifier卻得到error rate等於0的效果。

理論上來證明AdaBoost

• 要用理論來證明，iteration跑得越多，final classifier在training data的error rate就會越來越小。
• 大量數學公式，這邊我直接略過。

神奇的事情

• 持續地增加weak classifier，在training data的error rate已經維持在0，但在testing data的error rate仍然持續下降。
• 左下角g(x)代表summation權重乘以classifier，而margin則代表label乘以g(x)，因此margin大於1時，則代表判斷正確，然而0.001大於0，0.99也大於0，但代表的信心程度不同。
• 右下圖的綠色數字代表的是weak classifier的數量，數量等於5的時候，error rate就已經等於0，因為margin都是正值。但當classifier數量越多，data接近1的數量也會變多，代表model判斷data不但正確，而且具有較高的信心值。

Experiment: Function of Miku

• 最後用前面bagging做過的初音實驗，來觀察AdaBoost的成效。
• Decision Tree (depth=5) 的效果不是太好，因此這邊用AdaBoost增加iteration去觀察效果，可以看到iteration=100，就可以很好的fit training data。

小結

Boosting需要先有一些沒辦法fit training data的classifier (weak classifier)，然後為了解決fitting不了的問題，AdaBoost是透過重新更新錯分資料的權重，來互補這些model，讓集成的model可以fit training data，而下一篇會介紹Gradient Boosting，也是Boosting的方式但讓weak classifier進步的方式不太一樣，這篇就先告一段落啦。

如果喜歡我的筆記，歡迎給個clap或留下留言！