這是用自己理解的方式整理了林軒田老師 ML 課程. 其中 Decision tree and Random Forest 沒紀錄.
以前第一次接觸到 Adaboost 的時候就被它深深著迷了, 當時 face detection 可商用算法無不採用經典的 Viola and Jones adaboost method. 在現在 DNN 成主流的時候, 雖然 adaboost 光環已退去, 但在 data mining, data science 領域 boosting 方法仍是最成功的算法之一. 基本上在 Kaggle 比賽可以看到主要兩大方法, 舉凡聲音影像文字等等的辨識就是 DNN, 其他凡是 data mining 相關的就屬 boosting (xgboost).
有趣的是, 近年也有研究人員用 ensemble 的角度看待 DNN, 從這角度就能理解為何一路從 highway network –> skip layer resent –> resnext 的架構演變, 以及為何效果這麼好. 可以參考 “深度神经网络中深度究竟带来了什么？” 很精彩的解釋, 或是 MSR 2017 這篇論文 Deep Convolutional Neural Networks with Merge-and-Run Mappings
筆記內容如下:
- Bagging (or bootstrap)
- Adaboost 演算法
2.1 Adaboost large margin 解釋
2.2 Adaboost exponential error 解釋 - Additive Model (a framework)
- Gradient Boosting
- Adaboost as an additive model
- Gradient Boost Decision Tree (GBDT)
- 待研究: XGBoost (Kaggle 比賽神器)
Bagging (or bootstrap)
還記得我們在 Why-Aggregation-Work 這篇提到, 當我們有很多 weak learner ${g_t}$ 時, 要得到一個 strong learner $G$ 最簡單的方法就是投票(或平均). 所以一個關鍵問題是要怎麼產生很多的 $g_t$?
Bagging (or bootstrap) 提供了一個簡單的方法: 假設 dataset $D$ 有 $N$ 筆資料, bagging 就是從 $D$ 中重複採樣出 $N’$ 筆, 我們稱 $D’$, 然後 $g_t$ 就可以用 $D’$ 訓練出來.
既然現在可以方便地產生很多 ${g_t}$, 然後就 $G$ 就採用平均方式, ensemble algorithm 就結束了?! 當然沒有, 別忘了有一個很關鍵的特性是, 當 ${g_t}$ 意見愈分歧時產生出來的 $G$ 效果愈好!
那我們就問了, bagging 不就採樣嗎? 我怎麼知道這次採樣出來的 $D’$ 所訓練出來的 $g_t$ 會跟之前一次的意見分歧?
我們就是能知道! (神奇吧) 要了解為什麼, 我們必須先將 bagging 擴展一下, 想成是對 weighted $D$ 採樣, 其中每一筆資料 $x_n$ 的 weight $u_n$ 代表抽中的機率. 如果 bagging 是對 weighted $D$ 採樣的話, 在第 t 輪的 $g_t$ 得到方式如下:
其中 $\mathbb{I}[…]$ 表示 indicator function, 條件為 true 則 return 1, otherwise return 0.
想法就是我們要設計一組新的權重, 讓新的權重對於 $g_t$ 來說相當於亂猜, 這樣用新權重找出的 $g_t+1$ 就會跟之前的意見分歧了. 具體來說, 新權重要有以下的效果:
物理意義就是對於 $g_t$ 來說
$$\begin{align}
\mbox{for weak learner }g_t\mbox{: }\left(\mbox{total }u_n^{(t+1)}\mbox{ of incorrect}\right)=
\left(\mbox{total }u_n^{(t+1)}\mbox{ of correct}\right)
\end{align}$$
所以新的權重調整方式其實很簡單, 用一個例子解釋. 假如 $u_n^t$ incorrect 合是 300, $u_n^t$ correct 合是 500. 我們只要把之前的 $u_n^t$ incorrect部分都乘 500, 而 correct 部分乘 300就可以了.
或者我們這麼寫, 定義 $\epsilon_t=300/(300+500)$, 則
$$\begin{align}
u_n^{(t+1)}=u_n^{(t)}(1-\epsilon_t) \mbox{, if } y_n\neq g_t(x_n)\\
u_n^{(t+1)}=u_n^{(t)}\epsilon_t \mbox{, if } y_n = g_t(x_n)\\
\end{align}$$
或通常也可以這麼計算
所以目前為止, 我們可以用 bagging 的方式 (對 weighted data) 產生出看似相當意見不同的 $g_t$, 那最後的 $G$ 用平均就可以了嗎? 可能不大好, 因為 $g_t$ 是針對某一種權重的 dataset 好, 不代表對原來沒有權重 (或uniform權重) 的 dataset 是好的.
既然直接平均可能不夠好, 不如就用 linear combination 方式組合 $g_t$ 吧, 不過組合的 coefficients 是需要巧思設計的. 而 Adaboost 就設計出了一種組合方式, 能證明這種組合方式會使得 training error 收斂至0. (另一種用 additive model 的解釋方式為這樣的 coefficient 設計方式相當於用 steepest descent 並選擇最佳的步長). 這些會在文章下面說明.
Adaboost 演算法
Adaboost large margin 解釋
一般來說, model 愈複雜愈容易 overfit, 不過很特別的是 adaboost 隨著 iteration 結合愈多 weak learners 反而不會有容易 overfit 的現象. 其中一種解釋方式是 adaboost 具有類似 SVM 的 large margin 效果.
我們首先分析一下第 t+1 次 iteration, dataset 的 weights
$$\begin{align}
u_n^{(t+1)}=u_n^{(t)}\diamond_t^{-y_n g_t(x_n)}\\
=u_n^{(t)}\exp (-y_n \alpha_t g_t(x_n))
\end{align}$$
我們這裡使用 binary classification 來說明, 其中 $y_n,g_t(x_n)\in${-1,+1}, 式 (6) 可以從上一段 “Adaboost 演算法” 的圖中步驟2的 update 式子看出. 而式 (7) 從 $\diamond_t$ 定義得到.
上式可以一路展開到開頭 (iteration 1), 如下:
有發現嗎? 橘色的部分其實就是我們的 $G$
$$\begin{align} G(x_n)=sign\left( \color{orange}{ \sum_{t=1}^T \alpha_t g_t(x_n) } \right) \end{align}$$而如果將 $\alpha_t$ 看成是 t-th coefficient, $g_t(x_n)$ 看成是 t-th 維度的特徵, 橘色部分就等同於 unnormalized margin. (除以 coefficients 的 norm 就是 margin了)
Adaboost 可以證明 (with exponential decay)
這意味著什麼? 說明了隨著 iteration 增加, 橘色的值會愈大, 等同於我們的 $G$ 對於資料的 margin 會愈大.
證明可參考 李航 統計學習方法 p142
Adaboost exponential error 解釋
其實單看式 (9) 我們完全可以把它當成 error function. 重寫一下:
$$\begin{align} u_n^{(T+1)}=\frac{1}{N}\exp\left(-y_n \color{orange}{ \sum_{t=1}^T \alpha_t g_t(x_n) } \right)\\ =\frac{1}{N}\exp\left(-y_n \color{orange}{ f_T(x_n) } \right) \end{align}$$怎麼說呢? 其實橘色部分我們可想成是該筆資料 $x_n$ 的分數, 記做 $f_T(x_n)$, 當 $y_n=+1$ 時, 如果 $f_T(x_n)$ 很小則會導致 $\exp(-y_n f_T(x_n))$ 會很大, 同理當 $y_n=-1$ 時, 如果 $f_T(x_n)$ 很大則會導致 $\exp(-y_n f_T(x_n))$ 會很大. 因此 $\exp(-y_n f_T(x_n))$ 可以當成 error function 來 minimize.
而它跟 0-1 error function 有如下的關係:
而我們知道 Adaboost 滿足式 (11), 等同於說明 exponential error 收斂. 由於 upper bound 的關係也導致了 0-1 error 收斂.
聽到有個方法可以使 error 迅速收斂到 0, 這不是太完美了嗎? 別高興得太早, 因為這個 error 是 inside error. 有學過 ML 的童鞋就應該會警覺到當 inside error 為 0, 意味著非常容易 overfit! 好在實作上 Adaboost 卻不是那麼容易 (原因在上一段 large margin 的解釋), 這就帶來了一個好處, 就是在使用 Adaboost 的時候, 我們可以很放心的直接訓練多次 iteration, 甚至到 inside error 接近 0, 最後的 outside test 也不會壞掉. 這特性倒是挺方便的.
AdaBoost 小結論
我們希望藉由融合很多 {$g_t$} 來得到強大的 $G$, 同時我們知道 {$g_t$} 之間意見愈分歧愈好.
每一個 $g_t$ 都是根據當前 weighted dataset 得到的. 利用調整資料權重的方式來讓上一次的 $g_t$ 表現很差, 這樣新權重的 dataset 訓練出來的 $g$ 就會跟之前的看法分歧.
Adaboost 再利用一種頗為巧思的線性組合方式來融合 {$g_t$}, 最終得到強大的 $G$
Additive Model (a framework)
這是非常重要的一個框架, Adaboost 在這框架下可視為它的一個 special case, 同時著名的 Gradient Boost Decision Tree (GBDT) 也是基於此框架下的演算法. 通常 supervised learning 就是在學習 input and output 之間的 mapping function $f$, 簡單講, 直接學一個好的 $f$ 可能很困難, 所以不如使用 greedy 方式, 就是從目前的 $f_t$ 出發, 考慮怎麼修正現在的 $f_t$ 來使得 error 更小. 嚴謹一點數學描述如下:
考慮 additive model
$$\begin{align}
f_T(x)=\sum_{t=1}^T \alpha_t g_t(x)
\end{align}$$
其中, $g_t(x)$ 為第 t 次學到的 base learner, $\alpha_t$ 為它的權重.
定義 $L(y,f(x))$ 為 loss (or error) function, 所以我們要找的修正的 mapping function 如下:
用上式的方法找到要修正的 mapping function 因此 mapping function 更新如下:
$$\begin{align} f_T(x)=f_{T-1}(x)+\alpha_T g_T(x) \end{align}$$我們可以想成是在函數空間做 gradient descent. 每一次就是找一個 descent direction, 在這裡就是 $h$, 然後設定合適的步長 $\eta$, 這麼想就是最佳化的 gradient descent 了.
Gradient Boosting
Additive model framework 很簡單, 難的地方在那個 $\arg\min$ 式 (15). 而 Gradient Boosting 可以說是一種明確實現 Additive model 的方式, 我們可以將 $\eta$ 和 $h$ 分開找, 例如先找 $h$:
$$\begin{align} &\min_h\sum_{n=1}^N L(y_n,f_{T-1}(x_n)+\eta h(x_n))\\ &\mbox{by Taylor: }\simeq \min_h\sum_{n=1}^N\left(L(y_n,f_{T-1}(x_n))+\eta h(x_n) \color{red}{ \left(\frac{\partial L(y_n,f)}{\partial f}\right) _{f=f_{T-1}} } \right)\\ \end{align}$$Taylor 展開式那邊可以這麼想
$$\begin{align} &\mbox{將 }L(y_n, \color{green}{ f_{T-1}(x_n) }+ \color{blue}{ \eta h(x_n) } )\mbox{ 看作 }\hat{L}( \color{green}{ \tilde{x} }+ \color{blue}{ \delta } )\\ &\mbox{因此 by Taylor } \simeq \hat{L}( \color{green}{\tilde{x}} )+ \color{blue}{\delta} \left(\frac{\partial \hat{L}(x) }{\partial x}\right)_{x= \color{green}{\tilde{x}} } \end{align}$$上面紅色部分在計算的時候是一個固定值, 我們先令為
$$\begin{align} \left(\frac{\partial L(y_n,f)}{\partial f}\right) _{f=f_{T-1}}= \color{red}{-\tilde{y}_n} \end{align}$$所以 (18) 變成
$$\begin{align} &= \min_h\sum_{n=1}^N\left(L(y_n,f_{T-1}(x_n)) \color{red}{-} \eta h(x_n) \color{red}{ \tilde{y_n} } \right)\\ &\mbox{去掉與}h\mbox{無關項並補上}2=\min_h \sum_{n=1}^N \left(-2h(x_n)\tilde{y}_n\right) \end{align}$$很明顯, 如果 $h$ 無限制, 則解為 $h=\infty$, 這顯然不是我們要的, 在 optimization 的時候, 我們需要的只是 gradient 的方向, 而不是大小, 大小可以由 stepsize 控制. 不過如果加上 $norm(h)=1$ 條件並使用 Lagrange Multipliers 會較複雜, 實作上我們就直接將 $norm(h)$ 當作一個 penality 加在 loss 裡就可以. 因此 (23) 修改如下:
$$\begin{align} =\min_h \sum_{n=1}^N \left(-2h(x_n)\tilde{y}_n+(h(x_n))^2\right) \end{align}$$湊齊平方項會變成 (之前加的2是為了這裡湊平方項)
$$\begin{align} =\min_h \sum_{n=1}^N \left( \mbox{const}+\left(h(x_n)-\tilde{y}_n\right)^2 \right) \end{align}$$OK! 到這裡我們發現了一個重要的解釋, $h$ 的找法就是對 $\tilde{y}_n$ 做 sqaure error regression!
得到 $g_T=h$ 後, 那麼步長 $\eta$ 呢?
$$\begin{align} \alpha_T=\min_{\eta}\sum_{n=1}^N L(y_n,f_{T-1}(x_n)+\eta g_T(x_n))\\ \end{align}$$這個解通常很好算, 令 $L$ 微分為 0 即可, 是個單變量求解.
到目前為止, 我們可以將整個 Gradient Boost 演算法列出來了:
$$\begin{align} &\mbox{1. Init }g_0(x)\\ &\mbox{2. For }t=1~T\mbox{ do:}\\ &\mbox{3. }\tilde{y}_n=-\left(\frac{\partial L(y_n,f)}{\partial f}\right)_{f=f_{t-1}}\mbox{, n=1~N}\\ &\mbox{4. }g_t=\arg\min_h\left(h(x_n)-\tilde{y}_n\right)^2\\ &\mbox{5. }\alpha_T=\arg\min_{\eta}\sum_{n=1}^N L\left(y_n,f_{t-1}(x_n)+\eta g_t(x_n)\right)\\ &\mbox{6. }f_t(x)=f_{t-1}(x)+\alpha_t g_t(x) \end{align}$$Adaboost as an additive model
將 Adaboost 套用 additive model framework 時會是什麼情況?
首先 loss 是 exponential loss, 然後一樣用 binary classification 來說明, 其中 $y_n,g_t(x_n)\in${-1,+1}, 則我們要找的 $h$ 如下 (對照 (12) and (13) 並使用 additive model (14) 的架構):
(33) 到 (34) 使用 $u_n^{(T)}$ 的定義, 參考 (13). 而最後的 (36) 表明了實際上就是選擇讓 training data 在新的 weighted dataset 下表現最好的那個 $h$, 具體原因看下圖.
這不正是 Adaboost 選擇 weak learner 的方式嗎?
最後別忘了 stepsize, 將 (34) 換一下變數, $h$ 變 $\eta$:
$$\begin{align} \alpha_T=\arg\min_{\eta}\sum_{n=1}^N u_n^{(T)}\exp(-y_n \eta g_t(x_n))\\ \end{align}$$兩種情況:
$$\begin{align}
\mbox{1. }y_n=g_t(x_n)\mbox{: }u_n^{(T)}\exp(-\eta)\\
\mbox{2. }y_n\neq g_t(x_n)\mbox{: }u_n^{(T)}\exp(+\eta)\\
\end{align}$$
所以
$$\begin{align}
\alpha_T=\arg\min_{\eta}\left(\sum_{n=1}^N u_n^{(T)}\right) \cdot \left(\left(1-\epsilon_T\right)\exp\left(-\eta\right)+\epsilon_T\exp\left(+\eta\right)\right)
\end{align}$$
令微分為 0, 我們可以很容易得到
$$\begin{align} \alpha_T = \ln\sqrt{\frac{1-\epsilon_T}{\epsilon_T}} \end{align}$$這正好也就是 adaboost 所計算的方式!
總結一下, Adaboost 在 additive model 框架下, 相當於使用 steepest gradient descent 方式在函數空間找 weaker learner, 並且將 stepsize 指定為最佳步長.
Gradient Boost Decision Tree (GBDT)
Gradient Boost 很棒的一個特性是 error function 沒限定, 例如使用 exponential error 就是 adaboost, 而另一個常用的是 sqaure error.
當使用 square error 時, $\tilde{y}_n$ 就會變成 $(y_n-x_n)$ 也就是 residual. 對照 GradientBoost (27)~(32) 來看, 我們發現整個演算法變成對每一次 iteration 的 residual 做 regression.
另外在實務上 base learner 常常使用 Decision Tree (因為 decision tree 有很多好處: 可解釋性、訓練快、可處理缺失資料…), 不過這就要特別注意了, 因為如果長成 fully growed tree 就直接把 residual regression 到 0 了. 因此, decision tree 需要 regularization, 而實務上採用 pruned tree. 整個 GBDT 節自課程 slide 如下:
XGBoost
這篇文章 XGBoost的原理 介紹得很好
幾個重點整理, XGBoost 基本上也是 gradient boost 的一種, 比較特別的是泰勒展展開 (18) 使用到二階導函數:
$$\begin{align} &\min_h\sum_{n=1}^N L(y_n,f_{T-1}(x_n)+\eta h(x_n))\\ &\simeq \min_h\sum_{n=1}^N\left(L(y_n,f_{T-1}(x_n))+\eta h(x_n) \left(\frac{\partial L(y_n,f)}{\partial f}\right) _{f=f_{T-1}}\\ \color{red} { +\eta^2h^2(x_n)\left(\frac{\partial^2 L(y_n,f)}{\partial^2 f}\right)_{f=f_{T-1}} } \right)\\ &=\min_h\sum_{n=1}^N \left( L(y_n,f_{T-1}(x_n)) + \eta h(x_n)\mbox{Gradient}_n + \frac{\eta^2h^2(x_n)}{2}\mbox{Hessian}_n \right)\\ &=\min_h\sum_{n=1}^N \left( \eta h(x_n)\mbox{Gradient}_n + \frac{\eta^2h^2(x_n)}{2}\mbox{Hessian}_n \right)\\ \end{align}$$最後再加上一個 regularization term
$$\begin{align} &=\min_h\sum_{n=1}^N \left( \eta h(x_n)\mbox{Gradient}_n + \frac{\eta^2h^2(x_n)}{2}\mbox{Hessian}_n \right) + \Omega(h)\\ \end{align}$$針對 (46) 要找到最好的 $h$, 如果使用 Decision Tree, $\Omega(h)$ 可以使用樹的深度、葉子數量、葉子值的大小等等計算. 但關鍵是如何有效率地找到很好的 $h$, 而在 Decision Tree 此問題相當於如何有效率的對 Tree 做 splitting. XGBoost 文章使用非常有效率的近似方法, 並且該方法可以很好的並行加速.
對於 xgboost 就只粗淺的了解到這了, 也還沒有真的有什麼調整的經驗, 就把這個課題放在 todo list 吧.
Reference
- 林軒田老師 ML 課程
- 李航 統計學習方法
- Why-Aggregation-Work
- 以前 Adaboost and face detection paper survey
- 其中Rapid object detection using a boosted cascade of simple features, 2001, cited 17597
- 深度神经网络中深度究竟带来了什么？
- Deep Convolutional Neural Networks with Merge-and-Run Mappings
- XGBoost的原理
- XGBoost: A Scalable Tree Boosting System