Multi-class AdaBoost

---

이번 포스팅은 기존 이진(Binary Class) 분류를 위한 AdaBoost 알고리즘을 Multi class AdaBoost로 확장시킨 Zhu, H. Zou, S. Rosset, T. Hastie의 논문 "Multi-class AdaBoost"를 리뷰하려고 한다.

 

- 목차 -

 

1. Introduction

2. Statistical Justification

3. Numerical Results

4. Discussion

---

---

본 포스팅에서는 수식을 포함하고 있습니다.

티스토리 피드에서는 수식이 제대로 표시되지 않을 수 있으니

PC 웹 브라우저 또는 모바일 웹 브라우저에서 보시기 바랍니다.

---

---

   1. Introduction

부스팅(Boosting)은 2 클래스 분류 문제에서 만큼은 아주 성공적인 알고리즘이었다. 반면 대부분의 부스팅 알고리즘은 다중 클래스(Multi-Class) 문제를 여러 2 클래스 문제로 바꿔서 해결하였다. AdaBoost 알고리즘도 다중 클래스 문제를 여러 이진 분류 문제로 바꾸어서 적용할 수 있는데 이에 대한 논란이 많다.

 

AdaBoost는 Exponential loss를 최소화하는 Forward Stagewise Additive Modeling으로 볼 수 있다고 한다. 저자는 2 클래스 AdaBoost를 여러 문제로 쪼개지 않고 다중 클래스로 확장 가능한 새로운 AdaBoost 알고리즘을 소개한다. 이 새로운 알고리즘은 기존 2 클래스 AdaBoost의 일반화 버전이며 약간의 수정(하지만 굉장히 중요한 수정)만으로 다중 클래스 AdaBoost로 확장된다. 이 알고리즘은 Weak Learner가 임의 추측(Random Guessing)보다는 좋은 성능을 가졌다는 것을 가정한다. 또한 이 알고리즘은 다중 클래스 Exponential loss를 최소화하는 Forward Stagewise Additive Modeling임을 보인다. 게다가 Exponential Loss가 Fisher-Consistent Loss 함수인 것도 보인다. 

---

1.1 AdaBoost

먼저 데이터 $(x_1, c_1), \ldots, (x_n, c_n)$가 있다고 하자. 여기서 $x_i\in \mathbb{R}^p$ 는 설명 변수이고 그리고 $c_i \in \{1, \ldots, K \}$은 클래스를 나타내는 변수이다. 

 

학습 데이터는 독립적으로 그리고 동일한 분포 $P(X, C)$에서 추출되었다고 하자. 우리의 궁극적인 목표는 학습 데이터로부터 다음의 오분류율을 최소화하는 분류 규칙 $C(x)$를 찾는 것이다. 즉, $x$라는 입력값이 들어왔을 때 아래의 오분류율의 기대값

$$P(C(x) \neq c)$$

최소화하는 분류기를 찾는 것이다. 우리가 찾는 분류기는

$$\DeclareMathOperator*{\argminA}{arg\,min} C^*(x) = \argminA_{k} P(C(x) = k | x)$$

이때 $C^*(x)$를 베이즈 분류기라고 하며 베이즈 분류기의 오류율을 베이즈 오류율이라고 한다.

 

AdaBoost 알고리즘은 베이즈 분류기를 잘 근사 시키기 위하여 Weak Learner를 반복적으로 결합해나간다. 먼저 가중치가 없는 학습 데이터를 이용하여 분류기를 만들고 이 분류기를 통해 오분류된 데이터의 가중치를 증가시킨다. 두 번째 분류기는 앞에서 새롭게 만들어진 데이터에 대하여 피팅된 분류기이다. 이번에도 오분류된 데이터를 이용하여 가중치를 업데이트하고 세 번째 분류기를 얻는다. 보통 500~1000번의 반복 과정을 거쳐 분류기를 얻고 이를 선형 결합하여 최종 분류 모형을 얻는다.

 

$T(x)$를 다중 클래스 분류기라고 할 때 기존 AdaBoost 알고리즘은 다음과 같다.

---

Algorithm 1. AdaBoost

1. 먼저 초기 가중치를 다음과 같이 세팅한다.

$$w_i = \frac{1}{n}, i=1, \ldots, n$$

 

2. $m = 1 \text{ to } M$에 대하여

(a) 가중치 $w_i$를 이용하여 분류기 $T^{(m)}(x)$를 피팅한다.

(b) 다음을 계산한다.

$$err^{(m)} = \sum_{i=1}^nw_i I(c_i \neq T^{(m)}(x_i) )/\sum_{i=1}^nw_i$$

(c) 다음을 계산한다.

$$\alpha^{(m)} = \log \frac{1-err^{(m)} }{err^{(m)} }$$

(d) 가중치를 다음과 같이 업데이트한다.

$$w_i \longleftarrow w_i\cdot \exp (\alpha^{(m)} I(c_i \neq T^{(m)}(x_i) ) ), \text{ } i=1, \ldots, n $$

(e) 가중치를 정규화(Normalization)해준다.

 

3. 최종 분류기의 예측은 다음과 같이 세팅한다.

$$\DeclareMathOperator*{\argmaxA}{arg\,max} C(x) = \argmaxA_{k}\sum_{m=1}^M\alpha^{(m)}\cdot I(T^{(m)}(x)=k)$$

---

2 분류 문제의 한정해서 AdaBoost는 엄청난 성공을 거두었다. 하지만 다중 클래스 문제에서는 그렇지 못했다. 왜냐하면 AdaBoost의 좋은 성능은 Weak Learner의 오분류율이 0.5보다는 작아야 한다는 가정이 있는데 이 가정은 2 분류 문제에서는 잘 맞지만 다중 클래스에서는 잘 맞지 않기 때문이다. AdaBoost의 창시자인 Freund와 Schapire 도 지적했듯이 Weak Learner 오분류율을 0.5보다 작게 컨트롤하기가 힘들다고 한다. 그래서 다중 클래스에서는 기존 AdaBoost가 성능이 좋지 못한 것이다. 논문의 저자는 AdaBoost의 이러한 약점을 보여주기 위한 시뮬레이션 실험을 진행하였다. 

1.2 Multi-Class AdaBoost

여기서는 기존 2 분류 AdaBoost를 일반화한 다중 클래스 AdaBoost 알고리즘을 소개한다. 저자는 이 알고리즘을 SAMME(Stagewise Additive Modeling using a Multi-class Exponential loss function)라고 부르기로 하였다. 

 

SAMME 알고리즘은 다음과 같다.

---

Algorithm 2. SAMME

 

1. 초기 가중치를 다음과 같이 세팅한다.

$$w_i = \frac{1}{n}, i=1, \ldots, n$$

 

2. $m=1 \text{ to } M$에 대하여

(a) 가중치 $w_i$를 이용하여 분류기 $T^{(m)}(x)$를 피팅한다.
(b) 다음을 계산한다.
$$err^{(m)} = \sum_{i=1}^nw_i I(c_i \neq T^{(m)}(x_i) )/\sum_{i=1}^nw_i$$
(c) 다음을 계산한다.
$$\alpha^{(m)} = \log \frac{1-err^{(m)} }{err^{(m)} } + \log (K-1)$$
(d) 가중치를 다음과 같이 업데이트한다.
$$w_i \longleftarrow w_i\cdot \exp (\alpha^{(m)} I(c_i \neq T^{(m)}(x_i) ) ), \text{ } i=1, \ldots, n $$
(e) 가중치를 정규화(Normalization)해준다.

3. 최종 분류기의 예측 다음과 같이 세팅한다.
$$\DeclareMathOperator*{\argmaxA}{arg\,max} C(x) = \argmaxA_{k}\sum_{m=1}^M\alpha^{(m)}\cdot I(T^{(m)}(x)=k)$$

---

SAMME 알고리즘은 AdaBoost 알고리즘과 비교할 때 2-(c) 빼고는 모두 똑같다. 이때 $K=2$라면 SAMME 알고리즘은 AdaBoost와 같아진다. 저 미묘해 보이는 $\log (K-1)$이 굉장히 중요한 항이다. 이 로그항 덕분에 $\alpha^{(m)}$이 양수이기 위한 조건이 $1-err^{(m)}>1/K$이기만 하면 된다. 기존 $1/2$에서 $1/K$로 조건이 완화된 것이다. 논문의 저자는 시뮬레이션을 통해 기존 성능이 나빴던 AdaBoost 보다 SAMME의 성능이 훨씬 좋음을 밝혔다. 

---

   2. Statistical Justification

이번 섹션에서는 기존 AdaBoost와의 미묘하면서 엄청난 로그항 $\log (K-1)$의 힘을 알아보도록 한다. 이 로그항으로 인해 Algorithm 2. 가 다중 클래스 Exponential Loss를 최소화하는 Forward Stagewise Additive Model이라는 것이다. 먼저 Friedman, Hastie, Tibshirani는 기존에 2 클래스 AdaBoost가 다음의 손실 함수

$$L(y, f) = e^{-yf}$$

를 최소화하는 Forward Stagewise Additive Model임을 밝혔다. 여기서 $y = I(c=1)-I(c=2)$이다. 위 손실 함수를 최소화하는 전역 minimizer는 다음과 같다.

$$f^*(x) = \frac{1}{2}\log\frac{P(c=1|x)}{P(c=2|x)}$$

2.1 SAMME as forward stagewise additive modeling

다중 클래스 세팅 하에서 출력값 $c$를 다음과 같이 $\tilde{y} = (y_1, \ldots, y_k)^t$ 코딩할 수 있다.

$$y_k=\begin{cases} 1, & \text{ if } c= k, \\ -\frac{1}{K-1} & \text{ if } c\neq k \end{cases}\tag{2}$$

우리는 다음과 같은 손실 함수를 최소화하는 함수 $f(x)=(f_1(x), \ldots, f_K(x))^t$를 찾고 싶다.

$$\sum_{i=1}^nL(\tilde{y}_i, f(x_i))\tag{3}$$

이때 함수의 추정이 가능하도록(Estimable) 다음의 제약식을 만족시키는 것 중에서 위 손실 함수를 최소화하는 함수를 찾는다.

$$f_1(x)+\cdots+f_K(x) = 0\tag{4}$$

 

본 논문의 저자는 $f(x)$의 구조를 다음과 같이 기저 함수(Basis Function)의 선형 결합으로 가정했다.

$$f(x) = \sum_{m=1}^M\beta^{(m)}g^{(m)}(x)$$

이때 기저 함수에는 다음과 같은 제약 식이 있다.

$$g_1(x)+\cdots+g_K(x) = 0$$

 

Forward Stagewise Modeling은 (3)-(4)의 해를 근사 시키기 위하여 순서대로 기존 모델의 모수 또는 계수를 조정하지 않고 새로운 기저 함수를 추가한다. 특히 이 알고리즘은 초기 함수로 $f^{(0)}(x)=0$을 세팅하고 새로운 기저 함수를 추가해나간다.

---

Algorithm 3. Forward Stagewise Additive Modeling

 

1. 초기 함수를 세팅한다.

$$f^{(0)}(x)= 0$$

 

2. $m = 1 \text{ to } M$에 대하여

(a) 다음을 계산한다.

$$\DeclareMathOperator*{\argminA}{arg\,min} (\beta^{(m)}, g^{(m)}(x)) \\ = \argminA_{\beta, g}\sum_{i=1}^nL(\tilde{y}_i, f^{(m-1)}(x)+\beta g(x_i))$$

(b) 다음과 같이 세팅한다.

$$f^{(m)}(x) = f^{(m-1)}(x) + \beta^{(m)}g^{(m)}(x)$$

---

이제 손실 함수를 다음과 같이 다중 클래스 Exponential Loss를 도입한다.

$$L(\tilde{y}, f) = \exp \left ( - \frac{1}{K}\tilde{y}^tf \right )$$

그렇다면 우리는 Forward Stagewise Additive Model(FSAM) 알고리즘을 통해  다중 클래스 Exponential Loss를 최소화하는 $\beta, g$를 찾아야 한다. 다중 클래스 분류기 $T(x)$과 $g_k$의 관계를 다음과 같이 설정하자.

$$T(x) = k, \text{ if } g_k(x) = 1 \tag{8}$$

그리고 반대로

$$g_k(x) = \begin{cases} 1, & \text{ if } T(x) = k, \\ -\frac{1}{K-1}, &\text{ if } T(x) \neq k,  \end{cases}$$

이다. 

 

이러한 세팅 하에서 논문의 저자는 SAMME 알고리즘이 결국 Exponential Loss를 최소화하는 FSAM 알고리즘과 동치임을 밝혔다. 

2.2 The multi-class exponential loss

이번 섹션에서는 논문의 저자가 다중 클래스 Exponential Loss 를 최소화하는 분류기가 베이즈 분류기임을 증명하여 다중 클래스 Exponential Loss 사용의 정당성을 입증한다. 즉, 다중 Exponential Loss는 Fisher 일치성을 갖는 손실 함수가 된다.

2.3 Fisher-consistent multi-class loss functions

여기서는 다중 Exponential Loss 외에도 Fisher 일치성을 갖게 되는 손실 함수에 대한 충분조건에 대해서 소개한다. 이러한 조건을 만족하는 함수에는 $L_2$ 손실함수, 로짓 손실함수 등이 있다.

---

   3. Numerical Results

이번 섹션에서는 모의 데이터와 실제 데이터를 이용하여 SAMME의 위대함을 증명한다. 비교를 위해 CART 의사결정 나무, AdaBoost.MH를 고려했다. 논문의 저자는 SAMME가 궁극적인 도구가 아니라 합리적인 알고리즘이라는 것과 기존 2 분류 AdaBoost의 자연스러운 확장 버전임을 보여주고 싶었다고 한다.

3.1 Simulation 

SAMME가 AdaBoost.MH 보다 약간 성능이 좋았다.

3.2 Real Data

SAMME의 성능이 AdaBoost.MH과 견줄만하다고 했다.

---

   4. Discussion

이 논문을 요약하면 다음과 같다.

 

a. SAMME는 FASM을 다중 클래스 분류 문제에 적합시킨 다중 클래스 베이즈 규칙을 만들어간다.

b. SAMME는 데이터의 특징을 잘 반영한 Weak 분류기를 Strong 분류기로 만들어간다는 점에서 부스팅 모형의 한 축이다.

c. 알고리즘의 매 스텝마다 SAMME는 가중치를 가진 하나의 분류기를 생성하고 오분류율은 $K$개 클래스를 임의 추측보다 잘 예측하기만 하면 된다.

d. SAMME는 기존 2 분류기의 AdaBoost 알고리즘 구조와 매우 흡사하다.

 

본 논문의 저자는 SAMME가 궁극적인 도구가 아니라 합리적인 알고리즘이라는 것과 기존 2 분류 AdaBoost의 자연스러운 확장 버전임을 보여주고 싶었다고 한다.

---

이 논문은 내가 AdaBoost를 구현하기 위해 참고한 논문이다. Multi Class로의 확장된 AdaBoost의 알고리즘과 이론적인 배경을 제대로 알 수 있었던 좋은 시간이었다.

---

---