부스팅(Boosting)은 배깅(Bagging)과 마찬가지로 간단하면서도 성능이 높은 앙상블 기법이다. 우리는 편향-분산 트레이드오프 관계에서 확인했듯이 모델로 인해 발생하는 오류를 편향 성분과 분산 성분으로 나눌 수 있었다. Bagging이 분산 성분을 줄여서 모델의 오류를 줄이는 방식이라면, Boosting은 편향 성분을 줄이는 방식이라 할 수 있다.

Boosting이 Bagging과 어떤 면에서 차이가 있는지를 먼저 짚고 넘어가야 한다. 간단하게 표현하자면, Boosting은 모델을 Sequential 하게 생성하여 성능을 높이는 앙상블 기법이고 Bagging은 모델을 Parallel 하게 생성하여 성능을 높이는 앙상블 기법이다.

CF

그림과 같이 Bagging은 서로 독립적인 모델을 생성하고 이렇게 생성한 여러개의 모델의 평균/투표 방식으로 예측을 진행한다. 이 때, 평균을 구하는 과정에서 분산 성분의 오류를 줄이는 것이라 할 수 있다.

반면, Boosting은 Bagging과 달리 모델 간의 상호연관성이 있다. Boosting은 이전 모델의 학습 결과를 바탕으로 잘못 분류된 데이터를 더 잘 맞추기 위해 잘못 분류된 데이터에 대해 더 높은 가중치를 주게 되고 이를 바탕으로 모델의 편향 성분을 줄여나가는 방식의 학습을 진행한다. 즉, 처음에 활용되는 약한 분류기(weak classifier)를 점차 보완하여 결국 강한 분류기(strong classifier)를 만들어내는 앙상블 기법이라 할 수 있다.

AdaBoost

에이다부스트(AdaBoost)는 가장 빈번하게 사용되는 Boosting 알고리즘 중 하나다. AdaBoost 알고리즘이 어떻게 진행되는지 다음의 수식들을 통해 살펴보도록 하자.

2가지 클래스를 분류하는 경우 \(y_{n} \in \{-1,1\}\) 를 가정하자. 훈련 데이터셋 \(\mathbf{X}=\{x_{1},...,x_{N}\}\), 타깃 변수 \(\mathbf{Y} = \{y_{1},...,y_{N}\}\) 형태로 존재한다고 하자. 그리고 각 데이터에 대해 가중치 \(w_{n} = \frac{1}{N}\) 를 초기값으로 설정하자.

AdaBoost의 각 단계에서 이 가중치 \(w_{n}\)을 수정하여 모델을 업데이트 한다. 그리고 앞서 언급했던 것처럼 기존 모델에서 틀린 예측값을 기록한 데이터에 대해 가중치를 증가하는 방향으로 업데이트를 진행한다. 모델을 총 M회 업데이트 한다고 생각하자. 먼저 가중치 \(w_{n}\)의 초기값을 다음과 같이 \(w_{n}^{(1)}=\frac{1}{N}\) 로 설정한다.

이후, 다음의 오류함수를 최소화시키는 모델 \(f_{m}(\mathbf{X})\) 를 훈련 데이터에 적용한다.

\[J_{m} = \sum_{n=1}^{N}w_{n}^{(m)}\mathbb{I}(f_{m}(x_{n}) \neq y_{n})\]

다음의 값 \(\epsilon_{m}, \alpha_{m}\)을 계산한다.

\[\begin{align} \epsilon_{m} &= \frac{\sum_{n=1}^{N}w_{n}^{(m)}\mathbb{I}(f_{m}(x_{n}) \neq y_{n})}{\sum_{n=1}^{N}w_{n}^{(m)}} \nonumber \\ \alpha_{m} &= \log{\frac{1-\epsilon_{m}}{\epsilon_{m}}} \nonumber \end{align}\]

\(\epsilon_{m}\) 값은 각 모델의 데이터셋에 대한 가중 오류율을 의미하며, 이를 바탕으로 계산하는 \(\alpha_{m}\) 값은 오류율이 낮은, 즉 더 정확한 모델에 대해 더 큰 값을 가지게 될 것이다.

가중치 \(w_{n}^{(m)}\) 을 다음과 같이 업데이트 한다.

\[w_{n}^{(m+1)} = w_{n}^{(m)}\text{exp}\{\alpha_{m}\mathbb{I}(f_{m}(x_{n}) \neq y_{n})\}\]

우리는 이 식을 통해서 가중치 \(w_{n}^{(m)}\) 값이 잘못 분류된 것으로 판별되는 데이터 포인트에 대해 상승하고, 옳게 분류된 것으로 판별되는 데이터 포인트에 대해서는 변동하지 않음을 확인할 수 있다.

최종적으로 다음과 같이 예측을 진행한다. 이는 각 모델에 대해 서로 다른 가중치를 부여하여 값을 도출하는 방식으로 모든 모델이 평등하게 1표씩 행사하는 Bagging의 방식과는 다르다고 할 수 있다.

\[F_{M}(\mathbf{X}) = \text{sign}\left(\sum_{m=1}^{M}\alpha_{m}y_{m}(\mathbf{X})\right)\]

AdaBoost를 그림으로 표현하자면 아래의 그림과 같다.

CF

검정색 점선은 모델은 \(m\)번째 학습 시, 결정되는 결정 경계(hyperplane)라 할 수 있고 녹색 실선은 \(m\)번째 시행까지 생성된 모델들의 조합이 만들어낸 결정 경계라 할 수 있다. 이 그림에서 각 데이터 포인트에 대한 가중치는 원으로 표현되며 우리는 \(m\)차 학습 시, 잘못 분류된 것으로 간주되는 포인트들의 가중치가 커지는 것을 확인할 수 있다.

Gradient Boosting

Gradient Boosting은 간단히 잔차(이하 residual)에 대한 fitting을 통해 모델을 만들어가는 과정이라 받아들일 수 있다.

CF

Gradient Boosting은 그림과 같이 첫번째 tree 모델을 통해 예측을 진행하고 여기서 발생한 residual에 대해 두번째 tree 모델을 활용해서 fitting을 한다. 세번째 tree 모델은 2번째 과정에서 발생한 residual에 대해 fitting을 진행한다. 기존 모델의 residual에 fitting하면서 모델을 생성하고 각 모델을 합쳐서 강한 모델을 만드는 것이 Gradient Boosting의 과정이라 할 수 있다.

residual을 사용하는 것과 gradient는 무슨 관계일까? 간단한 이해를 위해서 예측값 \(F(\mathbf{X})\)와 \(\mathbf{y}\)의 loss-function \(L(\mathbf{y},F(\mathbf{X})\) 가 다음과 같은 오차제곱 형태 \((\mathbf{y}-F(\mathbf{X}))^{2}\) 를 갖는다고 가정하자. 이 때 residual은 다음과 같이 loss-function의 negative gradient 값과 관련이 있다.

\[\frac{\partial L(\mathbf{y},F(\mathbf{X})}{\partial F(\mathbf{X})} = -2(\mathbf{y}-F(\mathbf{X}))\]

모델을 생성하는 과정에서 negative gradient를 사용하기 때문에 gradient boosting이라 불리게 되는 것이며, 이는 오차제곱이 아닌 다른 형태의 loss-function을 사용하더라도 negative gradient가 사용되는 것은 분명하기에 Gradient Boosting이라 불린다.

조금 더 면밀하게 수식적인 부분을 통해 살펴보자면, Gradient Boosting은 다음과 같다. 데이터셋이 \(\{x_{1},y_{1}\} \cdot\cdot\cdot \{x_{N},y_{N}\}\) 의 형태로 존재한다면, 우리는 임의의 loss-function \(L(\mathbf{y},F(\mathbf{X})\) 값을 최소화시킬 수 있는 함수 \(\hat{F}(\mathbf{X})\) 를 발견해야 한다.

\[\hat{F} = \text{argmin}_{F}\mathbb{E}[L(\mathbf{y},F(\mathbf{X}))]\]

Gradient Boosting은 아래와 같이 이전 단계의 모델 \(F_{m-1}(\mathbf{X})\) 에 \(h_{m}(\mathbf{X})\) 의 가중합으로 다음 현재 단계의 모델 \(F_{m}(\mathbf{X})\) 가 생성되는 것으로 가정한다.

\[F_{m}(\mathbf{X}) = F_{m-1}(\mathbf{X}) + w_{m}h_{m}(\mathbf{X})\]

여기서 우리가 \(F_{0}(\mathbf{X}) = 0\) 또는 \(F_{0}(\mathbf{X}) = \bar{\mathbf{y}}\) 형태를 가정하면 최종 \(M\)번째 단계 모델은 아래와 같이 표현할 수 있다.

\[F_{M}(\mathbf{X}) = \sum_{m=1}^{M}w_{m}h_{m}(\mathbf{X}) + \text{constant}\]

여기서 우리는 최적의 모델을 찾기 위해 가중치 \(\omega = \{w_{1},....,w_{M}\}\) 와 함수 \(h\) 에 활용되는 parameter \(\Theta = \{\theta_{1},...,\theta_{M}\}\) 을 최적화시켜야 한다. 그런데 두가지 변수를 동시에 최적화하는 것은 어려운 일이므로 단계적으로 하나의 parameter씩 최적화시키는 전략을 취한다.

결과적으로 Gradient Boosting의 진행 절차는 다음과 같다.

  • 초기 모델 \(F_{0}(\mathbf{X}) = 0\) 또는 \(F_{0}(\mathbf{X}) = \bar{\mathbf{y}}\) 로 설정한다.

  • 다음의 pseudo-residual을 계산한다.

\[r_{m,i} = -\frac{\partial L(y_{i},F_{m-1}(x_{i}))}{\partial F_{m-1}(x_{i})}\]

  • \(h_{m}(\mathbf{X})\) 를 pseudo-residual \(\mathbf{r}_{m} = \{r_{m,1},...,r_{m,N} \}\) 에 fitting 한다.

  • 이제는 \(h_{m}(\mathbf{X})\) 에 활용될 가중치 \(w_{m}\) 값을 다음과 같이 계산한다.

\[w_{m} = \text{argmin}_{w} \sum_{i=1}^{N} L(y_{i}, F_{m-1}(x_{i})+wh_{m}(\mathbf{X}))\]
  • 앞선 과정을 통해 구한 \(w_{m}\) 값과 \(h_{m}(\mathbf{X}\) 를 이용하여 모델을 업데이트 한다.
\[F_{m}(\mathbf{X}) = F_{m-1}(\mathbf{X}) + w_{m}h_{m}(\mathbf{X})\]

이처럼 Boosting 기법은 residual에 모델을 fitting 해감으로써 전체적인 모델의 bias를 줄여 모델의 오류를 줄이는 방법이라 할 수 있다.

참조 문헌

  1. PRML

  2. 위키피디아