[리뷰] LightGBM : A Highly Efficient Gradient Boosting Decision Tree

부스팅 모델 중에서 가장 흔히 쓰이는 세 가지가 XGBoost, CatBoost, 그리고 LightGBM일 것이다.(최근에는 다른 여러 부스팅 모델이 나온 것으로 알고 있다.)

 

XGBoost와 CatBoost에 대해선 이미 포스팅 했고, 이번엔 LigthGBM에 대해서 리뷰해보려고 한다. 

 

간단하게 설명해보면, 이름 그대로 light 가볍다라는 뜻이다. 이름만큼 규모가 큰 데이터에서 빠른 학습 속도로 유리함을 가지고 있다. Microsoft에서 개발한 그레디언트 부스팅 프레임워크로 쉽게 사용할 수 있다.

 

단, 규모가 비교적 작은 데이터에서는 과적합이 생길 수 있으므로 유의해서 사용하자.

 

📌 1. Introduction

 

기존에 GBDT(Gradient Boosting Decision Trees)는 모든 변수에 대해 가능한 모든 분할 지점의 정보 이득을 추정하기 위해 모든 훈련 인스턴스를 확인해야한다. 이에따라 구현의 계산 복잡도는 변수의 수와 인스턴스의 수 모두에 비례하게 되고, 빅데이터를 처리할 때 당연하게도 시간과 같은 자원이 더욱 필요하게 된다.

 

데이터 변수의 차원을 줄이거나 데이터 인스턴스의 수를 줄일 수 있지만 당연하게도 정보가 줄어들기 때문에 좋은 방안은 아니다.

 

그래서 본 논문에서는 크게 두 가지 새로운 기술을 제안한다. 1. 그레디언트 기반 단축 샘플링(GOSS, Gradient-based One-Side Sampling), 2. 베타적 특징 번들링(EFB, Exclusive Feature Bundling)

 

◼️ (1) 그레디언트 기반 단축 샘플링 (GOSS)

 

기존의 GBDT에서는 더 큰 그레디언트를 가진 인스턴스들(즉, 잔차가 더 크다는 뜻으로 충분히 학습되지 않은 인스턴스들)이 정보 이득에 더 많은 기여를 한다. 

 

따라서 데이터 인스턴스를 다운샘플링할 때, 정보 이득 추정의 정확성을 유지하기 위해서는 큰 그레디언트를 가진 인스턴스들을 유지하고, 작은 그레디언트를 가진 인스턴스들만 무작위로 제거하는 것이 더 좋다.

 

◼️ (2) 베타적 특징 번들링 (EFB)

 

일반적으로 실제 상황에서 많은 수의 변수들이 있지만 변수 공간이 매우 희소하고, 효과적인 변수의 수를 줄이기 위한 무손실 접근 방식을 설계할 수 있는 가능성을 제공한다.

 

이게 무슨 소리인가?? 예를 들어보자.

예를 들어, 온라인 쇼핑몰에서 고객이 구매한 제품을 표현할 때

전자제품을 샀다면? 전자제품 = 1, 의류 = 0, 식품 = 0

의류를 샀다면?        전자제품 = 0, 의류 = 1, 식품 = 0

이된다.

 

이러면 쓰이지 않은 변수들이 너무 많아진다. 그래서 서로 동시에 값을 가질 수 없는(또는 거의 없는) 변수들을 하나로 묶는 것.

 

이를 위해 어떤 알고리즘을 사용하는가는 뒤에서 계속 살펴본다.

 

2. Preliminaries

GBDT에 대한 내용인데 이미 포스팅하기도 했고, 다 알거라 생각하고 넘어가보자.

 

📌 3. Gradient-based  One-Side Sampling

 

◼️ 3.1 알고리즘 설명

 

GOSS는 큰 그레디언트를 가진 모든 인스턴스들을 유지하고 작은 그레디언트를 가진 인스턴스들에 대해 무작위 샘플링을 수행한다. 즉, 예측이 잘된건 랜덤하게 뽑고 잘 안된건 그대로 다시 사용하는것.

 

구체적으로, GOSS는 먼저 데이터 인스턴스들을 그레디언트의 절댓값에 따라 정렬하고 상위 $a \times 100 %$ 인스턴스들을 선택한다. 그런 다음 나머지 데이터에서 $b \times 100 %$ 인스턴스들을 무작위로 샘플링한다.

 

그 후, GOSS는 정보 이득을 계산할 때 작은 그레디언트를 가진 샘플링된 데이터를 상수 $\frac{1-a}{b}$로 증폭시킨다.

> 이로써  원래 데이터 분포를 크게 변경하지 않으면서도 학습되지 않은 인스턴스들에 더 많은 초점을 둘 수 있게 된다.

 

◼️ 3.2 이론적 분석

 

GBDT는 입력 공간 $\mathcal{X}^s$에서 그래디언트 공간 $\mathcal{G}$로의 함수를 학습하기 위해 의사결정 트리를 사용한다.

 

$n$개의 i.i.d. 학습 인스턴스 ${x_1,\cdots,x_n}$이 있다고 가정하며, 각 $x_i$는 공간 $\mathcal{X}^s$에서 차원 $s$를 가진 벡터라고 하자.

 

그래디언트 부스팅의 각 반복에서, 모델 출력에 대한 손실 함수의 음의 그래디언트[잔차]는 ${g_1,\cdots,g_n}$으로 표시됩니다. 의사결정 트리 모델은 가장 정보량이 많은 특징에서 각 노드를 분할합니다(가장 큰 정보 이득을 가진). GBDT의 경우, 정보 이득은 일반적으로 아래와 같이 정의되는 분할 후의 분산으로 측정한다.

 

◼️ GBDT 분할 후의 분산 정의

 

$O$를 의사결정 트리의 고정된 노드의 학습 데이터셋이라 하자. 이 노드에 대한 특징 $j$의 점 $d$에서의 분산 이득은 다음과 같이 정의된다:

$$V_{j|O}(d) = \frac{1}{n_O}\left(\frac{(\sum_{[x_i \in O:x_{ij} \leq d]} g_i)^2}{n^l_{j|O}(d)} + \frac{(\sum_{[x_i \in O:x_{ij} > d]} g_i)^2}{n^r_{j|O}(d)}\right)$$

 

여기서 $n_O = \sum I[x_i \in O]$, $n^l_{j|O}(d) = \sum I[x_i \in O : x_{ij} \leq d]$ 그리고 $n^r_{j|O}(d) = \sum I[x_i \in O : x_{ij} > d]$

 

특징 $j$에 대해, 의사결정 트리 알고리즘은 $d^*_j = argmax_d V_j(d)$를 선택하고 가장 큰 이득 $V_j(d^*_j)$를 계산한다. 그런 다음 데이터는 특징 $j^*$의 점 $d_j$에서 좌우 자식 노드로 분할된다.

 

본 논문에서 제안하는 GOSS 방법에서는,

첫째로 학습 인스턴스들을 그래디언트의 절댓값에 따라 내림차순으로 정렬한다.

둘째로, 더 큰 그래디언트를 가진 상위-$a \times 100%$ 인스턴스들을 유지하여 인스턴스 부분집합 $A$를 얻는다.

셋째로, 더 작은 그래디언트를 가진 나머지 집합 $A^c$에서 크기가 $b \times |A^c|$인 부분집합 $B$를 무작위로 추가로 샘플링한다.

마지막으로, 부분집합 $A \cup B$ 위에서 추정된 분산 이득 $\tilde{V}_j(d)$에 따라 인스턴스들을 분할한다.

 

$$\tilde{V}j(d) = \frac{1}{n}\left(\frac{(\sum{x_i \in A_l} g_i + \frac{1-a}{b}\sum_{x_i \in B_l} g_i)^2}{n^l_j(d)} + \frac{(\sum_{x_i \in A_r} g_i + \frac{1-a}{b}\sum_{x_i \in B_r} g_i)^2}{n^r_j(d)}\right)$$

 

여기서 $A_l = {x_i \in A : x_{ij} \leq d}$, $A_r = {x_i \in A : x_{ij} > d}$, $B_l = {x_i \in B : x_{ij} \leq d}$, $B_r = {x_i \in B : x_{ij} > d}$이며, 계수 $\frac{1-a}{b}$는 $B$ 위의 그래디언트 합을 $A^c$의 크기로 정규화하는 데 사용된다

 

따라서 GOSS에서는 모든 인스턴스에 대한 정확한 $V_j(d)$ 대신 더 작은 인스턴스 부분집합에 대한 추정된 $\tilde{V}_j(d)$를 사용하여 분할 지점을 결정하며, 이를 통해 계산 비용을 크게 줄일 수 있다.

더 중요하게는, 다음 정리가 GOSS가 많은 학습 정확도를 잃지 않으며 무작위 샘플링보다 더 나은 성능을 보일 것임을 나타낸다. 

 

 

◼️ 정리 (Theorem)

 

GOSS에서의 근사 오차를 $\mathcal{E}(d) = |\tilde{V}j(d) - V_j(d)|$로 표시하고, $\bar{g}^j_l(d) = \frac{\sum{x_i \in (A\cup A^c)l} |g_i|}{n^l_j(d)}$, $\bar{g}^j_r(d) = \frac{\sum{x_i \in (A\cup A^c)_r} |g_i|}{n^r_j(d)}$로 합니다. 적어도 $1-\delta$ 확률로 다음이 성립합니다:

$$\mathcal{E}(d) \leq C_{a,b}^2 \ln 1/\delta \cdot \max\left\{\frac{1}{n^l_j(d)}, \frac{1}{n^r_j(d)}\right\} + 2DC_{a,b}\sqrt{\frac{\ln 1/\delta}{n}}$$

여기서 $C_{a,b} = \frac{1-a}{\sqrt{b}} \max_{x_i \in A^c} |g_i|$이고, $D = \max(\bar{g}^j_l(d), \bar{g}^j_r(d))$

 

정리에 따르면:

(1) GOSS의 점근적 근사 비율은 $\mathcal{O}\left(\frac{1}{n^l_j(d)} + \frac{1}{n^r_j(d)} + \frac{1}{\sqrt{n}}\right)$이다.

만약 분할이 너무 불균형하지 않다면(즉, $n^l_j(d) \geq \mathcal{O}(\sqrt{n})$와 $n^r_j(d) \geq \mathcal{O}(\sqrt{n})$), 근사 오차는 위 부등식의 두 번째 항에 의해 지배되며, 이는 $n \to \infty$일 때 $\mathcal{O}(\sqrt{n})$으로 0에 수렴한다.

이는 데이터의 수가 많을 때 근사가 상당히 정확하다는 것을 의미한다.

 

(2) 무작위 샘플링은 $a=0$인 GOSS의 특수한 경우다. 많은 경우에 GOSS는 $C_{0,\beta} > C_{\alpha,\beta-\alpha}$ 조건 하에서 무작위 샘플링보다 더 나은 성능을 보일 수 있으며, 이는 $\frac{\beta}{b} > \frac{\gamma_{\beta-a}}{\sqrt{\beta-a}}$와 동등하며 여기서 $\alpha_a = \max_{x_i \in A\cup A^c} |g_i|/\max_{x_i \in A^c} |g_i|$.

 

◼️ GOSS에서의 일반화 성능 분석

 

GOSS의 일반화 오차 $\mathcal{E}{gen}^{GOSS}(d) = |\tilde{V}j(d) - V*(d)|$를 고려하며, 이는 GOSS에서 샘플링된 학습 인스턴스들로 계산된 분산 이득과 기저 분포에 대한 실제 분산 이득 간의 차이다.

$\mathcal{E}{gen}^{GOSS}(d) \leq |\tilde{V}j(d) - V_j(d)| + |V_j(d) - V*(d)| \leq \mathcal{E}{GOSS}(d) + \mathcal{E}{gen}(d)$가 성립합니다.

따라서 GOSS의 일반화 오차는 GOSS 근사가 정확하다면 전체 데이터 인스턴스를 사용하여 계산된 것에 근접할 것. 한편, 샘플링은 기본 학습기의 다양성을 증가시킬 것이며, 이는 잠재적으로 일반화 성능을 향상시키는 데 도움이 될 수 있다.

 

📌 4. Exclusive Feature Bundling

 

앞서 설명한 EFB를 사용하기위해선 두 가지 해결해야할 문제가 있다. 1. 어떤 변수(특징)들을 함께 묶어야 하는지 결정하는 것, 2. 번들을 어떻게 구성할 것인지

 

◼️ 정리 4.1

 

특징들을 최소 수의 베타적 번들로 분할하는 문제는 NP-hard이다. 본 논문에서는 이를 그래프 색칠 문제에 빗대고 있다. 

 

그래프 색칠 문제???
: 그래프의 각 점을 색칠하는데, 서로 연결된 점은 다른색을 써야하는 문제로 이때 사용되는 색상의 수를 최소화하는 것이 목표이다. 해당 문제는 NP-hard로 알려져 있다.

https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%83%89%EC%B9%A0

 

이걸 번들링 문제에 빗댄것. 

각 특징을 그래프의 점이라고 생각하고, 서로 베타적이지 않은(동시에 값을 가질 수 있는) 특징들 사이에 선을 긋는다. 그럼 같은 색으로 칠할 수 있는 점은 하나의 번들로 묶을 수 있는 특징들로 볼 수 있는 것.

 

◼️ 1) 특징 번들링 방법

특징들 간의 충돌(동시에 0이 아닌 값을 가지는 경우)을 기반으로 그래프를 구성한다. 그래프에서 각 특징은 점이 되고, 충돌하는 특징들 사이에 선이 생긴다. 

이후 그래프의 각 점(특징)의 차수를 기준으로 내림차순 정렬하여 번들링을 수행. 정렬된 순서로 각 특징을 검사하면서 허용 가능한 충돌($\gamma$)을 가진 기존 번들에 할당하거나 새로운 번들을 생성.

 

◼️ 2) 특징 병합 방법

번들 내의 특징들을 하나로 병합할 때는 각 특징의 값 범위가 겹치지 않도록 오프셋을 사용. 예를들어 특징 A가 [0, 10], 특징 B가 [0, 20]의 값을 가질 때, B에 오프셋을 추가하여 [10, 30]으로 만들어 버린다.

따라서 병합된 특징이 어떤 값을 가지면 그것이 원래 어떤 특징의 값이었는지 구분할 수 있다. 

 

해당 방법에 대해선 아래 링크에 아주잘 설명이 되어있으므로 한번씩 확인해보면 좋을 것 같습니다.

 

https://www.youtube.com/watch?v=Y-IvfsjmqOQ