4-8 : Ensemble Learning - Light GBM

자료 출처

 

MS에서 개발되었고 XGBoost와 마찬가지로 Conventional GBM이 information gain을 계산하기 위한 split point를 모든 데이터 객체에 대해서 스캔하기 때문에 시간을 단축하기 위해서 고안되었다.

 

Idea

데이터 객체의 수와 feature의 수를 줄이기 위함

 

Gradient-based One-Side Sampling (GOSS)

• 서로 다른 gradient를 갖는 데이터 객체는 information gain 계산에서 서로 다른 역할을 한다. 그러니까 각각 gradient가 다르다고 이해할 수 있다.
• gradient가 큰 객체는 유지하고 gradient가 작은 객체는 샘플링을 통해 무작위로 drop한다.

Exclusive Feature Bundling (EFB)

• 상호배반적(exclusive)이라는 의미는 sparse한 feature 공간에서 데이터가 동시에 nonzero 값을 가지는 경우가 드물다는 뜻이다.
• 예를 들어 one-hot encoding의 경우에는 절대적으로 exclusive feature이다.
• 이러한 exclusive features를 bundling을 수행하고 이는 성능이 저하되지 않는다.
• 다만 sparse하기 하지만 동시에 nonzero값을 가지는 데이터가 있는 경우도 있는데, 이러한 경우에는 기법을 통해 성능 저하를 방지하지만 어느 정도의 risk는 안고 있다.

 

Gradient-based One-Side Sampling (GOSS)

예를 들어 a가 0.1이고 b가 0.9이면 일반적인 방법이고 $(1-a)/b$를 계산하면 1이 된다. GOSS의 의도를 극대화 하기 위해서는 a, b의 값을 적절히 조정해야한다. 예를 들어 b가 0.8이라면 $(1-a)/b$ 값은 1보다 크게 된다.

 

Exclusive Feature Bundling (EFB)

EFB에는 2가지 절차가 있다.

• Greedy Bundling : 어떤 변수들을 하나의 bundle로 묶을지 결정한다. 예를 들어 feature가 $x_1$부터 $x_5$까지 있다면 {1, 3}을 하나로 묶고 {2, 4, 5}를 하나로 묶는 것을 결정한다.
• Merge Exclusive Features : Greedy Bundling으로 결정된 변수들을 새로운 하나의 변수로 merge하는 과정을 의미한다.

 

EFB는 Graph coloring problem으로 이해할 수 있다.

• 노드가 feature이고 엣지가 노드간의 conflict이다.
• conflict를 정의하는 방법은 예를 들어 nonzero값을 갖는 비율로 정할 수 있다.
• 위의 그래프를 보면 엣지 하나로 연결되어 있지 않는 노드들이 같은 색으로 칠해져 있다. 즉, 같은 색끼리 번들링이 되었다.

 

Greedy bundling example

위와 같은 데이터가 있을 때 conflict를 nonzero가 발생한 횟수로 정의한다면 다음과 같이 나타낼 수 있다.

 

그런다음 cut-off 0.2로 bundling을 수행한다. cut-off가 0.2이면 데이터가 총 10개 있기 때문에 $10*0.2=2$로 2회 이상 conflict가 발생한 feature에 대해서는 bundling을 수행하지 않겠다는 의미이다.

엣지를 제거할 때는 d값이 높은 feature부터 수행한다.

 

$x_5$에 대해 2 이상의 엣지를 제거하면 다음과 같다.

그런 다음 $x_1$에 대해서 수행하면 $x_2$, $x_3$와 연결되어 있는 엣지가 제거된다. 이 과정에서 $x_1$과 $x_2$가 연결되어 있을 수 없기 때문에 $x_2$와 $x_4$의 엣지도 제거된다. 

최종적인 결과는 다음과 같다.

Exclusive feature merging

feature의 original value에 offset을 더한다.

• $x_1$과 $x_4$의 경우를 보자. $x_1$의 최대값은 3이고, $x_4$의 최대값은 4이다. offset을 더한다는 의미는 기준 변수가 가질 수 있는 최대 값을 더하는 것이다. $x_1$을 merge의 기준 변수로 잡는다면 offset으로 3을 더하는 것이다.
• offset을 더하는 경우는 기준 변수의 값이 0인 경우이다.
• 모든 변수가 0이라면 즉, conflict가 발생하였다면 기준 변수의 값을 그대로 사용한다.

위의 규칙을 적용하면 다음과 같이 merge를 수행할 수 있다.