Lightgbm: A highly efficient gradient boosting decision tree

논문: Ke, Guolin, et al. “Lightgbm: A highly efficient gradient boosting decision tree.” Advances in neural information processing systems 30 (2017): 3146-3154.

 

Gradient Boosting Decision Tree는 널리 사용되는 알고리즘이다. 하지만 데이터의 크기가 큰 경우 computational cost가 높아 비효율적이다. 또한 기존의 방식은 trade off가 심해 정확도와 효율을 둘 다 이끌어내지는 못했다. 이를 해결하기 위해 본 논문에서는 Gradient-based One-Side Sampling (GOSS) 과 Exclusive Feature Bundling (EFB)를 이용한 LightGBM 알고리즘을 제시한다. GOSS를 통해 데이터 중 gradient가 작은 data들을 제외시키고 사용할 수 있다. Gradient가 큰 데이터들이 정보를 얻는 데에 더 효과적이기 때문에 기존보다 작은 데이터로 효율적으로 정보를 얻어낼 수 있다. 하이퍼파라미터 a와 b를 사용하여 gradient가 작은 순서로 정렬을 했을 때 밑에서 b 만큼은 random하게 추출하고, 위에서 a만큼은 모두 사용하는 방식을 이용한다. 또한 해당 방식은 unform random sampling보다 성능이 좋았다. EFB는 상호 배타적인 feature을 묶는 데에 사용된다. 이를 구현하기 위해 두가지 알고리즘을 사용하였다. Greedy Bundling을 이용하여 각 feature들을 bundling 하고, 해당 set들을 Merge Exclusive Feature을 이용하여 하나의 변수로 만들어준다.

 

이 두개의 방법론으로 LightGBM이라는 새로운 boosting 방식을 제안한다. 실험을 통해 LightGBM이 기존의 GBDT 속도대비 20배 향상시켰으며, 정확도 손실이 없음을 확인하였다.