# 李宏毅_ML_Lecture_22
###### tags: `Hung-yi Lee` `NTU` `Machine Learning`
[課程撥放清單](https://www.youtube.com/channel/UC2ggjtuuWvxrHHHiaDH1dlQ/playlists)
ML Lecture 22: Ensemble
[課程連結](https://www.youtube.com/watch?v=tH9FH1DH5n0&list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49&index=32)
### Framework of Ensemble

Ensemble是一種團隊合作的概念，也許你手上有一堆的classifier，而每一個classifier有不同的屬性，就好像打game一樣，每個人角色不同一起去圍歐boss。

過去曾經說過，一個較小的模型可能會有較高的Bias，較低的Variance，而較大的模型會有較高的Variance，較低的Bias，如果我們可以將不同的模型組合起來，也許它的Variance就不會那麼大，將不同模型的輸出做平均來得到一個新的模型$\hat{f}$，它所得的答案就可能跟真實是接近的。
### Bagging

作法上如下：
1. 假設手上擁有N筆資料
2. 對資料集做採樣，每次取N'筆組成新的資料集
* 採樣之後會再放回，因此如果N'設置為N所得結果不見得會與原資料集相同，因為還有放回_{(replacement)}
3. 產生多個資料集，每個資料集內皆有N'筆資料
4. 訓練多個資料集，產生多個function

註：課程說明為產生四個資料集，即產生四個function
### Bagging

測試的時候將一筆測試資料丟到四個function中，將所得結果做Average(regression)/Voting(classifier)，這時候得到的結果通常會比只有一個function的時候Performance較佳，即Variance較小，因此所得結果較為robust。

問：什麼情況下我們需要做Bagging?
答：當模型較為複雜，擔心結果過於overfitting的時候才會做Bagging，執行Bagging是為了減低Variance

問：什麼模型容易Overfitting?
答：如Decision Tree，只要樹夠深就可以100%準
### Decision Tree

假設每一個object都有兩個feature($x_1$,$x_2$)，Decision Tree(決策樹)就是根據訓練資料來建置一棵樹。
1. 首先條件$x_1$<0.5就往左，反之往右
* 在$x_1$=0.5上劃一直線區隔空間
2. $x_2$<0.5就類別1(藍色)，反之類別2(橘色)
* 在$x_2$=0.3上劃一直線垂直第一條線，區隔空間
3. $x_2$<0.7就類別2(橘色)，反之類別1(藍色)
* 在$x_2$=0.7上劃一直線垂直第一條線，區隔空間

這只是一個簡單的說明範例，實務上可以設計的更複雜，而且需要注意的問題很多。i.e. 每個節點多少分支、以什麼Criterion(標準)做分支、什麼時候停止分支...
### Experiment: Function of Miku

假設現在有一個資料分佈，狀似初音，初音內為Class-1，初音外為Class-0。

### Experiment: Function of Miku

可以發現到，當決策樹深度到達20的時候已經可以完美的區隔兩個類別，這並不令人意外，因為只要你想要，決策樹是永遠可以正確率100%。
### Random Forest

因為決策樹太容易overfitting，因此有了Random Forest(決策森林)，它是決策樹Bagging的一種實現。

但如果使用稍早所說的採樣方法，那每所得的每一棵樹幾乎沒有差別，Random Forest的經典在於它每一次產生的tree都隨機的決定那些特徵或那些問題是不能用的，以此讓產生的tree都不相同，最後再做集合，得到最終的Random Forest。
### Experiment: Function of Miku

我們發現到，當深度為5的時候得到的結果並不會差異過大，這是因為執行Bagging並不會使資料更擬合，我們得到的是將多棵樹的結果平均，較為平滑。
### Boosting

Boosting與Bagging的差異在於，Bagging是應用於很強的Model上，而Boosting是應用於很弱的Model上。

Boosting's Guarantee_(保證):
1. 如果你擁有一個機器學習演算法，並且在訓練資料集上有著50%以上的錯誤率
2. Boosting可以保證將這些錯誤率略高於50%的模型組合起來之後給你一個錯誤率0%

作法如下：
1. 尋找第一個classifier $f_1(x)$
* 很弱沒有關係
2. 找classifier $f_2(x)$來協助$f_1(x)$
* 兩者之間是互補的關係，因此不能很像
3. 找出跟$f_1(x)$最互補的$f_2(x)$
4. 相同方式找出$f_3(x)$....

找到一堆classifier之後，將它們集合起來，就可以得到很低的error_rate，即使每一個classifier都很弱也可以辦的到。

也需要注意到，與Bagging不同的第二個點在於，Boosting是有順序的執行，而Bagging可以無序。因此Boosting要先擁有$f_1(x)$，再有$f_2(x)$...，但Bagging如Random Forest可以亂數擁有。
### How to obtain different classifiers?

類似於Bagging取得不同資料集的方式，在Boosting也可以利用Re-sampling_{(重新抽樣)}的方式來製造不同的訓練資料集，以此得到不同的classifier。

或者可以利用權重的變更來產生不同的資料集，如上圖所示，原始資料集權重皆為1，透過調整$u$的方式來產生不同的資料集，在考慮Loss Function的時候就單純的在每筆資料集乘上它的權重即可。
### Idea of Adaboost

Boosting的方式有很多，最為經典的即是『Adaboost』。

直觀說明如下：
1. 訓練一個classifier $f_1$
* $\epsilon_1$\_error-rate，加總計算每一筆訓練資料的結果是否正確，正確為0，錯誤為1，並且乘上權重$u^n$_{(每一筆資料各自權重)}，再做Normalization_{(除上$Z_1$)}
* $Z_1$即為所有資料權重加總
* $\epsilon_1$一定小於0.5
3. re-weight一組新的訓練資料集讓$f_1$效能爛掉
* 將權重調整變更為$u_2$，讓error-rate變為0.5
5. 利用re-weight的訓練資料集訓練$f_2$
* 利用$u_2$產生的新資料集訓練$f_2$

### Re-Weighting Training Data

舉例來說，目前有四筆訓練資料集，各自權重為$u^1...u^4$，並且預設值皆為1。
1. 訓練得到$f_1$，得到error-rate為0.25($\epsilon_1$)
2. 調整權重，讓$f_1$的error-rate變為0.5
* 答對的權重減小，答錯的權重加大
3. 利用調整權重的資料訓練$f_2$，得到$\epsilon_2$小於0.5

後續會有更完整的案例說明。
### Re-Weighting Training Data

Re-Weight的作法如下：
1. 當$x^n$分類錯誤即$u^n_1$乘上$d_1$得$u^n_2$
* 加大
3. 當$x^n$分類正確即$u^n_1$除$d_1$得$u^n_2$
* 縮小

而$d_1$的功能就是讓$u_1$變為$u_2$之後使得$f_1$的error rate變為0.5
### Re-Weighting Training Data

分子的部份是總計分類錯誤的資料_{(紅箭頭所指之處)}，$u_2$是由$d_1u_1$所得，因此可以寫成$\sum u_1^nd_1$。

分母的部份是總計$u_2$，它包含了正確與錯誤的資料，因此可得到$\sum u_2=\sum u_1d_1 + \sum u_1/d_1$

將式子帶入並翻轉，得到最下面的數學式
### Re-Weighting Training Data

數學式來看，分子前項與分母相同，因此可得分子後項除分母會得到1，再將分母移至等號右邊.....最後我們得到一個結論，$d_1=\sqrt{(1-\epsilon_1)/\epsilon_1}$

再拿這個$d_1$來產生新的資料集就可以讓$f_1$的error rate變更為0.5，要注意到，**$d_1$一定大於1**，這是因為$\epsilon_1$小於0.5，根號內的項目分子會大於分母所造成。
### Algorithm for AdaBoost

AdaBoost說明如下：
1. 我們手上有一個資料集共計N筆，預設權重為1，即$u_1^n=1$，分類正確為1，錯誤為-1
2. 執行T次的迭代，每次的迭代都得到一個$f_t$，集合起來就是一個超強的分類器
* 每次的迭代t都有自己的權重$u^n_t$
* 利用$u_t^n$計算第t次迭代的$\epsilon_t$
* Re-Weight
* 分類錯誤：$u^n_{t+1}=u^n_t*d_t$
* 分類正確：$u^n_{t+1}=u^n_t/d_t$
* $d_t=\sqrt{(1-\epsilon_t)/\epsilon_t}$

也可以將$d_t$取$ln$，即$\alpha_t=ln\sqrt{(1-\epsilon_t)/\epsilon_t}$，計算數學式也會連動變更，這麼做的好處是可以讓表達式更簡便，以一個式子表示即可，如下：
$u_{t+1}^n\leftarrow u_t^n\times exp(-\hat{y}^nf_t(x^n)\alpha_t)$
當分類正確，得到正1，正負得負，就進入分類正確的數學式，反正分類錯誤得到負1，負負得正，就進入分類錯誤的數學式。
### Algorithm for AdaBoost

現在我們的手上有了一把的分類器，是時候來結合它們：
1. Uniform weight
* 將所有的Output加總看得到的是正值或是負值
3. Non-uniform weight
* 上述用法_{(Uniform weight)}雖然可行，但不是最好的，因為每一個分類器有效能有好有壞，因此要利用權重調整。
* 在每一個分類器的Output都乘上一個權重$\alpha_t$，再加總取正負號。
* $\alpha_t$即是先前所提過改變資料權重的數值
* $\alpha_t=ln\sqrt{(1-\epsilon_t)/\epsilon_t}$
* i.e. $\epsilon_t=0.1$帶入計算即得$\alpha_t=1.10$
* 錯誤率較低的分類器會得到較高的權重$\alpha_t$，另一例的$\epsilon_t=0.4$，所得權重僅0.2。
### Toy Example

舉例說明，T = 3，n = 10，weak classifier = decision stump_{(見下附註說明)}
* t=1
* 初始權重皆為1
* 找出$f_1(x)$，並有三筆資料錯誤
* $\epsilon_1=0.3(3/10)$
* $d_1=0.53$
* $\alpha_1=0.42$
* 改變權重_{(正確減小，錯誤加大)}
* 正確：除1.53
* 錯誤：乘1.53

註1：Decision Stump:假設feature分佈於二維平面上，在平面上選擇一個Dimension切一刀，一邊是class-1，一邊是class-2
註2：實作Boosting一定要選擇弱分類器_{(weak classifier)}，因此選擇Decision Stump
註3：$\alpha_t$為每個分類器的權重
### Toy Example

尋找第二個Decision stump
* t=2
* 權重依分類結果調整
* 利用新的權重找出$f_2(x)$，並有三筆資料錯誤
* $\epsilon_2=0.21$
* $d_2=1.94$
* $\alpha_2=0.66$
* 改變權重_{(正確減小，錯誤加大)}
* 正確：除1.94
* 錯誤：乘1.94

### Toy Example

尋找第三個Decision stump
* t=3
* 權重依分類結果調整
* 利用新的權重找出$f_3(x)$，並有三筆資料錯誤
* $\epsilon_3=0.13$
* $d_3=2.59$
* $\alpha_3=0.95$

因為我們預設執行T=3，即3個分類器，因此只到這邊就結束了。

### Toy Example

將每一個Classifier的Output乘上對應的權重$\alpha_t$再取正負號來決定最後的Output結果。

上圖下將決策邊界區隔為六個空間說明：
* 上左：三個分類器皆同意為藍
* 上中：$f_1$覺得是紅，但另兩個權重加總較大，因此為藍
* 上右：$f_3$覺得是藍，但另兩個權重加總較大，因此為紅
* 下左：$f_3$覺得是紅，但另兩個權重加總較大，因此為藍
* 下中：$f_2$覺得是藍，但另兩個權重加總較大，因此為紅
* 下右：三個分類器皆同意為紅

很奇妙的是，三個分類器皆有錯誤，沒有一個是完美的，但是將這三個Decision Stump組合起來之後卻得到一個正確率100%的結果。
### Error Rate of Final Classifier

之前的課程說明了Boosting的精神，接著要證明，證明當分類器愈多(或Adaboost執行的iteration愈多)在訓練資料集上的失誤會愈小。

1. 計算$H(x)$的error rate
* 即加總錯誤筆數(n)除總資料數(N)
2. 以$g(x)$替代數學式
* 代表T個分類器的權重加總
* 同號error為0，異號為1

注意到error rate是存在upper bound，如圖所示，藍線區即為upper bound。

### Training Data Error Rate

我們要證明的是Upper Bound會愈來愈小，在證明之前先計算另一個數值$Z_{T+1}$_{(即第T+1次迭次的加總值)}

我們知道，初始權重$u^n_1$為1，後續再依所得的$\epsilon$來計算第二次、第三次...第T次的權重值，即$u^n_{t+1}=u^n_t\times exp(-\hat{y}^nf_t(x^n)\alpha_t)$，直觀來看就是每一筆資料都會乘上T次的exponential項目所得值。

因此得到如下推導：
1. $Z_{T+1}=\sum_n\prod^T_{t=1}exp(-\hat{y}^nf_t(x^n)\alpha_t)$
2. $=\sum_nexp(-\hat{y}^n\sum^T_{t=1}f_t(x^n)\alpha_t)$
* 將連乘$\prod$放至exponential內，乘項放至指數會是相加
* 其中$\hat{y}$是實際的lable，與iteration無關
* $\sum^T_{t=1}f_t(x^n)\alpha_t)$即是$g(x)$，
3. $=\sum_nexp(-\hat{y}^ng(x))$
* 此項目即為Upper Bound

上面推導之後我們發現到，Error的Upper Bound就是$\dfrac{1}{N}Z_{T+1}$，這代表著訓練資料集中的權重加總與Error Upper Bound是相關的。

因此，接下來我們只要證明Weight的Summation愈來愈小就可以。_{可以想像的是，當分類正確的時候權重是愈小，因此加總權重值愈小的時候就代表愈見正確}

$Z_t$：加總每一筆訓練資料集的權重值
### Training Data Error Rate

上面看到的是$Z_{t-1}$的計算推導，最終得到的數學式如下：
* $Z_{t-1}\times2\sqrt{\epsilon_t(1-\epsilon_t)}$
* $\epsilon_t$為Error Rate，並且Error Rate一定小於0.5，最大為0.5_{(可見課程最初說明)}
* 根號內所得的最大值就是0.5，即使乘上2還是只有1

從上面的推導可以知道，$Z_t$一定比$Z_{t-1}$還要小，無法想像的話就拿起紙筆簡單賦值計算就可以確認。

因此我們知道，訓練的Error是會愈來愈小，即$Z_t$會愈來愈小，所以Upper Bound就會愈來愈小。
### Adaboost Incredible

上圖可以看到，在訓練資料集上，Adaboost的收斂非常快，大約在T=5的地方Error Rate就收斂到接近0_註1，但是很神奇的是，即使已經接近於0，沒有東西可以再學習的情況下還是可以讓測試資料集的Error Rate再下降。

說明如下：
* $H(x)=sign(\sum^T_{t=1}\alpha_tf_t(x))$
* $\sum^T_{t=1}\alpha_tf_t(x)=g(x)$
* $g(x)\times \hat{y}$定義為Margin
* 我們希望$g(x)\hat{y}$是同號，同號代表正確，並且希望相乘之後數值愈大愈好
* $g(x)$大於0愈多愈好

上圖二可以發現到不同T所擁有的Margin的差異，即使T=5的時候已經讓Error Rate不再下降_{(因為所有$g(x)\times \hat{y}$皆大於0)}，但增加更多weak classifier是可以增加Margin，增加Margin的好處在於可以讓結果更Robust

註1：Adaboost假設Error Rate不會為0，若為0會造成計算$\alpha$錯誤
$H(x)$：所有weak classifier結合的結果
### Large Margin?

上圖是三種演算法Margin差異，剛才的推導我們知道，每一次的迭代都可以讓$Z_t$會愈來愈小，也就是Upper Bound會愈來愈小，即使我們根本沒有對Upper Bound做微分之類的優化。

直觀來看，只要能讓$g(x)\times \hat{y}$到右側，那Error Rate就是0，但Adaboost與SVM、LR一樣，即使在右側，它的Error也不會是0，而是可以繼續往下得到更小的Error，這也是為什麼愈大的T可以得到愈好的Margin的原因。

註：可以將Upper Bound視為Adaboost的Objective Function(目標函數)
### Function of Miku

上圖是利用Adaboost+Decision Tree，並且設定深度為5。

在課程開始的時候也有相同的範例，這種深度根本不可能完成一個初音Function，但讓人驚豔的是，深度為5並且T=10的時候_{(十棵深度為5的Decision Tree)}已經可以擁有初音造型，不同於Random Forest，這十棵樹是互補，在T=100的時候已經是完美擬合出初音的造型。

### Gradient Boosting

1. 每次迭代都找一個$f_t(x)$與$\alpha_t$_(weight)來imporve(提升)$g_{t-1}(x)$
* $g_{t-1}(x)$為過去所有已找出來的funtion做weight sum的結果
3. $g_t(x)=g_{t-1}(x)+\alpha_tf_t(x)$
4. Output：$H(x)=sign(g_T(x))$

問題在於如何找到一個$f_t$讓它來提升$g_{t-1}$，因此我們必需設置一個Objective Function_{(目標函數)}來優化_{(Minimize Cost Function或Maxmize Objective Function)}。

* Cost Function
* $L(g)=\sum_nl(\hat{y}^n,g(x^n))$
* 加總每一筆資料的差異
* 小寫$l$為loss function
* 使用Corss Entropy or Mean Square Error...
* $\sum_nexp(-\hat{y}^ng(x^n))$
### Gradient Boosting

如何找出一個新的$g_t$來優化Cost Function(L)?這就需要利用梯度下降來處理，將$g$對$L$做微分計算出Gradient，再利用這個Gradient去更新$g_{t-1}$來得到$g_t$_(註1)

如何由Boosting的角度來看的話，尋找一個$\alpha_tf_t(x)$加到$g_{t-1}(x)$之後變為$g_t(x)$，而其中的$\alpha_tf_t(x)$就是上面所談的偏微分部份$\eta\dfrac{\partial L(g)}{\partial g}$，只要兩者目標一致，那就一樣可以達到讓$g_t(x)$變小。

註1：雖然$g(x)$是一個function，但其中每一個點的變化都還是會影響著$L$，因此還是可以對function做偏微分。
### Gradient Boosting

我們希望$f_t(x)$的方向與$\sum_nexp(-\hat{y}^ng_t(x^n))(\hat{y}^n)$_{(偏微分項)}愈一致愈好_{(雖然兩者皆為擁有無窮多維的Vector，但如果僅考慮訓練資料集，那就是有限維度)}。

因此我們希望可以找到一個$f_t(x)$來最大化$\sum_nexp(-\hat{y}^ng_{t-1}(x^n))(\hat{y}^n)f_t(x^n)$，值愈大，就代表兩者愈一致，也就是希望$\hat{y}^n$與$f_t(x)$是同號，並且每一筆資料的前面都乘上權重$exp(-\hat{y}^ng_{t-1}(x^n))$

將權重$u_t^n$式子推導之後會發現，它就是Adaboost的獲得權重的方式。
### Gradient Boosting

現在我們發現到，在Gradient Boosting找到的$f_t$，就是Adaboost找到的$f_t$，而$\alpha_t$的作用就跟Learning rate一樣，只是我們要窮舉一切可能的值來試如何讓$g_t(x)$的$L$最小。

這麼做的理由在於，光是找出$f_t$就可能耗盡很大的資源，與NN不同，NN即使你的學習效率過低，只要多幾次的迭代還是可以收斂，
因此在Gradient Boosting的部份會固定住$f_t$然後窮舉一切可能尋找$\alpha_t$來讓$g_t(x)$的$L$掉最多。

實際做法就是找一個$\alpha_t$，它對$L$的偏微分為0_{($\dfrac{\partial L(g)}{\partial \alpha_t}$)}，那就是一個極值。

更巧合的是，找出來$\alpha_t$就是$ln\sqrt{(1-\epsilon_t)/\epsilon_t}$，就是Adaboost裡面的Weight。

很酷的範例：http://arogozhnikov.github.io/2016/07/05/gradient_boosting_playground.html
### Voting

直觀來看，你有多個Model，一筆資料進去之後各自擁有Outout，再結合四個答案來決定一個答案。如果是分類，那就可以用Majority Vote，多個模型最多Output的類別來決定你的最終類別。
### Stacking

但如果多個模型中好壞不一定的時候，以Voting的方式可能會得到不好的結果，這時候可以在多個模型的多出後面再加上一個最終的分類器，將多模型的輸出當做輸入，來做最後的決定。

如果前面已經是很複雜的模型，那最後可能只可以使用Logistic Regression就可以。

要注意到的是，採用這個方式要將原本的訓練資料集再拆成兩份，一份訓練前面多組模型，一份訓練最終的輸出分類器。