📝 LightGBM: A Highly Efficient Gradient Boosting
Decision Tree
Abstract
-
특징(Feature) 차원이 높고 데이터 크기가 클 경우 여전히 효율성과 확장성이 만족스럽지 않음
-
Gradient-based One-Side Sampling (GOSS)와 Exclusive Feature Bundling (EFB)
두 가지 기법을 제안 -
LightGBM은 기존 GBDT보다 최대 20배 이상 학습 속도를 향상
1 Introduction
-
Gradient-based One-Side Sampling (GOSS)
-
데이터 인스턴스에 대한 고유한 가중치(weight)가 존재하지 않음
-
기울기가 큰 데이터 인스턴스(즉, 덜 학습된 데이터 인스턴스)가 정보 이득에 더 많은 기여를 함
-
데이터 인스턴스를 샘플링할 때, 정보 이득 추정 정확도를 유지하려면 기울기가 큰 데이터 인스턴스를 유지해야 함
-
정보 이득 값의 범위가 넓을 때, GOSS 방식이 더욱 효과적
-
-
Exclusive Feature Bundling (EFB)
-
희소한 특징 공간에서는 서로 배타적인 특징이 많음
-
동시에 0이 아닌 값을 가지는 경우가 거의 없는 특징들이 존재
-
최적의 특징 번들링(optimal feature bundling)문제를 그래프 색칠 문제(graph coloring problem)로 변환하여 해결하는 효율적인 알고리즘을 설계함
-
-
LightGBM
-
GOSS와 EFB 기법을 적용한 새로운 GBDT 알고리즘
-
기존 GBDT 대비 최대 20배 이상의 학습 속도 향상을 달성하면서도, 거의 동일한 정확도를 유지
-
2 Preliminaries
2.1 GBDT and Its Complexity Analysis
GBDT(Gradient Boosting Decision Tree)는 의사결정 나무(Decision Tree)들을 순차적으로 학습하는 앙상블 모델이다. 각 반복(iteration)에서 GBDT는 음의 그래디언트(negative gradient, 즉 잔차 오차 residual errors)를 학습하여 새로운 결정 트리를 생성한다.
GBDT에서 가장 큰 연산 비용이 드는 부분은 결정 트리를 학습하는 과정이다. 그 중에서도 가장 시간 소모가 큰 부분은 최적의 분할 지점을 찾는 과정이다. 이 과정에서 가장 널리 사용되는 알고리즘은 사전 정렬(pre-sorted) 알고리즘이다. 특징(feature) 값들을 미리 정렬한 후, 모든 가능한 분할 지점을 하나씩 평가하는 방식이다.
다른 대안으로 히스토그램 기반(histogram-based) 알고리즘이 있다. 이 알고리즘은 연속적인 특징 값을 이산적인(bin) 구간으로 버킷팅(bucketing)하여 히스토그램을 구축한다.
2.2 Related Work
GBDT는 다양한 구현 방식이 존재하며, 대표적인 것들은 다음과 같다.
XGBoost (사전 정렬 / 히스토그램 기반 알고리즘)
pGBRT (히스토그램 기반(histogram-based) 알고리즘)
scikit-learn (사전 정렬(pre-sorted) 알고리즘)
R의 gbm 패키지 (사전 정렬(pre-sorted) 알고리즘)-
XGBoost는 다른 도구들보다 더 뛰어난 성능을 보이는 것으로 보고됨.
-
기존 샘플링 기법은 GBDT에 직접 적용하기 어렵고, 특징 선택 기법도 정확도를 저하시킬 수 있음.
-
희소한 데이터셋에서 히스토그램 기반 GBDT는 최적화가 어렵지만, GOSS와 EFB가 이를 해결할 수 있음.
3 SPLIT FINDING ALGORITHMS
3.1 Algorithm Description
-
그래디언트가 작은 데이터는 이미 잘 학습되었으므로 일부 무작위 샘플링을 수행하고, 그래디언트가 큰 데이터는 모두 유지함.
-
작은 그래디언트 샘플의 정보 이득 계산 시 보정 계수를 적용하여 데이터 분포 왜곡을 방지함.
3.2 Theoretical Analysis
-
GOSS는 전체 데이터가 아닌 샘플링된 데이터에서 정보 이득을 계산하여 연산량을 줄임.
-
근사 오차는 O(1/√n) 수준으로 감소하며, 단순 무작위 샘플링보다 성능이 우수함.
-
샘플링을 통한 모델 다양성 증가가 일반화 성능 향상에도 기여할 수 있음.
4 Exclusive Feature Bundling
-
NP-Hard 문제와 근사 해법
-
특징을 최소 개수의 번들로 묶는 문제는 NP-난해하며, 그래프 색칠 문제로 변환 후 탐욕적 알고리즘을 사용하여 해결함.
-
일부 충돌을 허용하면 번들 개수를 더욱 줄일 수 있어 계산 효율성이 높아짐.
-
-
특징 번들링 알고리즘
-
특징 간 충돌 정보를 기반으로 그래프를 구성하고, 차수가 높은 순서대로 번들을 생성하는 알고리즘을 설계함.
-
연산량을 줄이기 위해 그래프 없이 0이 아닌 값 개수를 기준으로 정렬하는 방법도 제안됨.
-
-
특징 번들 병합 방법
- 번들 내 개별 특징 값을 식별 가능하도록 오프셋을 추가하여 서로 다른 bin에 배치하는 방식으로 병합함.
-
추가적인 최적화
-
0이 아닌 값이 있는 데이터만 저장하는 테이블을 활용하여 히스토그램 계산 비용을 줄이는 기법을 제안함.
-
LightGBM에서 기본 기능으로 구현되어 있으며, EFB와 함께 사용할 수 있음.
-
