[ML] LightGBM: A Highly efficient Gradient Boosting Decision Tree (작성중)

 

어느 순간부터 정형 데이터 형태의 ML 모델링을 할 때는 대부분 LightGBM을 쓰는 것이 정석처럼 되었습니다. (물론 형식적으로 다양한 알고리즘으로 실험을 수행하긴 합니다만... 저의 짧은 경험에 비추어 보았을 때 대부분의 경우 LGBM이 모형 학습 속도와 성능 측면에서 가장 좋았습니다.)

 

물론 최근 트렌드가 딥러닝 기반 모델(+LLM)으로 넘어가버린 탓도 있지만, 5년도 정형 데이터 분석 파트에서 독보적인 자리를 지키고 있는 LightGBM 논문을 이제서야 읽어봤습니다. 

 

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

 

 

 

 

 

 

 

 

💜 Abstract 💜 

GBDT (Gradient Boosting Decision Tree) 프레임워크 기반의 우수한 알고리즘이 많지만 (XGBoost, pGBRT 등) feature dimension이 크고 데이터 사이즈가 클 때는 효율성(efficiency)과 확장성(scalability)에 한계가 있습니다. 이는 각 feature마다 모든 데이터를 스캔하여 가능한 모든 split point에서 information gain을 추정하는 과정이 시간이 아주 많이 드는 일이기 때문입니다.

 

이러한 문제를 해결하기 위해서 Gradient-based One-Side Sampling (GOSS), Exclusive Feature Bundling (EFB) 라는 두 가지 핵심 아이디어를 제시합니다.

 

GOSS : information gain을 추정 할 때 gradient가 작은 데이터는 제외하고 gradient가 큰 데이터만 사용합니다. 우리는 gradient가 큰 데이터들이 information gain 계산에 더 중요한 역할을 한다는 점을 증명하였으며, 그 결과 GOSS는 훨씬 적은 데이터만으로도 information gain을 매우 정확하게 추정 할 수 있습니다. 

 

EFB : mutually exclusive features들 (예 : 동시에 0이 아닌 값을 거의 가지지 않는 변수들)을 묶어서(=feature bundling) 변수의 개수를 줄입니다. bundling을 최적화하는 NP-hard 문제라는 것을 증명했지만, greedy algorithm으로도 꽤나 좋은 근사 비율을 달성 할 수 있고, 이로 인해 split point 결정의 accuracy를 크게 해치지 않는 선에서 feature의 갯수를 효과적으로 줄일 수 있었습니다. 

 

이렇게 GOSS와 EFB을 사용하는 새로운 GBDT를 LightGMB이라고 부릅니다.

 

여러 개의 공개 데이터셋에서 실험 한 결과 LightGBM은 기존 GBDT의 training 과정을 최대 20배 이상 가속화하면서도 거의 동일한 정확도를 유지했습니다.

 

 

💜 1. Introduction 💜 

 

(👀1) Gradient Boosting Decision Tree (GBDT)는 그 효율성, 정확성, 해석 가능성으로 인해 널리 사용되는 기계 학습 알고리즘입니다. GBDT는 다중 클래스 분류, 클릭 예측, 순위 학습 등 다양한 기계 학습 작업에서 최첨단 성능을 발휘합니다. 최근 몇 년 동안, 빅 데이터(특히 feature 수와 instance 수 모두 증가)로 인해 GBDT는 정확성과 효율성 간의 균형에 있어 새로운 도전에 직면해 있습니다.

 기존의 GBDT 구현은 각 feature에 대해 모든 데이터 instance를 스캔하여 가능한 모든 분할 지점의 information gain을 추정해야 합니다. 이로 인해 계산 복잡도는 feature 수와 instance 수 모두에 비례하게 되며, 대규모 데이터를 처리할 때 매우 시간이 많이 소요됩니다.

 

 이 문제를 해결하기 위한 직관적인 아이디어는 데이터 instance와 feature 수를 줄이는 것입니다. 하지만 이는 간단한 문제가 아닙니다. (👀2) 예를 들어, GBDT에서 데이터 샘플링을 수행하는 방법이 명확하지 않습니다. 부스팅의 학습 과정을 가속화하기 위해 데이터를 그들의 가중치에 따라 샘플링하는 일부 연구들이 있지만, 이 방법들은 GBDT에 직접적으로 적용될 수 없습니다. GBDT에는 기본적으로 샘플 가중치가 없기 때문입니다.

 

 이 논문에서는 이 목표를 달성하기 위한 두 가지 새로운 기술, Gradient-based One-Side Sampling (GOSS)과 Exclusive Feature Bundling (EFB)을 제안합니다.

 

 Gradient-based One-Side Sampling (GOSS). GBDT에는 데이터 인스턴스에 대한 기본적인 가중치가 없지만, 우리는 서로 다른 기울기(gradient)를 가진 데이터 인스턴스들이 정보 이득 계산에서 서로 다른 역할을 한다는 점에 주목합니다. 특히, 정보 이득의 정의에 따르면, 더 큰 기울기를 가진 데이터 인스턴스들(즉, 덜 학습된 인스턴스들)이 정보 이득에 더 크게 기여합니다. 따라서 데이터 인스턴스를 샘플링할 때, 정보 이득 추정의 정확성을 유지하려면, 더 큰 기울기를 가진 인스턴스들은 유지하고, 더 작은 기울기를 가진 인스턴스들만 무작위로 제거하는 것이 좋습니다. 우리는 동일한 목표 샘플링 비율을 사용할 때, 이러한 방식이 균일한 무작위 샘플링보다 더 정확한 정보 이득 추정을 제공할 수 있음을 증명했습니다. 특히 정보 이득의 값 범위가 클 때 이러한 방식이 더 효과적입니다.

 

Exclusive Feature Bundling (EFB). 실제 응용에서, 많은 특징(feature)이 있지만 특징 공간은 매우 희소한 경우가 많습니다. 이러한 희소성은 우리가 효과적인 특징 수를 거의 손실 없이 줄일 수 있는 가능성을 제공합니다. 구체적으로, 희소한 특징 공간에서는 많은 특징들이 상호 배타적(exclusive)이며, 즉 이 특징들이 동시에 0이 아닌 값을 가질 가능성이 거의 없습니다. 예를 들어, 텍스트 마이닝에서 사용되는 원-핫 인코딩(one-hot encoding) 특징들이 이에 해당합니다. 우리는 이러한 상호 배타적인 특징들을 안전하게 묶을 수 있습니다. 이를 위해, 우리는 최적의 묶음을 찾는 문제를 그래프 색칠 문제(graph coloring problem)로 변환하고(특징을 정점으로 보고, 상호 배타적이지 않은 특징들 사이에 간선을 추가), 상수 근사 비율을 가진 탐욕 알고리즘(greedy algorithm)을 사용하여 해결하는 효율적인 알고리즘을 설계했습니다.

 

우리는 GOSS와 EFB를 적용한 새로운 GBDT 알고리즘을 LightGBM이라고 부릅니다. 여러 공공 데이터셋에 대한 실험 결과, LightGBM은 기존 GBDT의 학습 과정을 최대 20배까지 가속하면서도 거의 동일한 정확도를 달성할 수 있음을 보여줍니다.

 

이 논문의 나머지 부분은 다음과 같이 구성되어 있습니다. 먼저, 2장에서는 GBDT 알고리즘과 관련 연구를 검토합니다. 그 다음, 3장에서 GOSS의 세부 사항을, 4장에서 EFB의 세부 사항을 소개합니다. 5장에서는 LightGBM에 대한 실험 결과를 제시합니다. 마지막으로, 6장에서 논문을 마무리합니다.

 

💛 1. Gradient Boosting 프레임워크 기반의 알고리즘입니다.

 

tree의 분할 과정에서 목표는 leaf-node에서 잔차를 최소화 하는 것

모델 학습은 각 tree는 데이터의 특징을 기준으로 이진 분할을 반복하며, 각 단계에서 모델이 학습하지 못한 잔차를 줄여나가는 방식으로 개선됩니다.

 

https://blog-ko.superb-ai.com/algorithm-in-3-minutes-gradient-boosting-model/

[3분 알고리즘] 그라디언트 부스팅

 

 

 

(👀1) GDBT가 무엇인가?

1. 결정 트리(Decision Tree)란 ?

 

decision tree는 반복적인 binary split을 통해 데이터를 학습합니다.

 

트리는 데이터의 여러 특징 중 중요한 특징 (feature) 하나를 선택해 데이터를 두 그룹으로 나누는 과정을 반복합니다. 각 node에서 데이터를 나눌 때에는 (=feature를 선택 할 때는) 데이터를 가장 잘 분리할 수 있는 feature를 선택하는데, 이 때 불순도를 기준으로 결정합니다. 불순도는 information gain, gini impurity, entropy 등의 지표를 사용하여 측정 할 수 있습니다.

 

트리는 불순도가 더이상 유의미하게 줄어들지 않거나 최소 노드 크기에 도달하면 분할을  멈춥니다. 이 때 더 이상 나눌 수 없는 노드를 leaf node라고 하며, 이 leaf node에 속한 데이터의 평균값(회귀모델) 또는 다수결(분류모델)을 예측값으로 사용합니다.

 

 

 

(👀2) GBDT에는 기본적으로 샘플 가중치가 없는 이유?

1. 부스팅(Boosting)이란?

 

부스팅은 여러 개의 weak model(보통은 작은 의사결정 나무들)을 결합하여 더 강력한 모델을 만드는 앙상블 학습 기법입니다. 부스팅의 핵심 아이디어는 연속적으로 모델을 학습하면서, 이전 모델이 틀린 부분을 개선하는 방식으로 진행된다는 것입니다.

 

이 과정에서, 부스팅은 학습할 때 데이터 instance 에 가중치를 부여하여, 틀린 예측을 더 많이 신경 쓰도록 합니다. 예를 들어, 처음 학습한 모델이 잘못 예측한 데이터 에는 더 높은 가중치를 주어, 다음 모델이 이 데이터를 더 잘 맞출 수 있도록 합니다.

 

2. 부스팅에서의 가중치 기반 샘플링

데이터 instance 마다 weight를 부여하는 방식은 부스팅의 중요한 요소입니다. 데이터를 샘플링할 때도 이 가중치를 활용할 수 있습니다. 즉, 가중치가 높은 데이터(즉, 이전 모델에서 잘못 예측된 데이터)를 더 자주 샘플링하여 모델이 그 데이터를 더 집중해서 학습하도록 하는 것입니다.

 

이를 통해 학습 속도를 가속화할 수 있습니다. 왜냐하면, 중요한 데이터에 집중함으로써 불필요한 데이터에 시간을 낭비하지 않고 더 효율적으로 학습할 수 있기 때문입니다.

 

3. GBDT에서 샘플 가중치가 없는 이유

하지만 GBDT는 부스팅의 한 형태임에도 불구하고, 데이터 instance에 명시적인 가중치가 부여되지 않는 방식으로 설계되어 있습니다. GBDT는 부스팅의 개념을 사용하지만, 기본적으로 각 데이터마다 따로 가중치를 두고 학습하는 것이 아니라, 각 iteration마다 모델이 예측한 오류(gradient)를 기반으로 새로운 의사결정 나무를 학습시킵니다.

 

GBDT에서는 부스팅의 학습 과정에서 모델이 틀린 부분을 보완하는 방식으로 동작하지만, 그 과정에서 데이터를 개별적으로 가중치를 주고 샘플링하는 과정은 포함되지 않습니다. 즉, 부스팅의 다른 방식에서는 가중치(weight)가 명시적으로 존재하지만, GBDT에서는 그런 가중치가 없기 때문에, 부스팅에서 사용하던 가중치 기반 샘플링 기법을 그대로 적용할 수 없는 것이죠.

 

4. 그럼 GBDT는 어떻게 학습을 개선할까?

GBDT는 명시적인 샘플 가중치 대신 잔차(residual error), 또는 **기울기(gradient)**를 사용합니다. 각 반복마다 이전 모델의 예측 오차를 계산하고, 이를 바탕으로 새로운 의사결정 나무를 학습합니다. 이 과정에서 틀린 예측에 더 집중하게 되지만, 이는 부스팅에서처럼 명시적인 가중치를 사용하지 않고, 오차를 반영한 기울기로 처리됩니다.

 

 

 

💛 2. leef-wise splitting 방식으로 대규모 데이터셋에서 더욱 효율적입니다.

leef-wise splitting이란 각 iteration에서 최대한의 잔차 감소를 이끌어내는 방식으로 트리를 성장시킵니다.이는 기존 level-wise 트리 성장 전략보다 더 깊고 불균형한 트리를 생성할 수 있습니다.

 

참고로 일반적으로는 level-wise로 트리를 확장 해 나갑니다.  

 

💛 3. histogram-based binning 기법으로 대용량 데이터에서 효율적(속도, 메모리)입니다.

분할 기준을 빠르게 찾을 수 있습니다. 또한 대용량 데이터에서 메모리 사용량을 줄이고 속도 또한 크게 향상됩니다. 

💜 3. GOSS 💜 

 

💜 4. Exclusive Feature Bundling 💜

💛 maxax-depth 대신 max-leaf-node를 제한하는 방식으로 모형의 overfitting을 방지합니다.

💛 CART(Classification and Regression Tree) 구조의 트리를 사용하여 분류와 회귀 문제에 모두 적용 할 수 있습니다.

💛 L2 normalization을 통해 모델의 복잡도를 제어합니다.

💛 learning-rate를 통해 대규모 데이터셋에서 빠르게 수렴하는 특성을 지닙니다.

 

💜 5. Experiment💜

💜 6. Conclusion💜