Ensemble Methods I

What is Ensemble?

여러 개의 약한 모델(Weak learners)을 조합해서
강력한 모델(Strong learner)을 만드는 방법

Homogeneous vs. Heterogeneous

Homogeneous :
→ 비슷한 종류(같은 알고리즘)의 약한 모델들을 결합하는 것.
ex. 전부 Decision Tree만 사용해서 Random Forest를 만드는 경우

Heterogeneous :
→ 서로 다른 종류(다른 알고리즘)의 약한 모델들을 결합하는 것.
→ ex. Decision Tree, SVM, Neural Network를 함께 사용하는 Stacking

Bias-Variance Tradeoff

Ensemble Methods

Error Decomposition

모델이 $x$를 예측할 때의 평균 제곱 오차(MSE)는 세 부분으로 나뉨

앙상블로 오차 줄이기

Reduce the variance → Bagging (ex. Random Forest)

Reduce the bias → Boosting

Motivation: Bagging

Bagging(Bootstrap AGGregatING)
: 편향에는 손대지 않고, 분산만 줄여주는 앙상블 기법

m개의 독립된 학습 세트를 가정하고,
각 세트로 학습된 모델들이 내린 예측 $y_1, \dots, y_m$ 을 단순 평균하여 최종 예측

편향(Bias): 원래 모델과 동일 → 변하지 않음
분산(Variance): m배 독립시킨 평균이므로 $1/m$ 로 줄어듦

Bagging

: 여러 모델을 앙상블해 예측의 안정성을 높이는 기법

여러 번 무작위 재추출(bootstrapping)
→ 여러 모델 학습 → 예측 결합(aggregating)

• 원본 데이터 N개에서 부트스트랩 샘플을 여러 개 (ex. m개) 생성
  : 중복 허용(with replacement)하여 각 샘플도 크기 N

• 각 샘플로 독립적인 모델 m개를 학습

• m개 모델의 예측을 평균(회귀) 혹은 투표(분류)하여 최종 출력

부트스트래핑(Bootstrapping)

: 원본 데이터에서 균일(random)하게 복원 추출

하나의 샘플에는 중복 데이터가 포함될 수 있음.
이렇게 만든 m개의 샘플집합이 각각 다른 모델의 학습용 데이터가 됨.

: 원본에서 임의로 N개를 뽑되, 뽑은 항목을 다시 원본에 돌려놓고 또 뽑음

Bagging

1. Training Set
   원본 데이터로부터

2. Subset 생성 (부트스트랩 샘플)
   부트스트래핑 과정을 통해 m개의 서로 다른 서브셋(subset 1…m) 생성

3. 약한 학습기(Weak Learner) 학습
   각 부트스트랩 샘플마다 동일한 모델 구조를 학습
   모델 간 학습 데이터가 달라 서로 다른 오차 패턴을 가짐

4. 개별 예측(prediction)
   학습된 m개의 모델이 각각 예측을 수행

5. Aggregation
   회귀: m개 예측의 단순 평균
   분류: 다수결 투표(Majority Vote)

→ 편향(Bias)은 유지하면서 분산(Variance)은 크게 줄여,
예측 성능과 안정성을 향상

Bagging: Aggregation Method

: Bagging의 분류문제에서의 예측 결합(aggregation) 방법

상황

이진 분류 문제 $(y∈{0,1})$

m개의 서로 다른 부트스트랩 모델이 각자 입력 x에 대해
확률 $\hat{p}_i = f_i(x) \in [0, 1]$ 예측

Majority Voting (다수결)

Weighted Voting (Accuracy-Based)

: 각 모델의 투표에 동일한 비중을 주지 않고
사전에 측정한 성능 지표를 가중치로 사용

1. 모델별 정확도 Acc(i) 를 미리 계산해 둠

2. 각 모델의 이진 예측 $\hat{y}_i \in \{0, 1\}$

3. 가중치 합산
   클래스 $k∈{0,1}$ 에 대해

   $S_k = \sum_{i=1}^{m} \text{Acc}(i) \mathbb{I}(\hat{y}_i = k)$

ex.
양성(1) 투표에 해당하는 모델들의 정확도 합
$S_1=0.80+0.75+0.88+⋯+0.83$ (총합)

음성(0) 투표에 해당하는 모델들의 정확도 합
$S_0=…$

4. 가중 다수결 결정
   $\hat{y}_{\text{bagg}} = \arg \max_{k \in \{0, 1\}} \frac{\sum_{i=1}^{m} \text{Acc}(i) \mathbb{I}(\hat{y}_i = k)}{\sum_{i=1}^{m} \text{Acc}(i)}$
   클래스 k 투표를 한 모든 모델의 정확도 합을 구한 뒤,
   전체 모델 정확도 합으로 나눠 비율을 계산
   → 정확도 합이 더 큰 쪽을 최종 예측으로 선택

장점

성능이 높은 모델에 더 높은 영향력 부여 → 앙상블의 전반적 정확도 향상
단순 다수결 대비, 저성능 모델의 잘못된 투표가 미치는 영향 감소

Stacking

여러 서로 다른(혹은 같은 구조지만 하이퍼파라미터가 다른)
기본 분류기(Base Learners)를 학습시키고,
이들의 예측을 다시 하나의 메타 분류기(Meta-Classifier)에 입력하여
최종 예측을 얻는 앙상블 기법

→ 모델을 “층(layer)”처럼 수직결합해,
1차 예측을 다시 학습시킴으로써 성능을 극대화

1. 입력
   앙상블 크기 T
   원본 훈련 집합 $S = \{(x_1, y_1), \dots, (x_N, y_N)\}$

2. 모델 생성 (for t=1 to T)
   부트스트랩 샘플 $S_t$ 구성 : S에서 크기 N 만큼 복원 추출
   모델 $h_t$을 $S_t$로 학습
   앙상블에 $h_t$ 추가

3. 예측 단계 (새로운 입력 ($x',y'$)에 대해)
   회귀: 각 $h_t(x')$값을 평균
   분류: 각 $h_t(x')$ 클래스 레이블을 투표(voting)

: Bagging을 통해,
여러 약한 학습기(weak learners)의 decision boundary 를 결합해
보다 안정적이고 일반화 성능이 좋은 최종 경계를 얻는 과정

Random Forest

: Bagging과 달리 모델 간 상관성(correlation) 때문에
이론적 최적치인 $1/m$ 분산 감소를 얻을 수 없음

Random Forest의 트리들은

• 부트스트랩 샘플이 서로 중복되고,
• 특성(feature) 랜덤 선택도 일부 공유되기 때문에

서로 완전 독립이 아님.
따라서,

실제 분산 감소율

: 모델 간 상관계수 $ρ$ 에 따라 결정

Random Forests

Random Forests = Bagging된 결정트리 + 노드별 무작위 특성 선택

• 여러 개의 결정트리(Decision Trees)를
  Bagging(부트스트랩 앙상블)으로 결합

• 추가로 트리 간 예측의 상관성(correlation)↓ 을 위한 무작위성(randomness) 도입

B: 생성할 나무(tree) 개수
훈련 집합 크기 N
전체 특성 수 p
노드 분할 시 무작위로 선택할 특성 수 m (m<p)

알고리즘

반복: i=1부터 B까지

1. 부트스트랩 샘플링
   원본 데이터에서 복원추출로 크기 N인 샘플 $S_i$ 생성

2. 의사결정트리 학습 (루트 노드부터)
   현재 노드의 샘플 수 > 최소 노드 크기일 때까지:

   1. 전체 p개 특성 중 무작위로 m개 추출
   2. 이 m개 특성 중 최적 분할 기준(예: 지니, 엔트로피)을 가장 잘 만족시키는 특성과 분할값 찾기
   3. 해당 분할로 노드를 둘로 분할(split)
   4. 재귀적으로 자식 노드에도 동일 과정을 적용

모델 반환 : 이렇게 생성된 B개의 트리를 묶어 Random Forest 완성

Random Forests: Variable Importance

각 입력 변수의 값을 임의로 뒤섞었을 때(Randomly permute)
Out-Of-Bag(OOB) 오류가 얼마나 증가하는지 측정하여,
변수의 중요도를 평가하는 방법

1. 기준 OOB 오류 계산
   각 트리마다 해당 트리가 학습에 쓰이지 않은(OOB) 샘플로 예측
   → 오류 $N_0$ 기록

2. 변수 j를 Permute
   모든 트리의 OOB 샘플에서 변수 j 열(Column)만 무작위로 뒤섞기.
   다시 예측 → 오류 $O_j$ 기록.

3. 중요도 점수 산출
   트리별로 $Δ_j=O_j-N_0$ 계산.
   m개의 트리 전체에서 $Δ_j$ 의 평균(mean) 과 표준편차(std) 이용

   평균이 클수록: 그 변수를 뒤섞었을 때 성능이 크게 떨어짐 → 중요도가 높음 (모델 예측에 큰 영향을 미치는 핵심 변수)
   표준편차는 중요도 안정성(variance)을 나타냄

중요도 판단 기준

변수가 중요하려면:

• OB 오류가 Permutation 전후에 크게 달라져야 함
• 그 차이의 표준편차가 낮아야 함 (안정적)

트리별 OOB 오류 차이

m번째 트리에서 변수 i를 섞기 전 OOB 오류: $e_i^m$
섞은 후 OOB 오류: $p_i^m$
두 값의 차이: $d_i^m = p_i^m - e_i^m$

전체 트리에서 평균·분산

평균 차이 :

표준편차 :

변수 중요도 점수

정규화된 중요도 :

$v_i$ 가 클수록
변수를 섞으면 오류가 크게 오르고, 그 차이가 안정적 → 높은 중요도

가로축 Loss (1 − AUC) : 중요도 척도

• AUC(Area Under the Curve) : 이진 분류기의 성능을 평가하는 지표

$Δ_{loss}$
= (OOB loss after permuting a variable)−(Original OOB loss)
= $(1−AUC_{permute})−(1−AUC_{orig})$
= $AUC_{orig}-AUC_{permute}$

→ gender (성별) : 뒤섞으면 예측력 가장 크게 저하