[Machine Learning] Light Gradient Boosting Machine (LGBM)

Dr.Trillion

이번에는 Light GBM으로 Microsoft에서 2017년 개발한 GBM모델입니다. categorical 변수가 많을 때 성능이 좋다고 하네요. 기존의 GBM이 모든 Feature의 모든 Data instance를 스캔해서 가능한 split에 대한 IG(Information Gain)을 계산했다면 이 방법은 Exclusive Feature Bundling (EFB), Gradient-based One-Side Sampling (GOSS)라는 기법을 통해 이를 발전(대규모 데이터셋에서도 학습속도를 높이고 메모리 사용량 감소)시킵니다. 

이번 포스팅 내용은 고려서울대학교 강필성 교수님의 강의 패스트캠퍼스 "실무 문제 해결을 위한 데이터사이언스" 를 참고하였습니다. 

---

https://www.youtube.com/watch?v=4C8SUZJPlMY

 

---

1. Exclusive Featuure Bundling (EF)

Feature의 차원이 많아지면 feature space에서의 sparsity가 높아집니다. 다시 말해, 많은 feature가 (almost) exclusive해 집니다(쉽게 생각해서 동시에 활성화 되지 않는 feature들입니다. 예를 들어 남과 여, LG와 두산...). 발상은 이런 exclusive한 변수들을 bundling하자는 것입니다. 이러한 개념을 그래프적으로 살펴볼 수 있는데요(Graph Coloring Problem), 아래와 같은 Feature가 있다고 합시다.

	x1	x2	x3	x4	x5
I1	1	1	0	0	1
I2	0	0	1	1	1
I3	1	2	0	0	2
I4	0	0	2	3	1
I5	2	1	0	0	3
I6	3	3	0	0	1
I7	0	0	3	0	2
I8	1	2	3	4	3
I9	1	0	1	0	0
I10	2	3	0	0	2

 

동시에 0이 아닌 것(Conflict)의 개수를 세어볼까요? 

	x1	x2	x3	x4	x5
x1	-	6	2	1	6
x2	6	-	1	1	6
x3	2	1	-	3	4
x4	1	1	3	-	3
x5	6	6	4	3	-

 

 

hyper-parameter인 cut-off값이 0.2라고 가정해봅시다. N=10은 10이므로 2번 이상 (10*(0.2)=2) non-zero 값이 나오면 필터링해서 cut-off시킬 겁니다. degree가 높은 것(x5)부터 작업을 하다보면

 

와 같이 됩니다. 이런식으로 feature를 묶은 Bundle을 찾습니다. 

 

그럼 이렇게 묶인녀석으로 변수는 어떻게 Merge할까요?

 

이런 방식으로 merge하게되면, Conflict이 일어난 빨간 부분을 제외하고는 원본의 정보를 보존할 수 있는 것입니다.

 

2. Gradient-based One-Side Sampling (GOSS)

Data point들은 각각 다른 Gradient를 갖고 있으며 IG 계산에 각각 다른 역할을 합니다(Gradient가 클수록 많이 틀렸으니 정보를 많이 반영). 그렇다면 Gradient가 큰 건 남겨두고 작은것들을 랜덤하게 drop시키면 어떨까요? 이것이 GOSS의 컨셉입니다. 데이터셋의 분포를 크게 변화시키지 않으면서 데이터셋의 크기를 줄이려는 목적입니다. 

패스트캠퍼스 실무 문제 해결을 위한 데이터사이언스

 

마치 비슷한 컨셉의 작업을 Sampling이나 강화학습에서 본 것도 같죠? 수식으로 설명하려면 꽤 복잡한데 혹시 궁금하신 분은 아래의 블로그를 참고해주세요.

https://kicarussays.tistory.com/38

[논문리뷰/설명] LightGBM: A Highly efficient Gradient Boosting Decision Tree