[Ensemble] Gradient Boosting, 차근차근

 

Gradient Boosting, 차근차근

Ensemble

 

 

---

 

Gradient Boost는 앙상블과 AdaBoost, 선형회귀에서의 Gradient Desent의 개념을 알고 있으면 쉽게 이해하고 사용할 수 있습니다. 이 포스트는 앞서 작성된 포스트를 기반으로 작성되었습니다.

 

[Ensemble] 백지장도 맞들면 낫다, 앙상블 OVERVIEW

[Ensemble] Ada Boost, 모델의 오답노트

[선형회귀] Gradient Descent

 

 

Gradient Boost

Gradient Boost는 Gradient Descent과 Boosting의 합성어입니다. 잠깐 Gradient Boost가 어떤 것인지 짚고 넘어가겠습니다. 선형회귀에서 Loss Function(혹은 Cost Function)에서 임의의 점을 기준으로 기울기의 반대방향으로 가면서 최소점을 찾는 방법이 Gradient Descent(경사하강법)입습니다.

다시 돌아와 Boosting에대해 살펴보자면, 앞서 AdaBoost(Adaptive Boost)는 Weak Model을 통해서 틀린 데이터에 가중치를 주어 다음번에 더 많이 뽑히도록하며, 동시다발적이 아닌 하나씩 하나씩 결과를 좋게 만드는 방법이었습니다. 앞선 Weak Model의 약점을 다른 Weak Model이 보완해주는 식이었습니다. weak model만으로도 복잡한 분류 경계면을 만들 수 있었습니다. AdaBoost와 Gradient Boost는 어디가 다른 걸까요?

• AdaBoost에서는 틀린데이터들을 가중치를 크게 줌으로써 문제를 해결하려했습니다.
• Gradient Boost에서는 틀린데이터들을 Gradient를 통해 문제를 해결할 것입니다.

그럼 이제 Gradient를 통해서 틀린데이터를 어떻게 다루는지 알아보겠습니다 !

 

 

 

Algorithm

Friedman, J. H. (February 1999). "Greedy Function Approximation: A Gradient Boosting Machine"

쉽게 생각해보겠습니다

여기서 $L$은 Loss Function을 의미합니다. 이문제를 회귀(Regression)이라고 생각하고 풀어봅시다. Loss Function은 OLS, 즉 예측치와 실제값의 차이를 제곱한 것이었습니다. 그리고 이 차를 최소화 시키기 위해서 편미분을 통해서 값을 구했었습니다. ($L(y_i,f(x_i))=\frac{1}{2}(y_i - f(x_i))$) (이전포스트 참고)

For Loop가 시작됩니다. 1부터 M까지 돌립니다. 편미분을 통해서 Gradient를 계산합니다. 그리고 이 값에 -를 붙여 음수로 만들어 줍니다. ( Negative gradient : pseudo-residual ) 경사를 하강시키는 것입니다.

4번과 5번에서는 gradient와 $p$(Learning Rate, multiplier)를 이용하여 $y_i$(실제값)과 지금까지 적용해온 $F_{m-1}$(이전모델까지 나온 output)의 차이의 합을 최소화시키는 값을 가지고

최종적으로 $F_{m-1}$을 새로운 $F_{m}$으로 업데이트해 줍니다.

Loss Function을 어떤 것을 사용하느냐에 따라서 그 결과물이 달라집니다. (회귀 : $L_1$,$L_2$,Huber,Quantile등, 분류 : Bernoulli, Adaboost)

 

 

 

 

Visualization

https://github.com/pilsung-kang/Business-Analytics-IME654-/blob/master/04%20Ensemble%20Learning/04-6_Ensemble%20Learning_Gradient%20Boosting%20Machine.pdf

Original Dataset에서 $f_{1}(x)$라는 모델을 이용하여 예측치를 냅니다. 그럼 그 예측치($f_{1}(x^{1})$$f_{1}(x^{2})$,...)와 실제값($y^{1}$,$y^{2}$,...)의 차이를 통해 Loss Function에 적용시킬 수 있습니다. 그럼 위 알고리즘을 통해서 $f_{2}$를 구할 수 있습니다. $f_{2}$모델로 새로운 예측을 하더라도 실제값과는 차이가 있겠죠? 또 이차이를 가지고 $f_{3}$을 만듭니다. 이 과정을 반복하여 실제값과의 오차를 최소한으로 줄이는 것입니다 ! 계속 진행하면 오차를 정말 많이 줄일 수 있겠죠?

 

아래는 Gradient Boost를 시각적으로 확인 할 수 있는 사이트입니다.

Gradient Boosting explained by Alex Rogozhnikov

 

 

 

 

Regularization

https://scikit-learn.org/stable/auto_examples/ensemble/plot_gradient_boosting_regularization.html

그래서 과적합이 문제가 될 수 있는데 (특히 Iteration이 많아질 때), 이를 극복하기 위해서 여러가지 방법을 사용합니다. 먼저 Subsampling이라는 방법이 있습니다. 위 그림에서는 subsample이 0.5입니다. 어떤 데이터가 있으면, Iteration을 할 때 50%만 뽑는다는 소리입니다. 그럼 50%로 만들어진 $f_{1}$모델을 전체 데이터에 적용하게됩니다. 그 다음 전체데이터에서 다시 50%를 뽑는 것입니다. 다음은 Shrinkage입니다. 수축이라는 뜻을 가진 단어처럼, 모델에대한 가중치를 서서히 줄이는 것입니다. 처음 만든 모델보다 뒤에 만들어진 모델이 더 영향이 적어집니다. Early Stopping은 모델이 에러가 커질 것 같을 때 중지를 시키는 것입니다. 위그림에서 파란색라인은 50정도에서 멈춰주면 좋을 것 같습니다.

위그림을 보면, Regularization을 아무것도 안한 모델은, Iteration이 많아질수록 증가하고있습니다(yellow line). 반면 러닝레이트와 subsampling을 적용한 모델은 iteration이 많을 수록 가장 좋은 성능을 보여주는 것을 알 수 있습니다.

 

 

 

Ada Boost vs Gradient Boost

1. 틀린 값(Shortcoming)을 다룰 때
   AdaBoost는 가중치를 높게(high weight)하여 데이터를 뽑고,
   Gradient Descent는 Gradient를 통해서 다룹니다.
2. 그렇기 때문에
   Ada Boost는 샘플링을 하는데 있어서 각 데이터(Observations)는 가중치가 다르고,
   Gradient Boost는 가중치가 같습니다.
3. Ada Boost는 Classifier(ex. tree)와 데이터에게 가중치를 부여함으로써 최대 분산을 얻어 학습합니다.
   Gradient Boost는 이전의 Classifier를 통해서 분산을 얻어 학습합니다.
4. Adaboost는 각 트리가 일반적으로 Decision stumps를 사용합니다. (이전 포스트 참고)
   Gradient Boost는 각 트리가 Ada Boost보다 깊고 일반적으로 8~32개의 노드를 가집니다.

 

 

 

참고자료

A Gentle Introduction to the Gradient Boosting Algorithm for Machine Learning

pilsung-kang/Business-Analytics-IME654-