Gradient Boosting Machine (GBM)
04_6 : Ensemble Learning : Gradient Boosting Machine (GBM)
이번 글에서는 Boosting 방법 중 하나인 Gradient Boosting Machine (GBM)을 알아보도록 하자. GBM에서 파생된 많은 Boosting 알고리즘들이 있다. 예를들어, XGBoost, LightGBM, CatBoost가 있는데, 이후 포스팅 할 글들을 통해 천천히 알아보도록 하자.
Gradient Boosting 이란?
Gradient Boosting = Gradient Descent + Boosting
Ada Boost 방법의 경우, 이전 base(weak) learner가 잘 분류/반영하지 못했던 단점(point들)을 다음 data sampling과정에서 high-weight를 주는 방법으로 성능을 개선하였다.
Gradient Boost 방법의 경우, 이름처럼 이전 base learner의 단점을 gradient로 나타내고, 이를 통해 Loss function이 최소가 되는 방향으로 base learner들의 학습을 진행해 나간다.
Gradient Boosting 또한 Regression, Classification, Ranking 모든 경우에 적용 가능하지만, Loss function 미분을 정의하기 어려운 순서대로 Regression<Regression<Ranking 순으로 이해가 더 어렵다. 우선 가장 직관적으로 이해하기 쉬운 Regression을 예시로 생각해보자.
- Motivation (for Regression problem)
$$the\;predicted\;value\;:\;\; \hat{y}_i = f_1(x)$$
$$residual\;:\;\;y-f_1(x)$$
이때 GBM의 아이디어는 다음 base learner로 하여금 residual을 예측하도록 하고, 계속해서 이 과정을 수행해 나가면 오차를 점점 줄일 수 있으리라고 기대한다.
예를들어, $f_2(x) = y-f_1(x)$ 로 $f_2$ 함수가 residual을 예측했다면, 추정함수는 아래와 같을 것이다.
$$y = f_1(x) + f_2(x)$$
다음 예시가 좀더 직관적인 예시일 것이다.
$$\hat{y} = f_1(x)$$
다음으로 residual을 예측하는 함수 $f_2$는 다음과 같이 정의될 것이다.
$$\hat{y} - f_1(x) = f_2(x)$$
더 나아가 $f_2$의 residual을 예측하는 함수 $f_3$는 다음과 같을 것이다.
$$\hat{y} - f_1(x) - f_2(x) = f_3(x)$$
계속해서 residual이 일정 이하로 줄어들거나, 원하는 base learner의 수에 도달할 때 까지 이 과정은 반복된다.
Gradient ?
그렇다면 왜 이 과정이 Gradient descent와 관련이 있는지 알아보자.
우리가 $M$번의 boosting 과정을 진행한다고 할 때, 학습 과정중인 imperfect model $F_m$은 아래와 같이 정의된다.
$$F_{m+1}(x) = F_m(x) + h_m(x) = y\;\;\;\;\;\;(1\leq m \leq M)$$
$$h_m(x) = y-F_m(x)$$
$h_m$ 함수는 $m$번째 residual을 예측하는 weak(base) learner이다.
Loss function으로 Mean Squared Error를 사용한다고 가정하고, 미분해보자.
$$L_{MSE} = \frac{1}{2} (y-F(x))^2$$
$$\frac{\partial L_{MSE}}{\partial F} = F(x) - y$$
$$h_m(x) = y -F(x) = - \frac{\partial L_{MSE}}{\partial F}$$
놀랍게도 residual 값이 Loss function의 미분값에 $-$를 취한 것과 동일하다.
다시말해 residual을 예측하도록 $h_m$을 학습하는 것이, Gradient descent 과정에서 기울기의 반대방향으로 점점 수렴하게 하는 것과 동일한 동작을 수행한다.
이제 좀 더 자세하게 구조적 위험 최소화 관점에서 어떻게 수식이 도출되는지 살펴보자.
Algorithm
$$\widehat{F} = arg\; \min_F \mathbb{E}_{x,y} \big[ L(y,F(x)) \big]$$
알고리즘의 목표는 Loss function $L$의 기대값을 최소화 하는 함수 $F$를 찾는 것이다.
함수 집합 $\mathcal{H}$에 속하는 여러개의 weak learner $h_i$를 사용하여 함수 $F$를 구성할 것이다.
$$\widehat{F} = \sum_{i=1}^M \gamma_i h_i(x) + const\;\;\;\;\;\; h_i \in \mathcal{H}$$
구조적 위험 최소화 관점에서 이 방법은 Loss function의 평균을 최소화 하는 추정 함수 $\widehat{F}$를 찾고자 한다. 우선 Greedy(탐욕법)한 방법으로 model의 처음 base learner를 생성하자.
$$F_0(x) = arg \min_\gamma \sum_{i=1}^n L(y_i,\gamma)$$
$\gamma$는 초기값으로 선택하는 적당한 상수이다. 이후 알고리즘이 찾을 $F_m$은 아래와 같이 정의된다.
$$F_m(x) = F_{m-1}(x) + arg\;\min_{h_m\in \mathcal{H}} \bigg[ \sum_{i=1}^n L(y_i, F_{m-1} (x_i) + h_m(x_i)) \bigg]$$
여기서 $h_i$가 $i$번째 weak(base) learner이다. 수식을 살펴보면 $L(y_i, F_{m-1} (x_i) + h_m(x_i))$는 $y_i-F_{m-1}(x_i)$를 추정하는 함수 $h_m(x_i)$에 대한 loss function $L(y_i- F_{m-1} (x_i) ,h_m(x_i))$과 동일하다.
여기서 문제가 있다. 수식적으로는 임의의 함수 집합 $\mathcal{H}$에서 최선의 $h_i$를 선택할 수 있지만, Computation관점에서 실제 구현은 불가능에 가깝다. 여기서 등장하는 아이디어가 Gradient Descent이다. 우리가 $\mathcal{H}$를 $\mathbb{R}$상에서 미분 가능한 함수 집합이라 가정하면, 아래와 같이 수식을 간략화 할 수 있다.
$$F_m(x) = F_{m-1}(x) - \gamma_m \sum_{i=1}^n \nabla_{F_{m-1}} L(y_i,F_{m-1}(x_i))$$
$$\bigg(\nabla_{F_{m-1}} L(y_i,F_{m-1}(x_i)) = \frac{\partial L(y_i,F_{m-1}(x_i))}{\partial F_{m-1}(x_i)} \bigg)$$
$$\gamma_m = arg\;\min_\gamma \sum_{i=1}^n L\big(y_i,F_{m-1}(x) - \gamma \nabla_{F_{m-1}} L(y_i,F_{m-1}(x_i))\big)$$
$\gamma_m$은 각 step의 length를 결정한다. 위의 과정을 $M$회 진행하여 $\widehat{F}$를 최적화 하는 것이다.
여기서 주의할 점은 유한한 함수 집합 $\mathcal{H}$에서 적합한 함수를 line search와 같은 방법으로 휴리스틱하게 찾아서 선택하기 때문에 주어진 문제에 대한 최적해를 찾는다고 보장하지 못한다는 점이다.
Pseudo-code로 알고리즘의 진행과정을 다시 살펴보자. (위에서 말로 풀어 쓴 것을 단계별로 적은 것임으로 따로 설명을 추가하지는 않았다)
1. Initialize model with a constant value :
$$F_0(x) = arg\;\min_\gamma \sum_{i=1}^n L(y_i,\gamma)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$$
2. For $m=1$ to $M$ :
(a) Compute so-called pseudo-residuals:
$$r_{im} = -\bigg[ \frac{\partial L(y_i,F(x_i))}{\partial F(x_i)} \bigg]_{F(x) = F_{m-1}\,(x)}\;\;\;for\;i = 1,\cdots,n$$
(b) Fit a base learner (or weak learner, e.g. tree)
$h_{m}(x)$ to pseudo-residuals, i.e. train it using the training set $\{(x_i,r_{im})\}_{i=1}^n$
(c) Compute multiplier $\gamma_m$ by solving the following one-dimensional optimization problem :
$$\gamma_m = arg\;\min\sum_{i=1}^nL(y_i,F_{m-1}(x) - \gamma h_m(x))$$
(d) Update the model :
$$F_m(x) = F_{m-1}(x) + \gamma_m h_m(x)$$
3. Output $F_M(x)$
Loss function
Gradient Boosting 알고리즘은 어떤 Loss function을 사용하는지에 따라서 성능이 많이 변한다.
Regression에 주로 사용되는 Loss function들은 아래와 같다.
Overfitting problem in GBM
GBM이 가지는 문제 중 하나가 Overfitting의 위험성이 크다는 점이다. 주어진 Original data의 noise까지 residual로 간주하고 모델이 외워버리는 문제가 발생할 수 있다.
이를 방지하기 위한 Regularization 방법들을 알아보자.
- Subsampling
일반화를 위해서 학습의 각 단계마다 random하게 original data의 일정 부분을 사용하지 않는 방법이다. 예를들어 80%만을 사용하겠다고 하면, 매 iteration마다 original data 중 80%를 subsampling하여 학습에 사용한다.
- Shrinkage
Aggregation과정에서 $\hat{F} = F_1 + F_2 + \cdots + F_M$을 사용한다면, 각 모델에 대한 가중치가 1이다. 하지만 Overfitting을 방지하기 위해서 나중에 만들어진 base learner일수록 영향력이 줄어들도록 shrinkage factor를 곱해준다. 위에서 살펴보았던 알고리즘에 적용해보면
learning rate $\nu\Rightarrow$ ($F_m(x) = F_{m-1}(x) + \nu \cdot \gamma_m h_m(x)$, $0<\nu\leq 1$)
- Early Stopping
Neural Network에서 자주 사용되는 방법 중 하나로, Validation Error를 계속 측정하다가, 증가하기 시작하면 학습을 멈춰버리는 방법이다.
Tree Based Gradient Boosting
Decision tree를 base learner로 사용하여 GBM을 사용하는 경우에 대하여 알아보자.
우선 residual에 대하여 m 번째 step에서 학습되는 하나의 decision tree는 아래와 같이 정의된다.
$$h_m(x) = \sum_{j=1}^{J_m} b_{jm} \textbf{1}_{R_{jm}}(x)$$
하나의 decision tree는 주어진 input data를 $J_m$개의 영역로 분할한다. 분할된 각 영역을 $R_{im}$이라고 하고, 이때 그 영역에 속하는 label 값을 $b_{jm}$이라고 한다. 그리고 $\textbf{1}_{R_{jm}}$ 함수가 생소할텐데, 이는 Indicator function으로 아래와 같이 정의된다.
$$\textbf{1}_A\;:\;X\rightarrow \{0,1\},\;\;\;\;\textbf{1}_{A}(x):={\begin{cases}1~&{\text{ if }}~x\in A~,\\0~&{\text{ if }}~x\notin A~.\end{cases}}$$
이제 $h_m$이 어떤 뜻인지 이해가 될 것이다. 각 영역별로 split된 후 해당 영역에 속하는 원소들이 가지는 값들을 합산한 것이다.
이제 다음 단계의 $F_m$을 정의해보자.
$$F_m(x) = F_{m-1}(x) + \gamma_m h_m(x)$$
$$\gamma_m = arg\;\min_\gamma \sum_{i=1}^n L(y_i,F_{m-1}(x_i) + \gamma h_m(x_i))$$
여기서 Friedman은 하나의 decision tree마다 지정되는 $\gamma_m$을 하나의 decision tree 안에서 영역 $R_{jm}$마다 하나씩 정해주자고 제안하였다. 이렇게 한다면 $\gamma_{jm}$이 $b_{jm}$까지 포괄하도록 하여, 식을 더 단순하게 만들 수 있다. ($h_m$을 대입해보면 수식 이해가 쉽다)
$$F_m(x) = F_{m-1}(x) + \sum_{j=1}^{J_m} \gamma_{jm} \textbf{1}_{R_{jm}}(x)$$
$$\gamma_{jm} = arg\;\min_\gamma \sum_{x_i\in R_{jm}} L(y_i,F_{m-1}(x_i) + \gamma)$$
Pseudo-code로 알고리즘의 진행과정을 한번 살펴보자.
1. Initialize model with a constant value :
$$F_0(x) = arg\;\min_\gamma \sum_{i=1}^n L(y_i,\gamma)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$$
2. For $m=1$ to $M$ :
(a) Compute so-called pseudo-residuals:
$$g_{im} = -\bigg[ \frac{\partial L(y_i,F(x_i))}{\partial F(x_i)} \bigg]_{F(x) = F_{m-1}\,(x)}\;\;\;for\;i = 1,\cdots,n$$
(b) Fit a regression tree to the targets $g_{im}$ giving terminal regions $R_{jm}$ ($j=1,\cdots,J_m$)
(c) For $j = 1,\cdots,J_m$, compute :
$$\gamma_{jm} = arg\;\min_\gamma \sum_{x_i\in R_{jm}} L(y_i,F_{m-1}(x_i) + \gamma)$$
(d) Update the model :
$$F_m(x) = F_{m-1}(x) + \sum_{j=1}^{J_m} \gamma_{jm} \textbf{1}_{R_{jm}}(x)$$
3. Output $F_M(x)$
Variable Importance (in Tree Based Gradient Boosting)
위와 같이 Tree를 기반으로 Gradient Boosting을 사용할 수 있다. 이때 Random Forest 처럼 각 변수의 중요도를 판단할 수 있다!
먼저 하나의 Tree에 대하여 $j$번째 변수의 중요도 $Influence_j(T)$는 아래와 같이 정의된다.
$$Influence_j(T) = \sum_{i=1}^{L-1} (IG_i \times \textbf{1}(S_i = j))$$
Tree의 종단(leaf/terminal) 노드가 $L$개라고 할 때, $L-1$번의 split이 이루어진다. 각 split과정에 대하여 얻어지는 Information Gain을 $IG_i$라고 하고, $\textbf{1}(S_i = j)$ 함수는 i번째 split에서 j번째 변수를 사용했다면 1을, 사용하지 않았다면 0을 반환하는 함수이다.
이때 Variable Importance는 아래와 같이 정의된다.
$$Influence_j = \frac{1}{M}\sum_{k=1}^M Influence_j(T_k)$$
Random Forest보다 변수의 중요도를 쉽게 계산이 가능하다.
이번 글을 작성하기 위해서 공부하는 과정에서 위키피디아가 많은 도움이 되었다. 정리가 잘 되어있으니, 참고해서 공부해보자! (링크)
※ 이 글은 고려대학교 산업경영공학과 강필성 교수님의 IME654 강의를 정리하고, 공부한 내용을 추가하여 작성되었습니다.
댓글
댓글 쓰기