Greedy Function Approximation : A Gradient Boosting Machine

---

이번엔 Gradient Boosting(GB)의 시초인 Friedman의 2001년 논문 Greedy Function Approximation : A Gradient Boosting Machine을 읽고 정리해보았다.

 

- 목차 -

1. Function Estimation

2. Numerical Optimization in Function Space

3. Finite Data

4. Applications : Additive Modeling

5. Regularization

6. Simulation Studies

7. Tree Boosting

8. Interpretation

9. Real Data

10. Data Mining

---

---

본 포스팅에서는 수식을 포함하고 있습니다.

티스토리 피드에서는 수식이 제대로 표시되지 않을 수 있으니

PC 웹 브라우저 또는 모바일 웹 브라우저에서 보시기 바랍니다.

---

---

   1. Function Estimation

우리에게 데이터 $(y_i, x_i), i=1, \ldots, n$이 있다. 함수 추정에서는 랜덤 입력 벡터 $x$와 출력 변수 $y$의 관계를 나타내는 함수 $F^*$를 찾게 된다. 어떻게 찾느냐 하면 손실 함수 $L$에 대하여 기대 손실 함수를 최소화하는 함수를 찾게 된다. 즉,

$$\DeclareMathOperator*{\argminA}{arg\,min} F^* = \argminA_{F}E_{y, x}L(y, F(x)) = \argminA_{F}E_x[E_y(L(y, F(x)) | x] \tag{1}$$

이다. 함수 추정에서는 $F^*$를 유한한 데이터를 이용하여 찾기가 어려우므로 $F^*$를 잘 근사하는 $\hat{F}$을 찾게 된다.

 

자주 사용하는 손실 함수는 회귀 문제에서는 $(y-F)^2$ 또는 $|y-F|$를 주로 사용하고 분류 문제에서는 특히 2 분류문제에서는 이항 로그 우도 함수 $\log (1+e^{-2yF})$를 찾게 된다. 

 

공통적은 추정 과정은 함수 $F$를 유한한 모수를 갖는 함수들의 집합으로 제약한 뒤 이러한 집합 내에서 기대 손실 함수를 최소화하는 함수를 찾게 된다.

 

여기서는 다음과 같은 형태를 갖는 함수 집합을 고려한다.

$$F(x; \{\beta_m, a_m\}_{1}^M) = \sum_{m=1}^M\beta_m h(x ; a_m)\tag{2}$$

식 (2)는 함수 추정에서 다루는 핵심 클래스라고 한다. 신경망, Radial Basis Expansion, MARS, Wavelet 그리고 서포트 벡터 머신도 다 이런 형태라고 한다.

 

여기서 관심의 대상이 되는 $h$는 의사결정나무이고 $a_m$은 분리가 되는 변수와 분리값 그리고 끝마디의 $y$들의 평균이라고 생각하면 된다고 한다.

---

1.1 Numerical Optimization

(2)와 같은 함수를 찾는 문제는 함수 자체를 찾는 문제가 아닌 모수를 최적화하는 문제로 풀 수 있다.

1.2 Steepest-descent

최적화 문제로 풀기는 하지만 대부분의 경우 closed form으로 안 나와서 반복적인 업데이트를 통해 최적 모수를 찾게 된다. 이때 사용되는 것이 Steepest-descent 알고리즘이다.

---

   2. Numerical Optimization in Function Space

앞에서 모수가 포함된 함수 클래스를 얘기해놓고 여기서는 비모수적인 방법을 얘기한다. 즉, $F(x)$ 값 자체를 추정하는 문제 말이다.

 

이때 $F(x)$는 다음을 최소화하는 값으로 한다.

$$\phi(F(x)) = E_y[L(y, F(x))|x]$$

 

우리는 유한한 데이터를 이용하여 $F(x)$를 찾아야 한다. 이때 다음과 같은 테크닉은 구사한다.

먼저 초기값 $f_0(x)$를 잡아주고 우리가 찾고자 하는 $F(x)$에 점점 근접하는 $f$를 반복적으로 찾아내게 된다. 이때 반복수를 $M$이라 한다면 반복이 끝나고 나서 찾은 것은 $$F^*(x) = \sum_{m=0}^Mf_m(x)$$가 된다.

 

그렇다면 $f_m$을 어떻게 찾을 것인가? Steepest-Descent 방법을 사용한다. 즉,

$$f_m(x) = -\rho_m g_m(x)$$

여기서

$$\DeclareMathOperator*{\argminA}{arg\,min}  g_m(x) = \left[\frac{\partial \phi(F(x))}{\partial F(x)}\right]_{F(x)=F_{m-1}(x)} \\ \rho_m = \argminA_{\rho}E_{y, x}L(y, F_{m-1}(x)-\rho g_m(x))$$

---

   3. Finite Data

함수 추정하는 방법의 하나로 Greedy Stagewise 접근법이 있다. 

$$\DeclareMathOperator*{\argminA}{arg\,min} (b_m, a_m) = \argminA_{b, a}\sum_{i=1}^NL(y_i, F_{m-1}(x_i)+bh(x_i, ; a))\tag{9}$$

$$F_m(x) = F_{m-1}(x)+b_mh(x;a_m)\tag{10}$$

여기서 $h$를 weak learner 또는 base learner라 하며 보통 분류 나무가 된다.

 

우리에게 주어진 데이터는 유한하므로 앞에 Steepest-Descent에서 유도한 방향 $g_m$을 정확하게 계산할 수 없다. 따라서 주어진 데이터를 이용하여 차선책을 구해야 한다.

$$-g_m(x_i) = -\left[ \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} \right]_{F(x)=F_{m-1}(x)}$$

하지만 이는 $x_i$에서만 계산된 값이며 이 값들 이외의 $x$에 대해서는 계산할 수가 없다. 이를 해결하기 위해 $g_m(x_i)$을 잘 설명하는 $h(x_i; a_m)$을 구하게 된다. 이러한 $h$는 임의의 $x$에 대해서도 계산할 수 있는 것이다. 이렇게 임의의 $x$에 대하여 $h(x; a_m)$은 $g_m(x)$와 가장 근접한 값이라고 생각하는 것이다.

 

이렇게 정확한 $g_m(x)$를 계산하는 것이 아닌 $g_m(x_i)$를 잘 근사하는 $h(x;a_m)$을 찾게 됨으로써 함수 추정 문제가 굉장히 쉬워진다(물론 잃는 것도 있다). 

 

이러한 아이디어를 종합하여 Gradient Boosting 알고리즘이 다음과 같이 탄생하였다.

 

Algorithm 1.

1. $\DeclareMathOperator*{\argminA}{arg\,min} F_0(x)=\argminA_{\rho}\sum_{i=1}^nL(y_i, \rho)$

2. $m=1, \ldots, M$에 대하여

3. $\tilde{y}_i = -\left[ \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} \right]_{F(x)=F_{m-1}(x)}, i=1, \ldots, n$

4. $\DeclareMathOperator*{\argminA}{arg\,min} a_m=\argminA_{a, b}\sum_{i=1}^n(\tilde{y}_i-bh(x_i;a_m))^2$

5. $\rho_m = \argminA_{\rho}E_{y, x}L(y, F_{m-1}(x)+\rho h(x_i;a_m))$

6. $F_m(x) = F_{m-1}(x)+\rho_mh(x;a_m)$

 

---

   4. Applications : Additive Modeling

여기서는 여러 손실 함수와 여러 $h$ 대한 Gradient Boosting 알고리즘을 소개한다. 여기서 $h$가 회귀 나무인 경우에 대하여 제곱 손실과 절대값 손실을 이용한 방법을 소개하는데 각각의 장점을 소개한다.

절대값 손실을 이용한 방법은 이상치의 강하며 제곱손실의 경우는 분리기준을 더 빨리 찾을 수 있다고 한다.

 

절대값 손실의 이상치 강함은 알겠는데 제곱 손실이 절댓값 손실보다 분리기준을 더 빨리 찾는 건 잘 모르겠다.

---

   5. Regularization

여기에서는 Gradient Boosting의 단점이라 할 수 있는 과적합을 방지하는 방법을 알아본다.

 

과적합을 방지하는 것 중 하나가 바로 반복수 $M$이다. 보통 수렴 조건을 사용하여 알고리즘을 종료하지만 이렇게 되면 과적합이 될 수 있으므로 반복수 $M$을 정해두는 것이다. 이는 교차검증을 통해서 적절한 값을 선택한다.

 

또한 $\nu$를 이용하여 6단계를 다음과 같이 변형하는 방법도 있다.

$$F_m(x) = F_{m-1}(x)+\nu\rho_mh(x;a_m), \;\;0<\nu\leq 1$$

이는 잔차의 스케일을 줄여서 데이터에 너무 휩쓸리지 않게 하는 조치이다.

 

$\nu$ 또한 교차검증을 이용하여 선택할 수 있다. 일반적으로 $\nu$가 작아질수록 최적 $M$은 커지는 관계에 있다. 저자는 이러한 관계를 보고자 모의실험을 진행했다.

 

모의실험에서 $\nu$가 작아질수록 성능이 좋았고 커질수록 과적합으로 인하여 성능이 안 좋아졌음을 보였다.

 

L2 TreeBoost에 대해서는 로그 우도 함수와 오분류율을 성능의 척도로 하여 비교실험을 했다. 이때 고르 우도 함수는 최적 반복수를 지나서 성능이 안 좋아진 반면 오분류율은 계속해서 성능이 향상되었다. 오분류율은 오직 의사결정 함수의 부호에만 의존하므로 로그 우도 함수보다 과적합의 덜 영향을 받는다고 한다.

 

저자는 $\nu$가 작아질수록 성능이 좋아지는 것에 대해서는 불명확하다고 했다. 

내용

---

   6. Simulation Studies

함수 추정을 할 때에는 여러 가지 가정을 하게 된다. 데이터 개수 $N$을 미리 알고 있고 때로는 오차항의 분포 또한 알고 있다고 한다. 대개의 경우 $F$는 모른다고 가정하게 된다. 

 

어떤 추정법을 평가할 때에는 여러 가지 상황에 대해서 실험해야한다. 이때 여러가지 상황을 일반화하여 흉내 낼 수 있는 몬테카를로 방법을 많이 사용한다고 한다. 그래서 여기에서도 사용하려나 보다.

 

여기에서 중점적으로 다루는 것은 현실을 최대한 잘 반영하는 모의실험 도구와 실험 결과의 소개인 것이다.

6.1 Random Function Generator

보통 모의실험에서는 여러 상황에서 트루 함수를 어떻게 잡느냐가 중요하다. 여기서는 저자가 Gradient Boosting 알고리즘 실험을 위해 트루 함수를 어떤 구조로 설정하고 어떻게 생성하는지에 대해서 설명한다. 이렇게 해서 여러 가지 상황에 따른 현실적인 데이터를 생성하고 싶었나 보다.

 

여기에서 다루는 Random Function의 입력 변수 벡터 차원은 10이라고 했다. 현실세계에서는 이보다 더 많은 변수들이 있지만 저자는 대부분의 변수들은 서로 간 상관관계가 있어서 본질적인 차원(Intrinsic Dimensionality)은 낮기 때문에 모의실험에서 사용하는 입력 변수 벡터 차원의 크기가 작아도 상관없다는 듯이 얘기하고 있다.

6.2 Error Distribution

여기서는 랜덤 함수 생성기를 통하여 $F^*$를 생성하고 적절한 오차항 $\epsilon$에 대하여 다음과 같이 학습 데이터를 생성한다.

$$y_i = F^*(x_i)+\epsilon_i$$

그리고 2가지 오차항에 대한 분포를 가정하여 실험을 진행한다. 

 

실험 결과 Huber Loss를 이용한 M treeBoost가 좋다고 한다. 아마도 Huber Loss가 이상치에 강건하여 그런 듯하다. 이유는 정확히 나와있지 않았다.

6.3 LS_TreeBoost vs MARS

회귀 문제를 다루는 GB와 다른 모형의 성능을 비교 실험한다.

 

Gradient Boosting으로 얻은 최종 모형은 결국 piecewise constant 모형이다. 이러한 특징 때문에 트루 함수가 연속이고 스무스한 경우라면 이러한 Gradient Boosting 알고리즘으로 얻은 모형은 좋지 못할 것이다. 따라서 연속이고 스무스한 함수를 잘 근사하는 MARS와 GB에서 손실 함수를 제곱 손실로 사용한 LS Tree Boost와 비교하는 실험을 한다. 왜냐하면 MARS도 기본적으로 최소제곱을 이용하여 적합을 하기 때문에 LS Tree Boost와 비교하는 것이다.

 

실험은 오차의 절대값과 제곱 오차 두 가지를 측도로 하여 성능을 평가했다. 오차 절대값에 대해서는 어떤 트루 함수에 대해서는 MARS가 더 좋기도 하고 더 나쁘기도 했다. ㄷㄷ;;

 

하지만 제곱 오차에 대해서는 일반적으로 LS Tree Boost의 성능이 더 좋았다. 특히 LS Tree Boost는 너무 큰 오차나 너무 작은 오차의 빈도가 작았다. 너무 작은 오차의 빈도가 작은 이유는 LS Tree Boost의 piecewise constant 한 성질로 인해 매우 스무스한 함수를 더 근접하게 근사하지 못해서 그렇다고 저자는 보고 있다.

 

이를 통해 piecewise constant 모형이 갖는 단점이 그렇게 치명적이지 않다는 것을 보여주었다.

6.4 Lk_TreeBoost vs K-class LogitBoost and AdaBoost.MH.

분류 문제를 다루는 GB와 다른 모형의 성능을 비교 실험한다.

 

GB를 K 클래스 분류에 적용한 Lk_TreeBoost가 K-class LogitBoost and AdaBoost.MH. 보다 좋았다. 하지만 축소 모수 $\nu$를 사용하니까 성능이 서로 비슷해졌다. 축소 모수의 중요성을 실감하는 순간이었다.

---

   7. Tree Boosting

여기서는 $M, \nu$외에도 끝마디 개수 $J$에 대한 이야기를 하고자 한다. 즉, 최적 끝마디 개수에 대해서 이야기하려는 것이다.

 

최적 끝마디 개수는 트루 함수의 구조에 따라 달라진다고 한다. 소위 주된 교호항(Interaction Term)의 차수에 따라 달라진다는 것이다.

 

회귀 부스팅에서는 교호 항의 차수를 개별 트리의 끝마디 개수를 가지고 컨트롤할 수 있다. 최적 끝마디 개수는 교차 검증 또는 OOB(Out of Bag)을 이용하여 얻을 수 있다고 한다. 저자는 개별 트리의 사이즈(끝마디 개수)가 커야 할 필요는 없다고 추측했다.

 

모의실험 결과 6~11 정도의 사이즈가 가장 좋았다고 한다.

---

   8. Interpretation

여기에서는 GB 알고리즘을 통해 얻은 모형 $\hat{F}(x)$의 해석에 관한 내용을 다룬다. 그 내용은 $\hat{F}(x)$ 변동에 가장 강한 영향을 미치는 인자와 이러한 인자에 대해서 $\hat{F}(x)$이 어떻게 변하는지 확인하는 것을 포함된다.

8.1 Relative Importance of Input Variables

여기서는 Relative Importance의 정의를 소개하고 모의실험 결과를 알려준다. 사실 잘 모르겠다. ㄷㄷ;;

8.2 Partial Dependence Plots

여기서는 입력 변수 벡터에서 한 원소에 대한 $\hat{F}(x)$의 변화를 시각화하는 것에 대하여 소개한다.

 

특히 입력 변수 벡터를 두 배타적인 집합으로 쪼개서 하나를 고정시켜놓고 나머지 입력 변수 집합에 대해서 $\hat{F}(x)$의 변화를 나타내는 방법도 소개한다.

 

특히 나무 기반 모형에서 특정 입력 변수 집합에 대한 Partial Dependence를 계산하는 방법도 써놓았다.

8.3 Randomly Generated Function

여기에서는 앞의 2 섹션에 대한 실험을 진행한다.

---

   9. Real Data

여기서는 GB를 실제 데이터에 적용하고 그 결과를 소개한다.

---

   10. Data Mining

Tree Boost 과정은 되게 강건하다. 여기서 다룬 모든 Tree Boost는 단조 증가 변환에 대해서 불변하다. 따라서 이러한 단조 증가 변수 변환을 생각하지 않아도 된다. 이에 따라 이상치에 대하여 덜 민감하게 된다(왜냐하면 결국 크기 순으로 매핑하는 변환을 생각하면 이상치가 크든 작든 결과는 똑같을 것이다). 트리 기반 모형은 결측치를 우아하면서 통합된 방법으로 다룰 수 있다고 한다.

 

하나의 의사결정나무는 많은 단점을 갖고 있다. 일단 예측력, 즉 정확도가 안좋다. 이는 piecewise constant로 인해 어찌보면 당연하다. 특히 사이즈가 작은 나무는 불안정하다. 반대로 사이즈가 큰 나무는 고차 교호항에 의해 정확도가 떨어질 수 있다고 한다(이 부분은 잘 모르겠다). 

 

하지만 GB는 이러한 단점을 완화한다. 불안정함은 여러 나무의 평균을 취함으로써 해결하고 고차 교호항은 나무 사이즈 조절을 통해 통제할 수 있다고 한다.

 

하나의 의사결정나무는 해석이 용이하다. 하지만 Tree Boosting은 해석이 어렵다. Tree Boosting 해석의 어려움은 Partial Dependence Plot으로 어느 정도 극복할 수 있다고 한다.

 

이 외에도 계산량과 축소 모수(Shrinkage Parameter) $\nu$와 반복수 $M$에 대한 관계와 계산량 문제 등을 다루며 논문이 마무리된다.

---