[머신러닝/딥러닝] 4. Boosting

Boosting

마찬가지로 [데이터마이닝 : 앙상블]의 Boosting과 상당부분 겹친다. 그런데 해석하는 방법이 달라서 처음엔 누가 틀렸나 한참 찾았다. 결국 의미하는 바가 같다는 것을 알았다는 점에서 이번 강의에서도 얻은 것이 많았다고 생각한다.
이 글에서는 주관적 생각이나 데이터마이닝에서 배운 지식을 최대한 덜어내고 교수님이 하신 강의내용만 다룬다.

"Can a set of weak learners create a single strong learner?(Michael Kearns, 1988)"

"Yes! Boosting!(Robert Schapire, 1989)"

성능이 약한 weak learner의 모임으로 성능이 좋은 1개의 strong learner로 만들 수 있을까? Robert Schapire(Boosting의 아버지라 불린다.) 는 Boosting기법으로 가능하다고 한다. 

※ 사실 위 개념은 Boosting 뿐만 아니라 Bagging, Stacking 등 모든 앙상블 모델의 핵심 컨셉이다.

Generic Boosting

일반적인(Generic) Boosting의 원리는 이렇다.

• Step 0. 일단 y를 예측하는 learner(=model=hypothesis) H(s) 를 만든다.

• Step 1. H의 성능을 판단한다.(ex. Squared error / Absolute error / Exponential loss / Logloss)

• Step 2. H의 성능을 보강할 수 있는 새로운 weak learner h을 만들고 성능을 판단한다.
  이 때, 성능에 따라 h의 weight α를 정해준다. (성능이 좋으면 α가 높게)

• Step 3. 모든 weak learner의 weighted sum을 strong learner H로 정의한다.
  ※ 최근 연구에 의하면 weight는 H(x)에 큰 영향을 주지 않는다고 한다.

• Step 4. H의 성능이 만족스러울 때까지 Step 1~3를 반복한다.

생각보다 원리는 간단하다. 부족한 모델의 성능을 채우기 위해 weak leaner를 계속 만들어서 Strong Learner라는 list에 쌓아두는 느낌이다. 실제로 새로운 데이터가 입력되면 모든 weak learner가 예측값을 내 놓는다. binary classification의 경우 예측값들이 두 팀으로 나눠질텐데, 각 팀의 weight 합이 큰 쪽의 손을 들어주는 식으로 예측한다.

여튼, strong learner가 만들어지는 원리를 보니, 최종 모델은 weighted sum이지만 1 batch일때는 아래와 같이 표현할 수 있다. 즉, 지금까지 만들어진 strong learner에 weak learner가 합쳐지는 것이다.

위 식을 가만 보면 gradient decent가 생각난다. gradient decent에서는 weight가 update됐는데 위 식은 function이 update되고 있다. 심지어 learning rate의 역할을 하는 모델의 weight(importance)도 있다.

그래서 Boosting을 Gradient decent in functional space 라고도 부른다.
※ 우리가 지금껏 배웠던 gradient decent는 parameter space에서 동작하는 알고리즘이라 할 수 있다.

그럼 H(x)의 성능을 보강시켜 줄 h(x)는 어떻게 만들 수 있을까?

당연히 H(x)와 h(x)가 합쳐졌을 때 성능이 최대로 나올 수 있도록, 즉 위 식처럼 오차가 최소인 weak learner 를 찾아야 한다. 이 functional gradient descent를 한번 풀어보자.

가장 먼저 오차함수 L(H + αh)을 근사화 하기 위해 Taylor series expansion을 적용해보자.

※ Tayler series expansion : 어떤 미지의 함수 f(x)를 근사 다항함수 p(x)로 변환하는 방법

위 공식은 n-order approximation 인데, 우리가 가진 오차함수L(H + αh) 를 first-order approximation 하면 아래와 같다.

※ Tayler 공식에서 x = H+αh,  a = H라 생각하면 위 식이 이해된다.
※ first-order기 때문에 p(x) = f(a) + f'(a)(x-1) 까지만 고려한다.
※ <>는 inner product이다. ex)<a, b> = a1*b1 + a2*b2 + ...
※ 마찬가지로 Tayler series expansion in functional space라 볼 수 있다.

이제 위 식을 최소화 하는 weak learner h를 찾아야 한다. 이 때 기존 learner H는 이미 학습된 상태이기 때문에 inner product 항을 최소화하는 수 밖에 없다.
(α는 상수항이기 때문에 argmin 함수에서 빠졌다.)

즉, inner product를 전개한 최종 목적함수는 위와 같이 쓸 수 있다.

이 때 새로 만들어진 모델의 L(H+αh)는 무조건 예전 모델의 L(H)보다 작아야 한다.

즉, 위 전개에 따라 Σ r*h < 0 일때만 Ht+1을 update하고, 0보다 크거나 같으면 더 이상 weak learner를 만들지 않게 된다. (종료조건) 아래는 실제로 Generic boosting을 구현하기 위한 Pseudo code이다.

functional gradient를 구하고, rn < 0 일때 Ht+1을 update 하는 모습을 확인할 수 있다.

Gradient Boosting, AdaBoost

위의 Generic Boosting이 더 powerful 해 질 수 있는 트릭(?)을 부린 알고리즘들이 많다. 대표적으로 Gradient Boosting, AdaBoosting이 있지만, 큰 원리는 Generic Boosting에서 왔다는 것이다. 그래서 이 글에서는 Gradient Boosting과 AdaBoost의 원리에 대해 수식은 파고 들지 않을 예정이다. [데이터마이닝 : 앙상블] 에 두 알고리즘의 동작원리가 자세하게 설명되어 있으니 참고하도록 하자.

[slideshare : Boosting 기법 이해, freepsw, 2017]

• AdaBoost : Generic Boosting 기법 중 weak learner 학습할 때 sampling을 더욱 효과적으로 한다. 기존 모델이 예측에 실패한 sample이 다음에 다시 학습 될 수 있도록 sample에 weight를 부과하는 방식으로 sampling한다. 그래서 점점 틀린문제를 잘 맞추는 weak learner를 만들 수 있다.

[slideshare : Boosting 기법 이해, freepsw, 2017]

• Gradient Boosting : 비교적 최근에 나온 Boosting 기법이다.(1997) label를 y로 학습하는 것이 아니라 잔차를 label로 설정해서 학습하는 기법이다. 다만 Gradient Boosting 알고리즘은 속도가 느리고 과적합 경향이 심하다. 이 문제를 어느정도 해결하고, CART(Classification & Regression) 기반으로 분류와 회귀 모두 가능할 수 있게 한 개량버전인 XGBoost가 발표되기도 했다.(2014)
  최근에는 Microsoft에서 XGBoost의 가장 큰 단점인 학습시간을 개선시킨 LightGBM을 발표하였다.(2020) LightGBM은 XGBoost에 비해 대용량 처리가 가능하면서 더 적은 자원(메모리)를 사용하며, GPU연산까지 지원한다.

XGBoost(extreme gradient boosting) vs. Deep Learning

최근에는 Powerful한 알고리즘을 2가지 고르라고 하면 당연 XGBoost와 Deep Learning이라 할 수 있다. (물론 올해 출시된 따끗따끈한 LightGBM도 있다.)

XGBoost는 Tree모형을 기반으로 하기때문에 복잡한 비선형문제를 빠른시간에 풀 수 있고, 특히 해석이 가능하다는 장점이 있다. (Tree 모형의 강력한 장점이다.)

반면 Deep Learning은 입력변수를 복잡한 선형+비선형 함수의 조합문제로 만들면서, 복잡한 상관관계가 있는 문제도 마치 사람의 직관처럼 모델링할 수 있다.

두 알고리즘을 굳이 경쟁을 붙인다면 아래와 같이 정의할 수 있겠다.

• Homogeneous feature : 픽셀, 글자와 같이 같은 unit을 갖는 feature를 다룰 때 Deep learning이 우수하다. 각 feature의 상관관계를 모델링할 수 있는 특징이 있기 때문이다.

• Heterogenous feature : 각각의 feature가 다른 것을 의미할 때 XGBoost가 더 우수하다. Tree 모형이 모든 feature가 independent할 때 성능이 좋은 것과 마찬가지다. Tree 모형 기반인만큼 주어지지 않은 데이터 즉, extrapolation 경우에 취약한 것은 어쩔 수 없다. 
  
  ※ 절대적인 비교는 어렵고, 일반적으로는 위와 같이 평가하는 추세다.