[BDA 데이터 분석 모델링반 (ML 1) 18회차] 에이다 부스트(AdaBoost)

에이다 부스트(AdaBoost) 알고리즘에 대해 알아본다.

 

 

에이다 부스트

오류 데이터에 가중치를 부여하면서 부스팅을 수행하는 알고리즘으로, AdaBoost 학습 단계에서 모델이 잘못 예측한 샘플에 더 큰 가중치를 부여하여 더 잘 학습하도록 유도한다.

 

초기에는 모두 동일한 가중치를 가지며, 단계가 진행될수록 잘못 예측한 샘플의 가중치를 점진적으로 증가시켜 이전 학습기들이 잘못 예측한 부분을 보완하도록 유도한다.

 

AdaBoost 알고리즘

 

 

Input : Dataset $ D = \left\{ (x^1, y^1), \cdots ,(x^N, y^N) \right\},$ $y^{(i)}\in \left\{-1, 1 \right\}$ $\textrm{for}$ $i = 1, \cdots , N$

 

Step0 : 모든 $i = 1, \cdots , N$에 대해, 초기 가중치는 $w_1(i)=\frac{1}{N}$로 설정한다.

 

Step1 : $t = 1, \cdots , T$에 대해 아래 과정을 반복한다.

 

가중치 $w_t(i),$ $i = 1, \cdots , N$에 따라 $N$개의 데이터를 훈련 집합 $D_t$로 설정한다.

 

$D_t$로 분류기 $h_t$를 학습한 후, $D$에 대한 훈련 오류율 $\varepsilon _t$를 계산한다.

 

$$\varepsilon_t=\sum_{i\ :\, h_t(x^{(i)})\neq y^{(i)}}^{}w_t(i)$$

 

만약, $\varepsilon_t$이면, 루프를 중단한다.

 

$\alpha _t = \frac{1}{2} \textrm{log}(\frac{1-\varepsilon _t}{\varepsilon _t})$를 계산한다.

 

잘못 분류된 예제의 가중치는 증가시키고 잘 분류된 예제의 가중치는 감소시킨다.

이때 $Z_t$는 가중치를 정규화하기 위한 변수이다. $Z_t = \sum_{i=1}^{N}w_t(i)\textrm{exp}(-\alpha _ty^{(i)}h_t(x^{(i)}))$

 

$$ w_{t+1}(i) = \frac{w_t(i)}{Z_t}\times \left\{\begin{matrix}
e^{-\alpha _t}, \textrm{if}\, \, \,  y^{(i)} = h_t(x^{(i)}) \\ e^{\alpha _t}, \textrm{if}\, \, \,  y^{(i)} \neq  h_t(x^{(i)})
\end{matrix}\right. = \frac{w_t(i)}{Z_t}\, \textrm{exp}(-\alpha _ty^{(i)}h_t(x^{(i)})) $$

 

Step2 : $g(x) = \sum_{i=1}^{N}\alpha _th_t(x)$로 정의하며, 최종 분류기 $H(x)\, = \, sgn(g(x))$이다.

 

---

오류율 계산 과정은 예측이 틀렸을 때는 1을, 맞으면 0을 반환한다고 상상해본다.

$w_t(i)$는 $i$번째 샘플의 가중치, $h_t(x_i)$는 $i$번째 샘플에 대한 $t$번째 학습기의 예측값, $y(i)$는 $i$번째 샘플의 실제 라벨을 의미한다.

 

예를 들어 3개의 변수 $x_1$, $x_2$,  $x_3$에 대해 실제 예측값은 $y_1 = 1$, $y_2 = -1$, $y_3 = 1$ 라고 가정한다.

초기 가중치는 $w_1(1) = 1/3$, $w_1(2) = 1/3$,  $w_1(3) = 1/3$로 동일하다.

첫 번째 학습기가 예측한 결과가 $h_1(x_1) = 1$, $h_1(x_2) = 1$, $h_1(x_3) = -1$ 이다.

 

가중치 계산은 0 + 1*1/3 + 1*1/3 = 2/3이다.

 

오류율이 낮을수록 가중치가 커지게 된다.

 

알파값을 계산하면, 1/2ln((1-0.6667)/0.6667) = -0.34로 음수값이 나왔다.

 

이를 통해 가중치를 업데이트한다.

$w_2(1) = 1/3(exp(-0.34*0)) = 1/3$, $w_2(2) = w_2(3) = 1/3(exp(-0.34*1)) = 0.23$ 으로

 

정규화를 해보면, 0.333 + 0.23 + 0.23 = 0.8

$w_2(1) = 0.3/0.8 = 0.41$$w_2(2) = 0.23/0.8 = 0.3$$w_3(2) = 0.23/0.8 = 0.3$

해당 업데이트 된 가중치를 다음 학습기에 사용한다.