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

Gradient Boosting Machine(GBM)

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

 

$$\begin{array}{rl}{y}_1& =F_{prev}(x_1)+h(x_1)\\ y_2& =F_{prev}(x_2)+h(x_2)\\ & ⋮\\ y_n& =F_{prev}(x_n)+h(x_n)\\ \Rightarrow & F_{new}(x)=F_{prev}(x)+l\cdot h(x)\end{array}$$

위의 식과 그림처럼 이전 모델 $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 _{i=1}^n(y_i-F(x_i){)}^2$$

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

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

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

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

$$\begin{array}{rl}for& m=1toM:\\ & (1)re{s}_{im}=negativegradient=-[\frac{\partial L(y_i,F_{m-1}(x_i))}{\partial F_{m-1}(x_i)}]fori=1,\cdots n\\ & (2)잔차re{s}_{im}을새로운종속변수로하여기본학습기(결정트리)g_m학습\\ & g_m은(x_i,re{s}_{im})을통해학습한DecisionTree\\ & g_m은TerminalRegion{R}_{jm}(j=1,\cdots ,J_m)을가진다\\ & g_m=\underset{g}{\arg min}\sum _{i=1}^n(re{s}_{im}-g(x_i){)}^2\\ & (3)Constant{\gamma }_m계산\\ & forj=1,\cdots J_m:\\ & {\gamma }_{jm}=\underset{\gamma }{\arg min}\sum _{x\in R_{ij}}L(y_i,F_{m-1}(x_i)+\gamma )\\ & \Rightarrow {\gamma }_m=\underset{\gamma }{\arg min}\sum _{i=1}^{n}L(y_i,F_{m-1}(x_i)+\gamma g_m(x_i))\\ & (4)F_m(x)Update\\ & F_m(x)=F_{m-1}(x)+\nu \cdot {\gamma }_m\cdot g_m(x)\\ & \nu 는Overfitting방지를위한Learningrate\end{array}$$  

---

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인 데이터에 대한 예측