Light GBM

[Light GBM이 등장한 계기]

 

• 전통적인 GBM의 경우 모든 변수와 객체에 대해 탐색하여 IG를 구하고 이를 통해 split point 를 찾음 => 연산시간이 오래걸림.
• Light GBM은 탐색하는 객체와 변수의 줄임.
• leaf-wise 방식을 취하고 있어 수렴이 굉장히 빠르나 over-fitting의 문제가 있으나 max-depth를 잘 조정해줘야 함.

 

[아이디어]

 

Gradient-based One-side Sampling (GOSS)

• 높은 gradient(Large Residual)를 갖는 객체를 기준으로 split하였을 때 IG가 높음.
• =>높은 gradient 를 갖는 객체들은 남기고, gradient가 낮은 객체들은 랜덤하게 제거함.
• 이 방식이 타깃 변수마다 동일한 표본추출비율로 무작위로 표본을 추출하는 것보다 더 정확하게 IG를 추정할 수 있음.

논문 내 알고리즘 요약

 

알고리즘 한글 요약

 

Exclusive Feature Bundling (EFB)

• In a sparse feature space, many features are (almost) exclusive, i.e., they rarely take nonzero values simultaneously.
• 상호배타적인 feature들 (컬럼 중 하나에만 값이 있고 나머지는 다 0인 경우) 의 경우 하나로 묶을 수 있음.
  sparse feature space에서 특정한 하나의 객체에 대해 특정한 2개의 변수가 0이 아닌 값을 가지는 경우가 드묾.  ex. One-hot Encoding
• A dataset with many features is likely to have sparse features (i.e. many zero values). These sparse properties are usually mutually exclusive, so they do not have non-zero values at the same time.
• Bundling : 이런 exclusive 변수들을 하나로 묶음. 잠재적 문제점은 간혹가다 변수들이 exclusive하지 않을 경우 문제가 발생할 수 있음.  almost exclusvie가 아니라 exclusive한 변수들을 묶어도 퍼포먼스 저하가 일어나지 않음.

 

EFB - STEP1 ) Greedy Bundling

• 현재 존재하는 feature에 대해 어떤 feature를 하나의 번들로 묶을지 결정.
• 두 변수씩 비교해서 둘 다 동시에 0이 아닌 값을 갖는 데이터(not mutually exclusive)의 수를 테이블에 기록.
• 각 변수(노드)의 degree가 큰 순서대로 cut-off 값 적용해서 edge 지워감.
• degree? 해당 노드에 연결된 edge의 개수 
• cut-off = 0.2 / hyper parameter => n=10 * 0.2 =  두 변수에 대해 동시에 0이 아닌 값을 갖는 객체의 수가 2 이상인 경우 bundling을 하지 않겠다. 대상에서 제외. 2 이상인 edge는 삭제, degree 가 큰 순서대로 진행.
• conflict가 많은 변수는 번들로 묶이지 않음. => x5만 따로.
• conflict란 non-zero value가 동시에 존재해 상호배타적이지 않은 상황.

not mutually exclusive 수 테이블에 기록

 

cut-off 정한 후 edge 지워감(좌) > 그 결과(우)  

EFB - STEP2 ) Merge Exclusive Features 

• 번들 결과를 바탕으로 하나의 결과값으로 표현하고자 하는 과정.
• 기준변수 0이고, 기준변수가 아닌 변수의 값이 0이 아닐 경우 새 변수의 값은 기준변수가 아닌 변수의 값 + offset(기준 변수의 최대값). Q. 왜 오프셋을 더하는가? 논문 봐도 이해안감 ㅠㅠ..
• 새 변수의 값을 채우는 기준 => x4가 0일 경우 x1값으로 채움/ x4가 0이 아니고 x1이 0일 경우 x4+offset 3 으로 채움 / 둘 다 nonzero value일 경우(conflict)할 경우 기준 변수의 값으로 채움
• 충돌된 데이터 외에는 손실되는 데이터가 없음.