Bagging Predictors

---

이번 포스팅에서는 Leo Breiman의 논문 'Bagging Predictors'에 대한 내용을 간략히 정리해본다.

 

- 목차 -

1. Introduction

2. Bagging Classification Trees

3. Bagging Regression Trees

4. Why Bagging Works

5. A Linear Regression Illustration

6. Concluding Remarks

---

   1. Introduction 

학습 데이터 $L=\{ (y_n, x_n), n=1, \ldots, N \}$이 있다. $y_n$은 클래스 라벨이거나 수치형 반응 변수일 수 있다. 

 

이때 학습 데이터 $L$을 이용하여 예측모형 $\phi(x, L)$을 만들어본다고 가정하자. 또한 학습 데이터의 시퀀스 $\{ L_k\}$가 $L$과 똑같은 분포에서 추출된 $N$개의 독립된 관측치로 이루어져 있다고 가정하자.

 

우리의 목표는 하나의 $L$로 만든 예측모형보다 $\{ L_k \}$를 이용하여 더 좋은 예측모형을 만들어내는 것이다.

 

$y$가 수치형 반응 변수라면 $\phi(x, L)$대신 $\phi(x, L_k)$의 평균을 생각할 수 있고 $y$가 클래스 라벨이라면 $\phi(x, L)$대신 $\phi(x, L_k)$를 다수결 표결을 이용하여 예측하는 방법을 생각할 수 있다. 하지만 우리에게 주어진 것은 $L$밖에 없다. 따라서 학습 데이터 시퀀스와 비슷한 걸 만들기 위해 Bootstrap Sampling을 고려한다. 즉, $L$에서 $N$개를 복원 추출하여 학습 데이터 시퀀스 $L^{(B)}$를 만드는 것이다. 이를 이용하여 예측 모형을 학습하는 과정을 Bootstrap Aggregating 을 줄여서 Bagging(배깅)이라고 부르겠다.

 

배깅이 정확도를 향상할 수 있을지 말지를 결정하는 중요한 요인은 예측 모형 $\phi$를 구축할 때의 안정성이다. 

 

$L$의 붓스트랩 샘플의 변화가 작을 때(오리지널 학습 데이터 $L$와 비슷할 때) $\phi$의 변화를 크게 하는 그러한 불안정한 과정은 정확도의 향상을 도모할 것이라고 한다. 하지만 안정적인 과정에서는 오히려 성능을 떨어트릴 수 있다고 한다.

---

   2. Bagging Classification Trees

2.1 Results for Moderate Sized Data Sets

여기서는 7개 데이터 셋을 이용하여 기존 오리지날 데이터만 갖고 만든 분류 모형과 붓스트랩 샘플을 이용해서 만든 분류 모형(배깅 모형)의 성능을 비교한다.

 

여기서는 다음의 과정으로 예측모형을 학습한다.

1) 먼저 원 데이터를 9대1 비율로 학습 데이터 $L$과 테스트 데이터 $T$로 나눈다.

 

2) 먼저 $L$을 이용하여 분류 나무를 만든다. 이때 10-fold 교차검증을 이용한다고 한다. 그리고 $T$를 이용하여 오분류율 $e_S(L, T)$를 계산한다. 교차검증을 하는 이유는 뭔가 나무 깊이나 가지치기를 위한 것 같다. 정확한 설명은 없었다.

 

3) $L$에서 붓스트랩샘플 $L_B$를 만든다. 그러고 나서 $L_B$를 이용하여 분류 나무를 만든다. 이때 기존 $L$을 테스트 데이터로 하여 가지치기를 수행한다. 이를 50번 반복하여 분류 나무 50개를 만든다($\phi_1(x), \ldots, \phi_{50}(x)$).

 

4) $T$를 이용하여 위에서 만들어진 50개 분류 나무를 이용하여 오분류율을 계산(다수결 투표)한다. 이를 $e_B(L, T)$라 하자.

 

5) 1) ~ 4) 과정을 100번 반복하여 $\bar{e}_S$와 $\bar{e}_B$를 계산하고 이에 대한 표준오차도 계산한다.

 

7개의 데이터 셋에 대하여 성능을 검증한 결과 정도의 차이는 있지만 붓스트랩을 이용한 분류 모형의 성능이 더 좋았다. 이때 당뇨 데이터에 대한 붓스트랩 분류 나무(배깅 모형) 성능의 향상 증가치가 가장 작았는데 이에 대한 이유로 기존 데이터를 이용한 분류 모형에 최적 오분류율에 근접했고 따라서 배깅이 향상할 수 있는 성능 증가치가 작기 때문이라는 추측을 했다.

2.2 Statlog Comparisons for Larger Data Sets

이번엔 사이즈가 큰 데이터에 대해서 비교를 해보았다. 여기에서도 위와 동일한 과정으로 성능 비교를 했고 마찬가지로 모든 데이터셋에 대하여 배깅을 이용한 예측 모형의 성능이 더 좋았다. 그리고 배깅과 다른 분류기(K-NN, C4.5 등)를 비교했을 때 배깅이 항상 성능 탑이었다고 한다.

 

---

   3. Bagging Regression Trees

분류 나무와 비슷하게 회귀 나무에서도 여러가지 데이터 셋에 대해서 배깅을 이용한 모형이 더 성능이 좋았다는 것을 알리고 있다.

---

   4. Why Bagging Works

4.1 Numeric Prediction

여기서는 회귀 문제에서 개별 모형의 불안정성이 배깅 모형의 성능 향상에 어떻게 영향을 미치는지 수식을 통해 알아본다.

 

먼저 $L$에 포함된  $(y, x)$이 확률분포 $P$로부터 독립적으로 추출되었다고 하자. 그리고 $\phi_A(x) = E_L(\phi(x, L))$이라 하자.

 

먼저 $(y, x)$를 고정시키자. 그러면 젠센 부등식을 이용하여 다음을 알 수 있다.

$$E_L(y-\phi(x, L))^2 \geq (y-\phi_A(x))^2\tag{4.2}$$

 

(4.2) 양변에 $(y, x)$에 대한 기대값을 취하면 배깅 모형의 Mean Squared Error가 개별 모형보다 더 작은 것을 알 수 있다. 이때 성능 차이를 극대화하는 요인은 아래의 부등식의 차이에 따라 달라진다.

$$\left [ E_L\phi(x, L) \right ]^2 \leq E_L\phi^2(x, L)$$

만약 $\phi(x, L)$이 $L$의 붓스트랩 샘플링에 따라서 크게 변화하지 않는다면, 즉, 안정적이라면 위 부등식은 거의 같아질 것이고 이에 따라 성능 차이는 나지 않을 것이다.

 

배깅으로 얻어진 예측 모형은 다음과 같다고 할 수 있다.

$$\phi_B(x) = \phi_A(x, P_L)$$

여기서 $P_L$은 $L$의 관측된 분포이다. $\phi_B$는 배깅 과정에서 안정성과 불안정성 사이에 성능의 증가가 더 이상 이루어지지 않는 지점이 있다고 한다.

4.2 Classification

여기서도 배깅을 이용한 분류 모형이 개별 모형보다 성능이 좋다는 것을 수식을 통해 설명한다. 또한 불안정한 분류기를 배깅 처리하면 개별 모형보다 좋은 성능을 갖지만 안정적인 분류기를 배깅하는 것은 좋은 선택은 아니라고 한다.

4.3 Using the Learning Set as a Test Set

여기서는 붓스트랩 샘플링 데이터 $L_B$로 예측 모형을 만들고 오리지널 데이터 $L$을 테스트 셋으로 사용해도 괜찮은 이유를 설명한다. 원래 같으면 테스트 셋으로 붓스트랩 샘플링을 한번 할 때 엄청 큰 샘플을 뽑아서 구성하는데 이것이 그냥 오리지날 데이터 $L$을 쓰는 것과 같은 효과를 낸다고 하기 때문이다.

---

   5. A Linear Regression Illustration

5.1 Forward Variable Selection

여기서는 변수 선택법에 대한 얘기를 한다. 저자의 모의실험에서는 전진 선택법을 이용한다고 한다.

5.2 Simulation Structure

전진 선택법으로 얻은 회귀 모형을 구축한다고 했을 때 개별 모형과 배깅 모형의 예측 오차를 비교하는 실험이었다.

5.3 Discussion of Simulation Results

모든 경우에서 배깅 모형의 성능이 좋았다. 하지만 변수를 많이 선택하는 경우에는 배깅의 성능이 좋지 못했다고 하며 저자는 그 이유를 변수를 많이 선택하는 것이 안정적(Stable)인 과정이기 때문이라고 했다.

---

   6. Concluding Remarks

6.1 Bagging Class Probability Estimates

$x$가 주어졌을 때 클래스가 $j$일 조건부 확률 $P(y=j|x)$를 예측하는 분류기에서 저자는 개별 분류기보다 배깅 분류기의 성능이 좋다고 했다. 이는 waveform 데이터에서 의사결정나무를 이용하여 보였다. 개별 의사결정나무보다 배깅 의사결정나무가 성능이 더 좋다는 것을 보였다는 것이다.

6.2 How Many Bootstrap Replicates Are Enough?

여기서는 붓스트랩샘플들의 개수를 50개로 했는데 당연히 몇개로 해야하냐는 질문이 나올 수 밖에 없을 것이다. 저자는 회귀 문제에서는 많이 필요없고 분류 문제에서는 클래스 개수가 많아질 수록 붓스트랩샘플 개수를 늘려야 한다고 추측했다.

 

붓스트랩샘플의 개수를 몇개로 할 것인지는 CART와 같은 알고리즘에서는 크게 중요하지 않다고 한다. 하지만 계산이 정말 많이 필요한 신경망같은 것은 중요해질 수 있다고 한다.

 

그리고 붓스트랩샘플의 개수는 무작정 늘려도 특정 지점 이후부터는 성능 향상이 없음을 실험 결과를 통해 보였다.

6.3 How Big Should the Bootstrap Learning Set Be?

그러면 한 붓스트랩샘플에 대하여 샘플 수는 얼마나 커야 하는 질문도 나올 수 있다. 붓스트랩 샘플 크기를 많이 하면 좋을 수 있다고 하지만 저자는 $L$보다 두배 더 큰 사이즈를 이용하여 실험했더니 성능 향상은 없었다고 한다. 

6.4 Bagging Nearest Neighbor Classifiers

배깅 모형은 기본 학습기가 NN인 경우 배깅의 효과가 없다고 한다. 왜냐하면 한 테스트 샘플에 대하여 결과가 달라지려면 원래 학습 데이터 $L$과 붓스트랩샘플이 절반 정도 달라져야 하는데 그럴 가능성이 현저히 낮기 때문이라고 한다.

6.5 Conclusions

배깅은 변변찮은 재료로 멋진 것을 만들어내는 알고리즘이다. 굳이 의사결정나무가 아니더라도 모든 예측 알고리즘에 적용할 수 있다. 붓스트랩샘플링과 집계 과정만 포함시키면 되므로 구현도 딱히 어렵지 않다. 배깅을 통해 잃는 것은 해석과 단순함이지만 성능의 향상을 도모할 수 있다.

---