14. LightGBM(Light Gradient Boosting Machine)

what?

• LightGBM은 boosting 알고리즘의 일종으로 빠르고 성능이 높으며 분류와 회귀 등에 사용될 수 있다.

• XGBoost와 마찬가지로 leaf-wise split을 진행하며, sparse data를 split 시 고려하지 않으며 node별로 병렬 연산을 진행하여 연산 속도가 빠르다.

• GOSS(Gradient-based One Side Sampling)를 통해 데이터의 일부만 sampling하여 빠른 속도를 보이고 있다. 이 알고리즘은 모든 데이터가 target label을 예측하는데 동일하게 기여하지 않는다고 가정하고 있다. gradient가 작을 경우 더 잘 훈련되었다고 볼 수 있으며 gradient가 큰 데이터를 집중적으로 훈련하는 게 효율적이다.(기울기가 보다 큰1(즉, 과소 훈련시킨 개체) 개체가 정보 획득에 더 기여할 것이다) 하지만 gradient가 큰 데이터만 훈련시키면 데이터의 분포가 불균형하게 변할 수 있기 때문에 gradient가 작은 데이터를 랜덤으로 추출하는 방식을 채택하고 있다

• Exclusive Feature Bundling을 통해 서로 겹치지 않는 feature를 묶어서 처리하여 feature의 수를 획기적으로 줄일 수 있다. 예를 들어 어떤 데이터에서 “cola” feature의 값이 0일 때 “sprite” feature가 1인 경우 두 feature를 하나의 feature로 합칠 수 있다. 이 경우 계산 복잡도는 O(#feature x # data)에서 O(#bundle x #data)로 바뀐다. 래의 변수 A는 [0, 10] 값을 취하고 변수 B는 [0, 20] 값을 취한다. 그렇다면 변수 B 값에 오프셋 10을 더하여 가공한 변수가 [10, 30]에서 값을 취하게 한다. 그다음, 변수 A와 B를 병합하고 [0, 30] 범위의 변수 묶음을 사용하여 원래의 변수 A와 B를 대체하는 것이 안전하다.

why?

• 학습 속도가 빠르다
• 연속형 데이터를 bin으로 쪼개서 이산형 데이터로 만들어 메모리 사용량에서도 효율적이다
• 다른 boosting 알고리즘에 비해 전반적으로 좋은 성능을 보인다

why not?

• 데이터의 규모가 작을 시 overfitting될 가능성이 높다. 1만 row 이상의 데이터에 적합함

how?

Input

1)Data{(\(x_i, y_i\))}, M rows(data) and N columns(features)
2) Model : \(\hat{y_i} = \sum_{k=1}^K f_k(x_i), f_k \in \mathcal{F}\)
3) Object function : \(\sum_{i=1}^n l(y_i, \hat{y_i}) + \sum_{k=1}^K\Omega(f_k)\)
\(w_j^* = -\frac {G_j} {H_j + \lambda}(=f_t)\),
\(obj = - \frac 1 2 \sum_{j=1}^T \frac {G_j^2} {H_j + \lambda} + \gamma T\)

Step 1 Initialize model with constant value with sampled data and features

1) GOSS(Gradient-based One Side Sampling)

• 모델에 대해 데이터를 학습시키고 미리 지정한 기울기 크기 상위 a%만큼의 데이터는 전부 다 사용한다
• (1-a)%의 데이터 중 b%의 데이터를 무작위로 추출한다
• 추출된 두 데이터셋을 합쳐 학습 데이터로 사용한다

2) EFB(Exclusive Feature Bundling)

3) \(f_0(x) = \underset \gamma {argmin} \sum_{i=1}^nL(y_i, \hat{y_i})\)

• \(f_0(x)\) : initial predicted value(=average of all target values)

Step 2 for k=1 to K(number of trees)

1) compute \(g_i, h_i\) on each split\((g_i = \partial \hat{y_{t-1}}l(y_i, \hat{y_i}), h_i = \partial^2 \hat{y_{t-1}}l(y_i, \hat{y_i}))\)

2) until \(Gain < 0\), greedily grow the tree using object function \(obj = - \frac 1 2 \sum_{j=1}^T \frac {G_j^2} {H_j + \lambda} + \gamma T\)
\(Gain = \frac 1 2 [\frac {G_L^2} {H_L + \lambda} + \frac {G_R^2} {H_R + \lambda} + \frac {(G_L + G_R)^2} {H_L + H_R + \lambda}] - \gamma\)

3) \(f_k(x_i) = w_k, w_k = -\frac {G_j} {H_j + \lambda}\)

4) Update \(f_K(x_i) = f_{(K-1)} + \nu f_k(x_i)\)

• \(\nu\) : learning rate

Step 3 output \(f_K(x)\)

Code usage

from lightgbm import LGBMClassifier

import pandas as pd
import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split

dataset = load_breast_cancer()
ftr = dataset.data
target = dataset.target

# 전체 데이터 중 80%는 학습용 데이터, 20%는 테스트용 데이터 추출
X_train, X_test, y_train, y_test=train_test_split(ftr, target, test_size=0.2, random_state=156 )

# 앞서 XGBoost와 동일하게 n_estimators는 400 설정. 
lgbm_wrapper = LGBMClassifier(n_estimators=400)

# LightGBM도 XGBoost와 동일하게 조기 중단 수행 가능. 
evals = [(X_test, y_test)]
lgbm_wrapper.fit(X_train, y_train, early_stopping_rounds=100, eval_metric="logloss", 
                 eval_set=evals, verbose=True)
preds = lgbm_wrapper.predict(X_test)

Tips : LightGBM parameters

1. 주요 parameters

• num_iterations(default=100) : 반복 수행하려는 트리의 개수를 지정함. 너무 크게 설정하면 overfitting이 발생함
• learning_rate(default=0.1)
• max_depth(default=1)
• min_data_in_leaf(default=20) : overfitting 방지 파라미터
• num_leaves(default=31) : 하나의 트리가 가질 수 있는 최대 leaf의 수
• boosting(default=gbdt)
• bagging_fraction(deafult=1.0) : 트리가 커져 과적합되는 것을 제어하기 위해서 데이터를 샘플링하는 비율을 지정
• feature_fraction(default=1.0)
• lmabda_l2(default=0.0)
• lambda_l1(default=0.0)
• objective : 최솟값을 가져야 할 loss function을 정의

2. 하이퍼 파라미터 튜닝 방안

• num_leaves를 중심으로 min_data_in_leaf, max_depth를 조정하면서 모델의 복잡도를 줄이는 것이 바람직하다
• learning_rate를 줄이면서 n_estimators를 크게 하는 것은 부스팅 계열의 기본적인 튜닝 방안이다.
• 과적합 방지를 위해 regularization 파라미터를 적용하거나 피처나 데이터의 수를 조정하는 feature_fraction, bagging_fraction 파라티터를 조정하는 것도 바람직하다.

Reference

Pros and Cons of LightGBM
Diffrence between XGBoost and LightGBM
LightGBM 논문 번역
LightGBM 예제 코드