AdaBoost [medium]

v1 Weighted Stump 한 개로는 약한 분류기 (weak learner). AdaBoost (Freund & Schapire 1997): T 라운드 반복, 매번 오분류된 샘플의 가중치를 증가 시켜 다음 stump 이 집중하게 함.

알고리즘 (Discrete AdaBoost, y ∈ {-1, +1})

1. 초기화: $w_i = 1/N$.
2. $t = 1, \ldots, T$:
   • 가중 stump $h_t$ fit.
   • 가중 오류율: $\epsilon_t = \sum_i w_i \cdot \mathbb{1}[h_t(x_i) \ne y_i]$.
   • 만약 $\epsilon_t \ge 0.5$ → 멈춤 (weak learner 조건 실패).
   • 가중치 $\alpha_t = \tfrac{1}{2} \log\tfrac{1 - \epsilon_t}{\epsilon_t}$.
   • 업데이트: $w_i \gets w_i \cdot \exp(-\alpha_t y_i h_t(x_i))$, 정규화.
3. 최종 예측: $H(x) = \text{sign}\left(\sum_t \alpha_t h_t(x)\right)$.

직관

• $\epsilon_t$ 작음 → $\alpha_t$ 크게 (좋은 learner 에 큰 투표권).
• 오분류된 샘플: $y_i h_t(x_i) = -1$ → $w_i$ 증가.
• 맞은 샘플: $y_i h_t(x_i) = +1$ → $w_i$ 감소.

과제

함수 fit_predict_adaboost(X_train, y_train, X_test, n_estimators) 를 완성하세요.

• y_train ∈ {-1, +1}.
• 반환: y_test_pred ∈ {-1, +1}, shape (M,).
• 각 round 에서 stump 을 fit → α 계산 → 가중치 업데이트.
• 중간에 $\epsilon \ge 0.5$ 나오면 종료 (더 쓸 수 없는 learner).
• $\epsilon = 0$ 에서 $\alpha$ 폭주 방지: ε = clip(ε, 1e-10, 1 - 1e-10).

테스트 케이스