LightGBM 개요

LightGBM은 트리 기반 학습 알고리즘을 사용하는 그래디언트 부스팅 프레임워크입니다.
다음과 같은 이점이 있는 효율적이고 잘 분산되도록 설계된 알고리즘입니다.

 

• 더 빠른 훈련 속도와 더 높은 효율성
• 메모리 사용량 감소
• 더 좋은 정확도
• 병렬, 분산 및 GPU 학습 지원
• 대규모 데이터 처리 가능

 

---

LightGBM 특징

LightGBM의 작동 방식에 대해 개념적으로 간단히 설명드릴게요. 다른 부스팅 패키지와 다를 수 있는 LightGBM의 측면에 초점을 맞추기 위해 의사결정 트리 부스팅 알고리즘에 익숙하다고 가정할게요.

자세한 알고리즘은 인용 또는 소스 코드를 참고하시면 돼요.

 

<속도 및 메모리 사용량 최적화>

많은 부스팅 도구는 의사 결정 트리 학습을 위해 사전 정렬 기반 알고리즘(예: xgboost의 기본 알고리즘)을 사용합니다. 간단한 솔루션이지만 최적화하기가 쉽지 않죠. 

 

LightGBM은 히스토그램 기반 알고리즘을 사용하여 연속적인 feature(속성) 값을 개별 빈으로 그룹핑합니다.

이렇게 하면 훈련 속도가 빨라지고 메모리 사용량이 줄어듭니다. 히스토그램 기반 알고리즘의 장점은 다음과 같습니다.

 

1. 각 분할에 대한 이득 계산 비용 절감

• 사전 정렬 기반 알고리즘에는 시간 복잡도가 있습니다.
• 히스토그램 계산은 시간 복잡도 O(#data)를 갖지만, 이것은 빠른 합산 연산만을 포함합니다. 히스토그램이 구성되면 히스토그램 기반 알고리즘은 시간 복잡도 O(#bins)를 가지며 #bins는 #data보다 훨씬 작습니다. 

2. 추가 속도 향상을 위해 히스토그램 빼기 사용

• 이진 트리에서 한 잎의 히스토그램을 얻으려면 부모와 이웃의 히스토그램 빼기 사용
• 따라서 하나의 리프(이웃보다 #data가 작은)에 대해서만 히스토그램을 구성해야 합니다. 그런 다음 적은 비용(O(#bins))으로 히스토그램 빼기로 이웃의 히스토그램을 얻을 수 있습니다.

3. 메모리 사용량 줄이기

• 연속 값을 이산 빈으로 대체합니다. #bins가 작으면 훈련 데이터를 저장하기 위해 작은 데이터 유형을 사용할 수 있습니다. 
• feature 값을 사전 정렬하기 위해 추가 정보를 저장할 필요가 없습니다.

 

<희소 최적화>

• 희소 feature에 대한 히스토그램을 구성하려면 O(2 * #non_zero_data)만 필요합니다.

 

<정확도 최적화>

리프 방식(최상 우선) 트리 성장

대부분의 의사결정 트리 학습 알고리즘은 다음 이미지와 같이 레벨(깊이) 별로 트리를 성장시킵니다.

LightGBM은 나무를 잎사귀로 자라게 합니다.(최상 우선). 최대 델타 손실이 있는 잎을 선택하여 분할합니다. #leaf 고정된 상태로 유지하는 leaf-wise 알고리즘은 level-wise 알고리즘보다 더 낮은 손실을 달성하는 경향이 있습니다.

 

Leaf-wise는 #data가 작을 때 과적합을 유발할 수 있으므로 LightGBM에는 트리 깊이를 제한하기 위해 max_depth 매개변수가 포함됩니다. 그러나 max_depth가 지정된 경우에도 나무는 여전히 잎 방향으로 자랍니다.

 

범주형 feature에 대한 최적 분할

원-핫 인코딩으로 범주형 기능을 표현하는 것이 일반적이지만 이 접근 방식은 트리 학습자에게 차선책입니다. 특히 카디널리티가 높은 범주형 기능의 경우 원-핫 기능을 기반으로 구축된 트리는 균형이 맞지 않는 경향이 있으며 우수한 정확도를 달성하기 위해 매우 깊이 성장해야 합니다.

 

원-핫 인코딩 대신에 최적의 솔루션은 범주를 2개의 하위 집합으로 분할하여 범주 기능을 분할하는 것입니다. feature에 k개의 범주가 있는 경우 2^(k-1) - 1개의 가능한 파티션이 있습니다. 그러나 회귀 트리에 대한 효율적인 솔루션이 있습니다. 최적의 파티션을 찾기 위해서는 O(k * log(k)) 정도가 필요합니다.

 

기본 아이디어는 각 분할에서 훈련 목표에 따라 범주를 정렬하는 것입니다. 보다 구체적으로, LightGBM은 누적된 값(sum_gradient / sum_hessian)에 따라 히스토그램(범주형 기능의 경우)을 정렬한 다음 정렬된 히스토그램에서 최상의 분할을 찾습니다.

 

<네트워크 통신 최적화>

LightGBM의 분산 학습에서 "All Reduce", "All gather" 및 "Reduce scatter"와 같은 일부 집합적 통신 알고리즘만 사용하면 됩니다. LightGBM은 최신 알고리즘을 구현합니다. 이러한 집합적 통신 알고리즘은 지점 간 통신보다 훨씬 더 나은 성능을 제공할 수 있습니다.

 

<분산 학습의 최적화>

LightGBM은 다음과 같은 분산 학습 알고리즘을 제공합니다.

 

Feature Parallel

전통적인 알고리즘

Feature Parallel은 의사 결정 트리에서 "최상의 분할 찾기"를 병렬화하는 것을 목표로 합니다. 기존 Feature Parallel의 절차는 다음과 같습니다.

1. 데이터를 수직으로 분할합니다(머신마다 feature set이 다름).
2. 작업자는 로컬 feature set에서 로컬 최상의 분할 지점 {feature, threshold}을 찾습니다.
3. 로컬 최고의 스플릿을 서로 소통하고 최고의 스플릿을 얻습니다.
4. 가장 잘 분할된 작업자가 분할을 수행한 다음 데이터의 분할 결과를 다른 작업자에게 보냅니다.
5. 다른 작업자는 수신된 데이터에 따라 데이터를 분할합니다.

기존 기능 병렬의 단점: 

• 시간 복잡도가 O(#data)인 "분할" 속도를 높일 수 없기 때문에 계산 오버헤드가 있습니다. 따라서 #data가 클 때 기능 병렬 속도가 잘 향상되지 않습니다.
• 분할 결과의 통신이 필요하며 비용은 O(#data / 8)(하나의 데이터에 대해 1비트)입니다.

 

Feature Parallel in LightGBM

#data가 클 때 기능 병렬 속도가 잘 향상되지 않으므로 약간 변경합니다. 데이터를 수직으로 분할하는 대신 모든 작업자가 전체 데이터를 보유합니다. 따라서 LightGBM은 모든 작업자가 데이터 분할 방법을 알고 있으므로 데이터 분할 결과에 대해 통신할 필요가 없습니다. 그리고 #data는 더 크지 않으므로 모든 시스템에 전체 데이터를 보관하는 것이 합리적입니다.

 

LightGBM의 병렬 기능 절차:

1. 작업자는 로컬 기능 세트에서 로컬 최상의 분할 지점 {feature, threshold}을 찾습니다.
2. 지역 최고의 스플릿을 서로 소통하고 최고의 스플릿을 얻습니다.
3. 최상의 분할을 수행합니다.

그러나 이 기능 병렬 알고리즘은 #data가 클 때 "분할"에 대한 계산 오버헤드가 여전히 발생합니다. 따라서 #data가 클 때 데이터를 병렬로 사용하는 것이 좋습니다.

 

Data Parallel

전통적인 알고리즘

데이터 병렬은 전체 의사결정 학습을 병렬화하는 것을 목표로 합니다. 데이터 병렬 절차는 다음과 같습니다.

1. 데이터를 수평으로 분할합니다.
2. 작업자는 로컬 데이터를 사용하여 로컬 히스토그램을 구성합니다.
3. 모든 로컬 히스토그램의 글로벌 히스토그램을 병합합니다.
4. 병합된 전역 히스토그램에서 최상의 분할을 찾은 다음 분할을 수행합니다.

기존 데이터 병렬의 단점:

• 높은 통신 비용. point-to-point 통신 알고리즘을 사용할 경우 한 기계에 대한 통신 비용은 약 O(#machine * #feature * #bin) 정도입니다. 집합 통신 알고리즘(예: "All Reduce")을 사용하는 경우 통신 비용은 약 O(2 * #feature * #bin)입니다.

Data Parallel in LightGBM

LightGBM에서 병렬 데이터의 통신 비용을 줄입니다.

1. "모든 로컬 히스토그램의 전역 히스토그램 병합" 대신 LightGBM은 "분산 감소"를 사용하여 다른 작업자에 대한 서로 다른(중첩되지 않은) 기능의 히스토그램을 병합합니다. 그런 다음 작업자는 로컬 병합 히스토그램에서 로컬 최적 분할을 찾고 전역 최적 분할을 동기화합니다.
2. 앞서 언급했듯이 LightGBM은 히스토그램 빼기를 사용하여 훈련 속도를 높입니다. 이를 기반으로 우리는 하나의 잎에 대해서만 히스토그램을 전달할 수 있으며, 빼기로 이웃의 히스토그램도 얻을 수 있습니다.

모든 것을 고려하면 LightGBM에서 병렬 데이터는 시간 복잡도 O(0.5 * #feature * #bin)를 갖습니다.

 

Voting Parallel

병렬 투표는 Data Parallel의 통신 비용을 일정 비용으로 더욱 줄여줍니다. feature 히스토그램의 통신 비용을 줄이기 위해 2단계 투표를 사용합니다. 

 

<GPU 지원>

 

 

<애플리케이션 및 측정항목>

LightGBM은 다음 애플리케이션을 지원합니다.

• 회귀, 목적 함수는 L2 손실입니다.
• 이진 분류, 목적 함수는 logloss입니다.
• 다중 분류
• 교차 엔트로피, 목적 함수는 logloss이고 비 이진 레이블에 대한 training 지원합니다.
• LambdaRank, 목적 함수는 NDCG가 있는 LambdaRank입니다.

LightGBM은 다음 측정항목을 지원합니다.

• L1 loss
• L2 loss
• Log loss
• Classification error rate
• AUC
• NDCG
• MAP
• Multi-class log loss
• Multi-class error rate
• AUC-mu (new in v3.0.0)
• Average precision (new in v3.1.0)
• Fair
• Huber
• Poisson
• Quantile
• MAPE
• Kullback-Leibler
• Gamma
• Tweedie

<다른 특징들>

• 나무가 잎 방향으로 자라는 동안 나무의 max_depth를 제한
• DART
• L1/L2 regularization
• Bagging
• Column (feature) sub-sample
• Continued train with input GBDT model
• Continued train with the input score file
• Weighted training
• Validation metric output during training
• Multiple validation data
• Multiple metrics
• Early stopping (both training and prediction)
• Prediction for leaf index