Bootstrap Sampling 기반 Accuracy 추정 지표

0. 왜 Bootstrap Accuracy Estimation이 필요한가

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

Bootstrap accuracy estimation은

• 복원 추출(sampling with replacement) 을 반복(Bootstrap Iteration)하여
• 하나의 dataset으로 여러 training/evaluation 조합을 만들고 
• 이를 통해 모델의 일반화 성능을 추정하는 방법임.
• 단일 train/test split 의 경우와 비교하여 "분산(variance)을 줄인 보다 안정적인 성능 추정" 이 가능

 

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

[ML] Bootstrap Sampling

---

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

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

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

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

 

이 문서에 다룬 것 외에도 Optimism-corrected Accuracy도 있음:

2026.05.26 - [Programming/ML] - Optimism-corrected Accuracy

Optimism-corrected Accuracy

---

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 Iteration 갯수 $B$	100

 

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

$$ \begin{aligned} \text{Acc}_{\text{train}} &= 0.95 \quad \text{(평균 훈련셋 accuracy, optimistic)} \\ \text{Acc}_{\text{OOB}} &= 0.72 \quad \text{(평균 OOB accuracy, pessimistic)}\end{aligned}$$

• $\text{Acc}_\text{train}$는 Resubstitution Estimate라고  불리며, bootstrap iteration마다 훈련에 사용되었던 자기 bootstrap sample에서 다시 평가한 평균 accuracy 임.
• $\text{Acc}_\text{OOB}$는 각 bootstrap iteration에서 선택되지 않은 out-of-bag (OOB) sample을 이용해 평가한 accuracy임

---

2. Resubstitution Estimate

2-1. Concept

• Bootstrap Iteration (b)마다 bootstrap sample $\mathcal{D}^{*(b)}$를 복원 추출로 생성함.
• 각 bootstrap sample $\mathcal{D}^{*(b)}$로 모델 $\mathcal{M}^{(b)}$를 학습함.
• 학습에 사용한 동일한 bootstrap sample $\mathcal{D}^{*(b)}$에서 다시 평가한 accuracy를 (b)-th resubstitution accuracy라고 함.

$$
\text{Acc}_{\text{resub}}^{(b)} = \text{Acc}\left(\mathcal{M}^{(b)}, \mathcal{D}^{*(b)}\right)
$$

따라서 bootstrap 전체에 대한 평균 resubstitution accuracy는 다음과 같이 정의됨.

$$\text{Acc}_{\text{resub}} = \frac{1}{B} \sum_{b=1}^{B} \text{Acc}\left(\mathcal{M}^{(b)}, \mathcal{D}^{*(b)}\right)$$

 

위 예제에서 $\text{Acc}_{\text{resub}} = 0.95$ 로 둔 값이 이에 해당함.

• 이는 각 bootstrap model을 자신이 학습한 데이터로 다시 평가한 값이므로,
• training accuracy라고 볼 수 있지만 더 정확한 명칭은 평균 resubstitution accuracy (=mean resubstitution estimate)임.

resubstitution이 붙은 이유는
학습에 사용한 sample을 평가 단계에서 다시 대입해서 사용하기 때문

---

2-2. Problem: Optimistic Bias

Resubstitution estimate는 학습에 사용한 sample을 다시 평가에 사용하므로 낙관적 편향(optimistic bias)을 가짐.

• 즉, $\mathcal{M}^{(b)}$ 는 이미 $\mathcal{D}^{*(b)}$를 이용해 학습되었고,
• 평가도 같은 $\mathcal{D}^{*(b)}$에서 수행되므로
• 실제 일반화 성능보다 accuracy가 높게 추정될 수 있음 (=Optimistic bias).

 

특히 다음과 같은 경우 낙관적 편향이 더 커질 수 있음.

• sample 수가 적은 경우
• 모델 복잡도가 높은 경우
• class imbalance가 심한 경우
• 소수 클래스 sample이 bootstrap sample 안에서 반복적으로 중복 선택되는 경우

예를 들어 C4처럼 원본 dataset에 sample이 2개뿐인 소수 클래스는 bootstrap sample 안에서 같은 sample이 여러 번 중복될 수 있음.
이 경우 모델은 해당 sample을 사실상 외운 상태(Memorization)가 되어
training accuracy는 높게 나오지만, 실제 unseen sample에 대한 일반화 성능은 훨씬 낮을 수 있음.

 

따라서 resubstitution estimate는

• 모델의 학습 데이터 적합 정도를 확인하는 용도 등으로 사용할 수 있지만,
• 일반화 성능 추정치로는 부적절함.

---

3. Ordinary Bootstrap Estimate

3-1. Concept

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

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

 

참고로, 이 값은 위의 예제에서 구하진 않음.

---

3-2. Problem: Optimistic Bias

• 이 방식도 optimistic bais가 발생.
• test set으로 사용되는 $\mathcal{D}$에 이론적으로 63.2%가량의 훈련 샘플이 포함 되기 때문임.
• 따라서 prediction error 기준으로는 error를 과소추정하고,
  accuracy 기준으로는 성능을 과대평가하는 optimistic bias가 발생한다.
• 특히 sample 수가 적거나 class imbalance가 심한 multi-class 문제에서는,
  훈련 중 본 sample에 대한 높은 성능이 전체 accuracy를 크게 끌어올릴 수 있다.
• 특히 C4처럼 샘플이 2개뿐인 소수 클래스도 훈련셋에서는 100% accuracy를 낼 수 있어, 실제 일반화 성능 대비 크게 과장된 수치가 됨.
• 적은 수의 데이터를 가진 경우와 멀티 클래스인 경우에 사용 비권장.

Resubstitution estimate보다는 낫지만,
여전히 training data가 evaluation data에 섞이므로 accuracy가 과대평가될 수 있음.

---

4. OOB (Out-of-Bag) Bootstrap

4-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)} \mid i \notin \mathcal{D}^{*(b)} \right\}, \mathbf{x}_i \right) = 0.72$$

• $N$ : the number of samples,
• $\mathcal{M}^{(b)}$ : the model trained on the $b$-th bootstrap sample,
• $\mathcal{D}^{*(b)}$ : is the $b$-th bootstrap training set,
• $i \notin \mathcal{D}^{*(b)}$ : sample $i$ is out-of-bag for model $\mathcal{M}^{(b)}$
• $\text{Acc}(\cdot)$ : the prediction accuracy evaluated using the OOB models for sample $\mathbf{x}_i$

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

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

---

4-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$

---

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

OOB estimate는

• 해당 bootstrap model 기준으로 학습에 사용되지 않은 sample을 평가하므로,
• 앞서 resubstitution estimate나 ordinary bootstrap estimate보다 일반화 성능 평가에 가깝다.

 

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

 

문제 1. 소수 클래스 OOB 평가가 어려움:

 

C4 샘플이 2개 뿐이고

각 C4 샘플이 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는 원본 dataset에 2개뿐임.

하나의 bootstrap sample에서 C4가 학습에 사용되는 기대 sample 수는 다음과 같음:

$$2 \times 0.632 \approx 1.262$$

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

---

OOB의 문제점 정리

세 문제를 종합하면:

$$ \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+ 보정이 등장하게 된 배경이 됨.

보통 OOB는 가장 나쁜(=비관적인) 결과가 나옴!

---

5. .632 Bootstrap

5-1. Concept

• Basic Bootstrap의 optimistic bias (낙관적 편향) 와 OOB의 pessimistic bias (비관적 편향) 를
• 고정 가중치(fixed weight) 로 결합하여 보정하려는 방법.

다음은 Accuracy 기준으로 살펴본 .632 Bootstrap 임:

$$\text{Acc}_{.632} = 0.368 \times \text{Acc}_{\text{resub}} + 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$에서 자연스럽게 유도됨.

---

5-2. Problem: Residual Optimistic Bias under Overfitting

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

즉, 모델이 심하게 과적합되어 $\text{Acc}_\text{resub}$가 거의 의미없는 1.0 이 나온 경우에도, 이를 36.8% 를 반영함.

 

.632 bootstrap은

• resubstitution estimate보다는 덜 낙관적이지만,
• 심한 과적합 상황에서는 여전히 낙관적 편향이 남을 수 있음.

---

6. .632+ Bootstrap

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

 

과적합(over-fit) 정도에 따라 가중치를 동적으로 조정함.

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

No-information accuracy는 feature와 label 사이에 유용한 관계가 없다고 가정했을 때 기대되는 accuracy임.

• 모델이 학습 없이 클래스 분포만으로 예측할 때의 기대 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}}$는 낮아짐.

하지만,

• class imbalance가 심하면 클래스 수가 증가하더라도
• $\acc\gamma_{\text{acc}}$ 가 반드시 낮아지지는 않음.

---

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

Accuracy 기준에서 relative overfitting rate를 다음과 같이 정의:

 

$$\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$ 계산

.632+ bootstrap에서는 OOB accuracy에 부여할 가중치 $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

.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}}$, No-information accuracy)과 같은
  • 최악의 시나리오가 실현된 상태임.
• .632+는 $w = 1.0$으로 설정하여 과적합으로 좋은 듯이 보이는 resubstituion accuracy (=훈련셋에서의 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보다 낮아짐}}$$

---

7. 결론

방법	계산식	결과	편향	특징
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}$이 "substitution accuracy를 얼마나 신뢰할 수 없는가"를 동적으로 정량화($\hat{R}$)하고,
  • 이에 비례하여 더 신뢰할 수 있는 OOB accuracy의 비중을 높인다는 것임.
• 4-class처럼 클래스가 많아 $\gamma_{\text{acc}}$가 낮아지면
  • $\hat{R}$의 분모가 커져 $\hat{R}$이 작아지고
  • $w$가 $0.632$에 가까워짐.
• 반대로 Overfit(과적합)이 심할수록
  • $\hat{R} \to 1$, $w \to 1$로 수렴하여
  • OOB accuracy만을 신뢰하는 방향으로 자동 조정됨.

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

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

 

따라서 일반적으로 작은 dataset에서 단순 resubstitution estimate는 일반화 성능을 크게 과대평가할 수 있음.

OOB estimate는 더 현실적인 평가에 가깝지만,
sample 수가 작거나 class imbalance가 심한 경우에는 불안정할 수 있음.

.632와 .632+는 이러한 문제를 완화하기 위한 bootstrap 기반 보정 추정량이며,
특히 .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

---

같이보면 좋은 자료들

https://dsaint31.me/mkdocs_site/ML/ch02/ml_cls_metrics/

BME

https://ds31x.tistory.com/307

[ML] Classification 과 관련 metrics 에 대한 소개.