[Data Science] 앙상블(Ensemble) 3. XGBoost, LightGBM

Ensemble

XGBoost

단일 의사 결정나무가 가지는 과적합 위험을 방지하기 위해 복원추출이 핵심인 bootstrap을 만드는 Bagging이 제안되었다. Bagging은 복원추출을 함으로써 앙상블의 다양성은 확보한다. 그 다양성 확보의 극대화를 위해서 tree를 split할 때마다 모든 변수를 사용하는 것이 아닌 일부분의 변수만 후보로 사용하는 Random Forest 기법이 제안되었다.

Bagging은 처음부터 데이터를 복원 추출하여 여러개로 생성하면서 각각의 bootstrap 마다 데이터의 분포가 조금씩 다르게하여 다양성을 확보하는 반면에 Boosting은 먼저 모델을 만들고 만들어진 모델이 잘 풀지 못하는 샘플들이 다음 학습 데이터에 더 많이 포함되도록 피드백을 전달하는 순차적인 구조로 이루어져 있다 (이전 모델에 결과물을 피드백 받아서 다음 모델의 학습 데이터로 구성하는 구조). AdaBoost는 이전 모델이 맞추지 못한 데이터를 학습 데이터 셋에 더 많이 포함시키도록, 즉, 모델이 가지고 있는 단점이 다음 학습 데이터셋을 구성하는데 영향을 준다. Gradient Boosting은 현재 모델이 가지고 있는 단점(현재 모델이 맞추지 못한 잔차)이 모델의 gradient에 반영이 된다. XGBoost는 여러 장치들(소프트웨어 + 하드웨어)을 통해 성능을 극대화 시킨 Gradient Boosting이다.

트리를 어떻게 하면 더 효율적으로 split할 수 있을 것인가에 대해 생각해보자.

Split Finding Algorithm

1. Basic Exact Greedy Algorithm

전체 데이터 셋에 대해 특정한 변수값을 기준으로 정렬한 뒤, 모든 분기점을 탐색하는 기법이다. 모든 분기점을 탐색하기 때문에 항상 최적의 해를 찾을 수 있다. 하지만 $N$개의 데이터가 있을 때, $(N-1)$번 분기점을 찾기 때문에 $N$이 클수록 부담스럽다. 데이터가 메모리에 모두 저장되지 않을 경우 탐색이 불가능하고 분산 컴퓨팅 환경에서 계산이 불가능하다.

2. Approximate Algorithm

그렇기 때문에 XGBoost에서는 어떤 feature $k$에 대해 백분율 기준으로 부분집합을 구분하고 따로따로 병렬적으로 탐색하는 근사해 기법을 사용한다.

첫번째 구역을 예로 들면 데이터 포인트가 4개 있으므로 3개의 split 후보군에 대해 점수를 계산하고 가장 높은 점수를 찾아낸다. Greedy Algorithm에서는 $(N-1)$개의 분기점 탐색이 필요하지만 데이터를 분할하여 개별적으로 계산하면 $10([\frac{N}{10}]-1)$개의 분기점 탐색이 필요해진다. 크게 차이가 나지 않는 것처럼 보이지만, 중요한 점은 “병렬처리”가 가능해진다는 점이다. 그렇기 때문에 Greedy Algorithm처럼 100% 최적해를 찾을 수 있다는 보장은 사라지지만, 더 빠르게 최적해를 찾아갈 수 있다는 장점이 있다.

Approximate Algorithm은 Global variant와 Local variant 두 가지 관점이 있다.

Global Variant는 tree마다 부분집합을 적용한다고 이해할 수 있다. Root node에서 찾은 best split point를 기준으로 child node가 나눠지고 root node에서 구분했던 영역들이 그대로 유지된다.

Local Variant는 split마다 부분집합이 적용되는데, 노드별 부분집합의 개수를 유지하기 때문에 split이 진행될수록(deepth)가 깊어질수록 촘촘하게 부분집합이 구분된다.

Global eps = 0.3은 global 범위를 30%로 듬성듬성 $\frac{1}{3}$씩 잡으면 greedy algorithm보다 성능이 확연히 낮은걸 볼 수 있다. 하지만 local로 각각 split마다$\frac{1}{3}$ 으로 부분집합을 설정하면 성능이 좋아진 것을 볼 수 있다. 마찬가지로 global도 5%로 부분집합을 설정하면 성능이 좋은 것을 볼 수 있다.

Sparsity-Aware Split Finding

첫번째 장치는 Split Finding Algorithm으로 분산 컴퓨터 환경을 통해 빠르게 split을 하도록 하는 것이었다. 두번째 장치 Sparsity-Aware Split Finding은 결측치를 핸들링하는 장치이다.

현실의 많은 데이터들은 입력 데이터의 밀도가 낮은 Saprse인 경우가 빈번하게 발생한다.

• 데이터에 결측치가 많은 경우
• 0의 값이 매우 높은 비중을 차지하고 있는 경우
• One-Hot Encoding과 같은 Feature Engineering이 수행된 경우

그럴 경우 결측치를 처음부터 설정한 방향으로 보내도록 default direction을 설정하는 방법으로 해결할 수 있다.

왼쪽으로 결측치를 보냈을 때 최적의 split을 찾았다고 할 수 있기 때문에 default direction을 “left“로 설정한다.

결측치가 있는 경우 미리 정해진 방향으로 보내면 Basic Algorithm이 처리하는 시간보다 Sparsity Aware Algorithm이 같은 스레드에서 훨씬 빠르게 수행되기 때문에 시간을 효율적으로 쓸 수 있다는 장점을 얻게 된다.

의사결정나무에서 가장 시간이 많이 소요되는 부분은 데이터를 각 변수 값으로 정렬하는 과정이다. XGBoost는 최적화된 알고리즘이기 때문에 최초 데이터 생성시 block이라고 부르는 곳에 데이터를 저장한 뒤 이후 과정에서 필요한 block을 꺼내서 계속 재사용한다.

Light GBM

Light GBM은 마이크로사에서 개발된 모델로, XGBoost보다는 나중에 제안된 모델이다. 카테고리 변수가 많은 데이터 셋에서 상당한 효과를 보이는 알고리즘이다. 이름에서 알 수 있듯 가벼운, 빠른 모델이다. 데이터 셋의 크기가 큰 경우 데이터의 크기를 줄여서 효과적으로 수행한다.

GBM은 모든 변수에 대해 모든 데이터 셋을 스캔한다. XGBoost도 이러한 문제를 해결하기 위해 데이터셋을 부분집합으로 구분한 뒤 스캔한다. Light GBM은 데이터 셋 가로(변수), 세로(관측치)를 어떻게 줄여가는가 두 가지 관점으로 데이터를 축약한다.

Gradient-based One-Side Sampling(GOSS)

Gradient-based One-Side Sampling(GOSS)은 모든 데이터 포인트를 다 스캔해야하는가?에 대한 질문에 대한 기법이다.

데이터 포인트들은 서로 다른 기울기를 가지고 있고 gradient가 큰 객체와 작은 객체는 information gain 측정하는데 있어서 다른 역할을 한다. 상대적으로 gradient가 클수록 많이 틀렸음을 의미하고 그 객체의 정보를 많이 반영하고, gradient가 작을수록 틀린 정도가 크지 않기 때문에 해당하는 객체들은 다음 모델을 구축할 때 덜 중요하게 생각한다.

여기서 아이디어를 얻고 Large Gradient를 가진 객체들은 그대로 두고 Small Gradient를 가진 객체들은 random하게 drop한다.

데이터를 gradient가 작은 것부터 큰 것까지 구분하고 정렬한다. 여기서는 $a, b$라는 하이퍼파라미터를 사용하는데, $\frac{1-a}{b}\gt1$이 되도록 설정하는 것이 좋다. 전체 데이터 중 [TOP $a \times 100$% ]의 데이터는 그대로 사용하지만, gradient가 작은 데이터는 랜덤으로 샘플링한다.

$a, b$가 작을 수록 실제 split하는데 사용되는 객체수가 줄어들기 때문에 효율성은 증가하지만 손실을 볼 수 있는 잠재적 risk가 있다.

✎ $a=0.2, \ b=0.5$일 경우 split 하는 데 1) graidnet 상위 20%의 데이터와 2) gradient 하위 80%의 데이터 중 50%만 샘플링해서 사용하겠다는 것을 의미한다.

Exclusive Feature Bundling(EFB)

Exclusive Feature Bundling(EFB)은 모든 변수에 대해 스캔할 것인가?에 대한 대답이다.

실제 데이터들은 결측치가 없는 완벽한 형태로 존재하지 않는다. 특히 One-Hot Encoding과 같은 경우 데이터는 Sparse한 형태로 존재한다. 이런 경우에, feature를 Bundle로 묶어서 처리한다.

그래프 컬러링과 같은 의미를 가지는데, 서로 연결되어 있는 Vertex는 같은 색이 아니도록 색을 칠하는 것처럼 이해할 수 있다.

Greedy Bundling을 예로들어 과정을 살펴보자 ! (Cut-off = 0.2)

complict 값을 weight로 갖는 feature에 대한 표를 만드는 과정이다. $x_5$가 가장 complict가 큰 변수이므로, $x_5$부터 그림을 그려나간다.

cut-off는 0.2이므로 $x_5$는 번들로 묶일 수 있는 다른 feature가 없다. 그 다음으로 $x_1$을 살펴보면

Cut-off 0.2를 넘지 않는 $x_4$와 번들로 묶이게 된다. $x_4$는 $x_1$과 이미 번들로 묶였기 때문에 $x_1$과 번들로 묶이지 않은 $x_2$와 번들로 묶일 수 없다.(cut-off 값 보다 작은 값을 가지고 있더라도)

결과적으로 $x_5 \ / x_1, x_4 \ /\ x_2, x_3 $가 번들로 묶이게 된다.

여기서는 몇 가지의 규칙이 존재한다. 기준 변수 $x_1$과 함께 묶이는 변수 $x_4$로 예를 들면

• 기준 변수 $x_1$과 $x_4$가 모두 0이거나, 둘 다 0이 아닐 때 → $x_1$
• 기준 변수 $x_1$가 0이고 $x_4$가 0이 아닐 때 → offset + $x_4$
• 기준 변수 $x_1$가 0이 아니고 $x_4$가 0일 때 → $x_1$

여기서 offset은 기준이 되는 변수가 가지고 있는 최대 값을 의미한다.

상호베타적인(동시에 0이 아닌 값을 갖지 않는 변수) 변수들을 묶어서 번들로 만드는 과정속에서 둘다 값이 0이거나, 둘다 0이 아닌 값을 갖는 변수들(빨간색 박스), 즉, exclusive하지 않은 영역에서의 번들링으로 왜곡이 일어나게 된다. 이 왜곡으로 original변수를 사용했을 때 보다 성능이 저하될 가능성이 있지만, 속도가 빠르고 성능이 좋다.

LightGBM은 Gradient Boosting Machine을 기초로 하지만, GBM에서 split을 위해 탐색해야하는 객체의 후보군과 변수의 후보군이 너무 많다고 판달될 때 사용하는 방법이다. 개체수를 줄일 때는 gradient가 충분히 큰 객체는 그대로 사용하고 gradient가 작은 객체들은 일부분 샘플링해서 사용한다. 변수의 개수는 하나의 변수값이 0이 아닌 값이고 나머지 변수들이 0인 경우가 많이 발생한다면 하나의 변수로 표현하여 효율적으로 탐색이 가능하다.