[분석알고리즘] LightGBM 정리

이전에 정리해 뒀던 LightGBM 알고리즘을 다시 보다가 

기껏 정리했는데 안올리기에는 아쉬워서 올려본다..ㅎㅎ

Light GBM은 트리(Decision Tree) 기반 모형으로 빠르게 학습하는 것이 장점이다.

​

LGBM을 구성하는 알고리즘

• GOSS(Gradient-based One-Side Sampling)
• EFB(Exclusive Feature Bundling)

​

1.GOSS 알고리즘

• Data Instance의 Gradient를 구해서 Gradient 기준으로 정확도는 유지하면서 Data Instance는 줄이는 Sampling 방법을 이용
• Instance의 Gradient가 작으면 그 Instance에 대한 Training error는 작고 이미 Training이 잘 되어 있음을 의미함
• 그래서 GOSS는 정보를 많이 줄 수 있는 Gradient가 큰 Data instance는 유지하고 작은 instance는 random으로 sampling을 함

-> Gradient를 적절하게 가져가고 Data 양은 줄이면서 기존의 Data 분포를 유지할 수 있음

​

Sampling 하는 순서는 다음과 같다.

1. 각 Data instance의 Gradient를 계산

2. Gradient의 절대값 기준으로 sorting

3. Gradient의 상위 a*100% 까지의 Data Instance는 모두 사용 (a는 임의의 값)

4. 나머지 (1-a)*100%의 Data Instance에서 b*100%개는 Random Sampling 하여 사용

5. b*100% 개의 Data Instance는 1-a/b (>1)의 상수를 곱해준다.

   -> Gradient가 높은 instance에만 넘 집중되지 않도록 하기 위함

​

​

2. EFB 알고리즘

• Feature 수를 줄이는 알고리즘
• 매우 높은 차원의 Data에서는 보통 매우 Sparse함 (0이 많은 데이터)
• Sparse Feature 공간에서 많은 Feature들은 서로 상호 배타적임
• 이때 Feature들은 동시에 0이 아닌 값을 가지지 않고 우리는 이런 Feature들을 하나의 Feature로 묶을 수 있음 (Exclusive Feature Bundle이라고 함)
• O(#data x #Feature)에서 O(#data x #Bundle)로 Histogram Building의 복잡성이 변경됨

-> 즉, Bundle로 묶음으로서 Feature를 줄이고 이런 방식으로 GBDT 훈련에 속도를 높일 수 있음.

​

컨셉은 다음과 같다.

1) 가중치가 있는 Edge들과 함께 graph 그림

2) 내림차순으로 그래프에서 Feature의 정도에 따라 Sorting

3) 내림차순 한 Feature들을 Existing Bundle에 작은 Conflict와 같이 할당하거나 새로운 Bundle을 생성

* Bundle 찾는 법: Conflict가 많은 애들은 같이 묶지 않음.

(Conflict : Edge의 강도(Degree), Conflict는 동시에 non-zero 값을 가지는 비율을 기준으로 계산)

​

예시와 그림을 보면 이해하기 쉽다.

​

[Greeding Bundling 예사]

Degree: 동시에 0이 아닌 값을 가지는 객체의 수

Dgree를 내림차순하여 가장 높은 Degree부터 시작(여기는 x5)

이때, cut-off(=0.2, 하이퍼파라미터)를 정해 Non-Zero value가 20%보다 크면 bundling을 하지 않음

​

각 Feauture와 Degree를 그래프로 나타내면 다음과 같다.

-> 여기서 N=10이므로 2 이상인 경우는 Bundling하지 않음(x로 표기)

 

 

x1과 x2가 같이 묶일 수 없기 때문에 x1, x2, x4는 같이 묶일 수 없다. 최종적으로 x5, (x1, x4), (x2, x3)으로 묶인다.

 

 

 

[크기 순으로 재정렬]

 

 

x5, (x1, x4), (x2, x3)으로 묶고 나서 off-set을 더한다.

Off-set 더하는 법:

• 기준 변수의 최대값을 다른 Bundle 변수에 더한다.
• 기준 변수의 값이 최소값이면 다른 Bundle의 값 + 기준변수의 최대값을 가지고 온다.
• 단, Conflict가 일어난 부분은 기준변수 값 그대로 가지고 옴

​예시)

예시에서는 기준변수로 X1, X2를 사용

 

당시에는 논문 이해를 하려고 정리한거 같은데,,

밑에 있는 고려대 설명영상을 보면 더 이해를 잘 할 수 있으니, 영상보는것을 추천

 

 

참고 자료:

http://ttps://papers.nips.cc/paper/2017/hash/6449f44a102fde848669bdd9eb6b76fa-Abstract.html

 

[고려대 설명 영상]

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