0. Ada Boost

ada boost는 여러 weak learner에 대해 결과물의 가중치를 두어 분류하는 분류기의 일종이다. ada boost는 weak learner의 결과물 중에 약한 학습기들 중에 올바르게 분류한 데이터에 대해서는 weight를 낮추고 틀리게 예측한 데이터에 대해서는 weight를 높여서 그 다음의 모델이 더 잘 예측하게 만든 boosting 기법이다.

1. Ada Boost의 analysis

ada boost의 분류기는 다음과 같은 식으로 나타낸다.

$F_T(x)=\sum_{t=1}^T f_t(x)\cdots(1.1)$

이 때, 각 변수의 의미는 다음과 같다.

• $T$ : 전체 weak learner의 수
• $f_t$ : $t$번 째의 weak lerner
• $F_T$ : 최종적으로 완성될 learner

$t$단계에서의 훈련 오류의 합 $E_t$는 다음과 같다.

$E_T = \sum E(F_{t-1}(x_i)+\alpha_i h(x_i))\cdots(1.2)$

여기서 $h(x_i)$는 각각의 훈련 샘플에 대한 가설이다.  또한 $\alpha_i$는 weight로 $E_t$가 최소값을 갖도록 조정해줄 변수이다. 또한 $F_{i-1}$은 $t-1$단계까지 만들어진 분류기이다. 따라서 지금부터 $\alpha_i$를 조정해서 $E_t$를 최소화해보자.

수학에서 함수의 최솟값을 analytic하게 혹은 numeric하게 찾는 과정을 최적화(optimization)이라고 한다. 위에서는 $\alpha_i$가 $E_t$에 대한 변수이므로 $\alpha_i$에 대해 편미분해서 최솟값을 찾을 수 있을 것이다. 물론 편미분이라는 것은 매우 computational cost를 많이 소모하는 작업이기 때문에 많은 머신 러닝 기법들이 gradient descending 방식을 선호한다. 하지만 ada boost에서는 편미분을 이용해 최적화를 해준다.

2. Ada Boost의 Derivation

우선 각 ${x_i}$에 대해 분류 결과값 $y_i\in\left\{-1,1\right\}$을 갖는다고 생각해보자. 또한 weak leaner $\left\{k_i\right\}_{i=1}^L$이 있다고 하자. 이 때 Ada boost는 다음과 같이 weak leaner의 linear combination(선형 결합)으로 이루어진다;

$C_{m-1}(x_i) = \alpha_1 k_1(x_i) + \cdots + \alpha_{m-1} k_{m-1}(x_i)\cdots(2.1)$

따라서 m번째 weak learner까지 합친 분류기는 다음과 같다.

$C_m(x_i)=C_{m-1}(x_i)+\alpha_m k_m(x_i)\cdots(2.2)$

마치 mathematical induction(수학적 귀납법)과 비슷한 방식으로 $\alpha_i,i<m$까지는 알고 있다고 가정해보자. 분류기 $C_m$의 error $E$는 다음과 같이 정의한다.

$E=\sum_{i=1}^N e^{-y_i C_m(x_i)}\cdots(2.3)$

(2.3)식을 $y_i$와 분류기를 거친 추정값 $C_m(x_i)$의 각 case에 대해 표로 나타내자.

$y_i$	$C_m(x_i)$	$e^{-y_i C_m(x_i)}$
-1	-1	$1/e$
-1	1	$e$
1	-1	$e$
1	1	$1/e$

표1

위의 표에서 알 수 있듯이 분류기가 잘 작동한 경우(즉, $y_i=C_m(x_i)$)에는 $1/e$를 갖는다. 반대로 분류기가 잘 작동하지 않은 경우에는 $e$를 갖는다. 이제 (2.2)와 (2.3)을 결합하면 다음과 같은 식을 얻을 수 있다.

$E=\sum_{i=1}^N e^{-y_i (C_{m-1}(x_i)+\alpha_m k_m(x_i))}$

$=\sum_{i=1}^N w_i^m e^{-y_i \alpha_m k_m(x_i)}\cdots(2.4)$

여기서 $w_i^m$은 다음과 같다.

$w_i^m = e^{-y_i \alpha_m k_m(x_i)}\cdots(2.5)$

이제 (2.4) 식에서 $m$번째 분류기가 잘 작동한 경우(즉, $y_i=k_m(x_i)$)와 그렇지 않은 경우로 Sigma를 나누자.

$$ E= \sum{y_i=k_m(x_i)} w_i^m e^{-y_i \alpha_m k_m(x_i)}+\sum{yi\neq k_m(x_i)} w_i^m e^{-y_i \alpha_m k_m(x_i)}=\sum{yi=k_m(x_i)} w_i^m e^{-\alpha_m}+\sum{yi\neq k_m(x_i)} w_i^m e^{\alpha_m}=\sum{i=1}^N wi^m e^{-\alpha_m}+\sum{y_i\neq k_m(x_i)}w_i^m (e^{\alpha_m}-e^{-\alpha_m}) \cdots(2.6) $$

한편, (2.6)의 가장 아래 식을 최소화하는 weight $\alpha_m$를 앞서 말했던 편미분을 이용해 찾자.

$\frac{dE}{d\alpha_m} = \sum_{y_i=k_m(x_i)} w_i^m e^{-\alpha_m}-\sum_{y_i\neq k_m(x_i)} w_i^m e^{\alpha_m}\cdots(2.7)$

(2.7)식을 최소화하는 $\alpha_m$에 대해서 $\frac{dE}{d\alpha_m}=0$을 만족하므로 (2.7)$=0$식을 풀면 다음과 같은 $\alpha_m$을 얻을 수 있다.

$\alpha_m = \frac{1}{2} \ln\frac{\sum_{y_i=k_m(x_i)} w_i^m}{\sum_{y_i\neq k_m(x_i)} w_i^m}\cdots(2.8)$

최종적으로 주어진 $C_{m-1}$을 활용하여 분류기 $C_m$을 만들면 다음과 같다.

$C_m = C_{m-1} + \frac{1}{2} \ln\frac{\sum_{y_i=k_m(x_i)} w_i^m}{\sum_{y_i\neq k_m(x_i)} w_i^m} k_m\cdots(2.9)$

3. Interpretation of Derivation

표1에서 분류기가 잘 작동하면 weight가 $1/e$이고 그렇지 않으면 $e$가 된다. 따라서 분류기가 잘 작동하지 못하면 $w_i^m$은 커지게 된다. 즉 weight는 분류기의 정확도 여부에 따라 편차가 $e$와 $1/e$가 된다. 약 $e=2.7$라고 하면 그 편차가 매우 크다고 할 수 있다. 따라서 분류기가 잘 분류하지 못한 데이터에 대해서는 weight를 2.7정도 갖고 잘 분류한 데이터에 대해서는 1/2.7, 약 0.4의 weight를 갖는다.

4. Reference

[1] https://www.slideshare.net/freepsw/boosting-bagging-vs-boosting

[2] https://ko.wikipedia.org/wiki/%EC%97%90%EC%9D%B4%EB%8B%A4%EB%B6%80%EC%8A%A4%ED%8A%B8