LGBM & XGBOOST & CATBOOST

https://greeksharifa.github.io/machine_learning/2019/12/09/Light-GBM/

Structural Differences in LightGBM & XGBoost

•  LightGBM은 split value를 찾기 위한 데이터를 추출할 때, Gradient-based One-Side Sampling (GOSS) 라는 참신한 기법을 사용함
•  반면 XGBoost와 같은 GBDT(Gradient Boosting Decision Tree)는 split value를 찾을 때 pre-sorted algorithm & Histogram-based algorithm을 사용함

Gradient Boosting Decision Tree (GBDT)은 모든 가능한 split point에 대한 정보를 얻기 위해 '데이터 객체 전부를 스캔' 해야 했기 때문에 고차원이고 큰 데이터셋에서는 결과가 좋지 않음(시간 소모적)

--> 이러한 문제를 해결하기 위해 LigntGBM 에서는 GOSS(Gradient-based One-Side Sampling) 과 EFB(Exclusive Feature Bundling)기법을 도입함

--> 대용량 데이터셋에서 빠른 학습 가능케 됨

 

1) GBDT의 pre-sorted & Histogram-based 알고리즘   vs   LGBM의 GOSS

 

[GBDT의 pre-sorted & Histogram-based 알고리즘]

GBDT는 음의 기울기(잔차 오차)를 적합함으로써 Decision Tree를 학습시킨다. 이 학습 과정에서 가장 시간이 많이 소모되는 과정이 바로 최적의 분할점(node)들을 찾는 것인데, 이를 위한 대표적인 방법에는 Pre-sorted(사전 정렬) 알고리즘과 Histogram-based 알고리즘이 있다.

 

Pre-sorted 알고리즘의 경우 사전 정렬한 변수 값에 대해 가능한 모든 분할점을 나열함으로써 간단하게 최적의 분할점을 찾을 수 있지만, 효율적이지 못하다는 단점이 있다. Histogram-based 알고리즘은 연속적인 변수 값을 이산적인 구간(bin)으로 나누고, 이 구간을 사용하여 학습과정 속에서 피쳐 히스토그램을 구성한다.

 

[LGBM의 GOSS]

AdaBoost에서 Sample Weight는 데이터 개체의 중요도를 알려주는 역할을 수행하였다. GBDT에서는 기울기(Gradient)가 이 역할을 수행한다. 각 데이터 개체의 기울기는 loss function의 기울기를 의미하므로, 데이터의 기울기가 크다는 것은 오차(error)가 크다는 뜻이므로 optimal split point를 찾는데 중요한 역할을 수행한다

따라서 기울기가 큰, 즉 학습이 잘 안된 데이터들은 모두 남겨두고 기울기가 작은(오차가 작은, 학습이 잘 된) 데이터들에서는 'random sampling'을 진행한다

 

이때 기울기가 작은 데이터를 그냥 제거한다면 데이터의 분포가 변화할 것이므로, 다른 접근법(GOSS)이 필요하다.

이를 위해 GOSS는 constant muliplier를 도입하여 데이터의 분포가 동일하도록 함

 

GOSS의 아이디어는 직관적이다. 큰 Gradient(훈련이 잘 안된)를 갖는 데이터 개체들은 모두 남겨두고, 작은 Gradient를 갖는 데이터 개체들에서는 무작위 샘플링을 진행하는 것이다. 

 

1) 데이터 개체들의 Gradient의 절대값에 따라 데이터 개체들을 정렬함
2) 상위 100a% 개의 개체를 추출함
3) 나머지 개체들 집합에서 100b% 개의 개체를 무작위로 추출함
4) 정보 획득을 계산할 때, 위의 2-3 과정을 통해 추출된 Sampled Data를 constant multipier를 이용하여 증폭시킴

 

 

2) LGBM의 EFB(Exclusive Feature Bundling)

희소한 변수 공간의 특성에 따라 배타적인 변수들을 하나의 변수로 묶을 수 있다. 그리고 이를 배타적 변수 묶음(Exclusive Feature Bundle)이라고 부른다. 정교하게 디자인된 변수 탐색 알고리즘을 통해, 각각의 변수들로 했던 것과 마찬가지로 변수 묶음들로부터도 동일한 변수 히스토그램들을 생성할 수 있게 된다.

 

예를 들어 변수 묶음에 변수 2개가 속한다고 할 때,
원래 변수 A는 [0, 10)의 값을 취하고, 원래 변수 B는 [0, 20)의 값을 취한다.
이대로 두면 [0, 10) 범위 내에서 두 변수는 겹칠 것이므로,
변수 B에 offset 10을 더하여 가공한 변수가 [10, 30)의 값을 취하게 한다.
이후 A, B를 병합하고 [0, 30] 범위의 변수 묶음을 사용하여 기존의 변수 A, B를 대체한다

 

 

 

 

How each model treats Categorical Variables?