Gradient Boosting Machine(GBM)이란 무엇인가? - 논문 리뷰

Gradient Boosting Machine의 개념을 제안한 Jerome H. Friedman의 Greedy Function Approximation: A Gradient Boosting Machine 논문을 바탕으로 작성해봤습니다.

 

Gradient Boosting Machine 이란?

Gradient Boosting 모델은 additive model로서 weak learner들이 예측한 결과 값과 label 데이터의 편차(residual)를 학습해나가는 모델입니다. Loss를 줄이기 위해 Gradient Descent 알고리즘을 사용하고 주로 decision tree 모델에서 사용됩니다. Decision tree에서 leaves들의 loss를 본 후 loss가 큰 부분들의 가중치를 좀 더 크게 조정하여 성능을 점점 향상하는 모델이라고 할 수 있겠습니다.

또 다른 앙상블 기법인 Bagging과의 큰 차이점은 학습의 흐름이라고 볼 수 있겠습니다. Bagging은 여러 decision tree들을 병렬적으로 학습하여 결과를 보여주는 것과 달리, Boosting은 decision tree들을 sequential하게 가중치들을 업데이트하며 진행합니다.

 

 

수식을 통해 좀 더 자세히 설명하겠습니다. (볼드체는 벡터를 의미합니다)

 

Function Estimation

training sample이 $\{{y_i,\mathbf{x}_i}\}_{1}^N$ 이러한 형태일 때 우리는 $\mathbf{x} = \{ x_1,\cdots,x_n \}$ 에서 $y$ 로 mapping 시켜주는 함수 $F$ 를 찾아주는 것이 목표입니다. 정확한 $f$ 를 찾는 것이 불가능하므로 아래 식처럼 손실 함수의 기댓값을 최소로 해주는 $F^*$ 를 구해주면 됩니다. (여기서 $L$ 은 loss)

 

$$F^* = \arg\min_{F}E_{y,\mathbf{x}}L(y, F(\mathbf{x})) = \arg\min_{F}E_{\mathbf{x}}\left[E_{y}(L(y,F(\mathbf{x}))) | \mathbf{x}\right]$$

 

loss function으로는 regression인 경우 MSE(mean squared error), MAE(mean absolute error)를 사용하고 classification(특히 이항 분류)의 경우에는 negative binomial log-likelihood function을 사용하게 됩니다.

 

$$F(\mathbf{x}; \{\beta_m, \mathbf{a}_m\}_{1}^{M}) = \sum_{m=1}^{M} \beta_m h(\mathbf{x}; \mathbf{a}_m)$$

 

위 공식에서 $h$ 는 decision tree이고 $\mathbf{a}_m$ 은 split variable, split point들로 decision tree들의 모수입니다. 이러한 모수들을 최적화하는 문제로 귀결되는데 여기서 gradient-descent 알고리즘을 통해 반복적인 업데이트를 하여 최적 모수를 찾아줍니다.

최적의 모수 $\hat{P}$ 를 구하기 위해 successive increment의 방식으로 모수를 매 단계마다 additive 하게 구해줘도 되지만, 여기선 non-parametric numerical optimization 방법인 함수를 수치적으로 근사하여 최적화 문제를 해결하게 됩니다.

우리는 $F$ 를 근사하기 위해 초기값 $\textbf f_0(x)$ 를 설정하고 $M$ 번 반복하여 잔차를 업데이트해줄 것입니다. 매번 업데이트를 할 때마다 잔차를 예측한 함수를 $\textbf f_m(x)$ 라 한다면 최종 근사 식은 아래와 같을 것입니다.

 

$$F^*(\mathbf{x}) = \sum_{m=0}^{M}f_m(\mathbf{x})$$

 

gradient-descent 방식에 의해 아래와 같은 식이 만족됩니다.

 

$$F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) - \rho{g}_m(\mathbf x)$$

$$g_m(\mathbf{x}) = \left[\frac{\partial L(y,F(\mathbf{x}))}{\partial F(\mathbf{x})} \right]_{F(\mathbf x) = F_{m-1}(\mathbf x)}$$

$$\rho_m = \arg\min_{\rho}E_{y,\mathbf{x}}L(y,F_{m-1}(\mathbf{x}) - \rho g_{m}(\mathbf x))$$

 

보통 dataset이 $\{{y_i,\mathbf{x}_i}\}_{1}^N$  로 유한하게 주어지기 때문에 $\mathbf{x}$ 와 $y$ 의 joint distribution을 정확하게 구할 수가 없습니다. 따라서 위에서 소개한 non-parametric numerical optimization을 다음 방식으로 치환해야 합니다.

 

다음과 같은 방법을 Greedy Stagewise 접근법이라 하는데

 

$$(\beta_m, \mathbf{a}_m) = \arg\min_{\beta,\mathbf{a}}\sum_{i=1}^{N} L(y_i, F_{m-1}(\mathbf{x}_i) + \beta h(\mathbf{x}_i;\mathbf{a}))$$

$$F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \beta_m h(\mathbf{x};\mathbf{a}_m)$$

 

의 방식으로 업데이트를 진행하게 됩니다.

 

위에서 $\beta_m, a_m$ 을 구할 때 최적화된 해를 구하기 쉽지 않은 경우 $f_{m-1}(x)$ 에 대한 gradient descent step direction인 $-\mathbf g_m$ 을 구하면 됩니다. 하지만, training data $\{x_i\}_{i=1}^N$ 에 대해서만 $\mathbf g_m$ 이 정의되기 때문에 모든 $x$ 에 대해서 일반화 가능한 $h(x)$ 를 이용해야 합니다. 가능한 $h(x)$ 들 중 아래와 같이 모수를 정의해줍니다.

 

$$\mathbf{a}_m = \arg\min_{\mathbf{a},\beta}\sum_{i=1}^N [- g_m(\mathbf{x}_i) - \beta h(\mathbf{x}_i;\mathbf{a})]^2$$

 

위 식을 통해 이러한 모수들을 통해 $\mathbf{g}_m \in R^N$ 에 가장 평행한 $h(\mathbf{x};\mathbf{a}_m)$ 을 찾을 수 있습니다. 이렇게 얻어진 $h(\mathbf{x};\mathbf{a}_m)$ 을 통해 $\rho_m$ 을 다시 구할 수 있습니다.

 

$$\rho_m = \arg\min_{\rho}\sum_{i=1}^N L(y_i,F_{m-1}(\mathbf{x}_i) + \rho h(\mathbf{x}_i ; \mathbf{a}_m))$$

 

이렇게 구한 값으로부터 업데이트 과정을 다음처럼 진행하면 됩니다.

 

$$F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \rho_m h(\mathbf{x};\mathbf{a}_m)$$

 

<Gradient-Boosting 알고리즘 요약>

$1. \; F_0(\mathbf{x}) = \arg\min_{\rho}\sum_{i=1}^N L(y_i,\rho)$

$1$부터 $M$까지의 모든 $m$에 대해

$2. \; g_m(\mathbf{x}_i) = \left[\frac{\partial L(y_i,F(\mathbf{x}_i))}{\partial F(\mathbf{x}_i)} \right]_{F(\mathbf x) = F_{m-1}(\mathbf x)}\;$, $\; 1 \leq i \leq N$

$3. \; \mathbf{a}_m = \arg\min_{\mathbf{a},\beta}\sum_{i=1}^N [-g_m(\mathbf{x}_i) - \beta h(\mathbf{x}_i ; \mathbf{a})]^2$ 

$4. \; \rho_m = \arg\min_{\rho} \sum_{i=1}^N L(y_i, F_{m-1}(\mathbf{x}_i) + \rho h(\mathbf{x}_i;\mathbf{a}_m))$

$5. \; F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \rho_{m}h(\mathbf{x};\mathbf{a}_m)$