[Ensemble] Light GBM, 마이크로소프트의 부스팅

 

Light GBM, 마이크로소프트의 부스팅

Ensemble

 

 

---

 

 

GBM은 최적의 Information Gain을 갖기위해서 모든 split point를 살펴봐야했습니다. XGBoost에서는 전체데이터를 버킷단위로 나누고 버킷안에서 split point를 찾음으로써 워크로드를 줄였습니다. 

Light GBM에서는 이를 줄이기 위한 방법으로 GOSS와 EFB를 제시합니다.

논문을 같이보고싶으신 분은 여기를 클릭하세요

 

 

Abstract

GOSS (Gradient-Based One-Side Sampling)

일반적으로 개별적인 데이터들은 다른 Gradient를 갖고 있습니다. 여기서 Gradient가 큰 객체들은 더 중요한 역할을 합니다. 그래서 Information gain을 계산할 때, gradient가 작은 객체들은 일부를 배제하고 계산합니다. 데이터사이즈를 작게만들고 계산하는 것입니다.

 

EFB(Exclusive Feature Bundling)

Mutually exclusive(상호배반)인 feature들을 번들링합니다. 여기서 mutually exclusive하다는 뜻은 OneHot Encoding같은 경우를 말하는데, nonzero values를 동시에 갖는 경우가 매우 드문 것을 뜻합니다. 이러한 feature들을 번들링, 하나로 엮습니다. 간혹 nonzero values를 동시에 가질 수도 있을 때, 이는 exclusive하지 않으므로 문제가 발생할 수도 있습니다. 하지만 만약 완벽하게 exclusive하다면 성능에 전혀 문제가 없습니다.

 

 

 

 

GOSS (Gradient-Based One-Side Sampling)

gradient가 큰 객체는 information gain에 더 큰 영향을 미칩니다. 그러므로 다운샘플링을 할 때 더 정확한 Information Gain을 유지하기 위해선 반드시 gradient가 큰 객체를 유지해야 합니다. 그리고 gradient가 작은 객체들은 randomly drop하는 샘플링 기법입니다.

여기서 Histogram-based Algorithm(왼쪽)에서  Histogram-based라는 의미는 곧 버킷에 담는 것과 같은 의미로 XGBoost를 뜻하며, 오른쪽 Gradient-Based One-Side Sampling)과 비교를 위해서 같이 실어놓았습니다.

방법은 굉장히 간단합니다. 아래는 Algorithm 2에대한 설명입니다.

1. 먼저 Gradient를 크기 순으로 정렬한 뒤에, 

2. top $a \times 100%$를 뽑습니다. 데이터에서 gradient 상위 a 비율만큼은 전부 뽑는다는 말입니다.

3. 그리고 randomly samples $b\times100%$를 나머지 데이터에서 뽑습니다.

4. 이제 small gradient쪽에서 뽑은 객체들에서 information gain을 계산할 때 $\frac{1-a}{b}$를 곱해줘서 증폭시킵니다. 여기서 a와 b는 하이퍼 파라미터입니다. 예를 들어, a와 b가 0.2, 0.8이면 누락되는 데이터가 없이 모두 뽑습니다. 그럼 $\frac{1-0.2}{0.8}=1$입니다. 샘플링의 의미가 없어집니다. 반면, a는 0.2이고 b는 0.4일 때 $\frac{1-0.2}{0.4}=2$입니다. 2배만큼 증폭이 됩니다.

5. 이렇게 함으로써 원본데이터의 분산의 큰변화 없이 under-trained된 객체에 집중할 수 있게됩니다.

정리하자면, gradient가 상위(TOP $a$)인 객체들은 전부 뽑고, gradient가 상위에 속하지 못한 객체들은 Random하게 뽑아서 $\frac{1-a}{b}$만큼 증폭시켜 under-trained된 객체에 집중합니다. 하이퍼파라미터($a,b$) 어떻게 조정하느냐에 따라서 성능이 많이 달라지겠죠.

수학적인 내용은 생략하겠습니다.

 

 

 

EFB(Exclusive Feature Bundling)

항상 DESNSE 한 데이터면 너무 좋겠지만 현실에서는 SPARSE 한 데이터가 훨씬 많습니다. 이런 데이터일 때는 많은 feature가 (almost) exclusive합니다. one-hot 인코딩을 한 feature의 경우가 대표적인 예가 되겠죠. 이러한 Feature들을 번들로 묶는 것이 목적입니다.

EFB를 위해서는 두가지 알고리즘이 필요합니다. Algorithm 3에서는 Greedy Bundling을 하는데, 서로 충돌되는 부분이 있으면 한 번들로 묶지 않습니다. 아래 graph coloring으로 보겠습니다.

https://jeremykun.com/tag/graph-coloring/page/2/

graph coloring에서 가장 유명한 것은 각 지역끼리 인접하면 다른색이어야 한다는 예제일 것 입니다. 여기서도 같은 원리입니다. 만약 동시에 non-zero value가 가진다면 각 Feature는 완전하게 exclusive하다고 할 수 없습니다. 동시에 non-zero value를 가지는 feature끼리 선으로 잇고, 선이 이어져 있는 feature는 같은색으로 칠하지 않습니다. 예를들어 위의 그림처럼 20개의 feature가 표현이 되었다면, 노란색 [1,10,12,14,16]끼리 한 번들로 묶습니다. 총 20개의 feature에서 4개의 feature(red,blue, yellow, green)으로 줄일 수 있습니다. 만약 겹치는 것이 하나만 있으면 어떻할까요? 그래도 exclusive하지 못하니까 같은 번들로 엮지 못할까요? Algorithms 3에서 K라는 숫자가 보입니다. K라는 상수로 최대로 충돌할 수 있는 수를 제한해 줍니다. Feature에서 충돌하는 데이터가 K 이하인 수로 나타나면, 번들링이 가능해집니다.

1. weighted edges를 기반으로 Graph를 만듭니다. 여기서 weight는 feature사이에 conflict에 대한 값입니다.
2. 그래프의 데이터를 weight기준 내림차순으로 정렬합니다.
3. 각 feature를 확인하고 $\gamma$(maximal conflict rate)를 기준으로 번들에 넣습니다. 

이제 이렇게 번들링이 완료된 것을 가지고 Algorithms 4로 넘어갑니다. conflict된 부분은 기준변수로가져오고, 충돌되지 않은 부분들을 offset으로 구합니다. Algorithm 4에대한 이해를 돕기위해 예를 들어보겠습니다.

$x_1$과 $x_2$가 번들링될 때, $x_1$에서 데이터가 [0,1,2,...,10]까지 있고 $x_2$에서 데이터는 [0,1,2,...,20]까지 있습니다. 번들링 된 충돌되지 않은 데이터이므로 한 쪽이 0입니다.

왼쪽의 테이블은 $x_1$과 $x_2$가 Merge되어 $x_12$가 되는 과정입니다.

 

 

 

 

기준변수를 $x_1$으로 잡고 merge를 시킬 때 

$x_1$에 값이 있으면 $x_1$ 그대로 가져옵니다.

$x_2$에 값이 있으면 Offset을 더해서 넣습니다.

여기서 offset은 10이 됩니다. ($x_1$는 10까지있으므로)

만약 충돌된 값이 있으면 기준변수 $x_1$를 그대로 가져옵니다. (10번째)

Algorithms4에서는 이러한 방식으로 Merge를 하게됩니다.

 

여기서 충돌된 10번째 데이터 빼고는 손실되는 데이터가 없습니다.

 

 

 

 

 

 

Comparison

논문에서는 얼마나 다른 부스팅기법과 비교해서 얼마나 더 빨리 높은 score를 달성하였는지 표로나타냈습니다. XGBoost보다도 더 빨리 달 성했던 것을 보여주고 있습니다.

 

 

 

참고자료

Welcome to LightGBM’s documentation! — LightGBM 3.1.1.99 documentation