0. Ada Boost
ada boost는 여러 weak learner에 대해 결과물의 가중치를 두어 분류하는 분류기의 일종이다. ada boost는 weak learner의 결과물 중에 약한 학습기들 중에 올바르게 분류한 데이터에 대해서는 weight를 낮추고 틀리게 예측한 데이터에 대해서는 weight를 높여서 그 다음의 모델이 더 잘 예측하게 만든 boosting 기법이다.
1. Ada Boost의 analysis
ada boost의 분류기는 다음과 같은 식으로 나타낸다.
FT(x)=∑t=1Tft(x)⋯(1.1)
이 때, 각 변수의 의미는 다음과 같다.
- T : 전체 weak learner의 수
- ft : t번 째의 weak lerner
- FT : 최종적으로 완성될 learner
t단계에서의 훈련 오류의 합 Et는 다음과 같다.
ET=∑E(Ft−1(xi)+αih(xi))⋯(1.2)
여기서 h(xi)는 각각의 훈련 샘플에 대한 가설이다. 또한 αi는 weight로 Et가 최소값을 갖도록 조정해줄 변수이다. 또한 Fi−1은 t−1단계까지 만들어진 분류기이다. 따라서 지금부터 αi를 조정해서 Et를 최소화해보자.
수학에서 함수의 최솟값을 analytic하게 혹은 numeric하게 찾는 과정을 최적화(optimization)이라고 한다. 위에서는 αi가 Et에 대한 변수이므로 αi에 대해 편미분해서 최솟값을 찾을 수 있을 것이다. 물론 편미분이라는 것은 매우 computational cost를 많이 소모하는 작업이기 때문에 많은 머신 러닝 기법들이 gradient descending 방식을 선호한다. 하지만 ada boost에서는 편미분을 이용해 최적화를 해준다.
2. Ada Boost의 Derivation
우선 각 xi에 대해 분류 결과값 yi∈{−1,1}을 갖는다고 생각해보자. 또한 weak leaner {ki}i=1L이 있다고 하자. 이 때 Ada boost는 다음과 같이 weak leaner의 linear combination(선형 결합)으로 이루어진다;
Cm−1(xi)=α1k1(xi)+⋯+αm−1km−1(xi)⋯(2.1)
따라서 m번째 weak learner까지 합친 분류기는 다음과 같다.
Cm(xi)=Cm−1(xi)+αmkm(xi)⋯(2.2)
마치 mathematical induction(수학적 귀납법)과 비슷한 방식으로 αi,i<m까지는 알고 있다고 가정해보자. 분류기 Cm의 error E는 다음과 같이 정의한다.
E=∑i=1Ne−yiCm(xi)⋯(2.3)
(2.3)식을 yi와 분류기를 거친 추정값 Cm(xi)의 각 case에 대해 표로 나타내자.
yi | Cm(xi) | e−yiCm(xi) |
---|
-1 | -1 | 1/e |
-1 | 1 | e |
1 | -1 | e |
1 | 1 | 1/e |
표1
위의 표에서 알 수 있듯이 분류기가 잘 작동한 경우(즉, yi=Cm(xi))에는 1/e를 갖는다. 반대로 분류기가 잘 작동하지 않은 경우에는 e를 갖는다. 이제 (2.2)와 (2.3)을 결합하면 다음과 같은 식을 얻을 수 있다.
E=∑i=1Ne−yi(Cm−1(xi)+αmkm(xi))
=∑i=1Nwime−yiαmkm(xi)⋯(2.4)
여기서 wim은 다음과 같다.
wim=e−yiαmkm(xi)⋯(2.5)
이제 (2.4) 식에서 m번째 분류기가 잘 작동한 경우(즉, yi=km(xi))와 그렇지 않은 경우로 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 αm를 앞서 말했던 편미분을 이용해 찾자.
dαmdE=∑yi=km(xi)wime−αm−∑yi=km(xi)wimeαm⋯(2.7)
(2.7)식을 최소화하는 αm에 대해서 dαmdE=0을 만족하므로 (2.7)=0식을 풀면 다음과 같은 αm을 얻을 수 있다.
αm=21ln∑yi=km(xi)wim∑yi=km(xi)wim⋯(2.8)
최종적으로 주어진 Cm−1을 활용하여 분류기 Cm을 만들면 다음과 같다.
Cm=Cm−1+21ln∑yi=km(xi)wim∑yi=km(xi)wimkm⋯(2.9)
3. Interpretation of Derivation
표1에서 분류기가 잘 작동하면 weight가 1/e이고 그렇지 않으면 e가 된다. 따라서 분류기가 잘 작동하지 못하면 wim은 커지게 된다. 즉 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