[EM] 그래디언트 부스팅(Gradient Boosting) 이론

[#1]

이번시간에는 그래디언트 부스팅(Gradient Boosting)에 대하여 다뤄보겠습니다.

introduction

그래디언트 부스팅이란 Gradient Desent 와 Boosting의 합성어로 쉽게 말해 Boosting에 Gradient Descent를

접목시킨 강력한 머신러닝기법입니다.

우선 Boosting이란 앞서 연재된 글에서 소개 된 바와 같이 단순한 모델들을 결합하여 단계적으로 학습함으로써

 이전모델의 약점을 점점 보완해 가는 모델입니다.

Gradient Descent

Gradient Descent는 단어 그대로 해석하면 ‘경사 하강’ 이란 의미입니다. 말 그대로 함수의 기울기를 구하여

기울기가 낮은 쪽으로 이동시키면서 극값에 이를 때까지 반복하는 방법입니다.

위의 그림은 를 얻는 모습을​ 나타내고 있습니다.

은 이동할 거리를 조절하는 매개변수입니다. 은 wolfe 조건을 만족하는 라인검색을 통해 구하거나 다음과 같은 Barzilai-Borwein 방법을 통해 구할 수 있습니다.

그래디언트 부스팅은 약한 모델들을 단계적으로 부스팅하는 과정에서 이전 모델의 오류를 손실함수로 나타내고

이 손실함수를 최소화하는 방법으로 Gradient Descent를 사용하는 분석기법입니다.

algorithm

이런 함수식을 추정량h(x)에 대하여 다시 정리하면

위와 같은 식이 나오는데 그래디언트 부스팅의 주 목적은 이 h(x)를 추정하는 것입니다. 그리고 h(x)를 추정하는 과정에서 Gradient descent를 사용하게 됩니다.

분류나 순위문제에서 손실함수에 대한 일반적인 아이디어는 주어진 모델에 대한 잔차 y-F(x)가 오차제곱 손실함수의 음의 기울기라는 점에서 나왔습니다.

따라서 그래디언트 부스팅의 목적은 특정한 손실함수의 기대값을 최소화하는 함수 F(x) 대한 근사치 을 찾는 것입니다.

 

하지만 임의의 손실함수 L에 대한 최고의 함수h를 고르는 것은 계산적으로 불가능합니다. 따라서 함수를 단순화 시키게 됩니다. 이때 Gradient descent를 적용하게 됩니다. 연속형의 경우, 아래와 같은 방정식에 따라 모델을 업데이트합니다.

그리고 이산형의 경우, 손실함수L의 기울기에 가장 가까운 후보함수h를 선택하고 계수 은 line search을 통해 구합니다. 비록 이런 접근법이 완벽하게 정확하지는 않지만 충분히 설득력있는 근사값을 얻을 수 있습니다.

loss function

대표적인 손실 함수는 Square loss :  가 있고 Square loss 는 수학적으로 다루기는

쉽지만 이상치에 민감한 단점을 가지고 있습니다. 이러한 단점을 보완하는 이상치에 민감하지 않은 손실함수로는 Absolute loss 나 Huber loss 가 있습니다.

Reference

https://en.wikipedia.org/wiki/Gradient_descent

http://www.ccs.neu.edu/home/vip/teach/MLcourse/4_boosting/slides/gradient_boosting.pdf

https://en.wikipedia.org/wiki/Gradient_boosting