기계 학습 관련된 지식은 현재 공부하는 중입니다. 차후 스스로 전문가라고 자칭할 수 있을 때, 잘못된 지식은 수정 예정입니다.
기계 학습에서는 주로 함수의 기울기(Gradient, 이하 그라디언트)를 이용하여 최적화(Optimization)하는 알고리즘을 이용한다. 현재까지 저자가 이해한 기계 학습은, 여러 함수가 관여하여 만들어진 신경망(Neural network)을 이용하여 결론을 예측하고 데이터와의 차이를 측정하는 손실 함수(Loss function, or objective function)를 최적화하는 과정이다. 여기에서 다른 수치 해석 분야들과 조금 다르게, 경사 하강법(Gradient-descent method)에서 파생된 방법들을 주로 사용한다.
수리 모델링으로 데이터를 분석할 때와 다르게, 기계 학습에서 의사 결정 트리(Decision tree) 모델도 상당히 많이 이용한다. 이 모델에선 잘 분류하여 획득하게 되는 정보의 양을 따지게 되는데, 이를 판단할 수 있는 지표로 정보 이득(Information gain)을 사용한다. 이 계열에서 발전한 방법들에 XGBoost, pGBRT 등이 있으며, 이들은 Gradient boosting decision tree (GBDT) 알고리즘의 일환이다. LightGBM(LGBM)은 위 기존 방법들의 한계점들을 극복하기위해 개발된 알고리즘이다.
기존의 문제와 해결
LGBM 논문의 저자는 기존 GBDT의 알고리즘들이, 특히 feature 수가 많고(또는, feature dimension이 높고) data size가 클 때, 효율성과 정확도에 문제를 가지고 있다고 논문에서 밝힌다. 모든 split point의 정보 이득을 계산하기 위해 매번 모든 data와 freature를 읽어야 한다. 즉, 계산 복잡도(Computational complexity)가 feature 수와 data 수 모두에 비례하게 된다. 그래서, 논문에서는 각각의 목적을 가진 두가지 방식을 제안한다.
- GOSS(Gradient-based One-Side Sampling); data 수 줄이기
- EFB(Exclusive Feature Bundling); feature 수 줄이기
GOSS 방법은, 그라디언트의 크기에 따라서 다음 스텝에 영향 주는 것이 달라지는 것을 활용하여 업데이트 계산에 포함되는 Data 수를 줄이는 방법이다. 훈련(Training) 과정 중에 data size가 너무 큰 경우는 흔하기 때문에, 그 수를 줄이려는 노력은 계속있어 왔다. 예를 들어, SGB(Stochastic gradient boosting) 방법은 무작위로 선택하여 업데이트에 반영한다. 하지만, 이러한 방법들은 보통 정확도를 낮추게 된다. GOSS는 이러한 정확도 손실 없이 진행할 수 있다.
EFB 방법은, 반면에, feature 수를 줄이는 방법인데, 이는 기계 학습에서 주로 이용하는 data의 특징을 이용한 것이다. 주로, data들을 one-hot encoding 등을 이용해 굉장히 sparse하게 만들게 되는데, 서로 베타적인(mutually exclusive) feature들을 묶어서 bundle로 사용하면 그 수를 확연히 줄일 수 있다. 여기에서 서로 베타적인 feature란 동시에 0이 아닌 값을 같지 않는 두 feature를 의미한다. 즉, bundle을 사용한다면 정확도 손실 없이 GBDT의 훈련을 많이 증가시킬 수 있다.
GOSS
앞서 설명한 바와 같이, GOSS 방법은 정확도 손실 없이 data 샘플을 줄이는 다운 샘플링(Down sampling) 방법이다. 어떤 방법이길레 가능하게 되는 것일까? GOSS는, 먼저, 그라디언트의 절댓값을 기준으로 data를 정렬한다. 여기에서 상위 $a\times 100\%$개의 data와 나머지 하위 data 중 $b\times 100\%$개를 임의로 추출하여 사용하는 방식이다. 이후, 작은 하위 data에서 추출한 값에서 계산한 정보 이득에 $\frac{1-a}{b}$을 곱하여 수준을 상위 그룹에 동일하게 조절해 사용한다. 논문에서는 이 이유를 훈련에 덜 참여하게 되는 data들을 원본 data distribution에 큰 변화를 주지 않고 집중하게 되는 효과를 준다고 한다.
아래와 같은 Theorem을 논문에서 제시하고 있는데, 이를 통해서 우리는 GOSS를 통해 얻은 새로운 정보 이득이 원본 data를 모두 사용한 값과 어느 정도의 차이를 가지는 지 알 수 있다.
Theorem. We denote the approximation error in GOSS as $\varepsilon(d)$ and \(\bar{g}^j_l(d)=\frac{\sum_{x_i\in(A\cup A^c)_l}\lvert g_i\rvert}{n^j_l(d)}, \bar{g}^j_r(d)=\frac{\sum_{x_i\in(A\cup A^c)_r}\lvert g_i\rvert}{n^j_r(d)}\) as the average value of absolute gradient values in, $l$, left split and $r$, right split, respectively. With probability at least $1-\delta$, we have
\[\mathcal{E}(d)\leq C^2_{a,b}\log1/\delta \cdot\max\left\{\frac{1}{n^j_l(d)}, \frac{1}{n^j_r(d)}\right\}+2DC_{a,b}\sqrt{\frac{1/\delta}{n}}\]where $C_{a,b}=\frac{1-a}{\sqrt{b}}\max_{x_i\in A^C}\lvert g_i\rvert$, and $D=\max(\bar{g}^j_l(d),\bar{g}^j_r(d))$.
여기에서 저자들은 GOSS로 구한 값의 오차가 $\mathcal{O}\left(\frac{1}{n^j_l(d)}+\frac{1}{n^j_r(d)}+\frac{1}{\sqrt{n}}\right)$으로 제한되고, 너무 언밸런스하게 split되지 않는 이상, $n$이 커질 수록 0에 가까워지는 것을 보여준다고 한다. 이는, data 수가 많아지면, 근사가 거의 정확하다는 것을 보여준다.
그런데, 증명과정에서 몇가지 의아한 점이 있다.
\[\begin{align*} C_l&:=\frac{1}{n^j_l(d)}\left(2\sum_{A_l}g_i+\sum_{A_l^C}g_i+\frac{1-a}{b}\sum_{B_l}g_i\right)\\ C_r&:=\frac{1}{n^j_r(d)}\left(2\sum_{A_r}g_i+\sum_{A_r^C}g_i+\frac{1-a}{b}\sum_{B_r}g_i\right)\\ Y_l&:=-\sum_{A_l^C}g_i+\frac{1-a}{b}\sum_{B_l}g_i\\ Y_r&:=-\sum_{A_r^C}g_i+\frac{1-a}{b}\sum_{B_r}g_i \end{align*}\]- 위에서 $C_lY_l+C_rY_r\leq \max{C_l,C_r}(Y_l+Y_r)$가 일반적으로 성립하지 않는데, 그냥 사용한다.
아래 식이 성립하지 않는다.
\[\frac{1}{n^j_l(d)}\left|\frac{1-a}{b}\sum_{B_l}g_i-\sum_{A^C_l}g_i\right|\leq \frac{D_{A^C}}{n^j_l(d)}\left|\frac{1-a}{b}\sum_{B_l}1-\sum_{A^C_l}1\right|\]Hoeffding’s inequality를 사용하는데 정확한 서술을 파악하기 힘들다. 아마 1개의 Hypothesis와 $bn$개의 sample이라고 생각하고 적용하는 것 같은데 맞다면 아래와 같이 $\delta$가 서술된다. 추후 확신할 수 있을듯.
\[P(\text{오차가 $\varepsilon$보다 크다})=\delta=2e^{-2\varepsilon^2bn}\]
EFB
EFB는 먼저 상호 베타적인 feature들을 찾는 알고리즘을 잘 구현해야 할 것이다. 하지만, 저자들은 이 문제가 그래프 색칠(Graph coloring) 문제로 환원(reduction)되기 때문에, NP-완전(NP-complete) 문제가 되고, 그러므로 다항 시간(Polynomial time, $\mathcal{O}(n^k)$) 내에 최적으로 묶는 bundle을 찾을 수 없다는 것을 알 수 있다. 대신, 그래프 색칠 문제로 환원하고 Greedy algorithm을 적용하여 답을 찾았다.
성능 테스트
[차후 추가 예정]
참고 자료
이 포스트는 LightGBM 논문과 해당 논문의 Supplementary information을 중점으로 공부하고 정리한 글이다. NP-complete 관련한 지식은 잘 모르고 있어서, 여러 블로그들(1,2)과 위키피디아의 그래프 색칠 문제, NP-완전 글을 참고하였다.
수정 사항
[23.05.17] 소제목 수정