AdaBoost

2021-1학기, 대학에서 ‘통계적 데이터마이닝’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

May 10, 2021 9 minute read

2021-1학기, 대학에서 ‘통계적 데이터마이닝’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

<Boosting>에 대한 개요는 아래의 포스트에서 확인할 수 있습니다 😁

👉 Boosting

AdaBoostPermalink

<AdaBoost>란 “Adaptive Boosting”의 약자로 <Boosting> 알고리즘을 처음으로 고안한 Schapire & Freund에 의해 1996년 개발된 최초의 Boosting 모델이다.

알고리즘을 살펴보기 전에 먼저 셋업을 확인하자.

[Data]

${(x_{1}, y_{1}), \dots, (x_{n}, y_{n})}$

p-dimensional input: $x_{i} \in X$
Binary output: $y_{i} \in {- 1, 1}$ // 1, -1로 인코딩

[Weak Classifier]

$m$ -th Weak Classifier $G_{m} : X \to {- 1, 1}$

[Prediction]

predictions are based on a weighted majority vote!

G (x) = sign (\sum_{m = 1}^{M} α_{m} G_{m} (x))

where $α_{m}$ is weight of weak classifier.

Algorithm. AdaBoost

Initialize the weights for data points
$w_{i} = 1 / n$ for $i = 1, \dots, n$ .

// training!
For $m = 1$ to $M$
Obtain $G_{m} (x)$ based on the training data using weights $w_{i}$
Compute error of $m$ -th classifier.

{err}_{m} = \frac{\sum_{i = 1}^{n} w_{i} \cdot I (y_{i} \neq G_{m} (x_{i}))}{\sum_{i = 1}^{n} w_{i}}

Compute weights for $m$ -th classifier

α_{m} = \log (\frac{1 - {err}_{m}}{{err}_{m}})

// 정분류 $w_{i}$ 가 그대로, 오분류 $w_{i}$ 가 커짐 → normalize → 정분류 $w_{i}$ ▼, 오분류 $w_{i}$ ▲

Update weights for data points

w_{i} \leftarrow w_{i} \cdot \exp [α_{m} \cdot I (y_{i} \neq G_{m} (x_{i}))] for i = 1, \dots, n

Output $G (x) = sign [\sum_{m = 1}^{M} α_{m} G_{m} (x)]$

Boosting as Additive ExpansionPermalink

<AdaBoost> 알고리즘의 결과인 $G (x)$

G (x) = sign [\sum_{m = 1}^{M} α_{m} G_{m} (x)]

를 additive/basis expansion 모델로도 이해할 수 있다.

Algorithm. general additive function expansion

f (x) = \sum_{m = 1}^{M} β_{m} \cdot h (x; θ_{m})

즉, $α_{m}$ 를 basis coefficient $β_{m}$ 로, weak classifier $G_{m} (x)$ 를 basis function $h (x; θ_{m})$ 으로 해석하는 것이다!

본래 additive model을 ERM(Empirical Risk Minimization)으로 fitting 시키는 것은 hard한 문제이다.

min_{{β_{m}, θ_{m}}_{m = 1}^{M}} \sum_{i = 1}^{n} L (y_{i}, \sum_{m = 1}^{M} β_{m} \cdot h (x_{i}; θ_{m}))

대부분의 경우에서는 computationally infeasible 하다고 보면 된다.

이런 계산적인 문제를 해결하기 위한 방법으로는

Update the expansion sequentially
Consider only a single basis function at each step

가 있는데, 이런 접근을 흔히 <Forward Stagewise Update>라고 한다!

간단하게 설명해보자면,

$β_{0}$ 를 fitting
$β_{0}$ 는 그대로 두고, $β_{1}$ 을 fitting
$β_{0}, β_{1}$ 은 그대로 두고, $β_{2}$ 를 fitting
…

Algorithm. Forward Stagewise Update 🔥

Supp. that the current expansion is

f_{m - 1} (x) = \sum_{j = 1}^{m - 1} β_{j} \cdot h (x; θ_{j})

then, the next update can be achieved by solving

(β_{m}, θ_{m}) = \underset{(β, θ)}{argmin} \sum_{i = 1}^{n} L (y_{i}, f_{m - 1} (x_{i}) + β \cdot h (x_{i}; θ))

즉, <forward stagewise update>는 기존의 solution을 수정하지 않으면서 새로운 basis function을 추가한다.

Example. Forward Stagewise Update with Squared Error Loss

Consider the squared error loss:

L (y, f (x)) = (y - f (x))^{2}

then, the loss in forward stagewise is

L (y_{i}, f_{m - 1} (x_{i}) + β \cdot h (x_{i}; θ)) = (y_{i} - f_{m - 1} (x_{i}) - β \cdot h (x_{i}; θ))

이때, current residual인 $(y_{i} - f_{m - 1} (x_{i}))$ 는 상수값으로 $β, θ$ 를 찾는데에 영향을 주지 않는다. 따라서 우리는 $β, θ$ 에 온전히 집중하면 된다!

Example. Forward Stagewise Update with Exponential Loss 🔥

Consider the exponential error loss:

L (y, f (x)) = \exp (- y \cdot f (x))

이때! 놀랍게도 <AdaBoost>는 Forward Stagewise Updates for the ERM with Exponential Loss와 동치다!! 😲

이 명제는 <Boosting>에 대한 완전히 새로운 방식의 시야를 제시한다!

Note that the $m$ -th step of the forward stagewise updates solves

\begin{aligned} (β_{m}, G_{m}) & = \underset{(β, G)}{argmin} \sum_{i = 1}^{n} \exp [- y \cdot (f_{m - 1} (x_{i}) + β \cdot G (x_{i}))] \\ = \underset{(β, G)}{argmin} \sum_{i = 1}^{n} w_{i}^{(m)} \cdot \exp [- y_{i} \cdot β \cdot G (x_{i})] \\ where w_{i}^{(m)} = \exp [- y \cdot f_{m - 1} (x_{i})] \end{aligned}

It can be shown that

G_{m} = \underset{G}{argmin} \sum_{i = 1}^{n} w_{i}^{(m)} \cdot I (y_{i} \neq G (x_{i}))

β_{m} = \frac{1}{2} \log (\frac{1 - {err}_{m}}{{err}_{m}})

where

{err}_{m} = \frac{\sum_{i = 1}^{n} w_{i}^{(m)} \cdot I (y_{i} \neq G_{m} (x_{i}))}{\sum_{i = 1}^{n} w_{i}^{(m)}}

Then, the update is

f_{(} x) = f_{m - 1} (x) + β_{m} \cdot G_{m} (x)

and leads the weights for the new iterations to be

\begin{aligned} w_{i}^{(m + 1)} & = w_{i}^{(m)} \cdot \exp [- y_{i} \cdot β_{m} \cdot G_{m} (x_{i})] \\ = w_{i}^{(m)} \cdot \exp [α_{m} \cdot I (y_{i} \neq G_{m} (x_{i}))] \cdot \exp [- β_{m}] \end{aligned}

where $α_{m} = 2 β_{m}$ appears in the AdaBoost algorithm.

Q. Why Exponential Loss?

Population minimizer of the exponential loss:

\begin{aligned} f^{*} (x) & = \underset{f (x)}{argmin} E_{Y ∣ x} [L (Y, f (x))] \\ = \underset{f (x)}{argmin} E_{Y ∣ x} [\exp (- Y \cdot f (x))] \\ = \frac{1}{2} \log \frac{P (Y = 1 ∣ x)}{P (Y = - 1 ∣ x)} \end{aligned}

equivalently,

P (Y = 1 ∣ x) = \frac{\exp (f^{*} (x))}{\exp (- f^{*} (x)) + \exp (f^{*} (x))}

Derivation

It is true that $P (Y = 1 ∣ x) = 1 - P (Y = - 1 ∣ x)$ .

\begin{aligned} f^{*} (x) & = \frac{1}{2} \log \frac{P (Y = 1 ∣ x)}{P (Y = - 1 ∣ x)} \\ \exp (2 \cdot f^{*} (x)) & = \frac{P (Y = 1 ∣ x)}{P (Y = - 1 ∣ x)} \\ = \frac{P (Y = 1 ∣ x)}{1 - P (Y = 1 ∣ x)} \\ \exp (2 \cdot f^{*} (x)) \cdot (1 - P (Y = 1 ∣ x)) & = P (Y = 1 ∣ x) \\ \exp (2 \cdot f^{*} (x)) & = P (Y = 1 ∣ x) + \exp (2 \cdot f^{*} (x)) \cdot P (Y = 1 ∣ x) \\ = P (Y = 1 ∣ x) \cdot (1 - \exp (2 \cdot f^{*} (x))) \\ \frac{\exp (2 \cdot f^{*} (x))}{1 - \exp (2 \cdot f^{*} (x))} & = P (Y = 1 ∣ x) \\ \frac{\exp (f^{*} (x))}{\exp (- f^{*} (x)) + \exp (f^{*} (x))} & = \end{aligned}

$◼$

<AdaBoost>에 대해서는 <AdaBoost>를 구하는 것이 사실 “Forward Stagewise Updates for the ERM with Exponential Loss”라는 것을 꼭 기억해야 한다!! 😤

이후에 나온 GBM 계열이 더 성능이 좋아서 요즘은 잘 쓰지 않는다고 한다 😥

Seokyun Ha (aka. bluehorn07)

AdaBoost

AdaBoostPermalink

Boosting as Additive ExpansionPermalink

You may also enjoy

Introduction: Numerical Differentiation

Interpolation Differentiation

Bundle Preference: Differentiability

Bundle Preference: Convexity