논문을 읽고 정리를 하기 이전에, Boosting을 간략하게라도 아는 것이 수식을 이해하는 것에 큰 도움이 될 것 같았습니다. 이에, StatQuest라는 채널의 AdaBoost 영상을 시청 후 정리를 해보았습니다.
본 유튜브 영상에선 Boosting을 설명하기 위하여 Decision Tree와 Random Forest를 활용합니다. 따라서 해당 내용에 대하여 미리 학습한 뒤에 Boosting을 학습하시면 원활할 것입니다.
Random Forest에선 트리를 만들때, full-size의 트리를 만듭니다. 하지만 트리의 최대 깊이가 정해져 있지 않기 때문에, 트리의 모양은 각양각색입니다.
AdaBoost Stump Tree 통일성
하지만 AdaBoost에서는 하나의 노드와 두개의 잎으로 이루어져 있습니다. 이런 구조의 트리를 그루터기(Stump)라고 합니다. 즉, 나무의 숲(Forest)이라기보다 그루터기의 숲이라고 표현하는것이 좋겠네요. 하지만 구조상, 잎이 적기 때문에 정확한 분류가 어렵습니다. 즉, 구조적으로 Weak합니다.
즉 위의 그림과 같이, Decision Tree가 4개의 변수로 의사 결정을 내릴 수 있는 반면에, 그루터기는 이 중 하나의 변수로만 의사 결정을 할 수 밖에 없습니다. 하지만 Adaboost는 이 상황을 오히려 좋아합니다.
Random Forest의 경우를 봐볼까요?
Random Forest에서는 각 트리가 모두 분류에 있어 동일한 투표권을 갖습니다. 1번째 트리의 분류에 대한 결정이 2번째, 3번째…와 모두 최종 Output을 내는 과정에서 같은 영향을 갖습니다.
하지만 Adaboost의 그루터기들은 각자의 의사가 차등적으로 전체 결과에 영향을 미칩니다.
Random Forest에선 각 트리들이 서로에게 영향을 미치지 않습니다. 즉 독립적으로 구성이 되는 것입니다. 하지만 AdaBoost에서는 서로 연쇄적으로 구성이 되기 때문에 서로의 결과가 서로에게 영향을 미치는 종속적인 관계라고 할 수 있습니다. 따라서 순서가 중요하게 됩니다.
즉 정리해보자면,
Chest Pain, Blocked Arteries, Patient Weight > Heart Disease 3개의 독립변수로 심장병을 예측하는 예시
먼저 데이터 셋을 구성한 뒤, Sample Weight을 정해줍니다. 이는 정확히 분류가 되어야 하는 중요도를 나타냅니다. 맨 처음, 즉 아무 분류가 이루어지지 않았을 때는 모두가 같은 값을 가지게 됩니다.
Sample Weight = $1/m$
m = 전체 샘플의 개수
하지만 이 Sample Weight는 첫 그루터기를 만든 뒤, 다음에는 어떤 데이터에 좀 더 집중을 해야할 지 계산하여 Update를 해주고 이는, 다음 그루터기를 만들 때 영향을 줍니다.
자, 이제 첫 그루터기를 만들어야 합니다. 이를 위해 변수들 중에서 가장 분류를 잘하는 변수를 하나 골라야 합니다. 현재는 Sample Weight가 모두 동일하므로 일단 해당 부분은 무시해보겠습니다.
먼저 Chest Pain으로 분류를 해볼까요?
다음은 Blocked Arteries로 분류해보겠습니다.
마지막으로, Heart Disease로 분류입니다.
Decision Tree에서 사용되는 방법으로 176이 가장 분류를 잘하는 기준이라는 것을 알았습니다.
이 중 Gini Index가 가장 낮은 그루터기는 Weight를 활용한 것입니다. 따라서 해당 그루터기가 숲의 첫 그루터기가 될 것입니다. 이제 이 그루터기가 최종 분류에 얼마나 영향력을 가질 지 알아봐야 합니다. 앞에서 언급했듯이 AdaBoost에서 각 그루터기의 영향력은 다르기에 제대로 조사해야할 필요가 있습니다. 이는 각 그루터기가 sample들을 얼마나 잘 분류해냈는지를 통해 결정합니다.
Weight로 구성한 그루터기에서 Error가 발생한 부분은 No Heart Disease를 잘못 분류한 1가지의 경우밖에 없습니다. ‘Total Error’는 에러가 발생한 sample의 Sample Weight를 나타내므로 이는 1/8이 됩니다.
NOTE: Sample Weights는 총합이 1입니다. 따라서, 완벽하게 잘 분류를 하는 분류기 같은 경우에는 Total Error가 0이 될 것이며, 아무것도 분류하지 못하는 저성능의 분류기는 Total Error가 1이 될 것입니다. 이 Total Error가 최종 분류에 미치는 영향력을 결정하게 될 것입니다. ‘영향력’의 수식은 다음과 같습니다. 식에서 Total Error가 0 또는 1이 되면 식이 난리가 나기 때문에, 대개 작은 error term을 넣어 이런 일이 발생하는 것을 막아줍니다.
위의 식에 Total Error에 해당하는 0~1의 수를 삽입함으로써 다음과 같은 그래프를 그릴 수 있습니다. X축은 Total Error를, Y축은 영향력을 의미합니다.
분류의 수행에 따라 Total Error & 영향력의 변화
그루터기가 분류의 역할을 잘 하여, Total Error가 작으면, 0에 가깝게 되겠고 그렇게 되면 영향력이 증가할 것입니다. 반대의 경우에는 영향력이 감소하겠지요. 또는 동전을 던져서 결정하는 것 만큼의 랜덤성을 갖는다면 Total Error가 0.5에, 그리고 영향력은 0으로 나타날 것입니다.
다시 예시로 돌아가서 우리의 Sample Weight가 1/8이었기에, 영향력 식에 1/8을 삽입하면
다음과 같이 나타날 것입니다. 위의 파란 그래프에 대입해서 영향력을 알아낼 수 있습니다.
다른 예시도 살펴볼까요? 우리는 Gini Index만 살펴보고 다른 그루터기들은 바로 버렸습니다. 하지만 해당 그루터기들에서도 Total Error 또는 영향력을 계산하여 감을 더 잡아보도록 합시다.
Chest Pain은 세 번의 에러를 나타냈습니다. Total Error란 오분류한 sample들의 Sample Weight들을 모두 더하는 것이었으므로,
Total Error = 3/8
이 될 것입니다. 이를 파란 그래프에 적용해본다면, 0에 가까운 수가 나타나며 이는 Weight로 그루터기를 만들었을 때보다 영향력이 적다는 것을 알 수 있습니다.
다시 Sample Weight를 살펴보겠습니다.
기존의 Sample Weight는 8개의 Sample들 간의 차이가 없이 동일합니다. 이는 어떤 Sample을 더 유심히 봐야 하는 지에 대한 강조를 전혀 하지 않을 것입니다.
하지만 우리는 빨간 밑줄이 쳐진 샘플이 오분류 되었음을 알고, 다음 분류 시에 이를 유념하여 더 주의를 두어 분류를 해야합니다. 그리고 그런 주의를 강조해두어야 합나다. 따라서 해당 Row의 Sample Weight를 증가시키고, 다른 정분류된 Row의 Sample Weight를 감소시켜야 합니다. 잘 맞춘 것은 굳이 주의깊게 볼 필요가 적어지기 때문이지요.
오분류된 Sample Weight를 증가시키기 위한 식입니다.
이 식이 어떻게 Sample Weight를 변화시킬 수 있는 지 역시 살펴봐야 합니다.
직전의 그루터기가 꽤 일을 잘해서 분류를 잘했고, 그에 따라 영향력이 높다, Sample Weight에 곱하게 될 가중치인 y축의 값이 증가하게 됩니다.
자 이제 줄일 놈들을 줄여보도록 할까요?
영향력이 비교적 크다면, Sample Weight를 0에 가까운 수로 곱해줍니다. 그렇다면 해당 Sample Weight는 0으로 없어지겠으며, 이는 해당 Sample은 더이상 보지 말라는 뜻이 됩니다.
정규화 후
자 이제 새로운 Sample Weight를 구축했으니, 이를 활용하여 두번째 그루터기를 만들 수 있습니다. 이론상으론 Sample Weight를 사용해 Weighted Gini Index를 만들고 다음 그루터기에서 어떤 변수로 분류를 해야할 지 알 수 있습니다. Weighted Gini Index는 이전 그루터기에서 오분류한 Sample이 Sample Weight가 높으므로 더 강조하여 분류하게 될 것입니다.
이런 Weighted Gini Index를 사용하는 대신에, Sample Weights를 사용하여, 숫자가 높은 Sample이 더 많이 추출될 수 있는 복원 추출을 사용하여 새로운 Sample Set을 구성할 수 있습니다. 복원 추출 시, Sample Weights를 추출 확률의 분포로서 활용하게 됩니다.
Random Number를 하나 뽑고, 해당 숫자가 위 사진에서
여러 분류기 중 이 4개는 Sample들을 심장병이 있는 것으로,
이들은 없는 것으
최종적으로 영향력의 합이 높은 분류기들이 낸 결과를 최종 분류의 결과로 정의한다!