[ML][Ensemble] AdaBoost(아다부스트, Adaptive Boosting)

AdaBoost(아다부스트, Adaptive Boosting)

Adaboost는 최초의 Boosting 알고리즘입니다

이전 Decision Tree가 잘못 예측한 데이터에 큰 가중치를 부여해, 다음 Decision Tree가 더 집중할 수 있도록 순차적으로 학습하는 방법입니다

Decision Tree로는 Stump 구조를 사용합니다

(여기서 Stump 구조란 하나의 Split 만을 가진 가장 간단한 형태의 Decition Tree입니다)

 

세부적으로 설명하자면 B개의 Decision Tree 별로 계산된 모델 가중치 ($c_b$)를 합산하여 최종 모델을 생성합니다

---

AdaBoost의 알고리즘 설명 전 AdaBoost의 Loss Function에서 사용되는 지수 손실에 대해서 간략히 설명하겠습니다

※ 지수 손실 

지수 손실은 Boosting 알고리즘에서 주로 사용되는 Loss Function으로, 예측이 실제 라벨과 일치하지 않을 때 큰 손실을 부과합니다

$$L(y,f(x))=e^{-yf(x)}$$

$y_i$	$\hat{f}(x_i)$	Loss ($e^{-y f(x)}$)
1	1	$e^{-1}$
-1	-1	$e^{-1}$
1	-1	$e$
-1	1	$e$

예측이 틀린 샘플에 대해($y_i \neq \hat{f}(x_i)$)에 대해 더 큰 Loss(지수함수이기 때문에)를 부여하게 됩니다

---

알고리즘

$${\widehat{f_b}}^{\ast }(x_i)=c_1\widehat{f_1}(x_i)+c_2\widehat{f_2}(x_i)+\cdots +c_b\widehat{f_b}(x_i)={\hat{f}}_{b-1}(x_i)+c_b\widehat{f_b}(x_i)$$

위의 식을 보면 최종 모델은 Recursive하게 도출됨을 알 수 있습니다(이전 모델의 결과 + 현재 모델의 결과)

 

Loss Function은 지수 손실의 합으로 정의합니다 ($w_i^1 = 1, \; w_i^b = e^{-y_i \hat{f}_{b-1}(x_i)}$)

 

$w_b$ : Sample 가중치, 잘못 분류된 샘플의 가중치는 증가하고, 올바르게 분류된 샘플의 가중치는 감소

$c_b$ : Weak Classifier 가중치, Error가 낮을수록 해당 모델의 가중치가 증가

$w_i^b = e^{-y_i \hat{f}_{b-1}(x_i)}$ : 이전 Step에서 $x_i$의 예측을 잘못 했다면, 현재 Step에서 $x_i$의 가중치 증가

 

Loss Function은 아래와 같습니다

$$\begin{gathered} \begin{array}{rl}L& =\sum _{i=1}^N{e}^{-y_i{\widehat{f_b}}^{\ast }(x_i)}=\sum _{i=1}^N{e}^{-y_i({\hat{f}}_{b-1}(x_i)+c_b\widehat{f_b}(x_i))}=\sum _{i=1}^N{e}^{-y_i{\hat{f}}_{b-1}(x_i)-y_i{c}_b\widehat{f_b}(x_i)}\\ & =\sum _{i=1}^N{w}_i^b{e}^{-y_i{c}_b\widehat{f_b}(x_i)}\\ & =\sum _{y_i=\widehat{f_b}(x_i) \\ (=1)}{w}_i^b{e}^{-c_b\cdot 1}+\sum _{y_i\ne \widehat{f_b}(x_i) \\ (=-1)}{w}_i^b{e}^{-c_b\cdot -1}=\sum _{y_i=\widehat{f_b}(x_i)}{w}_i^b{e}^{-c_b}+\sum _{y_i\ne \widehat{f_b}(x_i)}{w}_i^b{e}^{c_b}\\ & =\sum _{i=1}^N{w}_i^b{e}^{-c_b}+\sum _{y_i\ne \widehat{f_b}(x_i)}{w}_i^b(e^{c_b}-e^{-c_b})\end{array} \end{gathered}$$

---

이제 Loss Function을 최소화하여 Optimization을 진행해야합니다

 

$$L=\sum _{y_i=\widehat{f_b}(x_i)}{w}_i^b{e}^{-c_b}+\sum _{y_i\ne \widehat{f_b}(x_i)}{w}_i^b{e}^{c_b}=\sum _{i=1}^N{w}_i^b{e}^{-c_b}+\sum _{y_i\ne \widehat{f_b}(x_i)}{w}_i^b(e^{c_b}-e^{-c_b})$$
$\sum \limits_{i=1}^{N} w_i^b e^{-c_b}$ : 전체 데이터 셋에 의해 이전 모델의 가중치를 계산(특정 예측 결과에 의존 x)
$\sum_{ y_i \neq \hat{f_b}(x_i) } w_i^b (e^{c_b} - e^{-c_b})$ : 잘못 예측한 데이터의 가중치를 고려한 Decision Tree 학습

 

따라서 Loss Function을 최소화하는 $\hat{f_b}$는 $\sum_{ y_i \neq \hat{f_b}(x_i) } w_i^b$를 최소화하는 모델입니다

 

$$\begin{array}{rl}& \frac{\partial L}{\partial c_b}=\sum _{i=1}^N-w_i{e}^{-c_b}+\sum _{y_i\ne \widehat{f_b}(x_i)}{w}_i(e^{c_b}+e^{-c_b})=\sum _{y_i\ne \widehat{f_b}(x_i)}{w}_i^b{e}^{c_b}-\sum _{y_i=\widehat{f_b}(x_i)}{w}_i^b{e}^{-c_b}=0\\ & \Rightarrow c_b=\frac{1}{2}\frac{\sum _{y_i=\widehat{f_b}(x_i)}{w}_i^b}{\sum _{y_i\ne \widehat{f_b}(x_i)}{w}_i^b}=\frac{1}{2}\log \frac{1-{ϵ}_b}{{ϵ}_b}\end{array}$$

 

이 때, 오류율 ${\large \epsilon_b = \frac{ \sum_{ y_i \neq \hat{f_b}(x_i) } w_i^b  }{ \sum w_i^b} }$ 입니다

 

위의 과정을 B번 반복하면 최종 모델 $f_b^*(x)$를 생성하게 됩니다

$$f_b^{\ast }(x)=sign(\sum _{b=1}^B{c}_b\cdot \widehat{f_b}(x))$$