A Step by Step Gradient Boosting Decision Tree Example
결정 트리(decision tree)의 도입은 주로 투명한 결정에 기초한다. 또한 ML 연구 적용에서 압도적으로 성능이 좋다. 특히, 트리기반 GBM(Gradient Boosting Machine)은 케글 대회(keggle competition)를 지배한다. 몇몇 케글 우승 연구자들은 단지 특정 부스팅(boosting) 알고리즘을 사용했음을 언급했다. 그러나 몇몇 현역들은 단지 신경망(neural network)같은 블랙박스로 GBM을 생각한다. 그들은 이것의 배경지식 없이 LightBGM을 사용할 것이다. 이것은 결정 트리의 특성에 위배된다. 이 글에서는 GBDT(Gradient Boosting Decision Tree) / GBRT(Gradient Boosting Regression Tree)의 기본 아이디어를 다루고 단계적 예제로 이를 적용해 본다.
Boosting
Before Getting Started
Carnegie Mellon University에서 Zico Colter의 Lecture notes와 Northeastern University에서 Cheng Li의 Lecture notes가 개념을 이해하는데 도움이 된다. 게다가 Tianqi Chen의 presentation은 더 잘 이해하게 만든다.
여기에서 GBRT의 핵심 구현을 찾을 수 있다.
Objective
다음 비디오는 GBM 배경의 아이디어를 포함한다. 이는 시작하기 전에 정확하게 그라디언트 부스팅(gradient boosting)이 무엇인지 알기 위해 중요하다.
Gradient Boosting in Python
이 글에서는 그라디언트 부스팅 알고리즘에 대해 깊게 알아보고 단계별로 문제를 해결해 본다.
여기에서 그라디언트 부스팅 알고리즘을 파이썬으로 구현한 것을 찾을 수 있다.
우리는 실생활에서 실제로 부스팅을 적용한다!
이것은 최단 보폭-최장 보폭(baby-step giant-step)[1] 알고리즘과 아주 유사하다. 처음에 원시데이터에 대한 결정트리를 만든다. 이것이 최장 보폭(giant-step)이 된다. 이제는 튜닝(tune)과 부스팅(boost)할 시간이다. 이번에는 바로앞 트리의 오류를 기반으로 새로운 결정 트리를 만든다. 그리고 이 과정을 여러번 적용한다. 이것이 최단 보폭(baby-step)이 된다. Terence Parr은 이 과정을 놀랍게도 아래 그림처럼 골프 경기 시나리오로 설명했다.
골프에서 boosting
여기서, random forest 알고리즘을 기억해 보면 데이터를 n개의 다른 하위 데이터셋으로 분할하고 하위 데이터셋에 대해 다른 결정 트리(decision tree)를 생성한다. 반대로 데이터셋은 GBM에서는 동일하게 유지된다. 결정트리를 만들고 결정트리 알고리즘에 동일한 데이터셋을 사용하지만 $실제값 - 예측$으로 각 인스턴스 레이블 값을 갱신한다.
그라디언트 부스팅에서 순차적(sequential) 결정 트리를 생각할 수도 있다.
Summing the predictions
인스턴스에 대해 다음 그림은 첫번째 결정트리가 남자아이에 대한 결과로 '2'를 반환한 것을 보여준다. 그러면 첫번째 결정트리의 결과에 대한 오류(error)를 기초로 또다른 결정 트리를 만든다. 이 결정 트리는 이번에는 남자아이에 대해 '0.9'를 반환한다. 남자아이에 대한 최종 결정은 연속적 트리의 예측을 합한 2.9가 된다.
연속적 결정트리(Sequential Decision Trees)
A Step by Step Example
이전 글중에 regression trees가 있다. 해당 글은 GBM을 명확하게 이해하기에 도움이 된다.
이 글에서는 아래 데이터셋으로 작업한다.
| Day | Outlook | Temp. | Humidity | Wind | Decision |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 25 |
| 2 | Sunny | Hot | High | Strong | 30 |
| 3 | Overcast | Hot | High | Weak | 46 |
| 4 | Rain | Mild | High | Weak | 45 |
| 5 | Rain | Cool | Normal | Weak | 52 |
| 6 | Rain | Cool | Normal | Strong | 23 |
| 7 | Overcast | Cool | Normal | Strong | 43 |
| 8 | Sunny | Mild | High | Weak | 35 |
| 9 | Sunny | Cool | Normal | Weak | 38 |
| 10 | Rain | Mild | Normal | Weak | 46 |
| 11 | Sunny | Mild | Normal | Strong | 48 |
| 12 | Overcast | Mild | High | Strong | 52 |
| 13 | Overcast | Hot | Normal | Weak | 44 |
| 14 | Rain | Mild | High | Strong | 30 |
그리고 다음 결정트리를 구성한다.(regression tree의 결과이다.)
Decision Tree
이 업무는 'buildDecisionTree' 함수로 다루어진다. 데이터셋, 인라인 탭의 수(파이썬에서 중요하다. 내부 호출시마다 이를 증가시키고 호출후에는 복귀한다. - 파이썬의 indentation) 그리고 결정 규칙(decision rules)을 저장하기 위한 파일명을 전달한다.
root = 1
buildDecisionTree(df,root,"rules0.py") #generate rules0.py
데이터셋에 대해 이 결정트리 알고리즘을 생햏아면 아래 결정 규칙이 생성된다.
def findDecision(obj):
if Outlook == 'Rain':
if Wind == 'Weak':
return 47.666666666666664
if Wind == 'Strong':
return 26.5
if Outlook == 'Sunny':
if Temperature == 'Hot':
return 27.5
if Temperature == 'Mild':
return 41.5
if Temperature == 'Cool':
return 38
if Outlook == 'Overcast':
return 46.25
이 결정 트리를 만드는 것은 regression trees 글에서 진행했다. 그렇기 때문에 트리를 만드는 방법은 여기서 다루지 않는다.
1일차와 2일차 인스턴스를 점검해 보자. 둘 다 맑음 전망(outlook = sunny)에 더운 온도(temperature = hot)이다. 만들어진 결정트리는 맑음 전망에 더운 온도에 대해 27.5의 결정이라는 것을 보여준다. 그러나, 1일차는 25가 되어야 하고 2일차는 30이 되어야 한다. 이것은 오류(error 또는 잔차, residual)가 1일차에 $25 - 27.5 = -2.5$, 2일차에 $30 - 27.5 = +2.5$라는 것을 의미한다. 이후 날짜에도 비슷한 오류가 있다. 이 오류를 부스팅해보자.
손실함수(Loss Function)
이것은 필수는 아니지만 여기서는 손실함수로 MSE(Mean Squared Error)를 사용한다.
$\text{Loss} = \frac{1}{2} \times (y - y')^2$
- y : 실제값(actual value)
- y' : 예측값(prediction)
기울기(Gradient)는 그라디언트 부스팅(gradient boosting)에서 기울기 감소(gradient descent)를 나타낸다. 여기서 우리는 예측(prediction)에 관한 손실함수의 편도함수(partial derivative)로 각 예측을 갱신한다. 우선 편도함수를 찾아보자.
$\frac{\delta \text{loss}}{\delta y'} = \frac{\delta(\frac{1}{2} \times (y - f(x))^2)}{\delta y'} = 2 \cdot \frac{1}{2} \cdot (y - y') \cdot \frac{\delta (-y')}{\delta y'} = 2 \cdot \frac{1}{2} \cdot (y - y') \cdot (-1) = y' - y$
이제 다음 수식을 적용하여 예측을 갱신할 수 있다.
$y' = y - \alpha \cdot \frac{\delta \text{loss}}{\delta y'}$
- $\alpha$ : 학습률(learning rate)
오로지 업데이트한다는 것에만 집중하기 위해 $\alpha$를 '1'로 설정하여 식을 더 간단하게 만든다.
$-\alpha \cdot \frac{\delta \text{loss}}{\delta y'} = -\alpha \cdot (y' - y) = \alpha \cdot (y-y') = y - y'$
이것이 새로운 결정트리를 구축할 레이블(목표값)이다.
Epoch 1
오류가 1일차에 -2.5, 2일차에 +2.5였던 것을 기억하자. 유사하게 이후 일자에 대해 구축된 결정트리의 결과와 실제 레이블에 기초하여 오류를 찾는다.
import rules0 as myrules
for i, instance in df.iterrows():
params = [] #features for current line stored in params list
for j in range(0, columns-1):
params.append(instance[j])
prediction = myrules.findDecision(params) #apply rules(i-1) for data(i-1)
actual = instance[columns-1]
gradient = actual - prediction
instance[columns-1] = gradient
df.loc[i] = instance
#end of for loop
df.to_csv("data1.py", index=False)
그러면 새로운 데이터셋이 생성되고 각 라인의 잔차(residual, 오류)를 decision 컬럼에 넣는다.
| Day | Outlook | Temp. | Humidity | Wind | Decision |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | -2.5 |
| 2 | Sunny | Hot | High | Strong | 2.5 |
| 3 | Overcast | Hot | High | Weak | -0.25 |
| 4 | Rain | Mild | High | Weak | -2.66 |
| 5 | Rain | Cool | Normal | Weak | 4.333 |
| 6 | Rain | Cool | Normal | Strong | -3.5 |
| 7 | Overcast | Cool | Normal | Strong | -3.25 |
| 8 | Sunny | Mild | High | Weak | -6.5 |
| 9 | Sunny | Cool | Normal | Weak | 0 |
| 10 | Rain | Mild | Normal | Weak | -1.66 |
| 11 | Sunny | Mild | Normal | Strong | 6.5 |
| 12 | Overcast | Mild | High | Strong | 5.75 |
| 13 | Overcast | Hot | Normal | Weak | -2.25 |
| 14 | Rain | Mild | High | Strong | 3.55 |
이제 위 데이터셋을 기반으로 새로운 결정트리를 만든다. 아래 코드는 현재 데이터 프레임에 대한 결정 규칙을 생성한다.
root = 1
buildDecisionTree(df,root,"rules1.py")
회귀 트리(regression tree) 알고리즘을 실행하여 아래 결정 규칙을 생성한다.
def findDecision(Outlook, Temperature, Humidity, Wind):
if Wind == 'Weak':
if Temperature == 'Hot':
return -1.6666666666666667
if Temperature == 'Mild':
return -3.6111111111111094
if Temperature == 'Cool':
return 2.166666666666668
if Wind == 'Strong':
if Temperature == 'Mild':
return 5.25
if Temperature == 'Cool':
return -3.375
if Temperature == 'Hot':
return 2.5
Epoch 2
1일차와 2일차에 대한 예측을 다시 보자. 이제 구축된 결정 트리는 1일차가 약한 바람(wind = weak)에 더운 온도(temperature = hot)이고 예측값이 -1.666이지만 두번째 데이터셋에서 실제값은 -2.5인 것을 보여준다. 이것은 오류가 $-2.5 - (-1.666) = -0.833$이다.
유사하게 트리는 2일차가 강한 바람(wind = strong)에 더운 온도(temperature = hot)인 것을 보여준다. 그렇기 때문에 예측과 실제 모두 2.5이다. 이런 경우 오류는 $2.5 - 2.5 = 0$이다. 이런 방법으로 각 인스턴스의 예측과 실제값을 빼 다시 계산한다.
| Day | Outlook | Temp. | Humidity | Wind | Decision |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | -0.833 |
| 2 | Sunny | Hot | High | Strong | 0.0 |
| 3 | Overcast | Hot | High | Weak | 1.416 |
| 4 | Rain | Mild | High | Weak | 0.944 |
| 5 | Rain | Cool | Normal | Weak | 2.166 |
| 6 | Rain | Cool | Normal | Strong | -0.125 |
| 7 | Overcast | Cool | Normal | Strong | 0.125 |
| 8 | Sunny | Mild | High | Weak | -2.888 |
| 9 | Sunny | Cool | Normal | Weak | -2.166 |
| 10 | Rain | Mild | Normal | Weak | 1.944 |
| 11 | Sunny | Mild | Normal | Strong | 1.25 |
| 12 | Overcast | Mild | High | Strong | 0.5 |
| 13 | Overcast | Hot | Normal | Weak | -0.583 |
| 14 | Rain | Mild | High | Strong | -1.75 |
이번에는 위 데이터셋에 대한 결과를 생성한다.
def findDecision(Outlook, Temperature, Humidity, Wind):
if Outlook == 'Rain':
if Wind == 'Weak':
return 1.685185185185186
if Wind == 'Strong':
return -0.9375
if Outlook == 'Sunny':
if Wind == 'Weak':
return -1.962962962962964
if Wind == 'Strong':
return 0.625
if Outlook == 'Overcast':
return 0.3645833333333334
Epoch 5
각 에포크에서 적용되는 절차가 동일하기 때문에 3단계, 4단계 에포크는 건너 뛴다.
그 후에 아래와 같이 각 에포크에서의 예측을 정리하여 예측을 누적하여 계산하고 최종 예측을 찾기 위해 1단계 에포크에서 5단계 에포크까지의 값을 합한다.
| Day | Actual | epoch 1 | epoch 2 | epoch 3 | epoch 4 | epoch 5 | prediction |
|---|---|---|---|---|---|---|---|
| 1 | 25 | 27.5 | -1.667 | -1.963 | 0.152 | 5.55E-17 | 24.023 |
| 2 | 30 | 27.5 | 2.5 | 0.625 | 0.152 | 5.55E-17 | 30.777 |
| 3 | 46 | 46.25 | -1.667 | 0.365 | 0.152 | 5.55E-17 | 45.1 |
| 4 | 45 | 47.667 | -3.611 | 1.685 | -0.586 | -1.88E-01 | 44.967 |
| 5 | 52 | 47.667 | 2.167 | 1.685 | 0.213 | 1.39E-17 | 51.731 |
| 6 | 23 | 26.5 | -3.375 | -0.938 | 0.213 | 1.39E-17 | 22.4 |
| 7 | 43 | 46.25 | -3.375 | 0.365 | 0.213 | 1.39E-17 | 43.452 |
| 8 | 35 | 41.5 | -3.611 | -1.963 | -0.586 | -7.86E-02 | 35.261 |
| 9 | 38 | 38 | 2.167 | -1.963 | 0.213 | 1.39E-17 | 38.416 |
| 10 | 46 | 47.667 | -3.611 | 1.685 | 0.442 | -1.88E-01 | 45.995 |
| 11 | 48 | 41.5 | 5.25 | 0.625 | 0.442 | -7.86E-02 | 47.739 |
| 12 | 52 | 46.25 | 5.25 | 0.365 | -0.586 | 7.21E-01 | 52 |
| 13 | 44 | 46.25 | -1.667 | 0.365 | 0.152 | 5.55E-17 | 45.1 |
| 14 | 30 | 26.5 | 5.25 | -0.938 | -0.586 | -1.88E-01 | 30.038 |
예를 들면, 예측은 아래처럼 모든 에포크에 걸쳐서 변화된다.
- 1st Epoch = 27.5
- 2nd Epoch = 27.5 - 1.667 = 25.883
- 3rd Epoch = 27.5 - 1.667 - 1.963 = 23.87
- 4th Epoch = 27.5 - 1.667 - 1.963 + 0.152 = 24.022
오류 절대값(absolute error)은 1단계 에포트에서 1일차에 대해 $|25 - 27.5| = 2.5$이지만 5단계 에포트에서는 $|25 - 24.023| = 0.97$로 줄어든다. 보이는 바와 같이 각 인스턴스의 예측은 부스팅시 실제값에 가까워진다.
그렇지만 학습률($\alpha$)과 반복 회수(epoch)는 다양한 문제에 대해 튜닝되어야 한다.
Errors over iterations
각 에포크에 대한 MAE를 피보팅(pivot)해 본다.
| Day | epoch 1 | epoch 2 | epoch 3 | epoch 4 | epoch 5 |
|---|---|---|---|---|---|
| 1 | 2.5 | 0.833 | 1.13 | 0.977 | 0.977 |
| 2 | 2.5 | 0 | 0.625 | 0.777 | 0.777 |
| 3 | 0.25 | 1.417 | 1.052 | 0.9 | 0.9 |
| 4 | 2.667 | 0.944 | 0.741 | 0.155 | 0.033 |
| 5 | 4.333 | 2.167 | 0.481 | 0.269 | 0.269 |
| 6 | 3.5 | 0.125 | 0.813 | 0.6 | 0.6 |
| 7 | 3.25 | 0.125 | 0.24 | 0.452 | 0.452 |
| 8 | 6.5 | 2.889 | 0.926 | 0.34 | 0.261 |
| 9 | 0 | 2.167 | 0.204 | 0.416 | 0.416 |
| 10 | 1.667 | 1.944 | 0.259 | 0.183 | 0.005 |
| 11 | 6.5 | 1.25 | 0.625 | 0.183 | 0.261 |
| 12 | 5.75 | 0.5 | 0.135 | 0.721 | 0 |
| 13 | 2.25 | 0.583 | 0.948 | 1.1 | 1.1 |
| 14 | 3.5 | 1.75 | 0.813 | 0.227 | 0.038 |
| MAE | 3.011111 | 1.112963 | 0.599383 | 0.48669 | 0.406115 |
이 결과는 에포크 전체에 대해 전체를 도식화할 때 흥미로울 수 있다.
MAE over epochs
부스팅이 확실하게 잘 동작한다고 할 수 있다.
Conclusion
이 글에서는 그라디언트 부스팅에 대한 감각을 다뤘다. XGBoost와 LightGBM은 그라디언트 부스팅의 일반적인 변형이다. 결정트리가 아주 갈력한 머신러닝 알고리즘일지라도 단일 트리는 머신러닝 연구에 적용하기에 충분히 강력하지 않다. 그러나 실험은 GBM을 형성하는 연속적인 단일 트리는 적용된 ML 과제의 대부분을 지배한다.
[1] 최단 보폭-최장 보폭(baby-step giant-step): 최단 보폭-최장 보폭 알고리즘은 n을 $m={\lceil}\sqrt{n}{\rceil}$개의 원소를 가진 m개의 블록으로 분할하고 첫 번째 블록의 m개에 대해 $a^x$ (mod n) 값을 저장한다. 다음으로 m개의 블록에 대한 mod n을 계산하여 첫 번째 블록의 원소 값을 검색하여 일치하는 블록을 찾는 방법이다. 본 논문에서는 첫 번째로, $a^{{\phi}(n)/2}{\equiv}1(mod;n)$과 $a^x(mod;n){\equiv}a^{{\phi}(n)+x}$ (mod n)의 특징을 적용하여 m개의 원소를 가진 ${\lceil}m/2{\rceil}$개의 블록으로 분할하는 방법을 적용하여 최장보폭의 수행횟수를 50% 감소시켰다. 두 번째로, ${\lceil}m/2{\rceil}$개의 최단 보폭을 먼저 수행하여 저장하고, 첫 번째 블록의 m개 원소를 수행하는 최단 보폭을 수행하는 방법으로 최단 보폭-최장 보폭 알고리즘을 역으로 수행하는 방법을 제안하였다. 이 알고리즘은 최단 보폭-최장 보폭 알고리즘의 m개 저장과 검색을 ${\lceil}m/2{\rceil}$개로 50% 감소시키는 특징이 있다.