LightGBM: A Highly Efficient Gradient BoostingDecision Tree

링크: https://proceedings.neurips.cc/paper/2017/file/6449f44a102fde848669bdd9eb6b76fa-Paper.pdf

Introduction

Gradient boosting decision tree (GBDT)는 분류, 회귀, 예측등에서 효과적인 머신러닝 기법이지만 데이터의 크기가 커짐에 따라 Split point들의 모든 경우의 수를 다 계산하느라 시간 소모가 너무 커지는 문제가 있었다. 논문에선 data instance와 feature들의 수를 줄이기 위해 두가지 새로운 기법을 소개한다.

하나는 Gradient-based One-Side Sampling (GOSS)이고 나머지 하나는 Exclusive Feature Bundling (EFB)이다.

GOSS는 가중치가 없는 GBDT에서 gradient가 클수록 information gain에 더 크게 기여하는 것에서 착안해 gradient가 큰 instance들은 down sample시 유지하고 작은 gradient를 가지는 instance들을 랜덤하게 drop하는 기법이다.

EFB는 feature들의 수가 많아지면 feature space는 sparse하므로 대부분의 feature들은 상호배타적이고 이에 따라 배타적인 feature들을 하나의 bundle로 묶는 방법이다. EFB는 bundle문제를 graph coloring문제로 바꿔 그리디 알고리즘으로 효율적으로 풀어낸다.(graph coloring 문제는 방향성이 없는 그래프 G(V,E)에서 인접한 두 vertex(u,v)에 서로 다른 K개의 색을 칠하는 문제이다. EFB에선 feature를 vertex로 치환하고 상호배타적이지 않은 feature들 간에 간선을 연결하여 graph coloring 문제로 바꾼다.)

GBDT에 GOSS와 EFB를 더한 알고리즘을 LightGBM(LGBM)이라고 부른다. 

Preliminaries

GBDT에서 연산의 대부분을 차지하는 것은 decision tree를 학습하는 것이고 decision tree를 학습할 때 가장 시간을 많이 차지하는 부분은 최적의 split point를 찾는 것이다.

Split point를 찾기 위한 방법으로는 feature 값들을 정렬 후 가능한 모든 split point를 탐색하는 것과 연속형 변수를 이산형 bin들로 나눈 후 이산형 bin을 학습 시 feature histogram을 만드는데 사용하는 histogram-based algorithm이 있다.

Histogram-based algorithm에서 histogram을 만드는데 시간이 가장 많이 걸리고 시간복잡도는 O(#data*#feature)이므로 data혹은 feature의 수를 줄인다면 학습시간을 줄일 수 있을 것이다.

data의 수를 줄이는 방법으로는 data instance들을 down sample하는 방법이 있고 feature의 수를 줄이는 방법으로는 weak feature들을 없앰으로써 행해진다. 전자는 GBDT는 가중치가 없기에 정확도가 크게 떨어지고 후자는 중복이 있다고 가정한 방법이기에 실제 문제에 적용하기 힘들다.

이에 따라 data의 수를 줄이는 방법으로 GOSS를 소개하고 feature의 수를 줄이는 방법으로 EFB를 소개한다.

Gradient-based One-Side Sampling (GOSS)

Input: I: training data, d: iterations
Input: a: sampling ratio of large gradient data
Input: b: sampling ratio of small gradient data
Input: loss: loss function, L: weak learner
models ← {}, fact ← (1−a)/b
topN ← a × len(I) , randN ← b × len(I)
for i = 1 to d do
    preds ← models.predict(I)
    g ← loss(I, preds), w ← {1,1,...}
    sorted ← GetSortedIndices(abs(g))  # 모델이 예측한 값을 정렬하여 배열에 삽입
    topSet ← sorted[1:topN]  # gradient가 큰 instance들은 down sample시 그대로 사용 
    randSet ← RandomPick(sorted[topN:len(I)],randN) # gradient가 작은 instance들은 랜덤하게 몇개만 뽑아냄
    usedSet ← topSet + randSet
    w[randSet] × = fact . # 랜덤하게 뽑은 gradient가 작은 instance들에 fact라는 보정치 곱하기 
    newModel ← L(I[usedSet], − g[usedSet], w[usedSet])
    models.append(newModel)

논문에서 소개한 GOSS의 Pseudo-code이다. 이해한 대로 주석을 달아 보았다. 

AdaBoost에서 가중치는 해당 instance가 output에 얼만큼 영향력을 가지는지로 해석될 수 있다. 마찬가지로 GBDT에서는 instance의 gradient가 클수록 information gain에 많이 기여하고, gradient가 작은 instance들은 error값이 작고 error값이 작다는 것은 이미 traing이 잘 되었다는 것을 의미하니 gradient가 작은 instance들을 drop해도 된다.

물론 그러한 instance들을 모두 drop한다면 정확도에 영향을 미치기에 GOSS에서는 gradient가 작은 instance들에 fact= (1-a)/b라는 값을 곱하여 보정함으로써 원래의 데이터 분포와 크게 다르지 않으면서 training중인 instance들(=gradient가 큰 instance들)에 집중할 수 있게 된다.

Exclusive Feature Bundling (EFB)

EFB는 feature들을 bundle하여 시간복잡도를 O(#data × #feature)에서 O(#data × #bundle)로 바꾼다. bundle은 feature보다 훨씬 작기에 연산속도를 크게 높힐 수 있으나 어떤 feature들을 묶을지와 어떻게 bundle을 만들까하는 두가지 문제가 생긴다.

첫번째 문제에 대해서 bundle문제를 graph coloring문제로 근사하여 그리디 알고리즘으로 푼다. 또한 특정 feature들은 완벽하게 상호배타적이지 않을지라도 0이 아닌 값들을 동시에 가지는 경우가 드물기에(상호배타적이라고 가정할 수 있게 된다.) 이 conflict rate=γ를 작은 값으로 잘 선택하면 정확도와 효율성 모두 잡을 수 있다. 

Input: F: features, K: max conflict count
Construct graph G
searchOrder ← G.sortByDegree()
bundles ← {}, bundlesConflict ← {}
for i in searchOrder do  # graph의 정렬된 vertex만큼
    needNew ← True
    for j = 1 to len(bundles) do
        cnt ← ConflictCnt(bundles[j],F[i])     
        if cnt + bundlesConflict[i] ≤ K then  # K보다 작으면 bundle에 feature추가
            bundles[j].add(F[i]), needNew ← False
            break
    if needNew then  # bundle이 비어있으면 needNew=True, 따라서 F[i] bundle에 추가
        Add F[i] as a new bundle to bundles
Output: bundles

위에 설명한 bundle문제를 graph coloring 문제로 근사한 Pseudo-code이다.

두번째 문제인 bundle을 만드는 문제는 feature value에 offset을 더해줌으로써 배타적인 feature들이 서로 다른 bin에 넣어지게 함으로써 해결한다. 이의 Pseudo-Code는 아래와 같다.

Input: numData: number of data
Input: F: One bundle of exclusive features
binRanges ← {0}, totalBin ← 0
for f in F do
    totalBin += f.numBin
    binRanges.append(totalBin)  # feature들의 bin의 갯수를 누적해서 더해가며 range배열에 넣기
newBin ← new Bin(numData)
for i = 1 to numData do
    newBin[i] ← 0  # 배열 원소 초기화
    for j = 1 to len(F) do
        if F[j].bin[i] != 0 then  # feature의 bin이 0이 아니라면, 
            newBin[i] ← F[j].bin[i] + binRanges[j]  
            # offset(binRanges[j])를 더해줌으로써 상호배타적인 featuer들이 서로 다른 bin에 들어가게 함
Output: newBin, binRanges

위 Pseudo-Code에 대해 부연 설명을 하자면 논문에서는 feature의 value에 offset을 더함으로써 상호배타적인 feature들이 서로 다른 bin에 들어갈 수 있도록 하는 예시로 값의 범위가 [0,10)인 feature A가 있고 범위가 [0,20)인 feature B가 있다면 둘은 0이 아닌 값을 동시에 가질 수 있기에 상호배타적이지 않다. 그러나 B에 offset 10을 더해줌으로써 B의 범위는 [10,30)이 되고 둘은 상호배타적이기에 [0,30)를 범위로 하는 bundle로 A와 B를 묶을 수 있게 된다. 

위 두 방법에 따라 EFB는 많은 상호배타적 feature들을 묶음으로서 dense한 feature들로 만들고, 이에 따라 feature값이 0인 경우에 대해 불필요한 계산을 피할 수 있게 된다. 

Experiments

Table 1: Datasets used in the experiments.

Table 2: Overall training time cost comparison. (lEFB_only = lgb_baseline with EFB)

Table 3: Overall accuracy comparison on test datasets (SGB =  lgb_baseline with Stochastic Gradient Boosting)

LightGBM의 효율성을 실험적으로 증명하였다. 데이터셋의 크기는 대부분 크며 feature의 갯수는 적은것부터 많은것까지, feature의 차원이 Dense한것과 Sparse한 것 모두 사용하였다. Table2와 Table3를 통해 LightGBM이 정확도가 기존의 기법들과 차이 나지 않으면서 연산속도를 크게 줄인 것을 볼 수 있다. 

GOSS의 효과에 대해 더 자세히 보자면 Table2의 EFB_only와 LightGBM을 통해 GOSS Algorithm이 연산속도를 최대 2배 빠르게 해줌을 볼 수 있고 Table3의 SGB와 LightGBM을 통해 GOSS를 사용했을 떄 정확도가 모두 Stochastic Gradient Boosting을 사용했을 때보다 높음을 볼 수 있다.

EFB의 효과는 Table2의 lgb_baseline과 EFB_only를 비교함으로써 알 수 있다. EFB를 사용함으로써 속도가 최대 12배 증가하는 것을 볼 수 있다.