머신러닝 정리 4.5(3) - AdaBoost

Adaboost 를 만드는 방법이 몇가지 존재하지만, 그 중 Decision Tree를 사용하는 것이 가장 일반적이다. 

 

 Decision Tree를 기반으로 하는 Adaboost 를 살펴보자. 

 

 랜덤 포레스트 내용이 필수적으로 등장하니, 잘 모르는 분들은 먼저 이 글을 읽고 오면 좋다. 

 

랜덤 포레스트는 트리를 만들 때 마다 full-sized tree를 만든다. 그리고 max sample 개수나 특정 조건에 따라 각각의 트리의 깊이가 다르다. 

 

반면, Adaboost는 주로 깊이가 1인, 즉 루트 노드에 두개의 leaves 만 존재한다. 이러한 형태의 Tree를 Stump 라 한다. 아래 이미지와같이 stump 들의 모임은 주로 Forest of Stumps 라 부른다.

 

당연히 Stumps는 feature 하나로 결정을 내리다보니 좋은 의사결정이 나올 확률이 낮다. 

Stumps야 말로 "weak learners" 라 할 수 있다. 

 

Random Forests와 AdaBoost의 차이점

 

 

Random Forests(왼쪽) AdaBoost(오른쪽)

굉장히 흥미로운 점은 Random Forests는 각 트리의 vote 능력이 동등한 반면 AdaBoost는 vote 능력이 동등하지 않다. 이와 유사한 다양한 경우에서 능력에 따라 vote 의 weight를 다르게 주는 것이 항상 성능이 향상되었던 것을 떠올려볼 때, 굉장히 당연하다.

 

Random Forests는 tree의 순서가 상관 없었지만, AdaBoost는 순서가 굉장히 중요한 것도 다른점이다. 

 

선행 Stump가 판단을 잘 못 내리면 따라오는 Stump 는 영향을 받을 수 밖에 없는 구조이다. 

 

 정리하자면 AdaBoost 다음의 3가지 철학을 가지고 있다. 

 

• AdaBoost는 weak learner인 stumps를 여럿 결합하여 classifiaction을 수행한다.
• Stumps 중 몇몇은 classification에 있어 더 강한 발언권을 갖는다. (weight)
• 각 stump는 생성될 때 선행 stump 의 실수에 영향을 받는다. 

 

AdaBoost 생성 과정

위와 같이 데이터가 있다. 

 

Boost 는 선행 트리가 후행 트리에 영향을 끼쳐야하기 때문에 Weight의 값이 중요하다. 

초기 Weight는 전체 데이터 샘플 개수 분의 1 로 한다.

 

Weight는 Stump 를 만드는 과정에서 계속 update 된다. 

 

첫 Stump 를 결정하기 위해 각 feature를 택했을 때 Gini index 를 비교해보자. 

 

Chest Pain은 8개 중 총 3개의 incorrect한 결과를 생성한다. 

 

Blocked Arteries는 총 4개의 incorrect한 결과를 생성한다.  

 

Patient Weight > 176 은 총 1개의 incorrect한 결과를 생성한다. 

여기서 176으로 결정하는 방법은 이글에서 설명 했었다. Iterate 과정 중, 172 180 사이에서 Gini index 가 가장 작았기 때문이다. 

 

 

Patient Weight의 Gini Index가 가장 낮으므로 첫 노드로 선정 된다. 

 

AdaBoost는 각 Tree 마다 최종 의사결정 단계에서 발언권, 즉 가중치가 다르다. 

 

가장 먼저 Total Error 는 분류 실패한 데이터 샘플의 Weight를 모두 더한 값으로 여기서는 $\frac{1}{8}$이다. 

(참고로 Sample Weight의 총 합은 1이다. Total Error 가 0에 가까울 수록 좋은 stump 이고 1에 가까울 수록 나쁜 stump이다.)

 

Amount of Say 를 그래프화 하면 아래와 같다. Total Eror 가 0에 가까울 수록 Amount of Say는 무한대에 수렴하고, 1에 가까울 수록 - 무한대에 수렴한다. 물론 그런 극단의 상황은 피하기 위해서 실제 application단에서는 보정을 위해 작은 error term 을 추가하여 사용한다. 

 

정리하자면, Weight > 176 스텀프는 0.97의 Amount of Say를 갖는다. 

 

 

만약 Weight가 아닌 Chest Pain 을 골랐다면 Total Error 가 $frac{3}{8}$ 이고, Amount of Say 는 아래와 같았을 것이다.

 

차이가 큰 것을 알 수 있다. 

 

위 과정을 통해 잘못 분류된 샘플의 Sample Weight가 Amount of Say 에 얼마나 큰 영향을 끼치는지 이해했다. 

 

Sample Weight 업데이트

이제 첫 Stump 분류를 통해 잘못 분류한 Sample의 Weight 를 업데이트 한다. 

Sample의 Weight 을 업데이트 함으로써 다음 Stump를 위한 데이터 Sampling 과정에 영향을 끼친다. 

 

그래프를 통해 알 수 있듯이, 기존의 Sample weight를 amount of say 값에 따라 update한다. 

우리의 amount of say 는 0.97 이다. 

 

$\frac{1}{8}$에 비해 크게 증가하였다. 

 

해당 데이터 샘플의 weight 가 증가하였다면, 올바르게 분류하였던 샘플들의 weight는 작게 할 필요가 있다. 

 

이번에는 Amount of Say의 - 값을 승으로 삼아 Weight를 더 작게 만든다.

 

이후 sample weight를 업데이트 하고, 총 합이 1이 되도록 Normalize한다. 

 

다음 Stump 를 위해 데이터를 샘플링한다. 

데이터 샘플링을 위해 0 ~ 1사이의 난수를 총 8번 뽑는다. 

이 때 뽑은 8개의 난수를 아래의 기준에 맞춰 데이터 샘플링에 적용한다. 

 

Weight 의 총합은 1이므로, 앞쪽부터 순서대로

0 ~ 0.07: 1번째 샘플 

0.07 ~ 0.14: 2번째 샘플 

... 

0.21 ~ 0.7 : 4번째 샘플 

...

0.93 ~ 1 : 8번째 샘플 

 

데이터 샘플링 결과, weight가 높았던 4번째 sample 이 가장 많이 뽑힌 것을 확인할 수 있다. 

 

 

이 후, Sample Weight 는 다시 초기화 된다. 

하지만, 동일한 데이터가 4개나 있다보니 만약 이번에도 해당 데이터를 잘못 분류하게 되면 penalty가 굉장히 크다. 

애초에 해당 데이터에 대해 gini index가 낮은 feature를 선택하다보니 웬만하면 분류가 잘 될 확률이 높다고 생각한다. 

 

최종적으로 새로운 데이터가 들어오면 각 Stump들은 분류를 마친 후, 각 결과별로 Amount of Say를 총합하여 더 높은 쪽으로 결론을 내리게 된다. 

약한 분류기를 직렬로 쌓는 강력한 모델 AdaBoost를 살펴보았다. 다만, 과정에서 살펴보았듯이 첫 노드가 제대로 예측하지 못했던 데이터 샘플에 치우치는 경향이 발생하기 쉬워보인다.