[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^{-y f(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(지수함수이기 때문에)를 부여하게 됩니다

---

알고리즘

$${\large \hat{f _b}^*(x_i) = c_1 \hat{f_1}(x_i) + c_2 \hat{f _2}(x_i) + \cdots + c_b \hat{f _b}(x_i)  =  \hat{f}_{b-1}(x_i) + c_b \hat{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{aligned}
L &= \sum \limits_{i=1}^{N} e^{- y_i \hat{f _b}^*(x_i) } = \sum \limits_{i=1}^{N} e^{- y_i ( \hat{f}_{b-1}(x_i) + c_b \hat{f _b}(x_i))} = \sum \limits_{i=1}^{N} e^{- y_i \hat{f}_{b-1}(x_i) - y_i c_b \hat{f _b}(x_i)}\\
&= \sum \limits_{i=1}^{N}  w_i^b e^{ - y_i c_b \hat{f _b}(x_i) }\\
&= \sum_{y_i = \hat{f_b}(x_i)\\(=1)}w_i^b e^{- c_b \cdot 1} + \sum_{y_i \neq \hat{f_b}(x_i)\\(= -1)} w_i^b e^{- c_b \cdot -1} =  \sum_{y_i = \hat{f_b}(x_i)}w_i^b e^{-c_b} + \sum_{y_i \neq \hat{f_b}(x_i)} w_i^b e^{ c_b}\\
&= \sum \limits_{i=1}^{N} w_i^b e^{-c_b} + \sum_{ y_i \neq \hat{f_b}(x_i) } w_i^b (e^{c_b} - e^{-c_b})
\end{aligned}
$$

---

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

 

$$ L = \sum_{y_i = \hat{f_b}(x_i)}w_i^b e^{-c_b} + \sum_{y_i \neq \hat{f_b}(x_i)} w_i^b e^{c_b} = \sum \limits_{i=1}^{N} w_i^b e^{-c_b} + \sum_{ y_i \neq \hat{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{aligned}
&\frac{\partial{L}}{\partial c_b} = \sum \limits_{i=1}^{N} -w_i e^{-c_b} + \sum_{ y_i \neq \hat{f_b}(x_i) } w_i (e^{c_b} + e^{-c_b}) =\sum_{ y_i \neq \hat{f_b}(x_i) } w_i^b e^{c_b} - \sum_{ y_i = \hat{f_b}(x_i) } w_i^b e^{-c_b} = 0\\
&\Rightarrow c_b = \frac{1}{2} \frac{ \sum_{ y_i = \hat{f_b}(x_i) } w_i^b }{  \sum_{ y_i \neq \hat{f_b}(x_i) } w_i^b  } = \frac{1}{2} \log \frac{1-\epsilon_b}{\epsilon_b}
\end{aligned} 
$$

 

이 때, 오류율 ${\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^*(x) = sign(\sum \limits_{b=1}^{B} c_b \cdot \hat{f_b}(x))$$