LightGBM: A Highly Efficient Gradient Boosting Decision Tree

[koptimizer]

📋 논문의 정보를 알려주세요.

• LightGBM: A Highly Efficient Gradient Boosting Decision Tree
• Guolin Ke et al
• 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA.
• 2017

📃 Abstract

Gradient Boosting Decision Tree (GBDT) is a popular machine learning algorithm, and has quite a few effective implementations such as XGBoost and pGBRT. Although many engineering optimizations have been adopted in these implementations, the efficiency and scalability are still unsatisfactory when the feature dimension is high and data size is large. A major reason is that for each feature, they need to scan all the data instances to estimate the information gain of all possible split points, which is very time consuming. To tackle this problem, we propose two novel techniques: Gradient-based One-Side Sampling (GOSS) and Exclusive Feature Bundling (EFB). With GOSS, we exclude a significant proportion of data instances with small gradients, and only use the rest to estimate the information gain. We prove that, since the data instances with larger gradients play a more important role in the computation of information gain, GOSS can obtain quite accurate estimation of the information gain with a much smaller data size. With EFB, we bundle mutually exclusive features (i.e., they rarely take nonzero values simultaneously), to reduce the number of features. We prove that finding the optimal bundling of exclusive features is NP-hard, but a greedy algorithm can achieve quite good approximation ratio (and thus can effectively reduce the number of features without hurting the accuracy of split point determination by much). We call our new GBDT implementation with GOSS and EFB LightGBM. Our experiments on multiple public datasets show that, LightGBM speeds up the training process of conventional GBDT by up to over 20 times while achieving almost the same accuracy.

🔎 어떤 논문인지 소개해주세요.

• XGBoost같은 훌륭한 머신러닝 프레임웍이 출시되었지만, 아직 속도의 한계가 있었습니다. LGBM이 어떤 방식으로 해결하였는지 알아보려고 합니다.

🔑 핵심 키워드를 적어주세요.

• GOSS, EFB, LightGBM

📎 URL

• https://d1wqtxts1xzle7.cloudfront.net/59228936/LightGBM_f20190512-55031-xxtk42.pdf?1557713701=&response-content-disposition=inline%3B+filename%3DLightGBM_A_Highly_Efficient_Gradient_Boo.pdf&Expires=1613396479&Signature=emIfaNjB9GjLuBCkkdnn0FckS4FTh~yMT~r21Ftgb2l~5shDs3rDAgXNciDL548G3U1NGxU6E0oUAF2ZP00TpWHw65yTrPUR9rkxYaz0GT7RwdhZrqSW6fZ9jOG1ixWIYl0U1CwmWbHhhipFXIT4gGy4y5yjZmC5zV7H1ld2RnvbdkBV0PedGUlZ-aBOM-8p5nMByjFCIBDb2-fTR5SvhHP5d9EsIXtLN12m2ma1SJvevZkyvO~s1h6rGCpL39LEWIjt-aI-6SeIqagd7h-aSxFR3ogWdDpGadHcE7uJaX12pfCLVe5dKSnwjHfPDK4mt8hftYZHfYwt7F9MhWkwzQ__&Key-Pair-Id=APKAJLOHF5GGSLRBV4ZA