[CS246] Gradient Boosted Decision Trees (GBDT)

Gradient Boosted Decision Tree: Additive Learning

Example: Regression

다음과 같은 데이터에 대하여 regression task를 생각해보자.

\[ D = \{ (10, -10),\ (20, 7),\ (25,8),\ (35,-7) \} \]

Drug Effectiveness (Stanford CS246)

상수를 예측하는 것부터 시작하다. 여기서 $\hat{y}_i^{(0)}=0.5$라 하자.

$y$: groud truth vector

$y_i$는 $i$번째 instance(data point)의 ground truth이다.

$\hat{y}^{(t)}$: $t$번째 round에서 예측한 predicted value vector

$\hat{y}_i^{(t)}$는 $t$번째 round에서 예측한 $i$번째 instance의 predicted value이다. 

 

Example: How to split? use similarity score

각 data point마다 residual을 계산한다. (residual = true - predicted) 모든 residual을 leaf로 간주한다. 이때 $x$의 순서대로 정렬한다.

\[ \text{residuals} = \{ -10.5, 6.5, 7.5, -7.5 \} \]

similarity score를 계산한다. (왜 이렇게 계산하는지는 아래 math 부분에서 유도됨)

\[ \text{similarity score} = \cfrac{\sum (residuals)^2}{ \text{(# of residuals)} + \lambda} \]

$\lambda$는 regularization hyperparameter이다. 일단 idea의 흐름을 위해 $\lambda=0$이라 하자. 그러면

\[ \text{similarity score} = \cfrac{(-10.5 + 6.5 + 7.5 - 7.5)^2}{4+0} = 4 \]

이제 tree를 split하여 left/right child의 similarity score 역시 계산한다.

이때 얻은 (Similartiy) Gain은 $\text{Gain = Sim(Left) + Sim(Right) - Sim(Parent)}$이고, Gain이 가장 높은 $x$로 split한다.

만약 Gain < 0 이라면 더이상 split하지 않는다.

 

후보가 되는 split point는 (regression이므로) 각 $x$의 평균값이다. 즉 $[15, 22.5, 30]$이다.

$x<15$에서 split했을때 left, right의 similarity score는 각각 110.25, 14.08이고 Gain=11.25 + 11.08 - 4 = 120.33이다.

$x<22.5$에서 split했을 때 left, right의 similarity score는 각각 8, 0이므로 Gain=8+0-4=4

$x<30$에서 split했을 때 left, right의 similarity score는 각각 4.08, 56.25이므로 Gain=56.33이다.

따라서 $x<15$에서 split한다.

아래는 최종적으로 얻은 tree이다.

GBDT of example regression data (Stanford CS246)

Example: Prediction

각 leaf node마다 다음과 같이 계산한다. (위 그림에서 초록색 노드의 output)

\[ \text{Output} = \cfrac{\sum (residual)}{(\text{# of }residuals) + \lambda} \]

New prediction은 $\hat{y}^{(0)} + \eta \hat{y}^{(1)}$

$\eta$는 learning rate이고, defalut=0.3이다. 

 

$x=10$에서 예측한 값은 $0.5 + (0.3)(-10.5)=-2.65$

$x=20$에서 예측한 값은 $0.5 + (0.3)(7)=2.6$

$x=25$에서 예측한 값은 $0.5 + (0.3)(7)=2.6$

$x=30$에서 예측한 값은 $0.5 + (0.3)(-7.5)=-1.75$

 

$y=[-10, 7, 8, -7]$ 이므로 2nd round에서는 $residuals=[-7.35, 4.4, 5.4, -5.25]$를 이용하여 next tree를 만든다.

 

반응형

GBDT: Math

GBDT in math (Stanford CS246)

위 수식을 살펴보면 round-$t$에서의 prediction은 $\hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i)$ 이다.

그러므로 우리는 $f_t(\cdot)$를 결정하면 되고, 아래와 같이 loss가 가장 최소화하는 $f_t$를 찾으면 된다.

\[ \text{objective function} = \sum_i l(y_i,\ \hat{y}_i^{(t-1)}) + \Omega(f_t) \]

$\Omega(f_t)$: model complexity

 

Taylor expansion to approximate objective

테일러 전개식의 2차항까지 이용하면 다음과 같이 근사할 수 있다.

\[ g(x+\Delta) \approx g(x) + g'(x)\Delta + \frac{1}{2}g''(x)\Delta^2 \]

 

이를 이용하여 objective function을 근사하면 다음과 같다.

$f_t$를 최적화하는 것이므로 $l(y_i,\ \hat{y}_i^{(t-1)})$ 항은 무시한다.

The approximate objective (Stanford CS246)

Model Complexity

model complexity는 다음과 같이 정의한다.

\[ \Omega(f) = \gamma T + \cfrac{1}{2} \lambda \sum_{j}^{T}s_j^2 \]

$T$: tree $f$의 leaf 개수

$\gamma$: tree $f$에 leaf를 추가하는 비용

$w_j$: $j$번째 leaf의 output value

 

Re-write it by leaf

$i$는 data point의 index인데, objective function에서 leaf를 이용하기 위해 $j$로 바꾸자.

$i$번재 데이터 $x_i$가 속한 leaf index를 $j$라 하면 $I_j = \{ i | q(x_i)=j \}$라 정의하자.

Associated with leaf node $j$ (Stanford CS246)

Finding the Optimal $w_j^*$

$G_j = \sum_{i \in I_j} g_i,\ H_j = \sum_{i \in I_j}h_i$라 하자. 그러면

$ G_j w_j + \frac{1}{2} H_j w_j^2 $의 형태이고, 이는 $w_j$에 대한 2차식이다. 

중고등학교 이차함수의 최대/최소를 이용하면 우리는 위 식이 최소가 되는 값을 찾을 수 있다. 즉

\[  w_j^* = -\cfrac{G_j}{H_j + \lambda} \]

따라서 objective function은

\[ \text{objective} = -\cfrac{1}{2} \sum_{j=1}^{T} \cfrac{G_j^2}{H_j + \lambda} + \gamma T \]

Apply to Regression

Optimal $w_j^*$

먼저 Taylor expansion에서 사용되는 $g$와 $h$를 계산하면

$g_i = \partial_{\hat{y}^{(t-1)}}(\hat{y}^{(t-1)} - y_i)^2=2(\hat{y}^{)t-1)} - y_i)$

$h_i = \partial^2_{\hat{y}^{(t-1)}}(\hat{y}^{(t-1)} - y_i)^2=2$

 

따라서

Optimal $w_j^*$ in regression (Stanford CS246)

 

$w_j^*$를 바탕으로 objective function을 다시 구하면 다음과 같다.

Objective of regression (Stanford CS246)

Gain

Similarity Gain (Stanford CS246)

Summary: GBDT Algorithm

• 각 $t$-iteration(혹은 round)마다 새로운 tree $f_t(x)$를 추가한다.
  • 필요한 statistics를 계산한다.
  • $g_i = \partial_{\hat{y}^{(t-1)}} l(y_i, \hat{y}^{(t-1)})$
  • $h_i = \partial^2_{\hat{y}^{(t-1)}} l(y_i, \hat{y}^{(t-1)})$
• objective를 minimize하도록 greedy하게 tree grow
  • $\text{objective} = -\cfrac{1}{2} \sum_{j=1}^{T} \cfrac{G_j^2}{H_j + \lambda} + \gamma T$
• ensemble model에 $f_t(x)$를 더한다.
  • $y^{(t)} = y^{(t-1)} + \eta f_t(x_i)$
• $M$개의 ensemble tree를 만들때까지 반복한다.

 

XGBoost: eXtreme Gradient Boosting

regularization을 포함한 GBDT이며 매우 큰 데이터에도 적용가능하다.

Kaggle을 포함한 많은 competition과 다양한 문제에서 SOTA를 달성한다.

다음의 기능을 지원한다.

• Parallel tree comstruction: column block structure를 이용
• Distributed Computing: cluster of machine을 이용하여 매우 큰 모델도 학습
• Out-of-Core Computing: 메모리에 fit하지 않는 대용량 데이터셋