에이다 부스트 (AdaBoost)

에이다 부스트 (AdaBoost)

https://bkshin.tistory.com/entry/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-14-AdaBoost?category=1057680

위 블로그를 필사하며 공부

* 모든 텍스트와 이미지의 출처는 위 블로그입니다.

AdaBoost의 개요

아래와 같이 노드 1개에 2개의 리프(leaf)를 지닌 트리를 stump라고 합니다.

출처: StatQuest

AdaBoost는 아래와 같이 여러 개의 stump로 구성이 되어 있습니다. 이를 Forest of stumps라고 합니다.

출처: StatQuest

트리와 다르게 stump는 정확히 분류를 하지 못한다.

여러 질문을 통해 데이터를 분류하는 트리와 다르게, stump는 단 하나의 질문으로 데이터를 분류해야하기 때문이다.

따라서 stump는 약한 학습기 (weak learner)이다.

랜덤 포레스트는 여러 개의 트리의 결과를 합산해 다수결의 원칙을 통해 최종 결과를 낸다.

최종 분류를 하는데 있어 각 트리는 동등한 가중치를 지닌다.

출처: StatQuest

하지만 AdaBoost에서 특정 stump는 다른 stump보다 더 중요하다. 즉, 가중치가 더 높다.

아래의 그림에서 크기가 큰 것은 가중치가 더 높은 stump를 뜻한다.

여기서 가중치가 높다는 것은 Amount of Say가 높다고 표현한다. (결과에 미치는 영햐잉 크다는 뜻)

출처: StatQuest

또한, 첫 번째 stump에서 발생한 error은 두 번째 stump의 결과에 영향을 준다.

두 번째 stump에서 발생한 error 역시 세 번째 stump의 결과에 영향을 준다.

그렇게 마지막 stump까지 줄줄이 영향을 준다

정리하자면, AdaBoost는 다음과 같은 3가지 특징을 가진다.

1. 약한 학습기(weak learner)로 구성되어 있으며, 약한 학습기는 stump의 형태이다.

2. 어떤 stump는 다른 stump보다 가중치가 높다. (Amount of Say가 크다.)

3. 각 stump의 error은 다음 stump의 결과에 영향을 준다.

AdaBoost의 작동 원리

출처: StatQuest

Chest Pain, Blocked Arteries, Patient Weigth에 따른 Heart Disease 여부에 대한 데이터이다.

맨 처음 Sample Weight는 8개의 데이터 모두 동일하게 1 / (total number of samples) = 1/8 이다.

모든 sample의 가중치가 1/8로 동일하다.

이제 각각의 feature가 target value(여기서는 Heart Disease에 미치는 영향에 대해 살펴보자.

다음은 Chest Pain과 Heart Disease와의 관계이다.

출처: StatQuest

단순히 Chest Pain이 yes이면 Heart Disease도 yes 라고 판단하는 모델이다.

총 8개의 데이터 중 Chest Pain이 yes인 데이터 (즉, Heart Disease를 yes라고 판단한 데이터)는 5개, no인 데이터는 3개이다.

Heart Disease를 yes라고 판단한 것 중 올바르게 판단한 것은 3개, 틀리게 판단한 것은 2개이다.

반대로, Heart Disease를 no라고 판단한 것 중 올바르게 판단한 것은 2개, 틀리게 판단한 것은 1개이다.

다음은 Blocked Arteries와 Heart Disease와의 관계이다.

출처: StatQuest

마지막으로, Patient Weight와 Heart Disease간의 관계이다.

출처: StatQuest

각 stump의 지니 계수를 구한다.

출처: StatQuest

마지막 stump의 지니 계수가 가장 작기 때문에 forest의 첫 stump로 지정한다.

이 stump가 최종 결과 예측에 있어 얼마만큼의 중요도가 있는지 본다.

Amount of Say 구하기

틀리게 분류한 것이 No Heart Disease의 incorrect로 1개밖에 없다.

따라서 Total Error = 1/8 이다.

출처: StatQuest

모든 sample weights의 합은 1이기 때문에, Total Error은 0~1 사이의 값을 가진다.

Total Error가 Amount of Say를 결정한다.

Amount of Say는 최종 분류에 있어 해당 stump가 얼마만큼의 영향을 주는가를 뜻한다.

출처: StatQuest

Amount of Say를 그래프로 그려보면 아래의 그림과 같다.

X축은 Total Error, Y축은 Amount of Say이다.

Total Error가 0이면 Amount of Say는 굉장히 큰 양수이고, Total Error가 1이면 Amount of Say는 굉장히 작은 음수가 된다.

따라서 Total Error가 0면 항상 올바른 분류를 한다는 뜻이고, 1이면 항상 반대로 분류를 한다는 뜻이다.

Total Erorr가 0.5일 때는 Amount of Say가 0이다. (동전을 던지는 것과 마찬가지로 의미가 없다는 뜻)

출처: StatQuest

다시 Stump로 문제로 돌아와, Total Error=1/8이므로,

출처: 위 블로그

= 0.97이다.

그래프 상에서 표현해보면, Total Error가 1/8이고, Amount of Say=0.97인 아래 지점이다.

출처: StatQuest

Chest Pain Stump의 Amount of Say를 구하는 방법이다.

출처: StatQuest

이 stump의 Total Error은 1/8 + 1/8 + 1/8 = 3/8이므로, Amount of Say를 구해보면,

출처: 위 블로그

= 0/42이다.

Blocked Arteries도 동일한 방식으로 Amount of Say를 구해줄 수 있다.

샘플 가중치 설정

AdaBoost에서는 하나의 stump가 잘못 분류 한 sample에 대해서는 다음 stump로 넘겨줄 때 가중치를 더 높여 넘겨준다.

그래야 다음 stump에서 해당 sample에 더 집중해 올바로 분류해주기 때문이다.

맨 처음 weight stump에서는 아래 빨간 네모 안에 있는 sample만 잘못 분류했다.

따라서 해당 sample의 weight를 1/8보다 크게 하고, 나머지 sample의 weight는 1/8보다 작게 하여 다음 stump로 넘겨준다.

이전 stump에서 잘못 분류된 sample의 경우 다음 stump로 넘겨줄 때의 새로운 sample weight를 구하는 공식은 아래와 같다.

출처: StatQuest

(이전 stump에서 잘못 분류된 sample의) New Sample Weight = (1/8) * e^(0.97) = (1/8) * 2.64 = 0.33 이다.

기존의 sample weight = 1/8 = 0.125보다 더 높아졌다.

이전 stump에서 잘 분류된 sample인 경우 새로운 sample weight를 구하는 공식은 다음과 같다.

출처: StatQuest

(이전 stump에서 잘 분류된 sample의) New Sample Weight = (1/8) * e^(-0.97) = (1/8) * 0.38 = 0.05이다.

기존의 weight인 0.125보다 더 작아졌다.

이런 식으로 진행이 되어야 다음 stump에서 이전 stump에서 잘못 분류한 것에 더 집중을 해 올바른 분류를 해주기 때문ㅇ다.

새로 구한 sample weight는 아래와 같다.

출처: StatQuest

New Sample Weight는 공식에 의해 구한 weight이다.

단, 다 더했을 때 값은 0.68로 1이 되지 않는다.

Sample weight의 합은 항상 1이 되어야 하므로 오른쪽 Weight처럼 정규화시켜준다. (각 weight를 모든 weight의 합으로 나누기)

출처: StatQuest

그 다음 스텝은 샘플링을 통해 새로운 테이블을 만드는 것이다.

0부터 1까지의 숫자를 랜덤하게 뽑아 0~0.07 사이의 숫자가 나오면 첫 번째 sample을 선택한다.

0.07~0.14가 나오면 두 번째 sample을 선택, 0.14~0.21은 세 번째, 0.21~0.70가 나오면 네 번째 sample을 선택한다.

즉, sample weight의 누적 숫자에 해당하는 sample을 뽑는 것이다.

그렇게 원래 테이블의 sample 수와 똑같은 sample 수를 가진 새로운 테이블을 구성한다.

뽑힌 sample들을 보니 중복되는 것도 있다.

원래 테이블에서 sample weight가 0.49인 sample이 4번이나 뽑혔다.

(당연히 0.21~0.70 사이의 숫자가 나오면 해당 sample을 뽑으니 확률이 많을 것이다.)

출처: StatQuest

이제 원래의 테이블은 지우고, 샘플링한 새로운 테이블을 가져온다.

모든 sample의 weight는 다시 1/8로 통일시켜준다.

첫 stump에서 잘못 분류했던 sampel이 4번이나 포함되었다. -> sample weight는 1/8로 동일하더라도 똑같은 데이터가 4개가 있어 실제로는 4/8의 weight를 갖는 것이다.

이는 처음에 잘못 분류했기 때문에, 그 다음에는 weight를 높여 제대로 분류하기 위함이다.

weight가 높아지니 해당 sample에 가중치를 더 두고 분류할 것이다.

출처: StatQuest

다시 맨 처음 했던 것과 같은 방식으로 진행하면 된다.

최종 분류

이렇게 여러 차례 진행하면 아래와 같이 각 stump 마다의 Amount of Say가 나온다.

왼쪽은 Heart Disease가 있다고 판단한 stup이고, 오른쪽은 Heart Disease가 없다고 판단한 stump이다.

각 stump의 Amount of Say를 더하면 Total Amount of Say가 나온다.

이 경우 Heart Disease가 있다는 것의 Total Amount of Say가 2.7로 더 크다.

따라서 최종적으로 Heart Disease가 있다고 분류할 수 있다.

출처: StatQuest

각 stump마다 분류를 해주지만 stump 하나의 분류력은 굉장히 약하다. (weak learner)

하지만 여러 stump의 결과를 종합하면 강한 학습기(strong learner)가 된다.

또한, 각 stump마다 Amount of Say가 다르다.

각 stump의 Amount of Say를 합치면 Total Amount of Say가 나오고, 이를 통해 최종 분류를 해주는 것이다.

어렵닥 !!!!!!!!!!!!

from http://yeon22.tistory.com/128 by ccl(A) rewrite - 2021-11-07 18:00:34