[BDA 데이터 분석 모델링반 (ML 1) 18회차] 에이다 부스트(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$
해당 업데이트 된 가중치를 다음 학습기에 사용한다.