[Data Science] 앙상블(Ensemble) 2. AdaBoost, GBM

Ensemble

AdaBoost

Weak Model vs Strong Model

Strong model은 계산 복잡도가 높은 모델이나 하이퍼파라미터가 많은 모델로 복잡한 분류 경계면이나 복잡한 회귀직선을 추정해 내는 모델들을 의미한다. Weak model은 랜덤 모델(승률이 50:50인 모델)d에 비해 약간의 성능 개선이 있는 모델을 의미한다. Weak model은 Boosting의 일련의 절차를 통해서 성능이 우수한 모델로 향상될 수 있다.

AdaBoost는 베이스 러너로 Stump Tree를 사용하는 앙상블 기법이다. Stump tree는 split을 1회 수행한 의사결정나무로 특정한 축에 수직인 분류경게면을 생성한다. 하나의 직선으로 분류를 하는 로지스틱 회귀분석과 비슷하다고 생각할 수 있지만, 로지스틱보다도 자유도가 낮은 모델이다(로지스틱 회귀분석은 회귀선에 대한 기울기에 대한 제약이 없지만, stump tree는 무조건 축에 수직인 분류 경계면만 생성 가능).

Boosting의 메인 아이디어는 현재 모델이 잘 해결하지 못하는 어려운 케이스에 집중하는 것이다.

1. 현재 데이터셋에 대해서 단순한 모델(stump tree) 이용하여 학습
2. 학습 오류가 큰 개체의 선택 확률을 증가시키고 학습 오류가 작은 개체의 선택 확률을 감소시킴
3. 앞 단계에서 조정된 확률을 기반으로 다음 단계에서 사용될 학습 데이터셋을 구성
4. 1단계로 돌아감
5. 최종 결과물은 각 모델의 성능 지표를 가중치로 사용하여 결합

이러한 일련의 과정중에서 Bagging과 가장 큰 차이점을 보이는 건 2단계이다. Bagging은 복원추출을 통하여 우리가 가지고 있는 원래의 데이터 갯수만큼의 bootstrap을 생성하고 학습시켜서 개별 결과를 취합하는 방식이라면 Boosting은 학습 오류가 큰 객체는 다음 모델을 만들 때 더 많이 샘플링 될 수 있도록 선택확률을 증가시키고 학습오류가 낮은, 현재 모델에 의해 잘 맞춰진 객체는 선택확률을 감소시킨다.

릴레이로 퀴즈를 맞춰야하는 상황에 비유해보자. 1번 타자가 경제에 대한 문제를 잘 맞춰둔 상황이라면 2번 타자는 경제 문제보다는 물리 문제에 대한 준비를 더 많이하는 것이 유리하다. 즉, 이전 모델이 가지고 있는 약점을 데이터의 샘플링 확률에 반영을 해서 다음 모델이 더 많이 학습할 수 있도록 확률값을 조정한다.

Bagging은 bootstrap이 동시다발적으로 생성되고 각 객체가 포함될 확률은 같다. 하지만 Boosting은 이전 모델 학습 결과에 따라 다음 모델에 사용될 객체의 선택 확률이 변한다.

선택확률

각 개체가 다음 단계의 학습 데이터 셋에 선택될 확률은 아래와 같다.

\[D_{t+1}(i)=\frac{D_t(i)\exp(-\alpha_ty_ih_t(x_i))}{Z_t}\]

$D_t(i)$는 $t$시점에서의 선택확률이다. $\alpha_i$는 $0\le\alpha_i\le 0.5$로 양수이다. (랜덤 모델보다 성능이 좋아야 하기 때문에) $y_ih_t(x_i)$는 값이 정분류 되어있다면 +1, 오분류 되어있다면 -1의 값을 갖는다.

정분류 되었을 경우엔 $-\alpha_t y_i h_t(x_i)<0$이기 때문에 (지수함수 형태를 참고) 선택 확률이 감소한다. 하지만 오분류되었을 땐, $-\alpha_t y_i h_t(x_i)>0$이기 때문에 선택 확률이 증가한다.

그렇게 오분류된 개체들이 2단계에서는 정분류가 되고 그에 따른 선택확률이 다시 조정된다.

AdaBoost는 아주 단순한 모델을 사용하지만 boosting 해나가면서 복잡한 분류 경계면을 만들어낼 수 있는 앙상블 기법이다.

GBM

GBM는 Gradient Boosting으로 Gradient Descent + Boosting 형태의 앙상블 기법이다.

이 기법은 현재 모델이 못 맞춘 부분(잔차)만큼만 맞추는 두번째 모델을 만들어서 결합하면 좋지 않을까?라는 생각에서 시작된 기법이다. 회귀모형을 예로 들면

실제 데이터인 포인트와 추정한 회귀식인 검정 직선 사이의 차이, 잔차가 있는 것을 알 수 있다. GBM은 이 잔차에 포커스를 둔 앙상블 기법이다.

$x$값이 아닌 $y$값을 업데이트시키는데, 첫번째 모델이 못 맞춘만큼(정답 - 예측치)을 두번째 모델의 $y$값을 설정한다. 물론 두 번째 모델도 못 맞추는 부분이 존재할 것이기 때문에 세번째 모델의 $y$값은 정답에서 첫 번째 모델과 두 번째 모델이 못 맞춘만큼을 $y$값으로 설정한다.

필드에 나가서 골프를 친다고 생각하면 과정이 동일하다. 드라이버로 첫 번째 샷을 날린다. 두 번째 샷을 날릴 땐, 첫 번째 샷으로 공을 보낸 지점부터 홀컵까지의 거리를 계산해서 힘과 클럽을 조정하는 것과 같은 방식이다.

GBM은 Adaboost와 마찬가지로 개별 모델을 forward 방식으로 학습하고 stump tree를 베이스 러너로 사용해서 이전 단계의 단점을 보완해나가는 것도 동일하다. 하지만 GBM은 이전 단계의 모델의 단점이 손실 함수(loss Function)의 gradient에 적용된다.

회귀모형의 대표적인 손실 함수 Squared Loss로 과정을 살펴보자.

\[\min L = \frac{1}{2}\sum_{i=1}^n(y_i-f(\mathbf{x}_i))^2\]

Squared Loss를 우리가 찾고자 하는 함수 ($f(\mathbf{x}_i)$)로 미분(= 손실함수의 Gradient) 하면 아래와 같다.

\[\frac{\partial L}{\partial f(\mathbf{x}_i)}=f(\mathbf{x}_i)-y_i\]

회귀모형의 잔차는 $y_i-f(\mathbf{x}_i)$ 로 위의 손실함수의 Gradient의 음수와 같다. Gradient descent를 할 때, gradient의 정보만 가지고 있으면 0이 아닐 경우 역방향으로 움직이면 최소화된 함수를 찾아갈 수 있음을 의미한다.

GBM은 손실함수의 기울기를 사용하기 때문에 손실함수에 따라 성능이 달라진다.

• 회귀모형에 대한 손실 함수

• 분류모형에 대한 손실 함수

  

  $\log$를 씌운 Bernoulli loss보다 $\exp$인 Adaboost loss가 훨씬 더 민감하게 반응한다.

과적합 방지

GBM에서 가장 중요한 것은 과적합 방지이다.

원래 데이터 $y$는 어떠한 함수 $f(x)$에 의해 만들어지는데 자연발생적인 노이즈 $\epsilon$가 반드시 포함된다. $y=f(x)+\epsilon$. 앙상블 과정을 진행하면서 GMB은 첫 번째 모델의 단점을 보완할 때, $y-\hat{f}_1(x)=\hat{f}_2(x)$의 과정을 거치게 되고 이 과정은 원래 함수의 노이즈도 같이 학습하겠다는 것을 의미한다. 하지만 노이즈는 자연발생적인 변동성으로 학습하게되면 과적합된다.

A는 모든 데이터 포인트를 지나는 형태로 과적합된 걸 알 수 있고, B도 영역안에 영역이 존재할 정도로 과적합된 것을 볼 수 있다.

과적합을 방지하기 위한 방법 첫번째는 Subsampling이다. Subsampling은 학습 데이터의 일부분만 비복원 추출해 사용한다. 기울기를 만들 때는 모든 데이터가 사용되지만, 예를 들면 100개의 데이터가 존재할 경우, 100개의 데이터를 통해 기울기를 만들고 80개의 데이터만을 사용해 모델을 학습시킨다. 만들어진 모델에 100개의 데이터를 다시 fitting 시키고 gradient를 구하는 방식을 반복한다.

두번째는 Shrinkage이다. 모델들을 결합할 때, 모델 생성 순서에 따라 가중치를 다르게 부여하는 방식이다. $\hat{y}=f_1(x)+0.9f_2(x)+0.9^2f_3(x)+\cdots$의 형식으로 가중치를 부여한다.

GBM이 Random Forest와 함께 널리 쓰이는 이유 중 또 하나는 변수 중요도 계산이 가능하기 때문이다.

\[Influence_j(T)=\sum_{i=1}^{L-1}(IG_i\times 1(S_i=j))\]

변수 $j$의 single tree $T$에서의 중요도는 $I$번째 split에서 효과가 있었는지, $j$가 split $i$에 사용되는지 안되는지에 따라 계산된다.