[LightGBM] Features (2)

네트워크 통신 최적화 (Optimization in Network Communication)

 

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

 

분산 학습 최적화 (Optimization in Distributed Learning)

 

LightGBM은 기능과 데이터 병렬 분산 학습 알고리즘을 제공한다.

 

기능 병렬 (Feature Parallel)

 

1. 전통적인 알고리즘 (Traditional Algorithm)

 

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

 

데이터를 수직으로 분할한다 (머신마다 기능 세트가 다름). 로컬 기능 세트에서 로컬 최상의 분할 지점 {feature, threshold}을 찾는다. 로컬 최고의 스플릿을 서로 소통하고 최고의 스플릿을 얻는다. 가장 잘 분할된 분할을 수행한 다음 데이터의 분할 결과를 보낸다. 수신된 데이터에 따라 데이터를 분할한다.

 

기존 기능 병렬의 단점:

 

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

 

2. LightGBM 병렬 기능

 

기능 병렬은 #data가 크면 속도가 잘 안 나기 때문에 약간 변경한다. 데이터를 수직으로 분할하는 대신 전체 데이터를 보유한다. 따라서, LightGBM은 데이터 분할 방법을 알고 있을 때 데이터 분할 결과에 대해 통신할 필요가 없다. #data가 더 크지 않으므로 모든 시스템에 전체 데이터를 보유하는 것이 합리적이다.

 

LightGBM의 병렬 기능 절차:

 

로컬 기능 세트에서 로컬 최상의 분할 지점 {feature, threshold}을 찾는다. 지역 최고의 스플릿을 서로 소통하고 최고의 스플릿을 얻는다. 최상의 분할을 수행한다.

 

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

 

데이터 병렬 (Data Parallel)

 

1. 전통적인 알고리즘 (Traditional Algorithm)

 

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

 

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

 

기존 데이터 병렬의 단점은 높은 통신 비용이다. point-to-point 통신 알고리즘을 사용하면 한 기계에 대한 통신 비용은 약 O(#machine * #feature * #bin)이고 집합 통신 알고리즘 (ex: "All Reduce")을 사용하는 경우 통신 비용은 약 O(2 * #feature * #bin)이다.

 

2. LightGBM 병렬 기능

 

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

 

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

 

모든 것을 고려하면 LightGBM의 병렬 데이터에는 시간 복잡도가 있다 .O(0.5 * #feature * #bin)

 

Voting Parallel

 

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

 

애플리케이션 및 측정항목

 

applications	regression, the objective function is L2 loss binary classification, the objective function is logloss multi classification cross-entropy, the objective function is logloss and supports training on non-binary labels LambdaRank, the objective function is LambdaRank with NDCG
metrics	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

 

https://lightgbm.readthedocs.io/en/latest/Features.html#optimization-in-speed-and-memory-usage

Features — LightGBM 3.3.2.99 documentation