[Boosting] Light GBM

• 목표: 대표적으로 많이 사용하는 Boosting 계열 Light Gradient Boosting Machine에 대해 공부한다.

- Light GBM이 나오기전 배경

• Boosting 계열로 성능이 약한 모델의 예측값에 대한 오차를 이용해 모델을 더욱 최적값으로 보완하며 성능을 높이는 방법이다.

- AdaBoost (Adaptive Boosting)

• Adaboost는 여러 개의 약한 학습기(weak learner)를 결합하여 강한 학습기(strong learner)를 만드는 알고리즘이다.
  
  • 다시 설명하면 이전 모델(weak learner)이 틀리게 예측한 값에 가중치를 부여하여 다음 모델이 틀린 부분에 대해 잘 맞추도록 한다. 
  • step마다 오차가 큰 데이터에 대해서는 큰 가중치를, 오차가 작은 데이터에 대해서는 작은 가중치를 부여한다.

 

Ada Boost

 

- Gradient Boosting Machine(GBM)

• AdaBoost에서는 이전 모델의 오차값을 통해 데이터에 가중치를 부여하여 다음 모델이 더 잘 분류하도록 했다면,  GBM에서는 정답과 모델의 예측값을 통해 Gradient를 계산하여 다음 모델을 조정하는 방식이다.
• 다시말해, GBM은 이전 모델의 예측값과 정답값의 차이를 Loss함수로 계산하고 Gradient를 계산하여 모델을 업데이트 하는 Gradient Descent를 사용한다. 

GBM, source:  https://medium.com/@hemashreekilari9/understanding-gradient-boosting-632939b98764

 

- Light GBM 설명

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

 

• 전통적으로 GBM계열(위에서 설명한 알고리즘 포함)의 알고리즘은 모든 Feature에 대해, 모든 Data에 대해 Scan하여 Gradient를 구하게 된다.
  • 하지만, 모든 Feature와 모든 Data에 대해 Gradient를 구하기 때문에 데이터의 크기가 커질수록 시간이 많이 소요 된다.
• Light GBM은 훈련 속도, 메모리 사용량을 줄이면서 성능을 높인 GBM이다.
  
  • Data instance 측면에서는 Goss 알고리즘을 이용  => 속도개선 
  • Feature 측면에서는 EFB 알고리즘 이용  => 속도개선

- GOSS (Gradient-based One-side Sampling) 

• Gradient게산에 참여하는 data instance수를 줄이는 방법 

source: https://cdm98.tistory.com/m/31

• Gradient를 기준으로 instance를 정렬 후, 왼쪽은 Small Gradient -> 잘 훈련된 것, 오른쪽 Large Gradient -> 덜 훈련된 것
• TopSet : Gradient가 높은 순서대로 상위 k개 
• RandSet : 나머지 (n-k) 개의 인스턴스에서 Randomly Drop을 수행한 것 
• TopSet과 RandSet을 합쳐서 다음에 학습에 사용

 

 

- EFB (Exclusive Feature Bunding) 

• Feature Bundling(feature들의 묶음)을 통해 복잡도를 낮추는 방법이다.
• idea: Feature의 차원이 늘어날수록 0의 값들이 많아지면서 Sparse한 데이터가 구성된다. 예를들어 두 feature가 0일 때 정보손실이 거의 없다는 반면, 둘다 수치값을 가질경우, 정보손실은 상대적으로 많이 발생한다. 하지만 차원이 늘어나면 둘다 0이 아닌 값을 가질 확률이 작기 때문에 각 Feature간에 0이 아닌 값을 가지는 경우에 집중한 효율적인 방법을 사용한다.

 

• 예시 

- 1-1. bundles로 묶을 수 있는 feature 식별

• 원본데이터 에서 각 feature별 degree 구하기 

• original data에서 Feature간에 0이 아닌 값을 함께 가지는 경우 Conflict라고 하며, 각 feature 사이 Conflict 수를 집계
• 집계된 Feature간의 Conflict의 총합을 계산 이렇게 계산된 각 Feature마다 구성된 값을 degree라고 하자.
• Degree 기준으로 내림차순 정렬

 

- 1-2 degree를 구한 이후 이 알고리즘 순서대로 설명

   

- 변수 설명 

• K(max conflict count): 각 Bundle에서 허용하는 최대 Conflict count를 정의 (K값이 클수록 더 많은 feature가 묶여 학습시간은 감소하지만, 손실은 증가)
• bundles : 번들을 저장할 변수를 선언 ,   bundlesConflict : 저장한 각 번들의 Conflict를 저장 할 변수 
• needNew = True : 새로 저장되어야 할 번들이 있는지 판단

수도 코드

수도 코드 따라 실행결과

- 2. Feature 병합 

• offset: 기준 feature에서 최대값 

feture 병합과정, feat2,feat3도 다음과 같은 과정으로 진행하고 나머지와 병합하면 이 알고리즘이 끝난다.

• 기준 feature(번들내 degree 최대값)로 feature 병합하는 이유: 
  • degreer가 높다는 것은 다른 feature들과 충돌이 많이 일어났으므로 해당 feature정보를 최대한 유지한 채로 상대적으로 덜 충돌이 일어난 feature의 정보를 손실시키면 feture병합을 했을 때 정보손실이 덜 일어난다. 

 

- LGM 실혐 결과 

• DataSet

Table 1: Datasets used in the experiments

• 모델별 속도 비교 결과 
  • LightGBM : Goss + EFB 알고리즘 합친것으로 속도가 빠른것을 확인할 수 있다. 

Table 2: Overall training time cost comparison. LightGBM is lgb_baseline with GOSS and EFB. EFB_only is lgb_baseline with EFB. The values in the table are the average time cost (seconds) for training one iteration.

• 모델별 정확도 
  • LightGBM의 정확도가 다른 모델에 비해 높은것을 확인할 수 있다.