LightGBM: A Highly Efficient Gradient Boosting Decision Tree

논문 명: LightGBM: A Highly Efficient Gradient Boosting Decision Tree

저자 명: Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu

게재 저널: NIPS 2017 (31st Conference on Neural Information Processing Systems)

게재 날짜: 2017년

URL: http://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision

LightGBM: A Highly Efficient Gradient Boosting Decision Tree

사용 예시: https://www.kaggle.com/artgor/eda-feature-engineering-and-model-interpretation#Modelling-and-feature-generation

EDA, Feature Engineering and model interpretation

 

---

 

LightGBM = GBDT + (GOSS + EFB)

 

LightGBM 논문은 NIPS 2017에서 발표되고 나서 현재까지도 여러 분야의 연구, 여러 기업에서 어찌 보면 가장 흔한 머신러닝 알고리즘으로 활용되고 있는 것 같다. 그럴 수 있었던 이유는 논문에서도 언급된 바대로, LightGBM의 배경이 되는 그래디언트 부스팅 결정 트리(GBDT; Gradient Boosting Decision Tree)의 성능은 거의 그대로 유지하면서 모델 학습에 필요한 시간이나 필요한 컴퓨팅 파워(예: RAM memory)를 압도적으로 줄였기 때문이다(* 논문에서는 20 배 가량 빠르다고 나온다). 빠르게 성과를 도출해야하는 기업이나 연구자 입장에서는 충분히 매력적일 것으로 생각된다. 그리고 실제로 Kaggle이나 많은 해커톤에서 열리는 분류 문제뿐만 아니라 회귀 문제에 대해서도 좋은 결과를 얻고 있다.

그러면 어떻게 GBDT와 비교해 모델 학습 시간을 압도적으로 줄이면서 성능은 유지했는지, 위 논문을 참고하여 알아보고자 한다.

 

1. 학습 데이터의 샘플 수를 줄이는 방법 --> GOSS (Gradient-based One-Side Sampling)

2. 학습 데이터의 차원을 줄이는 방법 --> EFB (Exclusive Feature Bundling)

 

---

 

GOSS (Gradient-based One-Side Sampling)

 

기존의 GBDT에서는 데이터를 학습시키기 위해 전체 샘플들을 스캔(scan all the data instances)해야만 가능한 모든 분리점들에 대한 information gain을 추정할 수 있었다. 따라서, 훈련 샘플이 많아질수록 학습에 소요되는 시간 또한 상당히 길어질 수 밖에 없었다.

이렇게 시간 소모적인 문제에 대한 해결책으로 LightGBM에서는 GOSS라는 새로운 기술을 도입하였다. GOSS는 매 반복(iteration)마다 훈련 데이터를 "모델의 학습에 많은 도움이 되는 샘플(the data instances with larger gradients)" $A$ 집합과 "학습에 별 도움이 안 되는 샘플(the data instances with small gradients)" $B$ 집합으로 나눈다. "모델의 학습에 별 도움이 안 되는 샘플"이란 negative gradients (= residual errors)가 작다는 뜻이고, 이는 모델이 이미 그 샘플에 대해서는 잘 학습되어 있다는(well-trained) 것을 의미한다. 이렇게 두 그룹으로 나눈 훈련 데이터에서 $A$ 집합의 샘플들은 모두 학습에 사용하고 $B$ 집합에서는 랜덤하게 샘플링하여 일부 샘플들만 학습에 사용하게 된다.

하지만, 여기서 주의할 점이 있다. 이렇게 $B$ 집합에 대해서 랜덤 샘플링으로 추출할 경우 전체 훈련 데이터의 자료 분포와 달라질 수 있다. 그렇게 되면 기존의 전체 훈련 데이터를 사용해 학습했을 때와 다른 성능을 보일 가능성이 높다.

이를 해결하기 위해 GOSS에서는 negative gradients의 총합을 구할 때 스케일링 인자를 적용하였다. 구체적인 과정을 살펴보면 다음과 같다. 먼저, 훈련 데이터들을 negative gradient의 절댓값을 기준으로 내림차순으로 정렬한다. 그 다음, $a$를 전체 훈련 데이터에 대한 $A$ 집합의 표본 추출비(sampling ratio of large gradient data), $b$를 전체 훈련 데이터에 대한 $B$ 집합의 표본 추출비(sampling ratio of small gradient data)라 표현하겠다. 따라서, $A$ 집합에는 negative gradient의 절댓값이 큰 상위 $a\times100\%$의 샘플들이 포함된다. 반면, $B$ 집합은 $A$ 집합의 여집합인 $A^c$ 집합 $(1-a)\times100\%$에서 랜덤하게 추출된 $b\times100\%$의 샘플들이 포함된다.

전체 훈련 데이터를 사용해 negative gradients의 합을 구한다면, 간단하게,

$$\sum gradient(A) + \sum gradient(A^c) $$

와 같다. 반면, $A^c$ 집합에서 랜덤하게 추출한 $B$ 집합을 사용한다면,

$$\sum gradient(A) + \sum gradient(B)$$

로 두 번째 항이 첫 번째 식에서는 $(1-a)\times100\%$의 샘플에 대해 계산되고, 두 번째 식에서는 $b\times100\%$의 샘플에 대해서만 계산되기 때문에 서로 다른 결과를 보일 것이다(모델 학습에 차이가 발생하게 되고, 결국 모델 성능에 영향을 끼친다). 이 때, GOSS에서는 두 번째 식의 두 번째 항에 스케일링 인자 ${(1-a) \over b}$ 를 곱해줌으로써 $B$ 집합으로부터 계산한 negative gradients 합이 마치 $A^c$ 집합 규모에서 계산된 것처럼 스케일링을 하였다.

$$\sum gradient(A) + {1-a \over b} \times \sum gradient(B)$$

 

출처: https://www.slideshare.net/suman_lim/boostingsuman

 

GOSS 결론

 

기존의 GBDT에서는 전체 샘플 수 $N$에 대해서 negative gradient 계산을 수행해야했다. 하지만 GOSS를 적용함으로써 전체 훈련 데이터 중 일부만을 골라 $N\times(a+b)$만큼의 샘플만 사용하므로 계산량을 줄이고($\because a+b<1$), 스케일링 인자(${1-a \over b}$)를 곱해 학습 성능이 저하되지 않도록 하였다.

 

---

 

EFB (Exclusive Feature Bundling)

 

LightGBM의 GOSS에서 훈련 데이터의 샘플 수를 줄여 학습 시간을 절약했다면, EFB는 훈련 데이터의 차원(특성; feature)을 줄임으로써 학습 시간 절감에 기여한다.

훈련 데이터의 차원을 줄이는 과정에서는 두 가지 이슈가 있다.

1. 번들(bundle)로 만들 기존 특성들을 어떻게 고를 것인지,

2. 어떻게 새로운 번들을 만들 것인지

 

첫 번째 이슈의 경우 다음과 같은 순서로 진행된다. 특성별로 0이 아닌 값을 몇 개(the count of nonzero values)나 갖는지 확인한다. 여기서 0이 아닌 값을 많이 갖는 특성이 다른 특성과 충돌할 가능성이 더 높다(higher probability of conflicts)는 가정이 주어진다. 그리고 nonzero 개수로 특성들을 정렬한 다음, 하나씩 특성들을 체크하면서 기존의 번들과 충돌이 작으면 기존의 번들에 추가하고 반대로 충돌이 많다면 새로운 번들을 생성한다.

그 방법은 두 번째 이슈와 연관된다. 방법은 간단하다. 예를 들어 어떤 특성 $X_1$의 범위가 0 이상 10 미만의 값을 가지고, 다른 특성 $X_2$의 범위가 0 이상 20 미만의 값을 가진다고 가정한다. 두 특성을 하나의 번들로 구성한다고 할 때, $X_2$의 범위를 10 이상 30 미만으로 10 만큼씩 옮겨 $X_1$ 범위 뒤에 합칠 수 있다. 즉, 새로운 번들은 0 이상 30 미만의 값을 갖는 새로운 특성이 된다. 이렇게 함으로써 특성의 수는 줄이고, 원래 기존에 있던 특성에 대한 정보도 잃지 않을 수 있다.

 

EFB 결론

 

기존의 GBDT에서 많은 수의 특성(고차원 데이터)을 사용해 결정 트리 모델을 학습하는 경우 계산량의 오더는 $O(N(data) \times N(feature))$이며, 특히 원핫인코딩(One hot encoding)으로 전처리한 변수를 포함한 데이터의 경우 0 값으로 인해 불필요한 연산이 늘어날 수 있다. LightGBM의 EFB를 적용하면 히스토그램 방식으로 범주형으로 전환하여 사용하기 때문에 0 값의 영향을 줄일 수 있을뿐만 아니라, 계산량의 오더를 $O(N(data) \times N(bundle))$로 줄여 계산 시간을 단축시킨다($\because N(bundle) << N(feature)$).

 

---

 

실험 결과

 

출처: Ke et al. (2017, NIPS)