Advanced Machine Learning 7 - Ensemble

Before starting

“Class” 카테고리에 있는 포스팅들은 실제로 수업에서 배운 내용을 정리하려는 목적으로 작성되었다. 이 글은 그 중 Advanced Machine Learning 과목의 수업을 다룬다.

Ensemble

우리가 지금까지 본 모델들은 전부 다 단일 모델들이고, 각각은 너무 단순해서 한계가 있었다. 그래서 이러한 모델들을 합쳐서 하나의 모델을 구성하려는 시도가 있었는데, 이것을 Ensemble이라고 한다. 이렇게 합쳐진 모델들은 초창기의 Neural Networks보다 성능이 뛰어났었고, 지금도 특정 환경에서는 딥러닝 모델보다 좋은 성능을 내기도 한다.

이번 글에서는 Ensemble의 대표적인 두 가지 방법인 Bagging과 Boosting에 대해서 알아볼 것이다.

Bagging

Bagging은 Bootstrap Aggregating의 약자이다. Bootstrap이란 단어에는 여러 가지 뜻이 있지만, 여기서는 통계학에서 사용하는 “복원 추출 Sampling”을 뜻한다. 그 이름 그대로, 주어진 데이터셋 $D=\lbrace (x_1,y_1),\ldots,(x_n,y_n) \rbrace$에서 $n$개를 뽑는 복원 추출을 $m$회 시행한다. 이렇게 나온 데이터셋들을 각각 $D_i,i=1,\ldots,m$이라고 하자. 이제 이들 각각을 사용하여 동일한 클래스에서 온 모델 $h_i,i=1,\ldots,m$을 훈련시킨다.

그 후 이 각각의 $h_i$들의 표본평균으로 최종 예측값을 구하는 것이다. 즉, 만일 Regression 문제라면 $\hat{h}(x)=\dfrac{1}{m}\sum\limits_{i=1}^{m}h_i(x)$가 될 것이고, Classification 문제라면 $\hat{h}(x)=sign(\dfrac{1}{m}\sum\limits_{i=1}^{m}h_i(x))$, 혹은 $\hat{h}(x)=sign(\dfrac{1}{m}\sum\limits_{i=1}^{m}sign(h_i(x)))$가 될 것이다. 후자의 경우를 “Majority Vote”라고 부른다.

Variance Analysis

그러면 Bagging의 효과를 알아보기 위해 이전에 봤던 Bias와 Variance를 확인해보자.

\[Bias[\hat{h}(x)]=h(x)-\mathbb{E}[\hat{h}(x)]\] \[Variance[\hat{h}(x)]=\mathbb{E}\left[(\hat{h}(x)-\mathbb{E}[\hat{h}(x)])^2\right]\]

즉, Bias는 Ground Truth $h$와 얼마나 떨어져 있느냐를, Variance는 각각의 예측값이 전체 평균으로부터 얼마나 떨어져 있느냐를 나타낸다.

그런데 Weak Law of Large Numbers에 의해 $m \rightarrow \infty$라면 $\dfrac{1}{m}\sum\limits_{i=1}^{m}x_i \rightarrow \mathbb{E}[x]$가 된다. 즉, $m \rightarrow \infty$라면 Bagging을 통해 최종적으로 구한 $\hat{h}(x)=\dfrac{1}{m}\sum\limits_{i=1}^{m}h_i(x) \rightarrow \bar{h}(x)$가 된다.

그렇기 때문에 이론적으로 보면 Bootstrap한 데이터셋의 개수 $m$이 커질수록 Variance가 0에 수렴하게 된다. 그것도 심지어 Bias는 그대로 두고 Variance만 낮출 수 있다는 이야기가 된다. 물론 이건 이론상의 이야기이고, 실제로는 0에 수렴할 수는 없다. 왜냐하면 Weak Law of Large Numbers가 성립하려면 Random Variable $x$가 모두 같은 분포 $P$에서 왔다는 가정이 필요한데, 우리는 이 분포 $P$ 전체가 아니라 그 중 극히 일부인 데이터셋 $D$밖에 모르기 때문이다. 여기 안에서 아무리 Bootstrapping의 시행 횟수를 늘려봤자 이것이 전체 분포 $P$에서 온 데이터와는 차이가 있을 수 밖에 없다.

그럼에도 불구하고 Variance를 낮추는 효과는 여전히 존재하며, 그것도 매우 효과적으로 낮춘다는 것이 Bagging의 핵심이다.

Out-of-Bag Error

Bagging은 데이터셋을 Bootstrapping, 즉 복원추출해서 일부만을 사용한다. 물론 $m$개의 서브 데이터셋 전부 사용하지 않는 데이터가 있다면 문제가 되지만, 여하튼 각각의 서브 데이터셋은 우리가 갖고 있는 데이터 중 사용하지 않는 것이 있을 수 밖에 없다. 이 데이터를 Out-of-Bag라고 부른다.

그런데 Bagging의 구조를 잘 생각해보면, 각각의 모델 $h_i$는 다른 모델과 독립적이다. 그렇기 때문에 어떤 모델 $h_j$가 훈련에 사용하지 않는 데이터셋은 비록 다른 모델들에서는 사용될 수 있다고 할지라도 그것은 $h_j$와 무관하다. 즉, $h_j$ 입장에서 봤을 때, 이 Out-of-Bag에 들어간 데이터들을 그대로 Validation 용으로 사용해도 무방하다는 것이다. 이 Out-of-Bag 샘플을 사용해 계산한 에러를 Out-of-Bag Error라고 부른다.

이 말을 다시 생각해보면, Bagging 기반의 모델을 훈련시킬 거라면 별도의 Validation Set은 필요없다는 이야기이다. 각각의 Base Model이 훈련에 사용하지 않은 데이터들을 그대로 Validation으로 사용하는 구조로 모든 데이터를 알뜰하게 쓸 수 있기 때문이다.

Random Forest

그렇다면 Bagging을 적용할 Base Model은 어떤 것이 적합할까? Bagging은 Bias를 고정시키고 Variance를 낮추는 효과가 있고, 여기에 사용할 Base Model은 Bias-Variance Trade-off를 따르므로, Bias가 낮고 Variance가 높은 모델을 Base Model로 택할 때 Bagging의 효과가 극대화될 것이다.

그렇기 때문에 앞에서 살펴봤던 Linear Regression, Logistic Regression 등의 단순한 모델은 여기에 넣어봤자 큰 의미가 없다. 이런 단순한 모델들은 Bias가 높고 Variance가 낮기 때문이다. 이러한 관점에서 볼 때, Base Model로 가장 적합한 모델은 Decision Tree가 된다.

Decision Tree는 이름 그대로 트리 구조를 사용한 Model이다. 데이터를 특정 조건으로 반복적으로 나눠서 최종적인 예측값에 도달하는 형태인데, 여기서 각 노드가 어떤 Feature를 어떤 기준으로 나눌지를 결정한다. 이 Decision Tree의 Depth를 최대한 키우면, 데이터셋의 모든 샘플을 완벽하게 분류할 수 있을 것이다. 그런데 그 말은 모든 샘플을 전부 분류할 수 있다는 이야기고, 이 말은 곧 Overfitting이 매우 심하다는 뜻이다. 그리고 이 말을 다시 표현하면 Bias가 낮고 Variance가 높다는 의미이다.

이 Decision Tree를 여러개 모아 Bagging을 사용한 것이 바로 Random Forest이다. 이론상 Decision Tree는 Max Depth에 제한을 두지 않으면 에러를 완전히 0으로 만들 수 있는데, Random Forest에서는 Decision Tree를 학습할 때 하나의 트릭을 더 추가한다. Hyper Parameter $k$를 둬서 각각의 Decision Tree에서 split 기준을 정할 때마다 전체 Feature들 중 무작위로 $k$를 선택하여 그 중에서의 Best Split을 고르게 한다. Bagging에서 자연스럽게 발생하는 Subsampling의 랜덤성까지 저렇게 이중으로 랜덤성이 적용되었다고 할 수 잇다. 이러한 Decision Tree를 $m$개 만들어서 이들을 Bagging 방식으로 Ensemble한 것이 Random Forest가 된다. 이 Decision Tree와 Bagging의 조합이 상당히 좋아서, 지금까지도 딥러닝이 아닌 모델들 중에서는 성능이 순위권 안에 든다.

Random Forest는 Feature Importance라는 정보도 제공해줄 수 있다. 각각의 Decision Tree는 중요한 순서대로 Feature를 선택하기 때문에, 이 Decision Tree의 Feature들에 대한 평균을 구하면 중요한 Feature가 무엇인지 바로 알 수 있게 된다. 실제로 이러한 용도로도 많이 사용된다. 다만 이것이 이 모델이 설명적이라는 이야기는 아니다. Ensemble의 특징이기도 한데, 여러 모델이 섞여버린 상태라 구체적으로 어떠한 형태로 모델이 구성되었는지 밝히는 것은 불가능에 가깝다.

Boosting

Boosting은 위에서 본 Bagging과는 다른 방향으로 여러 모델들을 합치는 Ensemble 기법이다. 1990년에 Robert Schapire에 의해 제안된 방법으로, 성능이 좋지 않은 모델들을 모아서 성능을 높이는 방법을 제시한다. 그렇기 때문에 Bagging의 Base Model과 같은 각각의 모델을 여기서는 Weak Learner라고 부른다.

\[H(x)=\sum_{t=1}^{T}\alpha_t h_t(x)\]

각각의 $h_t$를 Weak Learner들이라고 하고, $H$를 이들을 모은 Ensemble Learner라고 하면, 위와 같이 계산하는 식으로 성능 향상을 꾀한다. 즉, 각 모델들에게 가중치를 주는 것이 핵심 아이디어다. 그 각각의 Weak Learner들에게 가중치를 부여하는 방식은 Gradient Descent와 상당히 유사한데, 각각의 Weak Learner들의 예측값을 확인하고, 올바른 방향으로 향하게끔 가중치를 재조정하는 작업을 반복한다.

즉, $H(x)=\sum\limits_{t=1}^{T}\alpha_t h_t(x)$에서, 우리의 목표는 다음 단계의 손실함수인 $l(H+\alpha h)$를 최소화하는 $\alpha$를 찾는 것이다.

\[h_{T+1}=\arg\min_{h\in \mathcal{H}} l(H+\alpha h) \text{ where } l(H)=\dfrac{1}{2}\sum_{i=1}^{n}(H(x_i)-y_i)^2\]

여기서 저번 글에서 다룬 Taylor’s Expansion($l(H+\alpha h) \approx l(H)+\langle \nabla_{H}l,\alpha h \rangle$)을 적용하면 다음과 같다.

\[\begin{aligned} h_{T+1} &=\arg\min_{h\in \mathcal{H}}\langle\dfrac{\partial l}{\partial H},\alpha h\rangle \\ &= \arg\min_{h \in \mathcal{H}}\sum_{i=1}^{n}\dfrac{\partial l}{\partial H(x_i)}\cdot \alpha h(x_i) \\ &= \arg\min_{h \in \mathcal{H}}\sum_{i=1}^{n}r_i h(x_i) \end{aligned}\]

Taylor’s Expansion을 생각해보면 내적 $\langle \nabla_{H}l,\alpha h \rangle \lt 0$이어야 손실이 감소하므로, 이 조건이 성립하는 $h$를 찾을 수 있는 한 위의 과정을 계속 반복하게 된다.

그러면 Boosting에서는 Weak Learner로 어떤 모델을 택해야 할까? 여기서는 Weak Learner라는 이름 그대로 예측 성능이 50:50을 넘기기만 하면 된다. 다만 각각의 모델의 분산이 심하면 다음 Weak Learner에까지 영향을 크게 미치기 때문에 Bias가 높고 Variance가 낮은 모델일수록 Boosting을 적용하기에 용이하다.

그렇기 때문에 이러한 요구사항에 잘 맞는 선형 모델을 주로 사용하며, 혹은 Depth가 낮은 Tree 기반의 모델을 사용한다. 후자의 경우가 XGBoost라는 모델에서 사용하는 케이스이며, 이는 위에서 다룬 Random Forest와 함께 아직까지도 성능이 상위권인 모델이다.

AdaBoost

AdaBoost(Adaptive Boosting)은 1995년에 Yoav Freund와 Robert Schapire에 의해 제안된 알고리즘으로 Boosting 모델 중 가장 간단한 알고리즘이다. 기본적인 동작 원리는 다양한 Weak Learner들 중에서도 추론을 좀 더 어려워하는 Weak Learner에게 좀 더 높은 가중치를 부여하는 것이다.

AdaBoost에서는 Binary Classification 문제를 다룬다. 즉, $y_i \in \lbrace -1,1 \rbrace$, 각각의 Weak Learner $h(x) \in \lbrace -1,1 \rbrace$를 만족한다. 또한 손실함수는 Exponential Loss를 사용한다. 즉, $l(H)=\sum\limits_{i=1}^{n}e^{-y_i H(x_i)}$이다.

AdaBoost는 크게 다음의 3파트로 나눌 수 있다.

Part 1에서는 Weak Learner들 중 가장 우수한 모델을 찾는다. 우선 반복을 피하기 위해 아래와 같이 정의하자.

• Gradient $r_i=\dfrac{\partial l}{\partial H(x_i)}=-y_i e^{-y_i H(x_i)}$
• $w_i=\dfrac{1}{Z}e^{-y_i H(x_i)}$, 여기서 $Z=\sum\limits_{i=1}^{n}e^{-y_i H(x_i)}$로 정의되며, $\sum\limits_{i=1}^{n}w_i=1$을 만족시키기 위한 Normalizing factor이다. $Z$가 $l(H)$와 같은 것은 의도된 사항이다.

이렇게 정의하면 $w_i$는 전체 Loss에 대한 각 데이터 ($x_i$, $y_i$)의 상대적인 기여도를 의미한다.

그 후 아래의 최적화 문제를 푼다.

\[\begin{aligned} h(x_i) &=\arg\min_{h\in \mathcal{H}}\sum_{i=1}^{n}r_i h(x_i) \\ &= \arg\min_{h\in \mathcal{H}}\left(-\sum_{i=1}^{n}y_i e^{-H(x_i)y_i}h(x_i)\right) \\ &= \arg\min_{h\in \mathcal{H}}\left(-\sum_{i=1}^{n}w_i y_i h(x_i)\right) \\ &= \arg\min_{h\in \mathcal{H}}\left(\sum_{i:h(x_i)\neq y_i}w_i - \sum_{i:h(x_i)=y_i}w_i \right) \\ &= \arg\min_{h\in \mathcal{H}}\sum_{i:h(x_i)\neq y_i}w_i \end{aligned}\]

이 값은 “Weighted Classification Error”이다. 이제 각각의 Weak Learner들에 대해 학습을 시킨 후 위의 Weighted Classification Error를 줄이는 Weak Learner를 찾으면 된다.

Part 2에서는 Step-size $\alpha$를 구한다. 이것도 역시 아래의 최적화 문제를 풀어야 한다.

\[\alpha=\arg\min_{\alpha}l(H+\alpha h)=\arg\min_{\alpha}\sum_{i=1}^{n}e^{-y_i(H(x_i)+\alpha h(x_i))}\]

다행스럽게도, 이 문제는 Closed form이 존재한다. 위 식을 풀면 $\alpha$는 다음과 같이 정해진다.

\[\alpha=\dfrac{1}{2}\ln\dfrac{1-\epsilon}{\epsilon}, \epsilon=\sum_{i:h(x_i)\neq y_i}w_i\]

Part 3는 Re-normalization이라고 부른다. Part 1, 2에서 계산한 값을 이용하면 $H_{t+1}=H_t+\alpha h$이기 때문에 다음 스텝으로 나아갈 수 있다. 이제 한 Step을 나아갔으니 이를 계속 반복하면 된다.

Bagging vs Boosting

그럼 Ensemble의 대표적인 두 방법에 대해 비교해보자. Bagging은 Variance를 낮추는 것이 목적이고, Boosting은 Bias를 낮추는 것이 목적이라는 점 외에도 아래와 같은 2가지 비교점들이 더 존재한다.

먼저 Bagging은 데이터셋에서 샘플을 무작위로 뽑은 후 각각에 대해서 학습시킨걸 합치기 때문에 자연스럽게 병렬 연산이 가능해진다. 심지어 각각의 모델들은 독립적이라 서로 간에 정보가 교환될 필요가 없어서 실제로 병렬 처리가 가능해진다. 그렇다면 Boosting은 어떨까? 각각의 Weak Learner의 예측값에 따라 다음 Weak Learner에게 맞는 가중치를 정해야 하기 때문에 Bagging과 같은 병렬 연산이 불가능하다. 이 말은 다수의 Weak Learner들을 Sequential하게 처리해야만 하므로 상당히 느리다는 뜻이다. 다만 학습 과정에서의 병렬이 불가능한거지 이를 가지고 추론할 때는 Boosting 모델 역시 병렬적으로 연산이 가능하다. 이미 가중치를 학습한 상태이기 때문이다.

또한 Bagging의 경우 Out-of-Bag 샘플이 존재하기 때문에 Validation 용으로 별도의 데이터를 준비할 필요가 없다. 각각의 모델이 자신이 학습할 때 사용할 데이터셋을 제외한 나머지를 가지고 충분히 Validation이 가능하기 때문이다. 하지만 Boosting의 경우는 데이터셋을 가지고 모든 모델이 학습하기 때문에 Validation용 데이터를 별도로 준비해야 한다.