Light GBM

이전에 소개했던 XGBoost에 이어서 Light GBM에 대해 정리해보려고 한다.

출처 : 이 글은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.

 

1. Light GBM

1.1 Motivation

전동적일 GBM은 모든 데이터의 모든 피처를 탐색후 정보 획득률을 조사한다. 모든 데이터에대한 탐색을 효율적으로 수행하기 위해 XGBoost와 같은 경우 데이터를 버켓(bucket)으로 나누어 탐색을 수행하는 Approximate 알고리즘을 사용하였다. Light GBM은 모든 데이터에 대한 탐색과 모든 피처에 대한 완전 탐색을 완화하기 위해 고안되었다.

 

1.2 idea

Gradient-based One-Side Sampling(GOSS)

개별적인 데이터는 일반적으로 서로 다른 그레디언트를 가지고 있다. 서로 다른 그레디언트를 가지고 있는 데이터는 각각 split을 함에 있어 서로 다른 역할을 하게 된다.

그레디언트가 큰 데이터의 경우엔 keep하고, 그레디언트가 작은 데이터의 경우엔 랜덤 하게 drop 한다.

GBM의 경우 그레디언트가 크다 의미는 잔차가 크다는 의미이다. Adaboost와의 차이점은 잔차가 작은 데이터 즉 이미 분류기가 잘 분류할 수 있는 데이터를 유지하는 것이 아닌 랜덤 한 비율로 버린다는 것이 차이점이다.

 

Exclusive Feature Bunding(EFB)

원핫 인코딩과같이 feature space가 sparse한 경우엔 거의 exclusive하다.  exclusive - 두개 이상의 변수들이 0이 아닌 값을 동시에 가질 가능성이 매우 낮은 변수들이 많이 존재한다. 원핫 인코딩은 어떤 두 개의 조합도 0이 아닌 경우를 동시에 가지는 경우는 없다.

서로 exclusive 한 피처를 하나의 피처로 묶는다(Bunding).

 exclusive 한 특징을 가지는 피처도 간혹 두 피처가 값을 갖는경우가 있는 위험을 감수하지만, 완전히 서로 exclusive한 피처들을 하나의 피처로 묶는다고 해서 성능 저하는 전혀 일어나지 않을 것이다.

 

 

1.3 Gradient-based One-Side Sampling(GOSS)

아래 그림을 통해 GOSS에 대해 이해해보자.

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

GOSS는 매우 간단하다. 높은 그레디언트를 갖는 데이터는 a 만큼 사용하지만 그레디언트가 작은 b만큼의 데이터는 랜덤 하게 사용한다는 의미이다. 1 - a / b를 1보다 크도록 하면 그 효과가 극명하게 들어간다.

예를 들어 상위 10퍼센트의 그레디언트는 그대로 사용하고 하위 90퍼센트의 그레디언트를 가지는 데이터를 무작위로 추출한다고 가정하자, 이때 a = 0.1, b = 0.9가 되고 1 - a / b를 계산해보면 1이 될 것이다.

만약 상위 5퍼센트의 그레디언트는 그대로 사용하고 하위 50퍼센트의 그레디언트를 가지는 데이터를 무작위로 추출한다고 가정해보자, 이때 a = 0.05, b = 0.5가 되고, 1 - a / b를 계산해보면 1.9가 된다. 

 

위와 같이 GOSS는 매우 간단한 방법이지만 하이퍼 파라미터 a, b를 적절히 사용해야 한다.

 

1.4 Exclusive Feature Bundling(EFB)

 

먼저 EFB를 이해하기 위해 아래 그림을 보자.

위 그림에서 그래프의 노드는 피처를 나타내고 엣지는 피처 간의 충돌을 나타낸다. 서로 충돌하는 피처 다시 말해 exclusive하지 않은 피처는 묶이면 안 된다. 첫 번째 그림에서 서로 엣지로 이어져 있는 노드는 다른 색을 칠하고 엣지로 이어져 있지 않은 경우는 하나의 색으로 묶을 수 있다고 했을 때 4개의 색으로 표현할 수 있다. 즉 8개의 피처를 4개의 피처로 줄일 수 있다는 의미이다. 실제로 EFB는 위의 예시와 매우 흡사하게 동작한다.

 

EFB는 크게 Greedy Bundling과 Merge Exclusive Features 두 가지 과정으로 나뉜다. 조금 더 자세한 얘 시를 통해 EFB를 알아보도록 하자. 

 

Greedy Bundling

위 그림에서 왼쪽 테이블의 각 행은 데이터 열은 피처를 의미한다. 오른쪽 위의 테이블은 데이터의 피처 노드로, 충돌 강도를 엣지로 하여 그래프를 구성하도록 하는 테이블이다. 충돌 강도를 구하는 방법은 동일한 데이터의 서로 다른 두 개의 피처가 0 또는 null 값을 동시에 갖지 않는 데이터의 개수를 세어 구할 수 있다. 예를 들어 x1 피처와 x2피처 간의 충돌 강도는 6인데 왼쪽 데이터 데이블에서 x1피처와 x2피처가 둘 다 0을 갖지 않는 데이터는 6개가 된다. 

 

이 충돌 강도가 클수록 exclusive하지 않은 피처가 된다. 

 

이러한 방법으로 변수를 노드, 충돌 강도를 엣지로 하는 그래프 데이터를 표현할 수 있다.

 

오른쪽 아래의 테이블의 d는 degree를 의미하는데 greedy 한 방법이기 때문에 그 시작점을 degree를 가지고 시작하게 된다. degree는 각 노드의 충돌 강도를 전부 합한 값이 되며 이 degree를 내림차순 정렬하여 가장 충돌 강도가 큰 노드부터 처리한다.

 

이제 그래프를 구성하였으니 degree가 가장 큰 x5부터 시작하여 bundling을 수행하도록 한다.

이때 cuf-off라는 하이퍼 파라미터를 사용한다 이 예시에선 cuf-off가 0.2인 경우에 대해서 알아보도록 한다.

cuf-off가 0.2라는 것은 N=10일 때 10 * 2 = 2번 이상 충돌이 일어나면 bundling을 하지 않겠다는 의미이다.

 

cut-off가 0.2일 경우에 x5는 모든 피처와 충동 강도가 2 이상 이기 때문에 어떤 피처와도 bundling 되지 않는다.(엣지가 끊어진다.)

 

그다음 degree가 큰 x1, x2에 대해 bundling을 수행하면 위와 같은 결과를 얻을 수 있다.

greedy bundling을 수행하고 나면 5개인 feature가 x5, {x4, x1}, {x3, x2} 3개의 피처로 줄어들게 된다.

이후 bundling 된 피처에 값을 새로 할당하여야 하는데 이 과정은 Exclusive feature merging 방법을 통해 수행된다.

 

Exclusive feature merging

 

아래 예시를 보고 Exclusive feature merging을 이해해 보도록 하자.

Exclusive feature merging은 기준이 되는 피처를 정하고 기준 변수를 그대로 사용하거나, 기준 변수 이외의 변수에 기준 변수가 가질 수 있는 최댓값을 더해줌으로써 수행된다.  오른쪽 테이블은 Exclusive feature merging을 수행한 결과 테이블이다. x14의 값이 정해지는 과정을 살펴보자.

 

• 먼저 기준 변수를 x1으로 정한다.
• i1의 경우 기준 변수인 x1이 1이고 x4는 0의 값이다. 이경우 x14는 기준 변수 값을 그대로 사용한다.
• i2의 경우 기준 변수인 x1이 0이고 x4는 1이다. 이경우 x14는 x1이 가질 수 있는 최댓값 3을 x4의 값인 1에 더한 값인 4가 된다.(offset을 더함)
• i7의 경우는 기준 변수인 x1과 x4가 모두 0이므로 충돌이 일어난 경우이다. 이경우는 기준 변수 값을 그대로 사용한다.
• i8의 경우 기준 변수인 x1과 x4가 모두 값을 가지므로 충돌이 일어난 경우이다. 이경우는 기준 변수 값을 그대로 사용한다.

위와 같은 방법으로 Exclusive Feature Bundling을 수행한다.

이와 같이 충돌에 의해 데이터 손실이 일어날 수 있지만, cut-off를 적절히 설정 함으로써 피처 탐색을 더 효율적으로 수행할 수 있을 것이다.

 

---

마치며

Light GBM에 대해 정리해보았다.

Gradient-based One-Side Sampling(GOSS)과 Exculsive Feature Bundling(EFB)을 통해 GBM이 모든 데이터와 모든 피처를 완전 탐색하는데 생기는 비효율을 개선할 수 있다.

EFB는 결측 값이 많은 데이터 이거나 Feature의 종류가 많은 데이터일수록 좋은 성능을 낼 수 있을 것 같다.

XGBoost에서 Sparsity-Aware Split Finding 방법보다 좋다고 만은 볼 수 없을 것 같다.

XGboost와 Light GBM, CatBoost는 데이터의 형태에 따라 성능이 갈리기 때문에 데이터마다 적절한 모델을 사용하는 것이 중요하다.