Bagging (Bootstrap Aggregating)

여러 데이터 샘플을 랜덤하게 생성한 후, 각 샘플에서 모델을 학습시켜 예측을 결합함으로써 분산을 줄이고 모델의 성능을 향상시키는 앙상블 학습 기법

원본 데이터셋으로부터 무작위로 복원 추출(bootstrap sampling)하여 여러 개의 서브셋을 생성하고, 이를 사용해 여러 개의 기본 학습기를 훈련시킨 후, 그 결과를 집계(aggregating)하여, 분산을 줄이고 과적합을 방지하면서 일반적으로 단일 모델보다 더 안정적인 예측 성능을 달성하는 머신러닝 앙상블 기법이다.

Bagging

---

---

Motivation of Bagging

• 각각 $\sigma^2$ dispersion 을 가진 n개의 observation $(Z_1,…,Z_n)$
• Average of observation $\overline Z$ 에 대한 dispersion 은 $\sigma^2 / n$
• 여러 observation 을 평균내면 dispersion 을 줄여준다.
• but, 다수의 학습 데이터 셋을 얻는 것은 현실적으로 어렵다.

Bagging

---

---

• Bootstrap 을 이용해, 한 개의 학습 데이터 셋으로 부터 B개의 데이터 셋을 추출
• 각각의 data sets 으로 $\hat f^{*b}(x)$ 모델을 학습한다.
• 모든 predictive value 를 mean (regression) 하거나, majority vote (classification) 를 취해 dispersion error 를 낮춘다.

• Bootstrap aggregation 이라고도 하며, 보통 decision tree 에서 많이 사용된다.
• Bagging 을 사용하면,
  1. Decision tree 의 performance 에서의 단점을 보완 가능
  2. 학습 결과에 대한 해석력이 떨어짐

  특히, 어떤 feature(variable) 가 중요한 지 판단이 힘듦.

• B 개의 decision tree 에서 each variable 에 따른 Split 으로 RSS (Regression) 또는 Gini index (Classification) 의 감소량을 평균하여 순위를 매긴다.

Out-of-Bag Error Estimation

---

---

OOB Error

• Bagged model 을 사용하면 test error 를 쉽게 estimate 할 수 있음
• Bagging 은 bootstrap 을 사용하기 때문에, 대략 2/3 개의 sample 만으로도 하나의 decision tree를 학습한다.

• 하나의 Bagged tree 를 학습할 때, 사용되지 않은 샘플들을 Out-of-Bag(OOB) 라고 한다.

  

• OOB prediction : i-th 샘플이 포함되지 않은 bootstrap 데이터 셋으로 학습된, 대략 B/3 개의 tree들의 i-th 샘플에 대한 mean(regression) 혹은 majority vote(classification)
• OOB error : each sample 들의 OOB prediction 으로 얻은 오류
• OOB error 는 test error 에 대한 valid predictive value 가 된다.
• B 가 충분히 많을 때, OOB error 는 LOOCV 와 거의 동일하다.

Random Forests

---

---

• Bagged tree 사이의 상관관계를 없애 성능을 향상시킨 알고리즘
• 원래는 p 개의 variable 을 모두 고려해 split 을 결정해 decision tree 를 학습한다.
• if, 강력한 variable 이 있으면, B개의 모든 tree 가 top split 으로 이를 사용할 것임
• 상관관계가 커지면 $=High\textrm{Cov}(\hat f^{i}, \hat f^{j})$), dispersion error 가 크게 deduce 될 수 없음

• p 개의 variable 중 m 개를 랜덤하게 선택해 decision tree 를 learning
• 상관관계가 줄어든 decision tree 를 사용하기 때문에, dispersion reduce effect 가 증폭 됨
• 일반적으로 $m \approx \sqrt p$ 값을 사용할 때, 효과가 제일 좋다.