Ensemble Methods II

Bias-Variance Tradeoff

데이터 생성 모델

$x,y$ : 모집단(population)에서 관측된 입력–출력 쌍
ε : 노이즈(오차) 항, $\epsilon \sim \mathcal{N}(0, \sigma^2)$

함수 정의

• 진짜 함수 $f(x)$ : 입력 x와 y 사이의 실제 관계
• 추정 함수 $\hat{f}(x)$ : 표본(sample) 데이터를 통해 학습된 모델의 예측 함수

예측 오차(Err) 정의

• Bias : 모델 추정치의 평균이 실제 함수에서 얼마나 벗어났는지
• Variance : 표본마다 $\hat{f}(x)$가 얼마나 변동하는가
• Irreducible Error ($σ^2$): 데이터 자체의 본질적 잡음.

복잡도↑ → Bias↓ but Variance↑
단순도↑ → Variance↓ but Bias↑

최적 모델은
전체 $Err(Bias^2+Variance+σ^2)$를 최소화하는 지점에 위치

Bias–Variance Tradeoff와 앙상블 기법의 역할

• Bagging 은 모델 다양성으로 분산을 낮춤
• Boosting 은 순차적 보완 학습으로 편향을 낮춤

Boosting

앞선 모델이 틀린 샘플에 집중하는 방식으로,
순차적으로(sequentially) 여러 약한 학습기(base learner)를 학습시켜
최종 예측을 개선하는 기법

1. 초기 모델 $h_1$학습

2. 오류 샘플 가중치 조정
   $h_1$이 잘못 예측한 데이터에 가중치를 높여 다음 학습에 반영

3. 두 번째 모델 $h_2$ 학습 → 전 단계 오류 보완

4. 반복

AdaBoost (Adaptive Boosting)

이전 모델이 틀린 샘플의 가중치(weight)를 높여,
다음 모델이 이들을 더 중점적으로 학습하도록 함

Gradient Boosting

이전 모델의 오차(잔차, residual)를 다음 모델이 채워 나감

AdaBoost

Algorithm

훈련 샘플 $\{(x_i, y_i)\}_{i=1}^m, y_i \in \{-1, +1\}$
반복 횟수 T 설정
각 샘플의 초기 가중치 분포 $D^{(1)}(i) = \frac{1}{m}$

반복 학습 (for t=1,…,T)

1. 기본 분류기 학습

   $f_t: x \mapsto \{-1, +1\} \text{ using weights } D^{(t)}$

2. 오류율 계산

   $\mathcal{E}_t = \sum_{i: f_t(x_i) \neq y_i} D^{(t)}(i)$

3. 모델 가중치

   $\alpha_t = \frac{1}{2} \ln\left(\frac{1 - \mathcal{E}_t}{\mathcal{E}_t}\right)$

4. 샘플 가중치 업데이트

   $D^{(t+1)}(i) = \frac{D^{(t)}(i) \exp(-\alpha_t y_i f_t(x_i))}{Z^{(t)}}$

: $Z^{(t)}$는 가중치 합이 1이 되도록 정규화

5. 최종 예측
   $F(x) = \text{sign}\left(\sum_{t=1}^T \alpha_t f_t(x)\right)$

Round 1 결과

초기 가중치 분포 : $D^1(i) = \frac{1}{10} = 0.1 \quad (\forall i)$

첫 번째 약한 분류기 $f_1$ 학습

• 틀린 샘플 수: 3/10 → 오류율
  $\epsilon_1 = \frac{3}{10} = 0.3$

• 모델 가중치

  $\alpha_1 = \frac{1}{2} \ln\left(\frac{1 - \epsilon_1}{\epsilon_1}\right) = \frac{1}{2} \ln\left(\frac{0.7}{0.3}\right) \approx 0.42$

가중치 업데이트 → $D^2$

각 샘플 i의 새로운 가중치는

정답 ($y_i f_1(x_i)=+1$)인 경우 :

오답 ($y_i f_1(x_i)=-1$)인 경우 :

→ 첫 모델이 틀린 3개 샘플의 가중치가 크게 올라가고(≈0.152),
맞춘 나머지 7개는 줄어듦(≈0.065)

Round 2

두 번째 약한 분류기 $f_2$ 학습
$D^2$ 가 반영된 데이터로 새로운 경계 학습

오류율 : $ε_2=0.21$

모델 가중치

Round 3

다시 업데이트된 가중치 $D^3$
: $f_2$가 틀린 샘플의 가중치가 다시 상승

세 번째 약한 분류기 $f_3$ 학습
: $D^3$ 를 반영해 또 다른 경계 학습

오류율 : $ε_3=0.14$

모델 가중치

흐름

매 라운드마다

• 가중치 분포 $D^t$에 따라 약한 분류기 $f_t$를 학습

• 오류율 $ε_t$ 계산 → 모델 가중치 $α_t$ 결정

• 오분류된 샘플의 가중치를 올려 다음 라운드에 더 집중 학습

$ε_t$ 가 작아질수록 $α_t$는 커져,
성능이 좋은 분류기는 최종 앙상블에서 더 큰 비중을 갖게 됨

AdaBoost 회귀 버전

손실 함수 선택

잔차(residual) 대신 세 가지 형태의 샘플별 손실 $L_i$을 쓸 수 있음

Linear :

Square law:

Exponential:

가중치 갱신

샘플 가중치 업데이트 계수

($p_i$ : 현재 샘플 가중치)

각 샘플 $i$의 다음 라운드 가중치는

$1-L_i$가 클수록(손실이 작을수록) 가중치가 더 증가

최종 예측

회귀든 분류 모두 가중합 방식을 사용

Gradient Boosting

각 단계에서 이전 모델이 놓친 부분(잔차, residual)을 다음 모델이 학습하도록 함

Gradient Boosting = Gradient Descent + Boosting

• 손실 함수(Loss) : MSE

• 손실 함수의 Gradient
손실 함수 $L$에 대한 모델의 예측값 $F(x_i)$을 미분

• 초기 모델 학습
  : 첫 스윙 → $F_0$, 손실 = ($y−F_0$)

• 1차 학습 → $F_1=F_0+f_1$
  : 두 번째 스윙 → Δ₁ , 손실 감소 → $(y−F_1)^2$

• 2차 잔차 학습 → $F_2=F_1+f_2$
  : 세 번째 스윙 → Δ₂ , 손실 추가 감소 → $(y−F_2)^2$

• 최종 예측 $F_4=F_3+f_4$
  : 네 번째 스윙 → Δ₄, 손실 거의 0에 근접
  

→ 작은 보정(잔차 예측) 을 반복해 합산

Example 1

Example 2

• Tree 1
  원본 $y$를 예측
  오차(잔차)가 많이 남아 있음.

• Tree 2
  남은 잔차 $r^{(2)}(x) = y - f_1(x)$를 목표로 두고
  두 번째 트리 $f_2(x)$ 를 학습.
  첫 트리가 놓친 부분(잔차)을 보정.

• Tree 3
  다시 남은 잔차 $r^{(3)}(x) = y - [f_1(x) + f_2(x)]$ 를 학습하는
  세 번째 트리 $f_3(x)$.
  점점 보정 폭이 작아지면서 전체 예측 $F_3(x) = f_1 + f_2 + f_3$
  가 Ground truth 곡선에 가까워짐

• 전체 예측 합산
  $F_T(x) = f_1(x) + f_2(x) + f_3(x) + \cdots$
  각 트리는 잔차만을 예측해 누적 보정
  트리가 많아질수록 모델은 복잡한 패턴을 더 정교하게 캡처

Algorithm

초기 예측값 설정

반복 보정 (for m=1 to M)

• 잔차(음의 gradient) 계산
  : 현재 모델 $f_{m-1}$가 틀린 만큼을 샘플별로 구함

  $r_{im} = - \frac{\partial L(y_i, f(x_i))}{\partial f(x_i)} \Bigg|_{f=f_{m-1}}$

  $r_{im}$ : m−1번째 모델이 i번째 샘플에 대해 틀린 정도

• 회귀 트리
  : 입력 $x_i$, 목표 $r_{im}$로 회귀 결정트리 $h_m$를 학습

• 리프별 최적 보정량 계산
  $R_{jm}$ : m번째 트리가 만든 j번째 리프 영역 (샘플들을 모아 놓은 구간)

  $\gamma_{jm} = \arg \min_{\gamma} \sum_{x_i \in R_{jm}} L(y_i, f_{m-1}(x_i) + \gamma)$

  $\gamma_{jm}$ : 각 리프 $R_{jm}$ 안에서 얼마만큼 예측을 보정할지 최적값

• 모델 업데이트

  $f_m(x) = f_{m-1}(x) + \sum_{j=1}^{J_m} \gamma_{jm} \mathbf{1}\{x \in R_{jm}\}$

  리프 구간마다 계산된 $\gamma_{jm}$를 더해 모델을 업데이트

Regularization

• Shrinkage (학습률, learning rate)

$η$ 가 작을수록 한 번에 보정하는 양이 줄어들어(느린 학습) 과적합 위험 감소

• Subsampling (Stochastic Gradient Boosting)

매 반복마다 전체가 아닌 데이터의 부분집합만 랜덤 샘플링해 트리를 학습
보통 replacement 없이 샘플링

• Early Stopping
학습 과정 중 검증 데이터(validation set)에 대한 오차가
더 이상 개선되지 않으면 반복 중단.

Variable importance

: Gradient Boosting에서의 변수 중요도

• 단일 트리 $T_m$ 내에서 변수 $j$의 중요도

트리 $T_m$에 말단 노드(terminal node)가 L개 있으면
→ 가능한 분할(split) 횟수는 $L−1$ 번

각 분할 i에서 얻는 정보 이득(Information Gain, $IG_i$)이 있고,
이 분할에 사용된 변수가 $j$라면 $IG_i$를 더해줌.

• 전체 앙상블(모든 M개의 트리)에 걸친 변수 $j$의 중요도

M개의 트리를 평균내어 최종 중요도를 구함.

Variants of Gradient Boosting

1. XGBoost (eXtreme Gradient Boosting)
2. LightGBM (Light Gradient Boosting Machine)
3. CatBoost
4. Regularized Greedy Forest (RGF)
5. H2O GBM

XGBoost (eXtreme Gradient Boosting)

Regularization

• 전체 목적 함수

$\hat{y}_i^{t-1}$ : 이전까지의 예측값
$f_t$ : 이번 단계에 추가할 트리

• 정규화 항 $\Omega(f_t)$

T: 트리의 말단 노드 수
$w_j$ : 각 말단 노드의 예측값(leaf weight)
λ: L2 페널티 강도
α: L1 페널티 강도

Handling missing values (결측치 처리)

분할 임계값(ex. x<0.6)을 고를 때 그 임계값 하나를 시험할 때마다
결측값을 왼쪽에 넣었을 때의 이득 vs 오른쪽에 넣었을 때의 이득 비교

• x>1.9 로 분류할 경우 여러 클래스가 섞여 있기 때문에 불순도가 높음.
• x<0.6 로 좌/우 노드를 나누면, 각 자식 노드의 불순도가 낮아짐.

가장 이득이 큰 (임계값, 결측 기본방향) 조합을 선택
: x<0.6 , 결측치는 항상 왼쪽으로

→ 별도의 결측치 보간(imputation) 없이,
각 분할 기준마다 최적으로 선택된 방향으로 자동 처리

Light GBM (Light Gradient Boosting Machine)

Leaf-wise growth (vs. Level-wise growth)

• Level-wise growth (기존 XGBoost 등)
깊이(depth) 기준으로 한 레벨에 속한 모든 leaf 노드를 동시에 분할(split)

→ 같은 깊이의 모든 노드 분할을 강제하기 때문에,
손실 감소(gain)가 큰 노드만 골라 분할하는 것보다 효율이 떨어질 수 있음

• Leaf-wise growth (LightGBM)
이득(gain)이 가장 큰 잎노드 하나만 골라 분할
그 다음에도, 전체 중 손실 감소량이 최대인 단일 잎노드를 분할하는 식으로 진행.

한쪽 가지(branch)가 깊게 자라나면서 가장 큰 손실 감소를 빠르게 달성

→ 특정 가지가 지나치게 깊게 파여 과적합(overfitting) 위험이 있을 수 있음

Gradient-based One-Side Sampling (GOSS)

: 잔차(gradient)가 큰 샘플에 집중하기 위해 관측치를 선별해서 트리 학습에 사용

• 잔차(Residual) 기준으로 정렬
  이전 트리까지의 예측값과 실제값의 차이(잔차)를 구한 뒤,
  절댓값이 큰 순서(= 모델이 크게 틀린 순서)로 데이터를 내림차순 정렬

• 상위 a%(ex. 20%) 전부 사용
  정렬된 데이터 중 절댓값 잔차 상위 20%를 무조건 학습에 포함
  모델이 가장 크게 실수한 사례에 집중하여 다음 트리를 학습

• 하위 나머지 중 b%(ex. 10%)만 랜덤 샘플링
  나머지 80% 중에서 일부만 무작위 추출
  : 과도한 데이터 축소로 편향이 생기지 않도록,
  잔차 작은(잘 맞춘) 샘플도 포함

Exclusive Feature Bundling (EFB)

$x_1$ 와 $x_4$은 한 번도 두 컬럼이 “둘 다 0”이 되는 행이 없음.
$x_2$ 와 $x_3$도 한 번도 두 컬럼이 “둘 다 0”이 되는 행이 없음.
→ Exclusive 한 feature 쌍

• 피처 묶기 (EFB)
$x_1$ 와 $x_4$은 Exclusive 하므로, 둘을 하나로 합쳐도 정보가 겹치지 않음

• 기준 컬럼을 잡음. (ex. $x_1$)
• $x_1$ 값은 그대로 두고
• 오프셋(offset)을 더함
  : $x_4$에서 0이 아닌 모든 값에 x1의 최댓값(=3) 더해줌

• 충돌(conflict) 처리
$x_1$ 와 $x_4$ 둘 다 원래 비어 있지 않고 nonzero 값을 가질 경우,
번들된 $x_{14}$ 에서 숫자가 $x_4$로부터 온 건지 $x_1$로부터 온건지 알 수 없음.
→ 충돌 시 기준 피처의 원래 값을 사용