[ML][Ensemble]Gradient Boosting Machine(GBM)

Gradient Boosting Machine(GBM)

Residual(잔차, $y_i - \hat{f}(x_i)$)($\approx$ Negative Gradient)를 이용하여 이전 모델의 약점을 보완하는 새로운 모형을 순차적으로 Fitting한 뒤 이들을 선형결합하여 얻어진 모델을 생성하는 지도학습 알고리즘

 

$$
\begin{aligned}
y_1 &= F_{prev}(x_1) + h(x_1)\\
y_2 &= F_{prev}(x_2) + h(x_2)\\
&\qquad\qquad \vdots \\
y_n &= F_{prev}(x_n) + h(x_n)\\
\Rightarrow &F_{new}(x) = F_{prev}(x) + l \cdot h(x)
\end{aligned}
$$

위의 식과 그림처럼 이전 모델 $F_{prev}(x)$와 잔차를 줄여주는 함수 $h(x)$를 통해 모델을 학습한다

---

※ Residual $\approx$ Negative Gradient

GBM의 Loss Function으로는 미분이 가능한 MAE(L1 Loss), MSE(L2 Loss), Logistic Loss를 사용한다

여기서 Residual은 단순한 잔차의 의미뿐만 아니라, Negative Gradient와도 의미가 같은데, 잔차를 단순히 잔차로만 생각하지 않고 다양한 Loss Function의 Negative Gradient를 통해 Residual을 정의할 수 있다

$$
Gradient =\frac{\partial L}{\partial \hat{f}(x_i)} = \frac{\partial (y_i - \hat{f}(x_i))^2 }{\partial \hat{f}(x_i)} = \hat{f}(x_i) - y_i = -Residual
$$ 

---

알고리즘

Loss Function : MSE Loss로 가정

$$L(y_i, F(x)) = \frac{1}{n} \sum \limits_{i=1}^{n}(y_i - F(x_i))^2$$

Step 1 : 초기 모형은 상수로 설정(하나의 Leaf Node)

$$F_0(x) = \underset{\gamma}{\arg\min} \sum \limits_{i=1}^{n} L(y_i, \gamma)$$

여기서 $\gamma$는 이전 모델의 Residual을 최소화하는 Decision Tree이다

Step 2 : Residual 계산 $\rightarrow$ Next Tree를 m번 생성

$$
\begin{aligned}
for\;&m=1\;to\;M:\\
&(1)\; res_{im} = negative\;gradient = -\big[ \frac{\partial L(y_i, F_{m-1}(x_i))}{\partial F_{m-1} (x_i)} \big]\; for\;i=1,\cdots n\\
&(2) 잔차\;res_{im}을\;새로운\;종속변수로\;하여\;기본\;학습기(결정트리)\;g_m\;학습\\
&\qquad g_m은\; (x_i, res_{im})을\;통해\; 학습한 Decision\;Tree\;\\
&\qquad g_m은\;Terminal\;Region\;R_{jm}\;(j=1,\cdots,J_m)\;을\;가진다\\
&\qquad g_m = \underset{g}{\arg\min} \sum \limits_{i=1}^{n} (res_{im} - g(x_i))^2\\
&(3) Constant\;\gamma_m\;계산\\
&\qquad for\;j=1,\cdots J_m:\\
&\qquad \qquad \gamma_{jm} = \underset{\gamma}{\arg\min} \sum \limits_{x \in R_{ij}}L(y_i, F_{m-1}(x_i) + \gamma)\\
&\qquad \Rightarrow \gamma_m = \underset{\gamma}{\arg\min} \sum \limits_{i=1}^{n} L(y_i, F_{m-1}(x_i) + \gamma g_m(x_i))\\
&(4) F_m(x)\;Update\\
&\qquad F_m(x) = F_{m-1} (x) + \nu \cdot \gamma_m \cdot g_m(x)\\
&\qquad \nu는\;Overfitting\;방지를\;위한\;Learning\;rate\\
\end{aligned}
$$  

---

Example

데이터

Step 1 : 초기 모델은 상수로 설정

Step 2 : $m=1, \cdots M$번 반복

우선 $g_m(g_1)$을 학습하기 위한 $res_{im}(res_{i1})$을 구한다

 

$g_1$ 학습(여기서 Decision Tree를 학습하는 과정을 모두 보여주기는 어려워 간단한 Decision Tree 정의)

 

상수 $\gamma_{j1}$ 계산

모델 업데이트

 

연 독서량 = 13, 하루 컴퓨터 사용량 = 2인 데이터에 대한 예측