[Machine Learning] AdaBoost

이번 포스팅에서는 AdaBoost에 대해서 배워보도록 하겠습니다.

본 포스팅은 STATQUEST 유튜브 채널을 참고하여 만들었습니다.

우선 알고리즘을 전체적으로 한 번 살펴보도록 하겠습니다.

AdaBoost 알고리즘을 수학적으로 풀어보았습니다.

우선 자세하게 들어가기전에 각 스텝별로 목적이 무엇인지를 미리 알아보도록 하겠습니다.

Step 1을 보시면 D라는 값에 동일한 1/N 이 주어집니다.

우선 D에 대한 정의를 보시면, 관측치에 대한 Weight라고 되어있습니다.

즉, Step 1에서는 모든 관측치에 동일한 Weight를 주고 시작하겠다는 의도로 볼 수 있습니다.

그리고 이제 Step 2부터는 T번의 Iteration이 돌게됩니다.

이 때, T는 weak learner의 개수라고 유추할 수 있습니다.

Iteration 안을 들여다보도록 하겠습니다.

우선 h_t라는 값에 weak learner로 예측한 값들이 입력됩니다.

그리고 입실론 값에 어떠한 값들이 계속 더해지는데, 이는 예측값과 실제값을 비교해서, 오답인 관측치의 가중치를 전부 더해줍니다.

예를 들어서, 첫 번째 Iteration에서는 모든 가중치가 1/N으로 같고, weak learner에서 총 4개의 관측치가 오답이라고 해봅시다.

그렇게 되면, 입실론 값은 4/N 으로 계산 될 것이라 예상됩니다.

그리고 If문을 보시면, 입실론이 0.5보다 크면 Iteration이 다시 반복 되는데, 이는 weak learner의 성능이 너무 안좋으니까, 다른 weak learner를 다시 만들어 보라는 의미입니다.

어쨋든 입실이 0.5보다 작을경우, 정의된 식으로 alpha가 계산이 됩니다.

그리고 weight가 업데이트가 되는데, alpha값이 가중되데, 오답의 경우 -h(x)y가 양의 값을 가지므로 1보다 큰 값이 곱해져, 가중치가 커집니다. 반대로, 정답의 경우 -h(x)y가 음의 값을 가지므로 1보다 작은 값이 곱해져, 가중치가 작아지게됩니다.

이러한 방법을 T번 반복 하는 것이 AdaBoost의 전체적인 알고리즘으로 보시면 됩니다.

그리고 최종 예측값으로, 각 모델의 예측값과 alpha들의 선형 조합으로 출력합니다.

​

그러면 이제 AdaBoost를 시각적으로 쉽게 설명하도록 하겠습니다.

이 부분부터는 유튜브의 STATQuest를 참조하였습니다.

Adaboost는 랜덤포레스트와 달리, 하나의 노드와 2개의 leaf로만 구성된 Stump를 Weak learner로써 사용합니다.

​

Step 1)

총 3개의 변수 Chest Pain, Blocked Arteries, Patient Weight로 Heart Disease를 예측하는 Task가 있다고 합시다.

Step 1에서는 sample weight가 동일한 값 (1/8)을 가지도록 만들어줍니다.

​

Step 2)

Step 2의 첫번째 과정으로, Weak learner를 학습해야 합니다.

이 때, Stump 중에서, Gini index가 가장 작은 것을 Weak learner로 정해줍니다.

​

이제 토탈 에러를 계산을 하고, 이를 바탕으로 alpha를 계산해줍니다.

이 때, alpha를 amount of say로 정의하도록 하겠습니다.

이제 가중치 정답과 오답에 대해서 위의 알고리즘의 식대로, 가중치를 업데이트 해줍니다.

그러면 정답인 관측치에 대해서는 가중치가 감소하였고, 오답인 관측치에 대해서는 가중치가 증가하였습니다.

위의 경우에서는 오직 1개의 관측치가 오답이므로, 가중치가 0.33까지 증가한것으로 관찰됩니다.

이렇게 총 T번의 Iteration을 반복하면 AdaBoost 모델이 만들어지는 것입니다.

​

이제 새로운 관측치가 들어왔다고 가정해봅시다.

총 6개의 Weak learner가 있을 때, 4개의 learner에서는 Yes로 예측하고, 2개의 learner에서는 No라고 예측했다고 가정합시다.

그러면 각 경우에 대해서 Amount say를 더해줍니다.

위의 경우에서는 Yes의 경우 0.97+0.32+0.78+0.63 = 2.7, No의 경우 0.41+0.82 = 1.23 이 됩니다.

이 중에서 큰 값, 즉 Yes로 Output class가 정해집니다.