LightGBM 특징

LightGBM 특징 (Features)

LightGBM이 어떻게 동작하는지 개념적으로 살펴보는 문서예요. 의사결정 트리 부스팅 알고리즘에 익숙하다고 가정하고, 다른 부스팅 패키지와 다른 LightGBM의 측면에 집중해요. 자세한 알고리즘은 인용문이나 소스 코드를 참조하면 돼요.

출처: LightGBM Features

속도와 메모리 사용 최적화

많은 부스팅 도구는 의사결정 트리 학습에 pre-sort 기반 알고리즘(예: xgboost의 기본 알고리즘)을 사용해요. 간단한 해법이지만 최적화하기 쉽지 않죠.

LightGBM은 히스토그램 기반 알고리즘을 사용해 연속 피처 값을 이산 빈(bin)으로 묶어요. 이 방식은 학습을 빠르게 하고 메모리 사용을 줄여요. 장점은 이래요.

  • 각 분할의 이득 계산 비용 감소: pre-sort 알고리즘은 O(#data) 시간 복잡도. 히스토그램 계산은 O(#data)지만 빠른 합산 연산만 포함하고, 히스토그램이 구성되면 O(#bins)이고 #bins는 #data보다 훨씬 작아요.
  • 히스토그램 뺄셈으로 추가 가속: 이진 트리에서 한 리프의 히스토그램을 얻으려면 부모와 이웃의 히스토그램 뺄셈을 사용해요. 그래서 리프 하나(이웃보다 #data가 작은 쪽)만 히스토그램을 구성하면 돼요.
  • 메모리 사용 감소: 연속 값을 이산 빈으로 대체해요. #bins가 작으면 uint8_t 같은 작은 데이터 타입으로 학습 데이터를 저장할 수 있어요.
  • 분산 학습의 통신 비용 감소.

희소 최적화

희소 피처의 히스토그램은 O(2*#non_zero_data)만 필요해요.

정확도 최적화

리프 중심(leaf-wise) 트리 성장

대부분의 의사결정 트리 알고리즘은 레벨(깊이) 중심으로 트리를 키워요. 반면 LightGBM은 리프 중심(best-first)으로 트리를 키워요. 손실 변화(delta loss)가 가장 큰 리프를 골라 성장시키죠. #leaf를 고정하면 리프 중심 알고리즘이 레벨 중심보다 낮은 손실을 달성하는 경향이 있어요.

리프 중심은 #data가 작을 때 과적합될 수 있어서 LightGBM은 max_depth 파라미터로 트리 깊이를 제한해요. 다만 max_depth를 지정해도 트리는 여전히 리프 중심으로 성장해요.

범주형 피처의 최적 분할

범주형 피처를 one-hot 인코딩으로 표현하는 게 흔한데, 트리 학습자에게는 최적이 아니에요. 특히 고차원 범주형 피처에서 one-hot 트리는 불균형해지고 깊이를 깊게 키워야 정확도가 나와요. 대신 범주형 피처의 범주를 2개 부분집합으로 나눠 분할하는 게 최적이에요.

k개의 범주가 있으면 2^(k-1)-1개의 가능한 분할이 있는데, 회귀 트리에는 효율적인 해법이 있어 O(k*log(k))로 최적 분할을 찾아요. 기본 아이디어는 각 분할에서 학습 목적에 따라 범주를 정렬하는 거예요.

분산 학습 최적화

LightGBM 분산 학습은 "All reduce", "All gather", "Reduce scatter" 같은 집단 통신 알고리즘만 사용해요. point-to-point 통신보다 훨씬 나은 성능을 제공하죠. 피처 병렬·데이터 병렬·투표 병렬 알고리즘을 제공해요.

  • 피처 병렬(feature parallel): "Find Best Split"을 병렬화. LightGBM은 데이터를 세로로 나누지 않고 모든 워커가 전체 데이터를 보유해서, #data가 커도 데이터 분할 결과를 통신할 필요가 없어요.
  • 데이터 병렬(data parallel): 전체 의사결정 학습을 병렬화. LightGBM은 "Reduce Scatter"로 서로 다른(겹치지 않는) 피처의 히스토그램을 병합하고, 히스토그램 뺄셈으로 리프 하나만 통신해 시간 복잡도 O(0.5*#feature*#bin)를 달성해요.
  • 투표 병렬(voting parallel): 데이터 병렬 통신 비용을 상수 비용으로 줄여요. 두 단계 투표로 피처 히스토그램 통신을 줄여요.

애플리케이션과 메트릭

LightGBM이 지원하는 애플리케이션은 다음과 같아요: 회귀(L2 손실), 이진 분류(logloss), 다중 분류, 크로스 엔트로피(비이진 레이블 학습 지원), LambdaRank(NDCG 포함). 지원 메트릭은 L1·L2 손실, 로그 손실, 분류 오차율, AUC, NDCG, MAP, 다중 클래스 로그 손실, 다중 클래스 오차율, Fair, Huber, Poisson, Quantile, MAPE, Kullback-Leibler, Gamma, Tweedie 등이에요.

더 알아보기