No Limitation
[논문 리뷰] LightGBM: A Highly Efficient Gradient Boosting Decision Tree 본문
[논문 리뷰] LightGBM: A Highly Efficient Gradient Boosting Decision Tree
yesungcho 2022. 1. 29. 20:40
참고 온라인 강의 영상
고려대학교 산업경영공학부 강필성 교수님
https://www.youtube.com/watch?v=4C8SUZJPlMY
Boosting 시리즈 (Ada-XG-LightGBM-Cat) 중 하나인 LightGBM부터 다루어보도록 하겠습니다!
LightGBM이 개발된 배경
: 전통적인 GBM은 DT 기반의 알고리즘 특성상, 모든 변수들에 대해, 모든 객체를 scan하여 동작을 해서 information gain을 측정하게 된다.
( 여기서 information gain은 DT에서 분류 기준을 정한 뒤 엔트로피가 주는 정도, 즉 pruning을 통해 얼마나 잘 분류가 되는 지를 측정하는 지표 )
위 두 문제를 대응하기 위해 LightGBM은 어떠한 방법을 적용할까?
[1] 모든 객체를 scanning 하는 문제에 대해서
→ XGB의 경우 전체 데이터를 'bucket'이라는 단위로 쪼갠 다음, 그 bucket안에서 탐색을 수행하여 최적의 대안을 찾는 방안을 적용 (여기는 추후 XGB 파트에서 정리하자)
→ 반면 LightGBM은 이를 대응하기 위해 Gradient-based One-Side Sampling (GOSS) 방법을 이용한다.
[2] 모든 변수를 이용하는 문제에 대응하기 위해서
→ LightGBM은 Exclusive Feature Bundling (EFB) 방법을 이용한다.
그럼 우선 GOSS에 대해 알아보자
Gradient-based One-Side Sampling (GOSS)
→ 개별적인 데이터들은 서로 다른 Gradient를 가지고 있음, 그로 말미암아 어느 지점을 split해야 하는지(information gain)를 계산하는 데 있어서 각 데이터들은 다른 역할을 수행하게 된다. 즉 Gradient가 크면 클수록 더 중요한 객체가 되는 것.
→ 고로 Gradient가 큰 객체는 Keep, 작은 객체는 Dropout을 수행
[원어]
Data instances with different gradients play different roles in the computation of information gain
Keep instances with large gradients and randomly drop instances with small gradients
ex) 예를 들어 1000개 데이터 중 Gradient가 큰 상위 몇 % 고정, 낮은 애들 중 하위 몇 % 버림, 랜덤하게
Exclusive Feature Bundling (EFB)
EFB의 기저 논리는,
One-hot Encoding처럼 Feature Space가 매우 sparse한 경우 ex) (0, 0, 0, ... , 1, 0, ..) 대부분의 피처들이 exclusive하다.
→ 이 Exclusive하다는 말의 의미는, 하나의 객체에 대해 두 개의 변수들이 0이 아닌 값을 동시에 가질 가능성이 매우 낮은 그러한 변수들이 상당히 많이 존재한다!
→ Many Features are exclusive의 의미!
[원어] In a sparse feature space, many features are (almost) exclusive, i.e., they rarely take nonzero values simultaenously
그러면 이런 Feature들을 어떻게 할까? 바로
하나로 묶는다! 즉, 하나로 bundling하는 것이다! 즉, 하나의 변수로 만든다고 보면 된다.
[원어]
we bundle mutually exclusive features, to reduce the number of features.
하지만 이러한 방법은 risk가 있는데,
만일 feature들이 exclusive하지 않을 경우에는 약간의 오류가 발생할 수 있다.
그렇다면, LightGBM의 Algorithm은 어떻게 동작하게 될까?
[1] Gradient-based One-Side Sampling
페이퍼에는 2개의 방법이 소개되고 있는데,
Algorithm 1의 경우 Histogram-based Algorithm로, XGB의 bucket 기반의 알고리즘이라고 보면 된다. Histogram은 bucket대신 쓴 용어이다.
즉, 이 경우 각각의 bucket 벼로 최적의 split point를 찾고 그 중 가장 좋은 split point를 전체 데이터의 split point로 사용하는 메커니즘으로 동작한다.
그럼 반대로 GOSS는 어떻게 동작할까?
다음 도식도를 살펴보자
앞에 논리처럼 결국 Gradient가 큰 건 보존하고 작은 건 랜덤하게 골라 dropout을 시켜주게 되는데
거기서 비율을 계산할 때, a,b의 하이퍼 파라미터가 등장하게 된다.
이 경우 맨 위의 문장처럼 a, b를 (1-a)/b > 1을 만족하게 설정하면 더 효과가 좋다고 하는데 그 의미가 무엇인지 확인해보자
예를 들어
a = 0.1, b = 0.9가 있다고 해보자
이 경우 위 수식의 값은 1이 된다. 이 경우가 가장 normal한 케이스라고 할 수 있다.
이 경우를 극대화하기 위해 가령, a=0.05, b=0.5라고 놓으면 (상위 5%는 남겨 놓고, 하위 50% 중에는 랜덤하게 샘플링 한다는 의미 )
이 경우 위 수식의 값은 1보다 크게 된다.
[2] Exclusive Feature Bundling
크게 2가지 절차를 거쳐 동작한다.
우선 Greedy Bundling부터 살펴보면,
이 녀석의 기능은 한마디로, 현재 존재하는 feature set들에 대해서, 어떠한 feature들을 하나의 bundle로 묶을 것인지를 결정
예상되는 아웃풋은 다음과 같이 나온다.
bundle1 = { x1, x4, x7 }
bundle2 = { x2, x5, x6, x9 }
그러고 난 다음에 Merge Exclusive Features에서는
실제로 하나의 변수로 바꾸어주는 동작을 하는 알고리즘
다음과 같은 기능을 한다고 보면 된다.
bundle1 = { x1, x4, x7 } → y1
bundle2 = { x2, x5, x6, x9 } → y2
Greedy Bundling 문제, 즉 bundle을 찾는 문제는 조금 더 세부적으로 들어가면,
Graph Coloring Problem으로 표현이 가능하다.
[ 실제 이 Minimum Vertex Coloring은 NP-hard 문제를 풀기 위함이라는데 이것도 나중에 정리하자 ]
저기서 각 피처는 노드에 해당하고 edge는 두 피처 간의 conflict를 나타낸다고 한다.
결국 bundling할 때 conflict가 많은 애들끼리는 bundling을 하면 안되고 ( 중복이 많단 소리겠지, 동시에 이 말은 conflict를 0이 아닌 값을 중복으로 갖는 비율을 의미하겠지 )
conflict가 없는 애들끼리는 bundling을 할 수 있는 것이다!
위 그림에서 첫 번째 그래프의 경우
파란색 끼리, 초록색 끼리 bundle을 형성할 수 있다. 하나의 bundle은 하나 그 자체겠지.
그래서 8개의 변수를 bundle을 통해 4개로 축소시킬 수 있는 것이다.
위 그림에서 첫 번째 그래프의 경우
파란색 끼리, 초록색 끼리 bundle을 형성할 수 있다. 하나의 bundle은 하나 그 자체겠지.
그래서 8개의 변수를 bundle을 통해 4개로 축소시킬 수 있는 것이다.
[1] 그럼 이 Greedy Bundling이 수행되는 메커니즘을 예시를 통해 이해해보자
다음의 경우 10개의 instance에 대해 5개의 변수가 존재한다.
우선 먼저 그래프를 그려야하니까,
각 피처 x1, x2, ~ x5를 노드로 잡고
edge를 설정해야 하는데 edge는 두 노드 사이의 강도 즉, conflict의 정도에 따라 설정할 수 있다.
이 conflict는 결국, [동시에 0이 아닌 객체의 수]로 나타낼 수 있다.
예를 들면 x1과 x2를 비교하게 되면 다음과 같이
10개의 객체 중 6개가 conflict 존재 따라서 다음처럼
6이 강도가 됩니다
그래서 이렇게 구해놓으면
다음과 같은 매트릭스가 구축됩니다.
이렇게 각 피처에 대한 degree는 다음과 같이 나온다.
그리디 알고리즘을 수행해주기 위해 시작점을 가장 degree가 높은 x5부터 시작.
여기서 input으로 cut-off는 0.2로 주었으면
전체 n=10이므로, 10*0.2 = 2 [2번 이상 conflict가 나타나면, bundling을 하지 않음 ]
x5를 기준으로 봐보자
이 경우 x4, x3, x2, x1다 끊김..!
그래서 x5는 bundle을 만들 수 없고 왕따가 된다!
다음으로 degree가 높은 x1 기준은 아래 그림과 같이 수행된다.
이 경우 x1를 필두로 x2, x3의 엣지가 제거 된다. 이렇게 되면 x2, x3는 x1과 bundle을 형성할 수 없게 되고 따라서 유일하게 남는 x4와 bundle을 형성하게 된다.
그 다음으로 degree가 높은 x2는 x3하고만 bundle을 형성할 수 있게 된다.
따라서 이러한 메커니즘으로
x1, x2, x3, x4, x5는
{ x5 } → y1
{ x1, x4 } → y2
{ x2, x3 } → y3
을 형성함을 알 수 있다. (살짝 서로소 느낌? )
고로 데이터는 다음과 같이 재구성되게 된다.
이렇게 열을 shuffling을 해준 다음에 merging 작업에 들어간다.
[2] 다음으로 Merging Exclusive Feature 방법론에 대해 알아보자
핵심 메커니즘은 다음과 같다.
Add offsets to the original values of the features
x1, x4에 대한 상황을 예로 생각해보자
이 경우 어떻게 x14로 bundling 되는 지 메커니즘을 살펴보자
우선 다음과 같은 Step으로 동작한다.
다음과 같은 매커니즘으로 동작한다.
그리고 이러한 방법을 수행하게 되면 아래와 같이 일부 conflict가 발생하는 경우의 loss가 발생하게 된다
다음과 같은 논리로 동작을 하게 된다
'논문 리뷰' 카테고리의 다른 글
| [논문 리뷰] Neural Machine Translation by Jointly Learning to Align and Translate (0) | 2022.02.04 |
|---|---|
| [논문 리뷰] Sequence to Sequence Learning with Neural Networks (0) | 2022.02.02 |
| [논문 리뷰] Random Forest (0) | 2022.02.02 |
| [논문 리뷰] A Short Introduction to Boosting, Adaptive Boosting (0) | 2022.01.30 |
| [논문 리뷰] XGBoost : A Scalable Tree Boosting System (0) | 2022.01.29 |
