단단한 머신러닝 8 앙상블 학습(markdown)

# 객체와 앙상블

앙상블 학습은 다수의 학습기를 생성하고 결합해서 학습을 시도하는 방법이다. 아래와 같은 구조를 갖고 있다.

여기서 같은 형태의 학습기만 있다면 동질적(homogeneous)이라고 하며, 서로 다른 형태의 객체 학습기로 이루어진 앙상블은 이질적(heterogeneous) 앙상블이라고 부른다.

일반적으로 앙상블 학습은 다수의 학습기가 결합해 단일 학습기보다 우수한 일반화 성능을 얻는다. 약한 학습기(일반화 성능이 랜덤 예측 학습기보다 조금 더 나은 학습기)를 통해 이론적으로는 증명되지만, 현실에서는 여러가지 이유로 그렇지 못한 경우도 종종 있다.

<aside>
💡

위 그림에서 ✓는 정확한 분류를, X는 잘못 분류되었다는 것을 뜻하고 앙상블 학습의 결과는 다수결 투표 방법을 통해 생성된다. 여기서 알 수 있는 것은 다음과 같다.

**좋은 앙상블 모델을 얻고 싶다면 객체 학습기는 최대한 좋은 성능을 갖는 동시에 다양해야 한다.**

</aside>

## 객체 학습기의 수와 오차율

객체 학습기의 수와 오차율 사이에는 어떤 상관관계가 있을까? 이진 분류 문제를 가정하고 정의해보자.

$$
P(h_i(x) \neq f(x)) = \epsilon.
$$

여기서 f(x)가 학습하고자 하는 함수이고 h_i(x)가 객체 학습기이다.

만약 앙상블이 간단한 투표 방법으로 T개의 객체 학습기를 결합하고 과반수 이상의 정답을 맞히면 앙상블 분류기가 정답을 맞혔다고 가정하자.

$$
H(x) = \text{sign} \left( \sum_{i=1}^{T} h_i(x) \right).
$$

만약 기초 분류기의 오차율이 서로 독립적이라면, Hoeffding 부등식에 의해 앙상블 오차율은 다음과 같다.

$$
\begin{align*}P(H(\mathbf{x}) \neq f(\mathbf{x})) &= \sum_{k=0}^{\lfloor T/2 \rfloor} \binom{T}{k} (1-\epsilon)^k \epsilon^{T-k} \\&\leq \exp \left( -\frac{1}{2} T (1 - 2\epsilon)^2 \right)\end{align*}
$$

위 식에서 알 수 있듯, 앙상블 내의 객체 분류기 수 T가 증가할수록 앙상블의 오차율은 기하급수적으로 하락하고 최종적으로는 0에 가까워진다.

하지만 위 관계는 객체 학습기가 서로 독립적이라는 가정을 바탕으로 하고 있기 때문에, 현실과는 큰 괴리가 있다. (실제로 객체 학습기는 같은 문제를 해결하기 위해 해결되므로 결코 상호 독립적일 수 없다)

사실상 객체 학습기의 정확성과 독립성은 근본적으로 모순되기 때문에, 매우 높은 정확도를 달성한 후 다양성을 늘리려 한다면 정확성이 희생되어야할 수 밖에 없다.

<aside>
💡

결국 좋지만 다른 객체학습기를 어떻게 생성하고 결합하느냐가 앙상블 학습의 핵심이다.

</aside>

현재 앙상블 학습법은 객체 학습기의 생성 방식을 기준으로 크게 두 가지로 나뉜다.

- serialization : 객체 학습기 간 강한 의존관계가 있어 연속적으로 생성되는 방법
    - **boosting**
- parrelization : 객체 학습기 간 의존관계가 약하고 동시 생성이 가능한 방법
    - bagging
    - **random forest**

# 부스팅

부스팅은 약한 학습기를 강한 학습기로 향상할 수 있는 알고리즘 계열을 의미한다. 이러한 알고리즘 계열의 작동 메커니즘은 서로 유사하다.

1. 초기 훈련 세트로부터 객체 학습기 훈련
2. 객체 학습기가 학습한 표현을 기반으로 훈련 샘플 분포 조정 (이때 학습기에서 오류를 범했던 훈련 샘플에 대해 조정)
3. 조정 후의 샘플 분포를 기반으로 다음 학습기 훈련

## AdaBoost

이러한 알고리즘 중 가장 유명한 것은 AdasBoost이다. 다음과 같은 객체 학습기의 선형 조합에서

$$
H(x) = \sum_{t=1}^{T} \alpha_t h_t(x)
$$

다음처럼 정의된 지수 손실함수를 최소화 하는 알고리즘이다.

$$
\ell_{\text{exp}} (H | \mathcal{D}) = \mathbb{E}_{\mathbf{x} \sim D} \left[ e^{-f(\mathbf{x})H(\mathbf{x})} \right]
$$

알고리즘은 다음과 같다.

입력:

- 훈련 세트 $D = \{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \dots, (\mathbf{x}_m, y_m)\}$
- 기초 학습 알고리즘 $\mathfrak{L}$
- 훈련 횟수 $T$

과정:

1. 초기 가중치 분포 설정
$\mathcal{D}_1(\mathbf{x}) = 1/m$
2. 반복 학습 ($t = 1$ to $T$):
    - 기초 학습기 훈련: 가중치 분포 $\mathcal{D}_t$를 사용하여 학습 진행
    $h_t = \mathfrak{L}(D, \mathcal{D}_t)$
    - 오차율 계산: 현재 분포 $\mathcal{D}t$*에서의 예측 실패 확률
    $\epsilon_t = P{\mathbf{x} \sim \mathcal{D}_t}(h_t(\mathbf{x}) \neq f(\mathbf{x}))$*
    - 조기 종료 조건: 오차율이 0.5를 초과하면 중단
    `if` $\epsilon_t > 0.5$ `then break`
    - 학습기 가중치($\alpha_t$) 결정: $\alpha_t = \frac{1}{2} \ln \left( \frac{1-\epsilon_t}{\epsilon_t} \right)$
    - 데이터 가중치($\mathcal{D}_{t+1}$) 업데이트:
    $\mathcal{D}_{t+1}(\mathbf{x}) = \frac{\mathcal{D}_t(\mathbf{x}) \exp(-\alpha_t f(\mathbf{x}) h_t(\mathbf{x}))}{Z_t}$
3. 최종 모델 출력 (가중치 투표)
$H(\mathbf{x}) = \text{sign} \left( \sum_{t=1}^{T} \alpha_t h_t(\mathbf{x}) \right)$
- $\alpha_t$: 해당 학습기가 전체 결과에 얼마나 기여할지 결정합니다. 오차율($\epsilon_t$)이 0에 가까울수록 $\alpha_t$는 무한대로 커집니다.
- $\mathcal{D}_{t+1}$: 이전 단계에서 틀린 샘플은 $\exp(\alpha_t)$가 곱해져 가중치가 커지고, 맞은 샘플은 $\exp(-\alpha_t)$가 곱해져 작아집니다.

<aside>
💡

AdaBoost 알고리즘은 지수손실함수를 최소화하는 방향으로 동작한다.

만약 H(x)가 지수 손실 함수를 최소화할 수 있다면,

$$
\frac{\partial \ell_{\exp}(H \mid \mathcal{D})}{\partial H(x)} = -e^{-H(x)} P(f(\boldsymbol{x}) = 1 \mid \boldsymbol{x}) + e^{H(x)} P(f(\boldsymbol{x}) = -1 \mid \boldsymbol{x})
$$

이고, 좌변을 0으로 만들면

$$
H(x) = \frac{1}{2} \ln \left( \frac{P(f(x) = 1 \mid x)}{P(f(x) = -1 \mid x)} \right)
$$

이다. 따라서,

$$
\begin{align*}\text{sign}(H(\mathbf{x})) &= \text{sign}\left(\frac{1}{2}\ln\frac{P(f(\mathbf{x})=1|\mathbf{x})}{P(f(\mathbf{x})=-1|\mathbf{x})}\right) \\&= \begin{cases}1, & P(f(\mathbf{x})=1|\mathbf{x}) > P(f(\mathbf{x})=-1|\mathbf{x}) \\-1, & P(f(\mathbf{x})=1|\mathbf{x}) < P(f(\mathbf{x})=-1|\mathbf{x})\end{cases} \\&= \operatorname*{arg\,max}_{y \in \{-1,1\}} ...