Gradient Boosting

Gradient Boosting

Gradient (혹은 Residual) 을 이용해 이전 모델의 약점을 보완하는 새로운 모델을 순차적으로 적합한 뒤, 이들을 선형 (linear) ㄱㄹ합하여 얻어진 모형을 생성하는 지도 학습 알고리즘.

최선의 greadient (residual) 로 얻어진 모델을 쓰는게 최대 전투력 아닌가?

1. Gradient Boosting 은 Residual 을 이용해 이전 모델의 약점을 보완한다.

$(x_i,y_i),i=1\sim n$. $x_i$ 는 $p$ 차원 vector, $y_i\in \mathbb{R}$ (범주형은 정수, integer 로 표현될 수 있으므로 여기에 포함된다.)

이전 모델 (예측 함수) 를 $F_{prev}$ 라 하고 개별 입력 변수 $x_i$ 에 대한 예측값을 $F_{prev}(x_i)$ 라 하자. 이전 모델의 약점이란 무엇인가? 이전 모델이 실제값 $y_i$ 를 정확하게 예측하지 못한 정도 (강도), 즉 실제값과 예측값 사이의 오차의 합 정도라고 생각하면 된다. 즉, 예측값과 실제값의 차이가 커지면 이전 모델의 약점은 치명적 critical 이 된다는 것이다. 이때 떠올리자, 예측값의 실제값의 차이 $=$ residual 이라는 걸.

이전모델의 약점을 보완하는 것이 Gradient Boosting. 그렇다면 어떻게 보완한다는 것인가? 이는 곧 실제값과 예측값의 차이 (residual) 을 줄여주는 함수 function $h$ 를 찾는 것에 의해 이루어짐. 즉

$$\begin{gathered} y_1=F_{prev}(x_1)+h(x_1) \\ \dots \\ {y}_n=F_{prev}(x_n)+h(x_n) \\ \Rightarrow y_{new}=F_{new}(\mathbf{x})+l\ast h(\mathbf{x}),0<l<1 \end{gathered}$$

즉, $h(\mathbf{x})$ $h(x)$ (자 체로 vector가 맞는거야 아닌거야) 를 그대로 더하는 것이 아니라 constant $l$ 을 곱하여 더하게 된다. 이 $l$ 을 학습률 (Learning-rate) 라고 하며, 이는 경사하강법 (Gradient Descent Algorithm) 에서 파라미터를 업데이트하는 정도를 조절하기 위한 변수 (패러미터) 가 된다. $l$ 을 곱해주지 않으면 학습 데이터에 지나치게 적합되므로 과적합 (오버피팅) 현상이 발생하게 된다. 따라서 $l$ 을 곱해주어 오버피팅을 방지한다.

아래에서 이전 모델의 예측값을 빨간 선이라고 하자 (좌측 상단). 그러고 나서 실제값과 예측값의 차이를 줄여주는 $h$ 를 학습하게 된다 (우측 상단). 이러고 나서 새로운 예측값을 그냥 깡으로 $F_{prev}(x)+h(x)$ 로 설정할 수도 있다 (우측 하단) 하지만 이 경우 학습 데이터에 과도하게 적합해버릴 수 있기 때문에 (오버피팅) residual (잔차) 를 많이 줄이는 대신 학습률 $l$ 을 $h(x)$ 에 곱한 값을 이전 모형의 예측값에 더하여 새로운 예측값 $F_{new}(x)=F_{prev}(x)+l\ast h(x)$ 을 얻게 된다. (좌측 하단 그림) (잔차를 많이 줄이는 대신 = $l$ 을 1로 설정한다는 이야기와 동일하며, 잔차 감소량을 줄인다고 해도 일단 이전 모형보다 잔차는 이미 작아졌다. $l$ 이 0일 일은 없으므로.)

딥러닝 도식

그렇다면 최적 $h$ 를 어떻게 찾을까? 이는 뒤에서 설명한다.

1. Gradient Boosting 은 순차적으로 적합한 뒤, 이들을 선형 결합한 모델을 생성한다.

1단계에서 Gradient Boosting 은 순차적으로 이전 모델의 약점을 보완하는 모델을 만들게 된다. 순차적으로 적합할 모델 개수를 $m$ 개라 하자. 첫번째 (시작) 모델의 예측값을 $F_0(x)=h_0(x)$ 라 하면 최종 모형 $F_m$ 은 다음과 같이 $h_j$ 들의 선형 결합으로 만들어진다.

$$\begin{array}{rl}{F}_m(X)& =h_0(X)+l\ast h_1(X)+\cdots +l{h}_m(x)\\ & =h_0(X)+l\ast (h_1(X)+\cdots +h_m(x))\end{array}$$

1. Gradient Boosting 은 지도학습 알고리즘이다.

Gradient Boosting 은 라벨 (또는 종속변수가) 있는 데이터를 학습하고, 이를 통해 새로운 데이터의 라벨 (또는 종속변수) 를 예측하는 지도학습 알고리즘이다.

1. 알고리즘
2. 초기 모형은 constant 로 설정하여 다음과 같이 찾는다.

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

3. $m=1\sim M$ 에 대하여 (a)~(d) 를 반복한다.

(a) 다음과 같이 유사 잔차 (Pseudo Residual) $r_{im}$ 를 계산한다.

\partial F(x_i) } \right]_{F(x)=F_{m-1}(x)} , i=1\sim n $$ (b) 앞에서 구한 residual 을 새로운 종속변수로 하여 **기본 학습기 (Base Learner, (ex) 의사결정나무)** $g_m$ 을 학습한다. 즉, $(x_i , r_{im}) , i = 1 \sim m$ 을 이용해 학습하게 된다. (c) 상수 $\gamma_m$ 을 다음과 같이 계산한다. $$ \gamma_m = \arg \min_\gamma \sum_{i=1}^n L\Big (y_i , \, F_{m-1} (x_i) + \gamma * g_m (x_i)\Big ) $$ (d) 모형을 업데이트한다. $$ F_m(x) = F_{m-1}(x)+ l*\gamma_m * g_m(x) $$ 1. 최종 모형은 다음과 같다. $$ F_M (X) $$