[부스팅 모델] AdaBoost

이 글은 Joshua Starmer의 AdaBoost, Clearly Explained를 정리한 것임을 밝힙니다.

Adaboost(Adaptive Boost)

부스팅의 알고리즘을 쉽게 이해할 수 있는 Adaboost에 대해 알아보자.

Stump

Adaboost는 Random Forest와 달리 Stumps들의 집합을 가정으로 한다. (여기서, stump란 그림처럼  자식 노드가 두 개, 부모 노드가 하나로 이루어진 구조를 말한다.) 각, Stump들은 순차적으로 생성이 된다. Random Forest에서는 각 Decision Tree들이 동일한 가중치로 결정권을 행사했다면, Adaboost의 Stump들은 다른 가중치를 부여받는다. (가중치에 대한 과정은 이후 자세하게 설명)

 

그럼, 예시를 통해 이해해 보자!

8개의 샘플 데이터를 뽑았다. 각각의 샘플 데이터는 처음엔 1/n의 가중치 값을 갖는다. 그리고, 모든 피처에 대해 지니 계수의 가중평균값을 구한다. 예시에서는 Weight로 분할했을 때, 가장 작은 *G.I.값이 나와 Weight로 나눈 Stump를 선택한다. 

 

(* Gini index: 1-(각각의 비율을 제곱한 다음 더한 것) 으로 0~0.5의 범위를 가지며 0이 될수록 분류가 잘 된 것이다.)

 

선택한 Weight 스텀프에 대하여 Stump weight를 구하는 수식은 위와 같다. 전체 중에 stump가 못 맞춘 샘플의 sample weight Total Error라고 부르고, Stump Weight는 위의 식처럼 0으로 갈수록 양수로 커지고, 1로 갈수록 음수로 작아지는 모습을 보인다. (Total Error가 0.5보다 작으면 오히려 stump가 예측한 값을 음수로 바꿔 역의 가중치를 취해준다. → stump 입장에서는 굴욕적..)

 

이제, stump weight를 구했다면, 각 sample weight을 갱신해줘야 할 차례이다. 

부스팅은 틀린 sample에 대해 더 큰 가중치를 주어 모델이 학습에 반영한다고 했었다. 그래서, 위의 수식에서 보면 맞은 샘플과 틀린 샘플의 weight에 대한 수식이 다르다.

 

- 틀린 샘플 가중치: 기존 샘플 weight(1/8) * e ^{stump weight}

- 맞은 샘플 가중치: 기존 샘플 weight(1/8) * e ^{-stump weight}

 

위 수식을 통해 weight이 큰 stump가 틀린 샘플에 대해서는 가중치를 더욱 크게 줌을 알 수 있다. 위에선 4행에 있는 데이터만 틀렸기 때문에 0.33으로 가장 크게 가중치가 갱신되고, 나머지는 맞았기 때문에 0.05로 작아진 것을 볼 수 있다. 그런데, 이 weight를 합하면 1이 되어야 하기 때문에 sum(sample weight)로 나누어 normalize를 해준다. 그리고 업데이트된 sample weight로 위 과정을 반복한다. (사실 sample weight로 weighted gini index를 구해야 하지만 그냥 여러 샘플을 복제하여 나타내서 표현함)

빨간 색이 틀렸던 데이터

보시다시피, 새로운 샘플을 구성할 때, 틀렸던 데이터가 8개 중 4개나 차지하는 것을 볼 수 있다!

이렇게 새로워진 샘플로 위의 과정을 n번 반복해 준다. (참고로, 새로워진 샘플 데이터에 대해서는 sample weight를 1/n으로 초기화한다.) 

 

최종적으로 n개의 stump들이 나오게 되고, 각 stump는 다른 stump weight를 가지고 있다. 그래서 test 데이터에 대해 각 stump가 예측한 것에 weight만큼의 행사권(?)을 주어 최종 예측값을 결정한다. 

 

다음 장부터는 XGB를 시작으로 다양한 부스팅 알고리즘에 대해 소개하려 한다.