model combining - 2. Boosting

2. 부스팅 boosting

부스트(boost) 방법은 처음부터 여러 개의 모형을 합쳐 문제를 푸는 취합(aggregation)과 달리 하나의 모형에서 시작해 하나씩 모형을 추가해나간다.

이 때 모형들의 집합을 위원회(commitee) $C$ 라고 하고, m개의 모형을 갖는 위원회를 $C_m$ 으로 표시한다. 위원회에 포함된 개별모형은 weak classifier라고 부르며 $k$ 로 표시한다.

$$C_1 = {k_1}\\ C_2 = C1 \cup k_2 = \{k_1,k_2\}\\ \vdots\\ C_m = C_{m-1} \cup k_m = \{k_1,k_2,\cdots ,k_m\}$$

m번째로 위원회에 추가되는 개별모형 $k_m$ 의 목표는 이전단계의 위원회 $C_{m-1}$ 이 잘 못 푼 문제를 풀어내는 것이다.

위원회의 최종 결정은 다수결 방법을 사용하지 않고 각각의 개별모형의 출력을 가중치 $\alpha$ 로 가중선형조합한 값을 판별함수로 사용한다. 새로운 모형이 추가될 때 해당 모형의 가중치가 결정된다.

이진분류에만 쓸 수 있으며, y 값은 1 혹은 -1이다.

$$y = -1 \,\,\,\text{or}\,\,\, 1$$ $$C_m(x_i) = \text{sign}(\alpha_1k_1(x_i) + \cdots + \alpha_mk_m(x_i))$$

1) 에이다부스트

에이다부스트(adaboost)는 적응부스트(adaptive + boost)에서 나온 이름이다. 에이다부스트에서는 위원회에 추가할 개별모형 $k_m$ 을 선별하는 방법으로, 학습데이터 집합의 i번째 데이터에 가중치 $w_i$ 를 주고 분류모형이 틀리게 예측한 데이터의 가중치를 합한 값을 손실함수 L로 사용한다. 이 손실함수값을 최소화하는 모형을 $k_m$ 으로 선택한다.

쉽게 설명하면, 1부터 N까지의 트레이닝 데이터에 대해 새로운 개별모형 $k_m$이 분류를 해서 1 혹은 -1의 답을 낸다. 그 답이 정답이라면 0점, 오답이라면 1점을 부여한다. 즉, 틀리면 벌점 1점을 받는 벌점제도와 같다. 각 데이터에 대해 얻어진 이 벌점의 가중합을 최소화하는 모델을 찾아내는 것이다.

$$L_m = \sum_{i=1}^N w_{m,i}I(k_m(x_i)\neq y_i)$$

위 손실함수 $L_m$에서 $I$ 가 벌점에 해당한다. 즉 0 혹은 1값을 갖는 지시함수 역할을 한다. 그리고 $w_{m,i}$ 은 모델마다, 또 데이터마다 주어지는 가중치로, 특정 로직에 의해 이미 결정된 수치이다.

따라서 손실함수 $L$은 예측이 틀렸을 경우에만 해당 데이터에 주어진 가중치에 1이 곱해져 더하는, 즉 틀린 문제에 대한 가중치의 합이 된다.

이렇게 손실함수값을 최소화하는 개별모형 $k_m$ 이 선택된 후에는 개별 모형의 출력값에 대한 가중치 $\alpha_m$ 을 결정해야 한다. 이 값을 계산하려면 먼저 다음 식이 필요하다.

$$\epsilon_m = \dfrac{\Sigma^N_{i=1} w_{m,i}I(k_m(x_i)\neq y_i)}{\Sigma^N_{i=1}w_{m,i}}$$

$\epsilon _m$ 은 벌점을 0-1사이로 정규화한 점수이다. 분모는 모든 데이터 예측을 다 틀렸을 때 계산된 벌점, 분자는 실제 틀린 문제에 대한 벌점을 의미한다.

데이터에 대한 가중치 $w_{m,i}$는 맨 처음 위원회에 모델이 1개일 경우 모든 데이터에 대해 같은 값을 갖지만, 위원회 멤버가 증가하면서 값이 바뀐다. 가중치 값은 지수함수를 사용해 맞춘 문제는 작게, 틀린 문제는 크게 확대(boosting)된다. 즉, 그 전에 적용한 모형이 정답을 맞추지 못한 데이터는 가중치가 커지고 맞춘 데이터들의 가중치는 작아져서 다음 추가된 모형은 가중치가 커진 데이터에 중점을 두고 분류를 하게 된다.

$$w_{m,i} = w_{m-1,i}\exp(-y_iC_{m-1}) = \begin{cases}w_{m-1,i}e^{-1} && \text{if}\,\, C_{m-1} = y_i\\ w_{m-1,i}e && \text{if} \,\, C_{m-1} \neq y_i \end{cases}$$

결국 에이다부스팅은 아래와 같이 전체 모형집단에 대한 손실함수를 최소화하는 모형집단을 찾아나가는 과정이라고 볼 수 있다.

$$L_m = \sum^N_{i=1} \exp(-y_iC_m(x_i))$$

이에 따라 유도된 가중치 $\alpha_m$ 의 공식은 다음과 같다.

$$\alpha_m = \frac{1}{2}\log\left(\frac{1-\epsilon_m}{\epsilon_m}\right)$$

다음은 scikit-learn의 ensemble 서브패키지가 제공하는 AdaBoostClassifier 클래스를 사용하여 분류 예측을 하는 예이다. 약분류기로는 깊이가 1인 단순한 의사결정나무를 채택하였다.

각 단계의 분류 모형에 대한 가중치 값과 분류 모형의 분류 결과를 시각화하면 다음과 같다. 데이터의 가중치는 스캐터플롯의 점의 크기로 표현하였다. 단계가 진행될 수록 가중치값의 변화가 커지는 것을 볼 수 있다.

2) 그레디언트 부스트

그레디언트 부스트(gradient boost) 모형은 변분법(calculus of variations)을 사용한 모형이다. 손실 범함수(loss functional) $ L(y, C_{m-1})$를 최소화하는 개별 분류모형 $k_m$ 을 찾는다. 이론적으로 가장 최적의 $k_m$은 범함수의 미분이다.

$$C_m = C_{m-1} - \alpha_m \dfrac{\delta L(y,C_{m-1})}{\delta C_{m-1}} = C_{m-1} + \alpha_m k_m$$

결국 그레디언트 부스트는 범함수를 최적화하는 과정이다. 앞에서는 기존의 데이터에서 가중치만 바꿔서 최적의 $k_m$ 을 선택했다면 여기서는 범함수의 그레디언트와 가장 비슷한 $k_m$ 을 찾는다.

그레디언트 부스트모형에서는 다음과 같은 과정을 반복해 개별모형과 그 가중치를 계산한다.

1. $-\frac{\delta L(y,C_m)}{\delta C_m}$ 을 목표값으로 개별 멤버 모형 $k_m$ 을 찾는다.
2. $\left(y - (C_{m-1} + \alpha_m k_m)\right)^2$ 를 최소화하는 스텝사이즈 $\alpha_m$ 을 찾는다.
3. $C_m = C_{m-1} + \alpha_m k_m$ 최종 모형을 갱신한다.

만약 손실범함수가 오차제곱형태라면 ,

$$L(y, C_{m-1}) = \frac{1}{2}(y-C_{m-1})^2$$

범함수의 미분은 실제 목푯값 y와 $C_{m-1}$ 과의 차이, 즉 잔차(residual)가 된다.

$$-\frac{dL(y,C_m)}{dC_m} = y - C_{m-1}$$

이 값과 가장 비슷한 다음 모델을 찾는 것이 그레디언트부스팅 방법이 된다.

scikit learn의 ensemble 에서는 그레이디언트부스팅방법을 위해 GradientBoostingClassifier 를 제공하지만, 그보다 그레디언트 부스팅만을 전문으로 구현해놓은 라이브러리들을 사용하는 것이 더 좋다.

• XGBoost 라이브러리

  :scikit learn에 비해 빠르다.

• Light GBM (gradient boosting machine) 라이브러리

  : xgboost보다 더 빨라서 많이 쓰인다.

그래디언트 부스팅모델에 들어가게 되는 인수는 함수이므로 decision tree classifier가 아니라 decision tree regressor이다. 따라서 개별 모형들은 0 또는 1의 클래스가 아니라 각각 다른 높이를 지닌 계단식 함수값을 출력한다. 그걸 다 합쳤을 때 최종결과에서 바이너리 클래스로 분류하게 되는 것이다.

• XGBoost 라이브러리

import xgboost

model_xgb = xgboost.XGBClassifier(n_estimators=100, max_depth=1, random_state=0)
model_xgb.fit(X_train, y_train)

• LightGBM 라이브러리

  import lightgbm
  
  model_lgbm = lightgbm.LGBMClassifier(n_estimators=100, max_depth=1, random_state=0)
  model_lgbm.fit(X, y)