[Machine Learning] AdaBoost

Dr.Trillion

Dr.Trillion

Dr.Trillion

Dr.Trillion

Dr.Trillion

AdaBoost 알고리즘은 부스팅에 대해 설명할 때 빈번하게 예시로 드는 알고리즘입니다. 아래서 보게 될 그림(Buffalo Univ.) 역시도 많이 접하셨을 거라 생각합니다. https://cse.buffalo.edu/~jcorso/t/CSE555/

Jason J. Corso

 

지난 번 "앙상블" 포스팅에서 

https://trillionver2.tistory.com/entry/%EC%95%99%EC%83%81%EB%B8%94Ensemble-%EA%B8%B0%EB%B2%95

[Machine Learning] 앙상블(Ensemble) 기법

Boosting이라는 것이 여러개의 weak classifier를 결합해서 종합적인 strong classifier를 만든다는 것을 그림으로 보여드린 적이 있습니다. 즉, 앞 라운드(round)에서의 모델(Tree)이 먼저 주어진 데이터 셋에서 sampling된 데이터를 예측하는 모델을 만듭니다. 그러면 분류가 제대로 되지 않는 관측치들이 생기는데, 다음 라운드에서 모델을 이어서 만들되 이를 위한 sampling 시에 앞 라운드에서 잘못 분류된 관측치들이 포함될 확률을 높여주는 방식으로 sampling 해주는 겁니다. 그럼 아무래도 앞선 모델이 제대로 예측하지 못했던 부분을 다음 모델은 상대적으로 잘 맞추겠죠? 비유하자면 모의고사를 계속 보는데, 매번 무작위로 문제를 뽑아서 모의고사를 보는게 아니라 2월 모의고사에서 많이 틀렸던 유형의 문제를 3월 모의고사에서 더 많이 출제하고, 3월 모의고사에서 많이 틀렸던 유형을 4월 모의고사에서 더 많이 출제하고.. 이런식으로 진행하다보면 아무래도 그 학생은 자기가 약했던 유형에 대해 더 많은 문제를 풀어보게 되어 대처능력이 올라갈 것입니다. AdaBoost도 역시 부스팅의 일종이기에 이 컨셉을 가지고 이해해보겠습니다. 

 

 

\(\alpha_t\) 는 \(t\)번째 모델의 결합가중치입니다. Pseudo code를 보시면 다음 시점에서 data point(=instance)가 선택될 확률이 고정된 것이 아니라 이번 시점에서의 data point 선택확률과 몇 가지 요인들에 의해서 결정된다는 것을 알 수 있습니다. 그림으로 한 번 살펴볼까요?

Data 공간에서 왼쪽에서 보시는 바와 같이 데이터(+, - Label)가 존재하고 이를 분류하는 tree를 만든다고 해봅시다. 예를 들어 첫번째 tree가 오른쪽 첫번째 그림처럼 +와 -를 분리하는 모델이었다고 해보겠습니다. 이러면 오른쪽에 있는 3개의 data point들이 + label임에도 불구하고 오분류가 되었죠(10개 중 3개의 오분류). 이러면 \(\epsilon_i\) 의 값은 0.3입니다. 모델의 신뢰도를 구해보면

\[ \alpha_i = \frac{1}{2} \log \left( \frac{1 - \epsilon_i}{\epsilon_i} \right) = \frac{1}{2} \log \frac{1 - 0.3}{0.3} = 0.42 \]

와 같이 계산할 수 있는 것이죠. 이 "신뢰도"라는 것은 다음단계 선택 확률 증감의 폭을 결정합니다. 클수록 진폭의 강도가 강해지는데요(0 ≤ \(\alpha_i\) <0.5).

패스트캠퍼스 실무 문제 해결을 위한 데이터사이언스

 

분자의 Exponential 안에 들어 있는 항, 그 중에서도 \(y_i\) \(h_t(x_i)\) 의 값을 생각해볼까요? 이 값은 실제 \(y_i\)와 모델에서 분류한 값을 곱하고 있죠? 제대로 잘 분류했으면 1*1 혹은 (-1)*(-1)이 되어 곱셈값이 1이 되겠지만, 모델값과 실제값이 다르면 -1이 됩니다. 그리고 이 계산값에 모델의 신뢰도 \(\alpha_i\)가 곱해지고 있는 것이구요. 이 \(\alpha_i\)값을 조절함으로써 오분류 data point가 다음 단계에서 선택될 확률을 심대하게 올릴 수도 있고, 적당히 정분류된 point들 보다 약간 높은 확률로 줄 수도 있습니다. 

 

이러한 방식으로 모델의 몇 라운드 이어서 만들어 나갑니다. 

그리고 마지막에 이러한 weak classifier들을 종합합니다(그리고 이 과정에서 모델의 신뢰도를 바탕으로 가중치를 주어 종합합니다).

 

개별적인 하나하나의 모델들은 오분류도 꽤나 있었지만 이렇게 합쳐진 강분류기는 모델의 bias를 효과적으로 잡아냈다는 것을 그림이 보여주고 있습니다. 다만, 이러한 boosting기법은 주어진 데이터는 기가막히게 예측하지만 새로운 test data에 대해서는 over-fitting이 굉장히 심해서 주의해야 한다는 점 잊지마세요.