LightGBM

LightGBM: A Highly Efficient Gradient Boosting Decision Tree 논문을 참고하여 작성

LightGBM

XGBoost의 장점은 계승하고 단점은 보완하는 방식으로 개발된 부스팅 모델

트리기반 학습알고리즘을 사용하는 gradient boosting framework

GBDT + GOSS + EFB = LightGBM

 

배경

GBDT의 계산복잡성은 feature와 instance의 수에 비례

handing big data할때 매우 많은 시간이 소요되는 것을 해결하기 위해 등장

 

solution 1 : to reduce the number of features, instance -> 그러나 쉽지않음

solution 2 : data를 weight따라 sampling해 속도를 올리는 방법 -> GBDT에는 sample weight가 전혀 없어 적용불가

solution 3 : GOSS와 EFB

 

데이터 개수를 내부적으로 줄여서 계산하여 모델링 시간을 단축시킴

 

GOSS (Gradient-based One-side Sampling)

 

데이터셋의 샘플(instance) 수를 줄이는 알고리즘

GBDT에 data instance에 대한 기본 weight는 없다 -> AdaBoost sampling방법이 적용 불가 (sample weight 이용)

각 data instance에 대한 gradient가 있다 -> data sampling에 유용한 정보를 제공

작은 gradient를 가진 인스턴스는 훈련오류는 작고 이미 잘 훈련된 것이라는 의미

-> small gradient가진 data instance를 삭제하는 방법을 생각 

>> 그러나 이렇게 할시 data distribution이 변경되어 정확성이 손상될 것임

그래서 GOSS를 제안

 

A1 : XGBoost, A2 : GOSS

 

GOSS는 large gradient instance들은 keep하고 small gradient instance에 대해 무작위 샘플링을 말함

데이터 분포에 대한 영향을 보상하기 위해 IG 계산시 ,small gradient갖는 instance에 대해 상수곱셈 도입

먼저 gradient 절댓값에 따라 data instance를 정렬
상위 a * 100 %instance를 선택
나머지 data(1-a)에서 b * 100% instance들을 무작위 샘플링
그후 IG 계산시 small gradient로 샘플링된 data를 일정한 (1-a)/b만큼 증폭
이를 통해 데이터분포를 크게 변경하지않고 훈련되지 않은 instance에 더 중점
선택한 instance들로 GBDT생

 

gradient가 상위(TOP a)인 객체들은 전부 뽑고, gradient가 상위에 속하지 못한 객체들은 Random하게 뽑아서 (1-a)/b 만큼 증폭시켜 under-trained된 객체에 집중

 

 

* Information gain (IG)
어떤 분류를 통해 얼마나 information(정보)에 대한 gain(이득)이 생겼는지를 나타낸다
entropy를 통해 계산
어떤 attribute를 선택함으로써 데이터를 잘 구분하게 되는 것
클수록 변별력이 좋다

 

EFB (Exclusive Feature Bundling)

 

데이터셋의 feature수를 줄이는 알고리즘

고차원의 데이터는 매우 희소하다 - 이 데이터의 경우 많은 feature들이 exclusive하다

즉 0이 아닌 값을 동시에 취하는 경우가 거의 없다 ex) one hot fatures

이런  exclusive한 feature들을 single feature로 안전하게 번들링할 수 있도록 하는 것 

 

 

상호배타적인 변수 (exclusive feature)들을 묶어서 최소의 bundle로 만드는 문제는 NP-hard (다항시간 내 풀 수 없는 문제)임으로 Greedy 알고리즘을 활용한다

최소 번들문제를 대표적인 NP-hard문제인 그래프 색칠문제로 reduce

1. 데이터 셋의 각 변수들을 그래프의 Vertex로 치환

2. 상호배타적이지 않은 변수들을 Edge로 연결

(상호배타적인 변수들은 서로 연결되어 있지 않아 같은 색으로 칠할 수 있음)

3. 최소한의 필요한 색깔 수가 bundle의 개수에 대응

 

알고리즘3 

1. 변수들의 상호배타여부를 고려해 그래프 G 생성

  각 Edge의 weight는 Edge와 연결된 두 Vertex사이의 conflict

2. 그래프의 각 Vertex들의 Degree를 계산하고  Degree크기에 따라 정렬

  Vertex의 Degree는 해당 Vertex에 연결된 모든 Edge들의 weight의 합

3. 번들을 만들고 Degree가 큰 변수 순서대로 나머지 다른 변수들간의 conflict계산

4. conflict의 합이 전체 데이터셋 개수 * 람다 * 100% 미만이 될때까지 번들에 추가

5. 번들의  conflict의 합이 기준을 넘어가면 새로운 번들을 만들고 모든 변수를 다 쓸때까지 3,4반복

 

* conflict : 상호배타적이지 않은 instance개수

 

알고리즘4

1. 번들 내에서 기준변수 설정

2. 모든 instance에 대해 conflict한 경우 기준 변수 값 그대로 가져감

3. 모든 instance에 대해 conflict가 아닌 경우(상호배타적인 경우) 기준 변수의 최대값 + 다른 변수값

 

변수에 해당하는 값들이 서로 겹치지 않게 기준 변수의 최대값에 해당 변수의 값을 더해

새로운 변수 값으로 취하는 것이다.

 

장점

XGBoost 대비 더 빠른 학습과 예측 수행시간

더 작은 메모리 사용

카테고리형 피처의 자동 변환과 최적 분할

-> 원핫인코딩 등을 사용하지 않고도 최적으로 변환하고 이에 따른 노드 분할 수행

 

단점

적은 데이터 셋에 적용시 과적합 발생하기 쉬움

 

 

기존 GBM과 차이

 

 

대부분의 decision tree 알고리즘은 레벨(깊이)별로 트리를 성장시킴 

-> 균형잡힌 트리를 유지하며 분할해 트리 깊이를 최소화

오버피팅에 강한 구조이나 균형을 맞추기 위한 시간이 필요

 

LightGBM은 tree를 리프단위로 성장시킴

-> 최대 손실값을 가지는 리프노드를 지속적으로 분할하면서 트리가 깊어지고 비대칭적으로 생성됨

오류손실 최소화

 

 

https://kicarussays.tistory.com/38 자세한 수식설명을 참고해주세요

---

참고 및 출처 : https://papers.nips.cc/paper/2017/hash/6449f44a102fde848669bdd9eb6b76fa-Abstract.html , https://kicarussays.tistory.com/38 , https://exupery-1.tistory.com/184