Gradient Boosting Algorithm의 직관적인 이해

Gradient Boosting Algorithm의 직관적인 이해

실패를 통해 성공을 발전시켜라. 낙담과 실패는 성공으로 가는 가장 확실한 두 개의 디딤돌이다. -데일 카네기

Gradient Boosting Algorithm (GBM)은 회귀분석 또는 분류 분석을 수행할 수 있는 예측모형이며 예측모형의 앙상블 방법론 중 부스팅 계열에 속하는 알고리즘입니다. Gradient Boosting Algorithm은 Tabular format 데이터 (엑셀형태와 같이 X-Y Grid로 되어있는 데이터)에 대한 예측에서 엄청난 성능을 보여주고, 머신러닝 알고리즘 중에서도 가장 예측 성능이 높다고 알려진 알고리즘입니다. 그렇기 때문에 Gradient Boosting Algorithm을 구현한 패키지들이 많습니다. LightGBM, CatBoost, XGBoost 같은 파이썬 패키지들이 모두 Gradient Boosting Algorithm을 구현한 패키지들입니다. GBM은 계산량이 상당히 많이 필요한 알고리즘이기 때문에, 이를 하드웨어 효율적으로 구현하는 것이 필요한데, 위 패키지들은 모두 GBM을 효율적으로 구현하려고한 패키지들이라고 볼 수 있습니다.

Boosting 이란?

주요 앙상블 알고리즘은 bagging과 boosting으로 나눌 수 있고, Gradient boosting은 boosting 계열의 앙상블 알고리즘입니다. Gradient Boosting 알고리즘은 Gradient 를 이용하여 Boosting하는 알고리즘입니다. Gradient boosting 외의 boosting 계열의 알고리즘의 예로는 Adaptive boosting을 들 수 있습니다. 

먼저 Boosting의 개념부터 살펴봅시다. Boosting이란 약한 분류기를 결합하여 강한 분류기를 만드는 과정입니다. 분류기 A, B, C 가 있고, 각각의 0.3 정도의 accuracy를 보여준다고 합시다. A, B, C를 결합하여 더 높은 정확도, 예를 들어 0.7 정도의 accuracy를 얻는 게 앙상블 알고리즘의 기본 원리입니다. Boosting은 이 과정을 순차적으로 실행합니다. A 분류기를 만든 후, 그 정보를 바탕으로 B 분류기를 만들고, 다시 그 정보를 바탕으로 C 분류기를 만듭니다. 그리고 최종적으로 만들어진 분류기들을 모두 결합하여 최종 모델을 만드는 것이 Boosting의 원리입니다. 

GBM의 직관적인 이해

GBM을 이해하는 가장 쉬운 방법은 Residual fitting으로 이해하는 것입니다. 아주 간단한 모델 A를 통해 y를 예측하고 남은 잔차 (residual)을 다시 B라는 모델을 통해 예측하고 A+B 모델을 통해 y를 예측한다면 A보다 나은 B 모델을 만들 수 있게 되죠. 이러한 방법을 계속하면 잔차는 계속해서 줄어들게되고, training set을 잘 설명하는 예측 모형을 만들 수 있게 됩니다. 하지만 이러한 방식은 bias는 상당히 줄일 수 있어도, 과적합이 일어날 수도 있다는 단점이 있습니다. 따라서 실제로 GBM을 사용할 때는 sampling, penalizing 등의 regularization 테크닉을 이용하여 더 advanced 된 모델을 이용하는 것이 보편적입니다. 하지만 본 포스팅의 목적은 GBM 에 대하여 직관적인 이해를 해보는 것이기 때문에 이 부분은 다음에 기회가 있을 때 정리해보도록 하겠습니다. 

위 그림을 보시면 tree 1을 통해 예측하고 남은 잔차를 tree2를 통해 예측하고, 이를 반복함으로서 점점 잔차를 줄여나가는 것을 볼 수 있습니다. 이 때, 각각의 모델 tree1,2,3 을약한 분류기 (weak learner), 이를 결합한 분류기를 강한 분류기 (strong learner)라고도 합니다. 보통 약한 분류기로는 간단한 의사결정나무 (decision tree)를 많이 사용합니다. 이를 Gradient boosting tree라고도 하는데, 구현한 대표적인 라이브러리로 XGboost를 들 수 있습니다. XGBoost는 python, R로 이용할 수 있습니다. 

Gradient란 무엇인가?

그렇다면 residual fitting과 gradient가 무슨 관계인지 궁금하실텐데요. residual은 loss function을 squared error로 설정하였을 때, negative gradient 입니다. 따라서 residual에 fitting해서 다음 모델을 순차적으로 만들어 나가는 것은 negative gradient를 이용해 다음 모델을 순차적으로 만들어 나가는 것으로 볼 수 있습니다. 우선 아래 식을 통해 이를 확인해봅시다. 

loss function을 아래와 같이 정의하면,

$$ j(y_i, f(x_i)) = \frac{1}{2}(y_i - f(x_i))^2 $$ 

이 때의 negative gradient는 residual이 됩니다.

residual이 $$ y_i - f(x_i) $$ 이기 때문에 negative gradient가 residual이 된다는 것을 알 수 있습니다. 

따라서 gradient boosting은 다음 모델을 만들 때, negative gradient를 이용해 만들기 때문에 gradient boosting 이라고 할 수 있습니다. 또한 residual fitting model은 gradient boosting 모델의 한 가지 종류입니다. 왜냐하면 다른 loss function을 이용해서 gradient boosting을 할 수 있기 때문입니다. 예를 들어 회귀 문제가 아닌 분류 문제라면 loss function으로 squared error 를 이용할 수 없기 때문에 새로운 loss function을 만들어야하는데, 이 경우에도 negative gradient를 이용해서 새로운 model 을 fitting하고 이를 합산해 나가시는 식으로 최종 모델을 만들게 됩니다. 

직관적으로 이것은 무엇을 뜻할까요? 왜 negative gradient를 이용해서 새로운 모델을 만드는 걸까요? negative gradient는 pseudo-residual이라고도 불리며, 이것은 어떤 데이터 포인트에서 loss function이 줄어들기 위해 f(x)가 가려고하는 방향입니다. 이 방향에 새로운 모델을 fitting해서 이것을 이전 모델과 결합하면, f(x) 는 loss function이 줄어드는 방향으로 업데이트가 되겠죠. 이것이 gradient boosting의 아이디어입니다. Gradient boosting을 gradient descent + boosting 이라고 하기도 합니다. 어쨌든, loss function을 줄이는 방향의 negative gradient를 얻고, 이를 활용해 boosting을 하는 것이기 때문에 gradient descent와 boosting이 결합된 방법이다. 라고 이해하셔도 괜찮습니다. 

위 그림은 위키피디아에서 gradient boosting에 대하여 설명한 알고리즘도입니다. 이제 위 내용을 이해할 수 있습니다. gradient boosting에서는 learning rate를 통하여 pseudo-residual에 fitting된 모델을 어느정도로 update할지에 대해서 정하게 되는데, 이 값은 위 알고리즘도의 3번처럼, loss를 최소화하는 값을 optimization 과정을 통해 얻을 수도 있겠지만, 일반적으로 0.001~0.01 정도로 매우 작은 값으로 설정하는 것이 보편적입니다. 왜냐하면 작은 값으로 설정하여야 굉장히 세밀한 분류기를 얻을 수 있습니다. learning rate가 높을 수록 빠르게 모델의 bias를 줄여나가지만, learning rate가 적으면 디테일한 부분을 놓칠 수 있다고 이해하시면 됩니다. 이와 관련해서는 gradient boosting 과정을 simulation 해볼 수 있는 사이트를 소개합니다. 이 곳에서 직접 gradient boosting 방법이 어떻게 함수를 fitting 해나가는지를 시각적으로 확인할 수 있습니다. 

참고

https://machinelearningmastery.com/gentle-introduction-gradient-boosting-algorithm-machine-learning/