Boost your Knowledge: Adaptive Boost

서준표·2023년 4월 29일
0

시작하며,

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

1. Problem Formulation

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

Training set SS은 n개의 data points로 구성되어 있습니다.
S:=[(x1,y1),(x2,y2),...,(xn,yn)]S := [(x_1, y_1),(x_2, y_2), . . . ,(x_n, y_n)]
yi[1,1],(i=1,2,...,n)y_i ∈ [-1,1], (i=1,2,...,n)
xi,yix_i, y_i는 각각 feature, label의 notation을 나타냅니다.

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

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

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

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

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

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

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

2. Algorithm

D1(i)1n,i=1,2,...,nD_1(i) ← {1 \over n}, i =1,2,...,n
retret ← ∅
for t=1,2,...,T:t = 1, 2, ..., T:
  htargminhHPiDt(h(xi),yi)\space\space h_t ← argmin_{h∈H} P_{i∼D_t}(h(x_i) , y_i)
  ϵtPiDt(h(xi),yi)\space\space \epsilon_t ← P_{i∼D_t}(h(x_i) , y_i)
  αt12ln(1ϵtϵt)\space\space \alpha_t ← {1 \over 2} ln({1−ϵt \over ϵt})
  retret(αt,ht)\space\space ret ← ret ∪ {(α_t, h_t)}
 \space for i=1,2,...,n:i = 1, 2, ..., n:
   Dt+1(i)Dt(i)e(αtyiht(xi))j=1nDt(j)e(αtyjht(xj))\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 분포의 초기화

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

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

tt번째 iteration에서 DtD_t의 분포를 가지는 training set SS에 대해 가장 좋은 performance를 지닌 hth_t를 찾아냅니다.

ht=argminhHEiDt[01(h,xi,yi)]=argminhHPiDt[yih(xi)]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 설정하기

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

ϵt=PiDt[yiht(xi)]\epsilon_t = P_{i∼D_t}[y_i \neq h_t(x_i)]

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

αt:=12ln1ϵtϵtα_t:= {1 \over 2} ln{1 − ϵ_t \over ϵ_t}

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

4. training set 분포 갱신

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

Dt+1(i):=Dt(i)eαtyiht(xi)j=1nDt(j)eαtyjht(xj)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) ht(xi)=yih_t(x_i) = y_i 일 때,
ht(xi)yi=1h_t(x_i) y_i = 1이므로 eαtyiht(xi)e^{−α_ty_ih_t(x_i)}은 1보다 작아집니다.

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

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

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

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

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

3. Theoretical Background

Theorem 1.

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

(1) ht=argminhH1ni=1ne(Ht1(xi)+Ch(xi))yi=argminhH1ni=1nlexp(Ht1+Ch,xi,yi)=argminhHLS(Ht1+Ch)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) ht=argminhHPiDt(yih(xi))h_t = argmin_{h∈H} P_{i∼D_t}(y_i \neq h(x_i))

Lemma 1.

PiDt(yih(xi))=i:h(xi)yiwt,ij=1nwt,j,wt,i=eyiHt1(xi)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α_t given hth_t: αt:=12ln(1ϵtϵt)α_t := {1 \over 2} ln ({1 − ϵ_t \over ϵ_t})

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

profile
연락은 메일로 부탁드립니다.

0개의 댓글