부스팅(Boosting)과 Adaboost(Adaptive Boosting)
20 Mar 2021 | Machine-Learning
해당 게시물은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.
Boosting
이번에는 앙상블 방법 중 하나인 부스팅(Boosting)에 대해서 알아보고 부스팅의 시초격인 Adaboost(Adaptive Boosting)에 대해서 알아보도록 하겠습니다.
Weak Model
부스팅을 이해하기 위해서는 약한 모델(Weak Model)에 대해서 알아야 합니다. 약한 모델이란 말 그대로 성능이 낮은 모델을 가리킵니다. 약한 모델의 성능은 랜덤 추측(Random guessing)보다 약간 더 나은 수준이지요. 예를 들어, 이진 분류라면 랜덤 추측의 정확도는 약 $50\%$ 가 될 텐데요. 약한 모델의 정확도는 $60\%$ 정도가 되는 수준입니다. 우리가 성능 좋은 모델이라고 일컫는 $80\%$ 이상의 정확도를 보이는 모델보다는 확실히 성능이 떨어지지요.
부스팅은 약한 모델을 결합하면 임의의 강한 모델의 성능 이상으로 끌어올릴(Boosting) 수 있지 않을까 하는 아이디어에서 시작되었습니다. 먼저 약한 모델을 만든 후에 학습 결과를 바탕으로 이를 보완해 줄 수 있는 모델을 반복해서 생성합니다. 그리고 최종적으로 이를 결합한 모델을 만들어내지요. 잠시 다른 이야기로 빠져보겠습니다.
Weighted on wrong cases
학창 시절에 오답 노트를 만들어 보신 적이 있으신가요? 오답 노트는 틀린 문제를 모아 놓는 노트인데요. 완벽히 알고 푼 문제라면 다음에 다시 볼 필요가 없습니다. 틀린 문제를 중심으로 학습해야 점수가 오르겠지요. 예를 들어, 수능수학 범위에서 공부를 하다보니 ‘확률과 통계’ 단원이 약한 학생은 해당 단원의 문제가 오답 노트에 모입니다. 오답노트로 공부하다 보니 통계 단원은 금방 학습했는데 ‘확률’은 계속 틀립니다. ‘확률’ 단원의 문제가 계속 오답 노트에 모이게 되고 이를 바탕으로 학습하다 보니 이번에는 ‘중복조합’ 관련 문제를 계속 틀리네요. 이 학생은 이제 전체 수학에서 ‘중복조합’만 공부하면 되는 학생이 될 것입니다.
갑자기 이런 이유를 하는 이유는 부스팅 알고리즘이 학습하는 이유도 이와 유사하기 때문입니다. 일단 첫 번째 약한 모델이 학습 결과를 내놓으면 이를 바탕으로 오답 노트를 만듭니다. 두 번째 모델은 오답 노트를 바탕으로 공부하게 되며 이런 과정을 계속 반복하게 됩니다. 이와 같이 순차적으로 진행되기 때문에 병렬 처리(Parallel processing)가 불가능하다는 단점을 가지고 있습니다. 다만 Stump tree(결정 경계를 하나만 형성하는 의사 결정 나무)와 같은 약한 모델을 기반으로 하므로 결정 경계가 없어도 복잡도가 높은 모델을 사용하는 배깅보다 빠르게 학습이 진행되곤 합니다.
이미지 출처 : quantdare.com
Adaboost
Adaboost는 여러 부스팅 알고리즘 중에서 초기에 사용된 알고리즘 중 하나입니다. 해당 알고리즘은 틀리게 예측한 인스턴스에 가중치(Weight)를 부여한다는 아이디어를 기본으로 하고 있습니다. 특이한 점은 이진 분류 문제에서 레이블을 ${0, 1}$ 이 아니라 ${-1, 1}$ 로 구분한다는 것인데요. 이는 서포트 벡터 머신에서도 그랬듯이 알고리즘에서 사용되는 수식 때문입니다. 일단 이렇게 구분한다는 것만 염두에 두고 설명을 이어나가도록 하겠습니다.
가장 먼저 데이터셋을 준비합니다. 부스팅의 첫 번째 데이터셋은 배깅처럼 균일한 분포 $D_1(i)$ 로 구성합니다. 샘플링은 비복원 추출(Sampling without replacement)을 기본으로 하지만 복원 추출을 사용해도 됩니다. 이렇게 구성된 데이터셋을 바탕으로 학습을 진행하지요. $t(단, 1 \leq t \leq T)$ 번째 모델 $h_t$ 는 분포가 $D_t(i)$ 를 바탕으로 학습합니다. 일반적으로 약한 모델로는 Stump tree를 사용합니다.
$h_t$ 가 결과를 내놓으면 이를 바탕으로 $\epsilon_t$ 과 $\alpha_t$ 를 계산합니다. $\epsilon_t$ 는 훈련 데이터셋 중에서 $h_t$ 가 틀리게 판단한 데이터의 비율입니다. 예를 들어, 10개의 데이터 중 3개를 잘못 판단했다면 $\epsilon = 0.3$ 이 됩니다. 그리고 이 값을 아래 식에 대입하여 가중치 $\alpha_t$ 를 구합니다. (참고로 랜덤 추측보다 성능이 떨어질 경우 $\epsilon > 0.5$는 break 됩니다.)
\[\alpha_t = \frac{1}{2} \ln \bigg(\frac{1 - \epsilon}{\epsilon}\bigg)\]
$\alpha_t$ 값에 대해 좀 더 탐색해보겠습니다. 만약 $\epsilon_t \approx 0$, 즉 거의 모든 데이터가 제대로 판단되었다면 $\alpha_t$ 값은 매우 커지게 됩니다. 반대로 $e_t \approx 0.5$, 즉 랜덤 추측과 비슷한 상태라면 $\alpha_t$ 의 값은 $0$ 에 가까워지지요. 이렇게 구해진 $\alpha_t$ 는 $t+1$ 번째 학습에 사용될 데이터의 분포를 구하는 데 사용됩니다. $t+1$ 번째 학습에 사용될 데이터의 분포 $D_{t+1}(i)$ 는 다음과 같습니다.
\[D_{t+1}(i) = \frac{D_t(i) \exp(-\alpha_t y_i h_t(x_i))}{Z_t}\]
위 식에서 $Z_t$ 는 정규화를 위한 상수입니다. 분자의 각 항에 대해서 어떤 것을 의미하는 지 알아보겠습니다. 먼저 첫 번째 항은 $D_t(i)$ 입니다 $t+1$ 번째 데이터셋의 분포는 $t$ 번째 학습 데이터셋을 기반으로 함을 알 수 있습니다. 다음으로 $\exp$ 내에 있는 값을 하나씩 살펴보겠습니다. 일단 $\alpha_t$ 가 앞에 있네요. 해당 값에 대해서는 위에서 알아보았습니다. 마지막은 $y_ih_t(x_i)$ 입니다. 이 항은 ${-1, 1}$ 의 2가지 값을 가질 수 있습니다. 아래 수식을 보겠습니다.
\[y_ih_t(x_i) =
\begin{cases}
1 \qquad &\text{if} \quad y_i = h_t(x_i) \\
-1 \qquad &\text{if} \quad y_i \neq h_t(x_i)
\end{cases}\]
이 항은 정답 레이블과 예측 레이블 $(y_i, h_t(x_i))$ 이 동일한 경우 $(1,1) \text{ or } (-1,-1)$ 에는 $1$ 이 됩니다. 반대로 예측 레이블이 정답 레이블과 $(1,-1) \text{ or } (-1,1)$ 처럼 다르면 $-1$ 값을 나타내지요. 이제 $\exp(-\alpha_t y_i h_t(x_i))$ 값이 어떻게 변하는지 예측해 볼 수 있습니다. 아래 표를
일단은 틀리게 판단한 인스턴스에는 무조건 1보다 큰 값을 곱합니다. 그렇게 판단한 분류기가 성능이 좋을 수록 이 가중치는 커지게 되지요. 이런 인스턴스는 다음 분포에 포함될 확률이 높아집니다. 반대로 맞춘 인스턴스는 무조건 1보다 작은 값이 곱해집니다. 성능 좋은 분류기가 맞춘 경우에는 거의 0에 가까운 값이 곱해지며 다음 데이터셋에는 거의 포함될 확률이 낮아집니다.
이 과정을 $T$ 번 반복한 다음에는 각 단계에서 구해진 가중치 $\alpha_t$ 와 예측 레이블 $h_t(x)$ 를 모두 더하여 최종 레이블을 결정합니다. 즉 새로운 테스트 데이터 $(x^\prime, y^\prime)$ 에 대한 예측값은 아래와 같이 구합니다.
\[H(x^\prime) = \text{sign}\bigg(\sum^T_{t=1} \alpha_t h_t(x^\prime)\bigg)\]
Example
사실 글로만 이해하기에는 복잡한 알고리즘입니다. 예시를 바탕으로 Adaboost가 어떻게 작동하는 지 알아보도록 하겠습니다. 아래는 첫 번째 데이터셋의 분포인 $D_1$ 과 첫 번째 Stump tree인 $h_1$ 을 나타내고 있습니다. 그리고 이 결과에 따라 다음 데이터셋의 분포 $D_2$ 가 변하는 모습도 보여주고 있습니다.
이미지 출처 : cse.buffalo.edu
총 10개의 인스턴스 중 $h_1$ 이 잘못 판단한 인스턴스가 3개이므로 $\epsilon_1 = 3/10 = 0.3$ 입니다. 그리고 이를 대입하여 구하면 $\alpha_1 = 0.42$ 가 됩니다. $(e^{0.42} = 1.52, e^{-0.42} = 0.66)$ 이므로 정답과 예측 레이블이 일치하는 7개의 인스턴스는 $D_2$ 에서 덜 $(\times 0.66)$ 중요하게 샘플링되고, 불일치하는 3개의 인스턴스는 더 $(\times 1.52)$ 중요하게 샘플링됩니다.
이미지 출처 : cse.buffalo.edu
두 번째 결과에 대해서도 마찬가지로 판단합니다. 대신 2번째 부터는 가중치가 부여되어 추출되었으므로 정확히 개수로는 판단할 수 없고 위와 같은 결과 $\epsilon_2 = 0.21, \alpha_2 = 0.65$ 가 나왔다고 하겠습니다. $(e^{0.65} = 1.92, e^{-0.65} = 0.52)$ 이므로 정답과 예측 레이블이 일치하는 인스턴스는 $D_3$ 에서 덜 $(\times 0.52)$ 중요하게 샘플링되고, 불일치하는 인스턴스는 더 $(\times 1.91)$ 중요하게 샘플링됩니다.
이미지 출처 : cse.buffalo.edu
두 번째 결과에 대해서도 마찬가지로 판단합니다. 이 3개의 결과를 조합하면 다음과 같은 결정 경계가 만들어집니다.
이미지 출처 : cse.buffalo.edu
3개의 약한 모델(여기서는 Stump tree)을 결합하여 그럴듯한 결정 경계를 만들어냈습니다. 이 과정을 반복하면 다음과 더욱 정확한 모델을 만들어 낼 수 있습니다. 아래는 해당 과정을 50번 반복하면서 만들어지는 결정 경계를 시각화한 동영상입니다. 50번의 반복으로 비선형 결정 경계를 만든 것을 확인할 수 있습니다.
이미지 출처 : gfycat.com
Conclusion
이상으로 부스팅 알고리즘의 개요와 부스팅 알고리즘 중 하나인 Adaboost에 대해 알아보았습니다. 틀린 인스턴스에 가중치를 부여한다는 다소 간단한 아이디어를 적용했음에도 딥러닝 기법이 나오기 전까지 실시간 얼굴 추적(Real-time Face detection) 등 다양한 곳에 사용된 뛰어난 기법이기도 합니다. 다음 시간에는 새로운 부스팅 기법이자 XGBoost, LightGBM, CatBoost 등 최근 좋은 성능을 보이는 부스팅 알고리즘의 기반이 되는 그래디언트 부스팅 머신(Gradient Boosting Machine, GBM)에 대해 알아보도록 하겠습니다.
해당 게시물은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.
Boosting
이번에는 앙상블 방법 중 하나인 부스팅(Boosting)에 대해서 알아보고 부스팅의 시초격인 Adaboost(Adaptive Boosting)에 대해서 알아보도록 하겠습니다.
Weak Model
부스팅을 이해하기 위해서는 약한 모델(Weak Model)에 대해서 알아야 합니다. 약한 모델이란 말 그대로 성능이 낮은 모델을 가리킵니다. 약한 모델의 성능은 랜덤 추측(Random guessing)보다 약간 더 나은 수준이지요. 예를 들어, 이진 분류라면 랜덤 추측의 정확도는 약 $50\%$ 가 될 텐데요. 약한 모델의 정확도는 $60\%$ 정도가 되는 수준입니다. 우리가 성능 좋은 모델이라고 일컫는 $80\%$ 이상의 정확도를 보이는 모델보다는 확실히 성능이 떨어지지요.
부스팅은 약한 모델을 결합하면 임의의 강한 모델의 성능 이상으로 끌어올릴(Boosting) 수 있지 않을까 하는 아이디어에서 시작되었습니다. 먼저 약한 모델을 만든 후에 학습 결과를 바탕으로 이를 보완해 줄 수 있는 모델을 반복해서 생성합니다. 그리고 최종적으로 이를 결합한 모델을 만들어내지요. 잠시 다른 이야기로 빠져보겠습니다.
Weighted on wrong cases
학창 시절에 오답 노트를 만들어 보신 적이 있으신가요? 오답 노트는 틀린 문제를 모아 놓는 노트인데요. 완벽히 알고 푼 문제라면 다음에 다시 볼 필요가 없습니다. 틀린 문제를 중심으로 학습해야 점수가 오르겠지요. 예를 들어, 수능수학 범위에서 공부를 하다보니 ‘확률과 통계’ 단원이 약한 학생은 해당 단원의 문제가 오답 노트에 모입니다. 오답노트로 공부하다 보니 통계 단원은 금방 학습했는데 ‘확률’은 계속 틀립니다. ‘확률’ 단원의 문제가 계속 오답 노트에 모이게 되고 이를 바탕으로 학습하다 보니 이번에는 ‘중복조합’ 관련 문제를 계속 틀리네요. 이 학생은 이제 전체 수학에서 ‘중복조합’만 공부하면 되는 학생이 될 것입니다.
갑자기 이런 이유를 하는 이유는 부스팅 알고리즘이 학습하는 이유도 이와 유사하기 때문입니다. 일단 첫 번째 약한 모델이 학습 결과를 내놓으면 이를 바탕으로 오답 노트를 만듭니다. 두 번째 모델은 오답 노트를 바탕으로 공부하게 되며 이런 과정을 계속 반복하게 됩니다. 이와 같이 순차적으로 진행되기 때문에 병렬 처리(Parallel processing)가 불가능하다는 단점을 가지고 있습니다. 다만 Stump tree(결정 경계를 하나만 형성하는 의사 결정 나무)와 같은 약한 모델을 기반으로 하므로 결정 경계가 없어도 복잡도가 높은 모델을 사용하는 배깅보다 빠르게 학습이 진행되곤 합니다.
이미지 출처 : quantdare.com
Adaboost
Adaboost는 여러 부스팅 알고리즘 중에서 초기에 사용된 알고리즘 중 하나입니다. 해당 알고리즘은 틀리게 예측한 인스턴스에 가중치(Weight)를 부여한다는 아이디어를 기본으로 하고 있습니다. 특이한 점은 이진 분류 문제에서 레이블을 ${0, 1}$ 이 아니라 ${-1, 1}$ 로 구분한다는 것인데요. 이는 서포트 벡터 머신에서도 그랬듯이 알고리즘에서 사용되는 수식 때문입니다. 일단 이렇게 구분한다는 것만 염두에 두고 설명을 이어나가도록 하겠습니다.
가장 먼저 데이터셋을 준비합니다. 부스팅의 첫 번째 데이터셋은 배깅처럼 균일한 분포 $D_1(i)$ 로 구성합니다. 샘플링은 비복원 추출(Sampling without replacement)을 기본으로 하지만 복원 추출을 사용해도 됩니다. 이렇게 구성된 데이터셋을 바탕으로 학습을 진행하지요. $t(단, 1 \leq t \leq T)$ 번째 모델 $h_t$ 는 분포가 $D_t(i)$ 를 바탕으로 학습합니다. 일반적으로 약한 모델로는 Stump tree를 사용합니다.
$h_t$ 가 결과를 내놓으면 이를 바탕으로 $\epsilon_t$ 과 $\alpha_t$ 를 계산합니다. $\epsilon_t$ 는 훈련 데이터셋 중에서 $h_t$ 가 틀리게 판단한 데이터의 비율입니다. 예를 들어, 10개의 데이터 중 3개를 잘못 판단했다면 $\epsilon = 0.3$ 이 됩니다. 그리고 이 값을 아래 식에 대입하여 가중치 $\alpha_t$ 를 구합니다. (참고로 랜덤 추측보다 성능이 떨어질 경우 $\epsilon > 0.5$는 break 됩니다.)
$\alpha_t$ 값에 대해 좀 더 탐색해보겠습니다. 만약 $\epsilon_t \approx 0$, 즉 거의 모든 데이터가 제대로 판단되었다면 $\alpha_t$ 값은 매우 커지게 됩니다. 반대로 $e_t \approx 0.5$, 즉 랜덤 추측과 비슷한 상태라면 $\alpha_t$ 의 값은 $0$ 에 가까워지지요. 이렇게 구해진 $\alpha_t$ 는 $t+1$ 번째 학습에 사용될 데이터의 분포를 구하는 데 사용됩니다. $t+1$ 번째 학습에 사용될 데이터의 분포 $D_{t+1}(i)$ 는 다음과 같습니다.
\[D_{t+1}(i) = \frac{D_t(i) \exp(-\alpha_t y_i h_t(x_i))}{Z_t}\]위 식에서 $Z_t$ 는 정규화를 위한 상수입니다. 분자의 각 항에 대해서 어떤 것을 의미하는 지 알아보겠습니다. 먼저 첫 번째 항은 $D_t(i)$ 입니다 $t+1$ 번째 데이터셋의 분포는 $t$ 번째 학습 데이터셋을 기반으로 함을 알 수 있습니다. 다음으로 $\exp$ 내에 있는 값을 하나씩 살펴보겠습니다. 일단 $\alpha_t$ 가 앞에 있네요. 해당 값에 대해서는 위에서 알아보았습니다. 마지막은 $y_ih_t(x_i)$ 입니다. 이 항은 ${-1, 1}$ 의 2가지 값을 가질 수 있습니다. 아래 수식을 보겠습니다.
\[y_ih_t(x_i) = \begin{cases} 1 \qquad &\text{if} \quad y_i = h_t(x_i) \\ -1 \qquad &\text{if} \quad y_i \neq h_t(x_i) \end{cases}\]이 항은 정답 레이블과 예측 레이블 $(y_i, h_t(x_i))$ 이 동일한 경우 $(1,1) \text{ or } (-1,-1)$ 에는 $1$ 이 됩니다. 반대로 예측 레이블이 정답 레이블과 $(1,-1) \text{ or } (-1,1)$ 처럼 다르면 $-1$ 값을 나타내지요. 이제 $\exp(-\alpha_t y_i h_t(x_i))$ 값이 어떻게 변하는지 예측해 볼 수 있습니다. 아래 표를
일단은 틀리게 판단한 인스턴스에는 무조건 1보다 큰 값을 곱합니다. 그렇게 판단한 분류기가 성능이 좋을 수록 이 가중치는 커지게 되지요. 이런 인스턴스는 다음 분포에 포함될 확률이 높아집니다. 반대로 맞춘 인스턴스는 무조건 1보다 작은 값이 곱해집니다. 성능 좋은 분류기가 맞춘 경우에는 거의 0에 가까운 값이 곱해지며 다음 데이터셋에는 거의 포함될 확률이 낮아집니다.
이 과정을 $T$ 번 반복한 다음에는 각 단계에서 구해진 가중치 $\alpha_t$ 와 예측 레이블 $h_t(x)$ 를 모두 더하여 최종 레이블을 결정합니다. 즉 새로운 테스트 데이터 $(x^\prime, y^\prime)$ 에 대한 예측값은 아래와 같이 구합니다.
\[H(x^\prime) = \text{sign}\bigg(\sum^T_{t=1} \alpha_t h_t(x^\prime)\bigg)\]Example
사실 글로만 이해하기에는 복잡한 알고리즘입니다. 예시를 바탕으로 Adaboost가 어떻게 작동하는 지 알아보도록 하겠습니다. 아래는 첫 번째 데이터셋의 분포인 $D_1$ 과 첫 번째 Stump tree인 $h_1$ 을 나타내고 있습니다. 그리고 이 결과에 따라 다음 데이터셋의 분포 $D_2$ 가 변하는 모습도 보여주고 있습니다.
이미지 출처 : cse.buffalo.edu
총 10개의 인스턴스 중 $h_1$ 이 잘못 판단한 인스턴스가 3개이므로 $\epsilon_1 = 3/10 = 0.3$ 입니다. 그리고 이를 대입하여 구하면 $\alpha_1 = 0.42$ 가 됩니다. $(e^{0.42} = 1.52, e^{-0.42} = 0.66)$ 이므로 정답과 예측 레이블이 일치하는 7개의 인스턴스는 $D_2$ 에서 덜 $(\times 0.66)$ 중요하게 샘플링되고, 불일치하는 3개의 인스턴스는 더 $(\times 1.52)$ 중요하게 샘플링됩니다.
이미지 출처 : cse.buffalo.edu
두 번째 결과에 대해서도 마찬가지로 판단합니다. 대신 2번째 부터는 가중치가 부여되어 추출되었으므로 정확히 개수로는 판단할 수 없고 위와 같은 결과 $\epsilon_2 = 0.21, \alpha_2 = 0.65$ 가 나왔다고 하겠습니다. $(e^{0.65} = 1.92, e^{-0.65} = 0.52)$ 이므로 정답과 예측 레이블이 일치하는 인스턴스는 $D_3$ 에서 덜 $(\times 0.52)$ 중요하게 샘플링되고, 불일치하는 인스턴스는 더 $(\times 1.91)$ 중요하게 샘플링됩니다.
이미지 출처 : cse.buffalo.edu
두 번째 결과에 대해서도 마찬가지로 판단합니다. 이 3개의 결과를 조합하면 다음과 같은 결정 경계가 만들어집니다.
이미지 출처 : cse.buffalo.edu
3개의 약한 모델(여기서는 Stump tree)을 결합하여 그럴듯한 결정 경계를 만들어냈습니다. 이 과정을 반복하면 다음과 더욱 정확한 모델을 만들어 낼 수 있습니다. 아래는 해당 과정을 50번 반복하면서 만들어지는 결정 경계를 시각화한 동영상입니다. 50번의 반복으로 비선형 결정 경계를 만든 것을 확인할 수 있습니다.
이미지 출처 : gfycat.com
Conclusion
이상으로 부스팅 알고리즘의 개요와 부스팅 알고리즘 중 하나인 Adaboost에 대해 알아보았습니다. 틀린 인스턴스에 가중치를 부여한다는 다소 간단한 아이디어를 적용했음에도 딥러닝 기법이 나오기 전까지 실시간 얼굴 추적(Real-time Face detection) 등 다양한 곳에 사용된 뛰어난 기법이기도 합니다. 다음 시간에는 새로운 부스팅 기법이자 XGBoost, LightGBM, CatBoost 등 최근 좋은 성능을 보이는 부스팅 알고리즘의 기반이 되는 그래디언트 부스팅 머신(Gradient Boosting Machine, GBM)에 대해 알아보도록 하겠습니다.
Comments