[Machine Learning] CatBoost
Boosting알고리즘의 마지막은 CatBoost입니다. 이 모델은 제가 현재 재직중인 회사에서도 빈번하게 사용하는 모델인데요. 특히나 특별한 Hyper-parameter 튜닝이 필요하지 않은 것으로 알려져있죠. 어떤 특징이 있는지 한번 알아보겠습니다. 역시 서울대학교 강필성 교수님 강의를 많이 참고하였습니다.
1. 기존 GBM의 문제점
일단, CatBoost가 등장한 맥락을 먼저 살펴보겠습니다. 어떤 문제가 있었기에 CatBoost라는 것을 고안했는지 말이죠.
(1) Prediction Shift :
기존의 GBM에서는 Sampling을 통해서 Expectation을 계산하는데 당연하게도 Training dataset과 Test dataset의 Conditional distribution이 동일할 것이라 기대합니다. 실제는 그렇지 않기에 "Prediction shift"가 생기게 됩니다.
\[ \arg \min_{h \in \mathcal{H}} \mathbb{E} \left[ \left(-g'(x, y) - h(x)\right)^2 \right] \approx \arg \min_{h \in \mathcal{H}} \frac{1}{n} \sum_{k=1}^{n} \left(-g'(x_k, y_k) - h(x_k)\right)^2 \] Training Dataset: \(\mathcal{D} = \{(\mathbf{x}_k, y_k)\}_{k=1,\ldots,n}\) where \(\mathbf{x}_k = (x_k^1, \ldots, x_k^m)\), \(y_k \in \mathbb{R}\)
Training Data의 \( F^{t-1}(\mathbf{x}_k) \mid \mathbf{x}_k \) 와 Test Data의 \( F^{t-1}(\mathbf{x}_k) \mid \mathbf{x}_k \)가 같지 않다는 겁니다.
(2) Target Leakage :
만약, Categorical Feature를 수치화(Embedding)할 때 training data안에 있는 target의 평균값으로 설정하면(Data imbalance문제 등을 해결하기 위해 one-hot encoding이 아닌 이런 식의 인코딩을 할 때도 있습니다) 어떻게 될까요? 우리는 주어진 설명변수를 이용해서 Target을 맞추는 과제를 해야하는데.. 설명변수에 그 Target의 정보가 이미 들어가 있죠? 마치 KOSPI주가 지수를 맞추려고 하는데 설명변수에 삼성전자의 주가가 들어가있는 그런 상황으로 비유할 수 있을 것 같습니다.
강필성 교수님의 강의에서는 Prediction Shift / Target Leakage의 예시가 나와 있습니다. 우리는 카테고리 변수를 아래와 같이 수치화했다고 해보겠습니다. \[ \hat{x}_k^i = \frac{\sum_{j=1}^{n} \mathbf{1} \{ x_j^i = x_k^i \} \cdot y_j + a p} {\sum_{j=1}^{n} \mathbf{1} \{ x_j^i = x_k^i \} + a} \]
사실 이 설명변수는 원래 raw data가 A, B, C, D, E...인 한눈에 봐도 분류에 쓸모없는 녀석이었는데.. 이렇게 변환하고 보니 마치 엄청 분류에 설명력이 좋은 변수처럼 되어 버렸습니다. 더구나 Test data가 아래와 같이 들어온다고 하면 더욱 더 문제가 심각해집니다.
아니나 다를까 Test data에 대해서는 전혀 쓸모없네요.. 왜 이런일이 발생한 걸까요? \(y_j\) 가 문제라는 겁니다. 지금 Target statistics를 만드는데 이 녀석이 들어가 있는데, Training에서는 \(x_k\)를 계산하는 과정에서 \(y_k\)를 쓸 수 있지만 Test에서는 \(x_i\)를 계산하는 과정에서 \(y_i\)를 쓸 수 없고 결국 \(\hat{x}^i|y\)의 분포가 training과 test 데이터 간에 다르기때문에 conditional shift가 생긴다는 것입니다.
그렇다면 바람직한 target statistics의 조건은 무엇일까요? Catboost 논문의 저자들이 말하는 조건은 다음과 같습니다.
\(\mathbb{E}(\hat{x}^i \mid y = v) = \mathbb{E}(\hat{x}_k^i \mid y_k = v) \quad \text{where } (\mathbf{x}_k, y_k) \text{ is the } k\text{-th training example} \)
Effective Usage of all training data for calculating TS features and for learning a model
CatBoost에서는 이를 위해서 어떤 접근을 취할까요?
1) Ordered Target Statistics
CatBoost에서는 target statistics를 만들 때 (비록 그 데이터가 시계열 데이터가 아닐지라도) 마치 가상의 시간이라는 개념이 있다고 생각하고 현 시점전까지의 데이터만을 가지고 인코딩하게 됩니다. \( \mathcal{D}_k = \{ \mathbf{x}_j : \sigma(j) < \sigma(k) \} \])
\[ \hat{x}_k^i = \frac{\sum_{\mathbf{x}_j \in \mathcal{D}_k} \mathbf{1} \{ x_j^i = x_k^i \} \cdot y_j + a p} {\sum_{\mathbf{x}_j \in \mathcal{D}_k} \mathbf{1} \{ x_j^i = x_k^i \} + a} \]
모양은 이전의 TS와 거의 유사하지만 하나가 다르죠? 시그마 인덱스 범위가 해당 관측치 이전까지의 범위로 좁혀졌습니다. 강필성 교수님의 예시를 살펴볼까요? (hyper-parameter \(a=0.1\)로 설정했다고 하겠습니다)
이런식으로 쭉 계산해 나가면
2) Ordered Boosting
기존의 부스팅 모델은 모든 training 데이터 전체에 대해 residual 계산을 하게됩니다. Ordered Boosting에서는 일부만 가지고 Residual 계산을 해서 모델을 일단 생성합니다. 그리고 다시 이 모델의 예측치를 가지고 잔차를 계산합니다. (반복) 강필성 교수님의 그림을 보면 이해가 빠를 것 같습니다.
자 그럼 Catboost의 작동에 대해서 전체적으로 한 번 짚어보고 끝내겠습니다.
CatBoost Procedure
1) Initialization: generate (s+1) independent random permutations of the training dataset
- s permutations to evaluate the split
- 1 permutation to compute the leaf value of the obtained trees
2) Building an oblivious tree in the ordered boosting mode
Oblivious Tree는 트리의 모든 노드에서 **동일한 feature를 사용하여 데이터를 분할합니다.
역시.. 빛강필성 교수님의 예시를 한번 볼까요?
leaf node에 아직 아무값도 없었던 처음 두 관측은 0으로 initialize한다고 가정했습니다.
이런식으로 이어 나가다보면...
Loss는 아래와 같이 계산할 수 있습니다.
