시작하며,

그동안 수강과목의 과제와 중간고사를 준비하고 치르느라고 정신이 없었네요. 사실은 좀 더 시간관리를 잘했더라면 블로그에 글도 남길 수 있었을 것 같은데 말이죠. 앞으로 커피를 있는 대로 때려 부어 waking hours에 hype 상태를 유지해야겠어요. 아무튼, 오늘은 머신러닝과 컴퓨터 비전 수업에 종종 등장하는 Adaptive Boost의 theory에 관해서 공부하던 중 새롭게 익힌 인사이트와 이론적 근사함을 글로 슬쩍 남겨보려고 합니다. Adaptive Boost의 problem formulation, algorithm 그리고 theoretical background 순으로 살펴봅니다.

1. Problem Formulation

Adaptive Boost는 ensemble 기반으로 binary classification 문제를 다룹니다.

Training set $S$은 n개의 data points로 구성되어 있습니다.
$S := [(x_1, y_1),(x_2, y_2), . . . ,(x_n, y_n)]$
$y_i ∈ [-1,1], (i=1,2,...,n)$
$x_i, y_i$는 각각 feature, label의 notation을 나타냅니다.

hypotheses set $H$에서 T개의 개별적 hypothesis $h_i(x), (i=1,2,...,T)$를 뽑아 ensemble $H(x)$를 아래와 같이 구성합니다.

$H(x) = \sum_{i=1}^{T} \alpha_ih_i(x)$

$H(x)$는 weak classifier $h_i(x)$의 linear combination의 형태임을 관찰할 수 있습니다. 한편, $H(x)$를 아래와 같이 시간의 변화에 따른 함수 수열로 전환해 생각할 수 있습니다.

생각의 전환!
$H_t(x) = \sum_{i=1}^{t} \alpha_ih_i(x) = H_{t-1}(x) +\alpha_th_t(x)$, $H_0(x) := 0$

태초에는 data point에 대해서 추론을 할 때, 합리적으로 -1과 1의 중간 값인 0으로 초기화합니다. 따라서, $H_0(x)$를 0으로 설정합니다.

Adaptive Boost의 핵심 아이디어는 $t$번째 hypothesis $h_t(x)$가 앞선 $t-1$번째까지의 hypotheses $H_{t-1}(x)$를 교정함에 있습니다.

구체적으로는, $t − 1$개의 hypotheses를 선택해 $H_{t-1}(x)$의 구성을 끝마치고 어떤 data point에서 $H_{t-1}(x)$이 틀렸는지 확인합니다. 그 뒤, 그 data points에 대해서 next step의 hypotheses $H_{t}(x)$가 더 잘 작동할 수 있게 합니다. 알고리즘의 구현을 먼저 이야기해보겠습니다.

2. Algorithm

$D_1(i) ← {1 \over n}, i =1,2,...,n$
$ret ← ∅$
for $t = 1, 2, ..., T:$
$\space\space h_t ← argmin_{h∈H} P_{i∼D_t}(h(x_i) , y_i)$
$\space\space \epsilon_t ← P_{i∼D_t}(h(x_i) , y_i)$
$\space\space \alpha_t ← {1 \over 2} ln({1−ϵt \over ϵt})$
$\space\space ret ← ret ∪ {(α_t, h_t)}$
$\space$ for $i = 1, 2, ..., n:$
$\space\space\space D_{t+1}(i) ← {D_t(i) e(−α_ty_ih_t(x_i)) \over \sum_{j=1}^n D_t(j)e(−α_ty_jh_t(x_j))}$
return ret

1. training set 분포의 초기화

$D_t$를 $t$번째 반복에서 training set $S$의 확률 분포로 정의합니다. n개의 data point마다 $D_t(i)$가 정의 되어있습니다. 처음엔 uniform distribution으로 간주하고 $D_1$의 값을 전부 $1 \over n$으로 초기화합니다.

2. 새로운 hypothesis를 찾아서 ensemble에 반영하기

$t$번째 iteration에서 $D_t$의 분포를 가지는 training set $S$에 대해 가장 좋은 performance를 지닌 $h_t$를 찾아냅니다.

$h_t = argmin_{h∈H}E_{i∼D_t}[ℓ_{0−1}(h, x_i, y_i)] = argmin_{h∈H}P_{i∼D_t}[y_i \neq h(x_i)]$

우리는 이를 "weighted loss"라고 부릅니다. 0-1 loss를 직접 계산할 수 없기 때문에 위와 같이 분포를 활용해서 기대값을 추정합니다.

3. hypothesis에 weight 설정하기

앞선 과정에서 찾은 $h_t$를 활용해 다음과 같이 에러를 구할 수 있습니다.

$\epsilon_t = P_{i∼D_t}[y_i \neq h_t(x_i)]$

이를 활용해 weight $\alpha_t$를 아래와 같이 구합니다.

$α_t:= {1 \over 2} ln{1 − ϵ_t \over ϵ_t}$

에러가 작을수록 weight은 커지게 됩니다. 그 말은 즉, $h_t$가 $H(x)$에 대한 contribution이 적어진다는 이야기입니다.

4. training set 분포 갱신

$h_t$가 결정되고 나면 우리는 training set의 분포를 다시 계산해야됩니다. $D_{t+1}$은 아래와 같이 계산 할 수 있습니다.

$D_{t+1}(i) := {D_t(i)e^{−α_ty_ih_t(x_i)} \over \sum_{j=1}^n D_t(j) e^{−α_t y_j h_t(x_j)}}$

이후에 정확한 Theoretical Background를 서술할 계획입니다. 당장은 직관적으로 살펴보겠습니다.

(1) $h_t(x_i) = y_i$ 일 때,
$h_t(x_i) y_i = 1$이므로 $e^{−α_ty_ih_t(x_i)}$은 1보다 작아집니다.

(2) $h_t(x_i) \neq y_i$ 일 때,
$h_t(x_i) y_i = -1$이므로 $e^{−α_ty_ih_t(x_i)}$은 1보다 커집니다.

따라서, $h_t(x_i)$가 틀린 답을 생성한 경우에 대해서 S에서의 $x_i$의 분포 확률을 더 부각시킵니다.

5. $H(x)$로 테스트하기

$1, \space if \space H(x) = \sum_{i=1}^{T} \alpha_ih_i(x) \geq {1 \over 2}\sum_{i=1}^{T} \alpha_i$
$-1, \space otherwise$

weight의 절반들의 합보다 클 경우 correct으로 분류하도록 설정합니다. 모든 weak classifier에 대해 절반 이상의 동의를 얻었다고 생각하면 편할 것 같네요.

3. Theoretical Background

Theorem 1.

임의의 C와 training set S에 대해 아래의 exponential-loss를 optimize하는 두 식은 동치입니다.

(1) $h_t = argmin_{h∈H} {1 \over n} \sum_{i=1}^{n} e^{(H_{t−1}(x_i) + Ch(x_i))y_i} = argmin_{h∈H} {1 \over n} \sum_{i=1}^{n}l_{exp}(H_{t−1} + Ch, x_i, y_i) = argmin_{h∈H} L_S(H_{t−1} + Ch)$
(2) $h_t = argmin_{h∈H} P_{i∼D_t}(y_i \neq h(x_i))$

Lemma 1.

$P_{i∼D_t}(y_i \neq h(x_i)) = \sum_{i:h(x_i) \neq y_i}{w_{t,i} \over \sum_{j=1}^{n} w_{t,j}}, w_{t,i} = e^{-y_iH_{t-1}(x_i)}$

Theorem 2.

optimal choice of $α_t$ given $h_t$: $α_t := {1 \over 2} ln ({1 − ϵ_t \over ϵ_t})$

수학적 proof는 아래의 주소를 참고하길 바랍니다.
https://mbernste.github.io/files/notes/AdaBoost.pdf