Ensemble Learning(앙상블 기법)

앙상블 기법(Ensemble Learning)은 더 정확한 학습 모델을 만들기 위해 여러 개의 학습 기법을 결합하는 방법입니다.

그림1. 의사결정나무

지난번에는 연속되는 질문과 대답을 통해 클래스를 예측하는 Decision Tree(의사결정나무)를 알아보았습니다.

그런데 위의 의사결정나무가 어떤 동물이 포유류인지를 정확히 예측할 수 있을까요?

그림2. 오리너구리

그림 2는 오리너구리입니다. 오리너구리는 알을 낳기 때문에, 그림 1의 decision tree를 이용해 판정을 하면 포유류가 아니라는 결과가 나옵니다. 하지만 오리너구리는 새끼를 낳아 젖을 먹이기 때문에 포유류로 분류됩니다.

 

이와 같이 의사결정나무는 데이터의 작은 변화에 의해 예측 결과가 크게 변하는 특성(high variance)이 있습니다. 이러한 특성을 보완하기 위해 쓰이는 기법이 앙상블 기법입니다.

 

 

포유류/포유류가 아님을 결정하는 100개의 트리가 있다면, 어떤 의사결정나무에서는 오리너구리를 포유류로, 어떤 의사결정나무에서는 오리너구리를 포유류가 아닌 동물로 판정할 것입니다. 앙상블 기법을 사용하면 한 가지 의사결정나무의 판정에 전적으로 의존하는 대신, 이 판정들을 모두 모아 총체적으로 결론을 내릴 수 있습니다.

 

앙상블 기법의 종류는 Bagging과 Boosting, Stacking기법이 있습니다.

그림3. 앙상블 모델의 비교

 

1. Bagging

1-1. Bootstrap

Bagging은 Bootstrap Aggregating 이라고도 합니다. Bagging에 대해서 알기 위해서는 먼저 Bootstrap에 대해서 알 필요가 있습니다.

 

우리가 알고자 하는 모집단의 분포 $P$가 있고, 그로부터 샘플링되어 나온 $S$를 트레이닝 셋으로서 가지고 있다고 합시다. ($S$~$P$)

모집단에 대한 특정 값, 예컨대 평균을 알고 싶다고 할 때, $S$의 평균을 계산해볼 수 있지만,

이 값이 어느 정도 정확한지 확인하기 위해서는 모집단으로부터 더 많은 데이터를 샘플링해 검증할 필요가 있습니다.

 

그러나 모집단으로부터 데이터를 계속해서 추출하는 것은 현실적으로 불가능할 때가 대부분입니다.

그럴 경우 모집단의 분포가 가우시안 분포와 같은 특정 분포를 따른다고 가정하거나, 혹은 가지고 있는 데이터를 최대한 활용하는 선택을 할 수 있습니다.

 

부트스트랩은 모집단으로부터 충분히 많은 데이터를 추출하기 어려울 때 사용하는 기법으로,

주어진 $S$를 원래의 모집단을 대표하는 데이터 셋이라고 가정하고 복원 추출을 통해 $S$로부터 새로운 데이터셋 $Z_1, Z_2, \ldots, Z_M$을 이끌어냅니다.

 

1-2. Aggregation

Bagging 기법에서는 같은 유형의 알고리즘들을 독립적으로 학습한 후, 그 결과를 결합해(평균, majority vote 등) 결정론적으로 결과 점수를 계산합니다.

 

Bootstrap 방식으로 기존의 트레인 데이터 $S$로부터 $Z_1, Z_2, \ldots, Z_M$을 끌어냈습니다.

이제 각각의 $Z_i$에 대해 머신러닝 모델 $G_m$을 학습시키고, 새로운 aggregate 예측 모델을 수립합니다.

 

$G(X) = \sum_{m} \frac{G_m(x)}{M}$

 

이러한 과정을 Bagging이라고 합니다.

Bagging을 통해 variance를 크게 줄이면서 정확도를 향상시킬 수 있지만,

특히 의사결정나무 모델의 경우 bagging기법을 사용하면 트리 모델의 장점 중 하나였던 설명력을 잃게 되는 단점이 있습니다.

이러한 설명력 부족을 보충하기 위해 variable importance measure라는 방법이 사용됩니다.

 

1-3. Random Forest

• 의사결정나무 앙상블 기법입니다.
• Bagging 기법을 사용하면 보유한 많은 알고리즘들이 거의 비슷한 형태를 띄게 되는데, 이를 방지하기 위해 변경을 가한 방법입니다.
• 가진 데이터셋의 feature중 일부를 랜덤하게 선택해, 그 feature에 대해서만 학습합니다.

1-4. Bagging 기법의 장단점

• 장점:
  • variance의 감소
  • 정확도 증가
  • out-of-bag estimation: bootstrap과정에서 뽑히지 않은 데이터들을 validation set으로 사용할 수 있음
• 단점:
  • bias의 증가
  • 해석력의 감소
  • 계산 가격의 증가

2.  Boosting

Boosting 기법에서는 같은 유형의 알고리즘을 순차적으로 (이전에 학습한 알고리즘은 다음에 학습할 알고리즘의 Base model이 됨) 학습한 후 그 결과를 결합해 결정론적으로 결과 점수를 계산합니다.

 

Bagging이 variance를 줄이는 기법이라면 boosting은 bias를 줄이는 기법입니다.

따라서 boosting에는 high bias, low variance모델들이 사용되는데 이를 weak learners라고도 합니다.

그런데 의사결정나무 모델은 high variance모델이라고 했었는데 어떻게 boosting을 적용할 수 있을까요?

의사결정나무 모델을 boosting에 적용하기 위해 각 트리당 단 하나의 의사결정만 하게 한 것을 decision stump라고 합니다.

 

 

그림4. Boosting

그림 3의 맨 왼쪽 데이터셋으로부터 시작합니다.

그림 3의 중앙과 같이 공간을 분할했다면, 네모 모양으로 표시된 점들은 학습이 잘 되지 않는 점이 됩니다.

Boosting알고리즘에서는 다음번 학습 때 이 "hard negative"들에 더 많은 가중치를 부여해, 학습할 수 있도록 합니다.

다음 번 학습에서는 그림 3의 맨 오른쪽 그림과 같이 이전에 틀리게 학습했던 점들을 옳게 학습할 수 있는 방향으로 움직이게 됩니다.

이렇게 매번 틀리게 예측하는 점에 가중치를 부여하는 방식으로 학습하는 방법을 Boosting이라고 합니다.

 

2-1. Adaboost (Adaptive Boosting)

Input: $(x_i, y_i)$, $i = 1, ..., N$  output: Ensemble classifier $f(x)$  $w_i = 1/N$, $i=1,..., N$  for $m=0$ to $M$:     1. 트레이닝 데이터와 가중치 $w_i$에 대해 $G_m$을 학습     2. $err_m = \frac{\sum w_i * (y_i != G_m(x_i))}{\sum(w_i)}$      3. $a_m = \log\frac{(1-err_m)}{err_m}$      4. $w_i$ <- $w_i \cdot \exp(a_m \cdot (y_i != G_m(x_i)))$  $f(x) = \textit{argmax}_k (\sum(a_m \cdot (G_m(x)=k)))$

Adaboost는 처음에 가중치를 $\frac{1}{N}$으로 초기화한 후 잘못 분류된 데이터들에 대한 가중치를 점점 높이는 방식으로 학습을 진행합니다.

결과로 주어지는 분류 모델은 모든 weak learner의 가중합으로 주어집니다.

 

그림5. Adaboost

 

2-2. Forward Stagewise Additive Modeling

Input: $(x_i, y_i)$, $i = 1, ..., N$  output: Ensemble classifier $f(x)$  $f_0(x) = 0$  for $m=0$ to $M$:     1. $(\beta_m, \gamma_m) = \textit{argmin}_{\beta, \gamma} \sum(L(y_i, f_{m-1}(x_i) + bG(x_i;\gamma)))$     2. $f_m(x) = f_{m-1}(x) + \beta_m G(x;\gamma_m)$ $f(x) = f_m(x)$

 

2-3. Gradient Boosting

Gradient Boosting은 각 트레이닝 포인트에 대한 gradient를 계산해, 다음 모델에서 그 gradient를 이용해 학습하는 방식입니다.

input: $(x_i, y_i)$, $i = 1, ..., N$ output: Ensemble classifier $f(x)$  $f_0(x) = 0$ for $m=0$ to $M$:     1. pseudo-residual 계산: $r_{im} = -\frac{\partial L(y_i, f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}$     2. $(x_i, r_{im})$ 에 대해 베이스 모델 $G_m$을 학습     3. $\beta_m = \textit{argmin}_{\beta} \sum_{i=1} ^n L(y_i, f_{m-1}(x_i) + \beta G_m(x_i))$      4. $f_m(x) = f_{m-1}(x) + \beta_m G_m(x)$ $f(x) = f_m(x)$

 

위 알고리즘에서 만약 loss function이 $L(y, f(x)) = \frac{1}{2}(f(x)-y)^2$와 같이 mean squared error로 주어졌다고 가정해 봅시다.

이 때 각 $r_im = y_i-f_{m-1}(x_i)$이므로, $G_m$을 $(x_i, y_i-f_{m-1}(x_i))$에 학습시키게 됩니다. 

즉, 지금까지 엇나간 예측치에 대해서만 예측한 모델을 기존의 모델에 더하게 됩니다.

Gradient Boosting에 대한 설명에 잔차(residual)라는 단어가 자주 나오는 것은 이러한 이유입니다.

 

 

 

그림6. Residual Fitting

 

예컨대 어떤 데이터셋  $(x_i, y_i)$, $i = 1, ..., N$에 대해 MSE를 최소화하는 모델을 만드려고 한다고 가정해 봅시다.

만약 기존에 $F(x)$라는 완벽하지 않지만 괜찮은 모델을 가지고 있지만, 이를 변경할 수는 없다고 할 때,

합리적 선택지 중 하나는 $F(x)$에 $h(x)$라는 모델을 덧붙여 정확도를 향상시키는 것입니다.

즉, $F'(x) = F(x) + h(x) = y_i$ 인 $h(x)$를 만들 수 있을 것입니다.

다시 말하면 $h(x) = y_i = F(x)$를 최대한 만족하는 $h(x)$를 찾을 수 있습니다.

위 알고리즘은 이런 과정을 $M$번 반복한다고 볼 수 있습니다.

 

2-4. Boosting 기법의 장, 단점

• 장점: 
  • bias의 감소
  • 정확도 향상
• 단점
  • variance 증가
  • overfitting가능성 증가

 

3.  Stacking

• 서로 다른 유형의 알고리즘들을 병행 학습해 결합합니다.
• 결합된 결과를 meta-model을 사용해 트레이닝해 최종 예측결과를 산출합니다.

 

참고:
[1] http://cs229.stanford.edu/notes/cs229-notes-ensemble.pdf
[2] https://stats.stackexchange.com/questions/26088/explaining-to-laypeople-why-bootstrapping-works
[3] https://www.chengli.io/tutorials/gradient_boosting.pdf