Bootstrap Sampling 기반 Accuracy 추정 지표

0. 왜 Bootstrap Accuracy Estimation이 필요한가

• 모델 성능 평가의 이상적인 방법은 독립적인 test set을 사용하는 것임.
• 하지만 데이터가 부족한 경우, 충분한 test set을 확보하기 어려움.

Bootstrap accuracy estimation은 복원 추출(sampling with replacement) 을 반복하여 하나의 dataset으로 훈련과 평가를 동시에 수행하는 방법으로, 단일 train/test split 대비 분산(variance)을 줄인 보다 안정적인 성능 추정 이 가능

2024.06.05 - [.../Math] - [ML] Bootstrap Sampling

[ML] Bootstrap Sampling

---

하지만 어떻게 평가하느냐에 따라

• 낙관적(optimistic) 또는
• 비관적(pessimistic) 편향(bias)이 발생함.

이를 보정하는 방향으로 다음 순서로 발전해 왔음:

 

이 문서는 간단한 예제를 통해 이들을 비교 설명함.

---

1. 예제 설정

이하 모든 설명에서 다음 4-class 분류 문제를 공통 예제로 사용함.

항목	값
샘플 수 $N$	20
클래스	C1, C2, C3, C4
실제 클래스 분포 $\hat{p}_k$	$[0.40,\ 0.30,\ 0.20,\ 0.10]$
예측 클래스 분포 $\hat{q}_k$	$[0.40,\ 0.30,\ 0.20,\ 0.10]$
Bootstrap 반복 수 $B$	100

 

Bootstrap 실험을 통해 다음 두 accuracy 값을 얻었다고 가정함:

$$\text{Acc}_{\text{train}} = 0.95 \quad \text{(훈련셋 accuracy, optimistic)}$$

$$\text{Acc}_{\text{OOB}} = 0.72 \quad \text{(OOB accuracy, pessimistic)}$$

---

2. Basic Bootstrap

2-1. Concept

• 각 bootstrap sample $\mathcal{D}^{*(b)}$ 로 훈련한 모델을
• 원본 dataset 전체 로 평가하고 $B$회 평균냄.

$$\text{Acc}_{\text{basic}} = \frac{1}{B}\sum_{b=1}^{B} \text{Acc}(\mathcal{M}^{(b)}, \mathcal{D}) = 0.95$$

---

2-2. Problem: Optimistic Bias

• test set에 훈련 샘플이 포함 될 수 있으므로 낙관적 편향(optimistic bias) 이 발생함.
• 4-class 문제에서 모델은 훈련 중 본 샘플을 거의 완벽히 맞출 수 있음.
• 특히 C4처럼 샘플이 2개뿐인 소수 클래스도 훈련셋에서는 100% accuracy를 낼 수 있어, 실제 일반화 성능 대비 크게 과장된 수치가 됨.
• 적은 수의 데이터를 가진 경우와 멀티 클래스인 경우에 사용 비권장.

---

3. OOB (Out-of-Bag) Bootstrap

3-1. Concept

sampling with replacement 특성상

각 샘플이 특정 bootstrap $\mathcal{D}^{*(b)}$ 에서 제외될 확률이 다음과 같음:

$$P(\text{excluded}) = \left(1 - \frac{1}{N}\right)^N \approx e^{-1} \approx 0.368$$

• 이 제외된 샘플들을 OOB sample $\mathcal{D}^{\text{OOB}(b)}$ 이라 함.
• 완벽하게 훈련에 사용되지 않은 샘플들이므로 독립적인 평가가 가능함.
• 전체 20개 샘플 중 평균 $20 \times 0.368 \approx 7.4$개가 OOB sample로 사용됨.

$$\text{Acc}_{\text{OOB}} = \frac{1}{N}\sum_{i=1}^{N}\text{Acc}!\left(\left{\mathcal{M}^{(b)}: i \notin \mathcal{D}^{*(b)}\right},\ \mathbf{x}_i\right) = 0.72$$

2024.06.20 - [.../Math] - [ML] Out of Bag: 유도하기.

[ML] Out of Bag: 유도하기.

---

3-2. Per-Class OOB / Training Sample Analysis

클래스	비율	전체 수 $N_k$	기대 OOB 수 ($\times 0.368$)	기대 훈련 수 ($\times 0.632$)
C1	0.40	8	$\approx 2.94$	$\approx 5.06$
C2	0.30	6	$\approx 2.21$	$\approx 3.79$
C3	0.20	4	$\approx 1.47$	$\approx 2.53$
C4	0.10	2	$\approx 0.74$	$\approx 1.26$

---

3-3. 문제점: Problem: Pessimistic Bias Worsens with More Classes

클래스 수가 많고 데이터가 불균형할수록 다음 세 가지 문제가 동시에 발생함:

 

문제 1. 소수 클래스 OOB 평가 불가 확률 급증

C4 샘플이 2개뿐이고 각각이 bootstrap에 포함될 확률이 $\approx 0.632$이므로,

두 샘플 모두 포함되어 C4의 OOB sample이 하나도 없을 확률이 다음과 같음:

$$P(\text{C4 OOB} = 0) \approx 0.632^2 \approx 0.40$$

• 즉 bootstrap의 약 40%에서 C4에 대한 OOB 평가가 아예 불가능함.
• $\text{Acc}_{\text{OOB}}$의 분산(variance)을 크게 증가시킴.

---

문제 2. 다수 클래스 위주의 편향

• C4의 OOB 평가가 불가능한 bootstrap에서는 C4의 성능이 전혀 반영되지 않으므로,
• $\text{Acc}_{\text{OOB}}$는 다수 클래스(C1, C2) 위주로 편향됨.
• 모델이 C4를 전혀 맞추지 못해도 해당 bootstrap의 OOB accuracy에는 영향이 없음.

---

문제 3. 소수 클래스 훈련 부족에 의한 pessimistic bias 심화

• C4는 평균 1.26개만으로 훈련해야 하므로 모델이 C4 패턴을 제대로 학습할 수 없음.
• OOB 평가에서 C4를 자주 틀리게 되어 $\text{Acc}_{\text{OOB}}$의 pessimistic bias가 심화됨.

세 문제를 종합하면:

$$ \underbrace{\text{클래스 수} \uparrow}_{\text{소수 클래스 OOB 부족}} \Rightarrow \underbrace{\text{Var}(\text{Acc}_{\text{OOB}}) \uparrow}_{\text{추정 불안정}} + \underbrace{\text{Bias}(\text{Acc}_{\text{OOB}}) \downarrow}_{\text{비관적 편향 심화}}$$

• 이같은 OOB의 단점이 .632 및 .632+ 보정이 등장하게 된 배경이 됨.

---

4. .632 Bootstrap

4-1. Concept

• Basic Bootstrap의 optimistic bias 와 OOB의 pessimistic bias 를
• 고정 가중치(fixed weight) 로 결합하여 상쇄함.

$$\text{Acc}_{.632} = 0.368 \times \text{Acc}_{\text{train}} + 0.632 \times \text{Acc}_{\text{OOB}}$$

$$= 0.368 \times 0.95 + 0.632 \times 0.72 = 0.3496 + 0.4550 = \mathbf{0.805}$$

• 가중치 $0.632$는 각 샘플이 하나의 bootstrap에 포함될 확률 $1 - e^{-1} \approx 0.632$에서 자연스럽게 유도됨.

---

4-2. Problem: Residual Optimistic Bias under Overfitting

• $\text{Acc}_{\text{train}} = 0.95$처럼 과적합이 심한 경우에도 훈련 accuracy가 항상 고정 비율 $0.368$만큼 반영됨.
• 과적합 정도 차이가 있음에도 이를 고려하지 않고 항상 같은 가중치를 적용하는 것이 .632의 근본적 한계임.

---

5. .632+ Bootstrap

Efron & Tibshirani (1997)가 제안한 방법으로, .632의 고정 가중치 문제를 해결함.

 

과적합 정도에 따라 가중치를 동적으로 조정함.

Step 1. No-Information Accuracy $\gamma_{\text{acc}}$ 계산

• 모델이 학습 없이 클래스 분포만으로 예측할 때의 기대 accuracy.
• 모델 성능의 최저 기준선(baseline) 역할을 함.

$$\gamma_{\text{acc}} = \sum_{k=1}^{K} \hat{p}_k \cdot \hat{q}_k$$

$$= (0.40 \times 0.40) + (0.30 \times 0.30) + (0.20 \times 0.20) + (0.10 \times 0.10)$$

$$= 0.16 + 0.09 + 0.04 + 0.01 = \mathbf{0.30}$$

• 4-class 균등 분포라면 $\gamma_{\text{acc}} = 0.25$이지만, 클래스 불균형으로 인해 $0.30$이 됨.
• 클래스 수 $K$가 커질수록 $\sum_k \hat{p}_k^2$이 감소하여 $\gamma_{\text{acc}}$는 낮아짐.

---

Step 2. Relative Overfitting Rate $\hat{R}$ 계산

$$\hat{R} = \frac{\text{Acc}_{\text{train}} - \text{Acc}_{\text{OOB}}}{\text{Acc}_{\text{train}} - \gamma_{\text{acc}}} = \frac{0.95 - 0.72}{0.95 - 0.30} = \frac{0.23}{0.65} \approx \mathbf{0.354}$$

참고: Qualitative Meaning of $\hat{R}$

$\hat{R}$은 단순히 train/OOB accuracy의 차이가 아니라,
"그 차이가 얼마나 심각한가(얼마나 과적합 되었나)"
를 맥락 속에서 정규화한 지표임.

$$\hat{R} = \frac{\overbrace{\text{Acc}_{\text{train}} - \text{Acc}_{\text{OOB}}}^{\text{실제 과적합 격차}}}{\underbrace{\text{Acc}_{\text{train}} - \gamma_{\text{acc}}}_{\text{최대 가능 과적합 격차}}} = \frac{\text{실제 과적합 격차}}{\text{최악 시나리오의 격차}}$$

• 분자 $(\text{Acc}_{\text{train}} - \text{Acc}_{\text{OOB}})$:
  • 모델이 실제로 과적합된 정도.
  • 훈련셋과 OOB셋 간의 실제 성능 격차.
• 분모 $(\text{Acc}_{\text{train}} - \gamma_{\text{acc}})$:
  • 모델이 낼 수 있는 최대 과적합 격차.
  • 훈련 accuracy가 아무런 의미 없는 수준인 $\gamma_{\text{acc}}$에서 최대로 부풀어 오를 때의 격차.
• $\hat{R}$은 모델 신뢰도에 대한 지표 로서,
• 이 값이 클수록 낙관적인 훈련 accuracy를 덜 신뢰 해야 함을 의미함.

$\hat{R}$ 값	정성적 의미	가중치 $w$ 방향
$\hat{R} \approx 0$	과적합 없음: train/OOB accuracy 거의 동일	$w \to 0.632$ (.632와 동일)
$\hat{R} \approx 0.354$	본 예제: 중간 수준의 과적합	$w \approx 0.727$
$\hat{R} \approx 1$	심각한 과적합: 훈련 accuracy가 baseline 수준까지 과장	$w \to 1.0$ (OOB만 사용)

---

Step 3. Dynamic Weight $w$ 계산

$$w = \frac{0.632}{1 - 0.368 \times \hat{R}} = \frac{0.632}{1 - 0.368 \times 0.354} = \frac{0.632}{0.870} \approx \mathbf{0.727}$$

• $w$는 항상 $[0.632,\ 1.0]$ 범위에서 결정됨.
• $w = 0.727 > 0.632$이므로, .632 estimator보다 OOB accuracy에 더 많은 가중치를 부여함.

 

---

Step 4. 최종 .632+ Accuracy

$$\text{Acc}_{.632+} = (1-w) \times \text{Acc}_{\text{train}} + w \times \text{Acc}_{\text{OOB}}$$

$$= 0.273 \times 0.95 + 0.727 \times 0.72 = 0.259 + 0.524 = \mathbf{0.783}$$

---

.632 vs .632+: 가중치 비교

	$\text{Acc}_{\text{train}}$ 가중치	$\text{Acc}_{\text{OOB}}$ 가중치
.632	$0.368$ (고정)	$0.632$ (고정)
.632+	$(1 - w) \leq 0.368$	$w \geq 0.632$

• $w \geq 0.632$이므로 .632+의 $\text{Acc}_{\text{OOB}}$ 가중치는 항상 .632보다 크거나 같음.

따라서 $\text{Acc}_{\text{train}} > \text{Acc}_{\text{OOB}}$인 모든 일반적인 과적합 상황에서:

$$\text{Acc}_{.632+} \leq \text{Acc}_{.632} \quad \checkmark$$

---

Extreme Overfitting Scenario Verification

$\text{Acc}_{\text{train}} = 1.0$, $\text{Acc}_{\text{OOB}} = \gamma_{\text{acc}} = 0.25$ (랜덤 수준, 4-class 균등)인 경우:

$$\hat{R} = \frac{1.0 - 0.25}{1.0 - 0.25} = 1.0$$

$$w = \frac{0.632}{1 - 0.368 \times 1.0} = \frac{0.632}{0.632} = 1.0$$

$$\text{Acc}_{.632} = 0.368 \times 1.0 + 0.632 \times 0.25 = \mathbf{0.526}$$

$$\text{Acc}_{.632+} = 0 \times 1.0 + 1.0 \times 0.25 = \mathbf{0.250}$$

• $\hat{R} = 1.0$의 정성적 의미: 실제 과적합 격차가 최대 가능 격차와 완전히 일치함.
• 훈련 accuracy가 아무런 의미 없는 수준($\gamma_{\text{acc}}$)까지 부풀어 오른 최악의 시나리오가 실현된 상태임.
• .632+는 $w = 1.0$으로 설정하여 훈련 accuracy를 완전히 무시함.
• 반면 .632는 이 상황을 감지하지 못하고 무의미한 $\text{Acc}_{\text{train}} = 1.0$을 여전히 $36.8%$ 반영하여 크게 과장된 $0.526$을 출력함.

$$\underbrace{\hat{R} \to 1}_{\text{최악의 과적합}} \Rightarrow \underbrace{w \to 1}_{\text{훈련 accuracy 완전 배제}} \Rightarrow \underbrace{\text{Acc}_{.632+} \to \text{Acc}_{\text{OOB}}}_{\text{.632보다 낮아짐}}$$

---

결론

방법	계산식	결과	편향	특징
Basic Bootstrap	$\text{Acc}_{\text{train}}$	$0.950$	낙관적 ↑↑	평가/훈련 데이터 중복
OOB Bootstrap	$\text{Acc}_{\text{OOB}}$	$0.720$	비관적 ↓	훈련 63.2%만 사용
.632 Bootstrap	$0.368 \times 0.95 + 0.632 \times 0.72$	$0.805$	약간 낙관적	고정 가중치
.632+ Bootstrap	$0.273 \times 0.95 + 0.727 \times 0.72$	$0.783$	보정됨 ✓	$\hat{R}$ 기반 동적 가중치

$$\underbrace{\text{Basic}}_{\text{낙관적 편향}} \xrightarrow{\text{훈련/평가 분리}} \underbrace{\text{OOB}}_{\text{비관적 편향}} \xrightarrow{\text{고정 가중 결합}} \underbrace{\text{.632}}_{\text{잔존 낙관 편향}} \xrightarrow{\hat{R}\text{ 동적 보정}} \underbrace{\text{.632+}}_{\text{편향 최소화} \checkmark}$$

• .632+의 핵심은
  • $\hat{R}$이 "훈련 accuracy를 얼마나 신뢰할 수 없는가"를 자동으로 정량화하고,
  • 이에 비례하여 더 신뢰할 수 있는 OOB accuracy의 비중을 높인다는 것임.
• 4-class처럼 클래스가 많아 $\gamma_{\text{acc}}$가 낮아지면
  • $\hat{R}$의 분모가 커져 $\hat{R}$이 작아지고
  • $w$가 $0.632$에 가까워짐.
• 반대로 과적합이 심할수록
  • $\hat{R} \to 1$, $w \to 1$로 수렴하여
  • OOB accuracy만을 신뢰하는 방향으로 자동 조정됨.

Random Forest는 OOB 방식을 기본 평가 방식으로 사용함 (대규모 데이터 권장)

 

일반적인 소규모 데이터셋에서는 .632 또는 .632+를 권장함.

---

References

Efron, B. (1983). Estimating the error rate of a prediction rule: improvement on cross-validation. Journal of the American Statistical Association.

https://www.jstor.org/stable/2288636?seq=1

 

Efron, B., & Tibshirani, R. (1997). Improvements on cross-validation: The .632+ bootstrap method. Journal of the American Statistical Association, 92(438), 548–560.

https://www.jstor.org/stable/2965703