Boosting

Boosting

Boosting은 weak learner 또는 baseline model 여러 개를 결합하여 보다 높은 성능의 prediction model을 만드는 방법으로, Bagging 및 Random Forest와 함께 널리 사용되는 ensemble 방법 중 하나이다 (Bagging and Random Forest). 이 때, boosting model은 baseline model의 linear combination으로 볼 수 있다.

특히 data가 적을 때에는 bagging보다 boosting의 성능이 더 좋은 편이다.

Boosting은 decision tree를 기반으로 개발된 방법은 아니지만, 실제적으로 대부분의 boosting algorithm은 model의 유연성과 효율성, 특히 outlier에 둔감하다는 장점으로 인해 decision tree를 baseline model로 사용한다.

AdaBoost

Boosting은 1997년 Freund and Schapire(1997)이 처음 개발한 AdaBoost (Adaptive Boosting)을 시작으로 다양한 boosting algorithm들이 개발되었다.

AdaBoost는 다음과 같이 동작한다.

1. 모든 data point에 대해 동일한 weight $w_i$를 부여한다.

2. 각 baseline model $f_b(x) \in \{-1,1\}$ ($b=1\dots B$)에 대해,

   1. 현재 weight를 기반으로 $f_b(x)$에 대해 학습을 진행한다.

   2. Model의 error rate을 계산한다.

      $\text{err}_b = \frac{\sum_{i=1}^n w_i I(y_i\ne f_b(x))}{\sum_{i=1}^n w_i}$

   3. Model의 weight $c_b$를 계산한다. Model의 error rate이 작을수록 $c_b$는 커진다.

      $c_b = \log((1-\text{err}_b)/\text{err}_b)$

   4. $c_b$과 분류 결과를 이용해서 잘못 분류된 data point이 더 높은 weight를 갖도록 $w_i$를 update한다.

      $w_i \leftarrow w_i \exp(c_b I(y_i \ne f_b(x_i)))$

3. Model의 weight $c_b$을 이용하여 각 model의 prediction에 대한 weighted average 값의 부호로 최종 prediction을 결정한다.

AdaBoost model은 weight factor를 사용한 알고리즘의 특성 상 overfitting에 강한 편이라는 것이 (실험적으로도) 알려져 있지만, exponential loss function을 갖기 때문에 다른 boosting algorithm에 비해 outlier에 대해서 상대적으로 민감하게 반응하는 경향이 있다.

Gradient Boosting

Gradient boosting은 functional gradient descent라는 optimization 방법을 사용한 boosting algorithm으로, 쉽게 말해 residual을 반복적으로 fitting하여 prediction accuarcy를 향상시키는 방법이다. 일반적으로 boosting 방법을 지칭할 때, gradient boosting을 말하는 경우가 많다.

Gradient boosting의 개략적인 원리는 다음과 같다 (여기서는 regression 문제를 가정한다).

1. $\hat{f}(x)=0$, $r_i=y_i \; \forall i$ 로 설정한다.

2. 각 baseline model $f_b(x)$ ($b=1,\dots,B$)에 대해,

   1. $f_b(x)$에 대해 학습을 진행한다.

   2. $f_b(x)$에 shrinkage parameter $\lambda$를 곱하여 $\hat{f}(x)$를 업데이트한다.

      $\hat{f}(x) \leftarrow \hat{f}(x) + \lambda f_b(x)$

   3. Residual $r_i$를 업데이트한다.

      $r_i \leftarrow r_i - \lambda f_b(x)$

3. 최종 boosting model을 얻는다.

Gradient boosting을 recursive algorithm으로 착각하여 각 baseline model의 기여분이 $\lambda$의 제곱만큼 차이가 날 것으로 생각할 수 있는데, 모든 tree의 기여분은 $\lambda$만큼이다.

Logit Boosting

Logit boosting은 binary classification 문제에 특화된 algorithm으로 기본적인 알고리즘은 gradient boosting과 동일하다.

차이점은 gradient boosting model의 loss function이 MSE $\frac{1}{n} \sum_{i=1}^n (y_i-f(x_i))^2$ 인데 반해, logit boosting은 logistic loss function $\sum_{i=1}^n \log(1+\exp(-y_if(x_i)))$를 이용한다는 것이다.

Gradient 및 Logit boosting은 AdaBoost에 비해 outlier에 더 robust하다는 장점이 있다.

Prevent Overfitting for Gradient Boosting

Gradient 및 Logit boosting의 경우 기본적으로 gradient 또는 residual에 대한 fitting을 진행하므로 overfitting 가능성이 무척 크다는 단점이 있다.

따라서, 기본적으로 좋은 성능의 boosting model을 얻기 위해서는 다음과 같이 regularization을 설정해야한다.

• 각 baseline tree model의 max depth를 제한한다.

  • 각 model의 depth는 feature간 interaction을 얼마나 반영할 지를 결정한다.
  • 4~5 정도의 값으로 설정하는 것이 적당하다고 한다.

• 개별 tree의 기여분을 결정하는 $\lambda$ 값을 적절하게 설정한다.

  • 일반적으로 $\lambda$가 작을수록 성능이 더 좋아지나, cost 측면에서 주로 1/100 또는 1/1000으로 설정한다.

• Tree의 수 $B$를 적절하게 설정해야한다. 만약 $B$가 너무 크면 overfitting이 발생할 우려가 있다.

  • 하지만 tree의 개수에 따른 overfitting은 굉장히 천천히 생기기에 일반적으로는 bagging보다 훨씬 더 많은 수의 tree (100~1000개 이상)를 사용한다.

Hyperparameter tuning 시, $\lambda \times B = \text{constant}$가 되도록 조정하는 것이 좋다고 알려져 있다.