[논문리뷰/설명] CatBoost: unbiased boosting with categorical features

요즘 가장 대표적인 그래디언트 부스팅(GBM) 모델을 고르자면 XGBoost, LightGBM, CatBoost 입니다.

세 알고리즘들은 모두 2016-2017년에 등장했고, 높은 완성도로 작성된 패키지를 통해 현재까지도 매우 활발하게 사용되고 있습니다. 이미지, 음성 데이터와 같은 비정형데이터에서는 딥러닝이 강세를 보이지만, 테이블 형태의 정형데이터에서는 GBM이 강세를 보입니다. GBM은 상대적으로 딥러닝보다 해석가능성(interpretability)이 높아서 결과의 근거를 찾을 수 있다는 장점도 있습니다.

 

앞서 XGBoost, LightGBM은 리뷰 포스팅을 했었고, 이제 마지막 CatBoost를 정리해볼까 합니다.

 

논문 링크: https://arxiv.org/abs/1706.09516

 

 

 

 

 Introduction

 

CatBoost는 Categorical Boosting을 줄인 것입니다. CatBoost는 범주형(categorical) 데이터를 처리하는 새로운 방법 을 제시하고, 기존의 그래디언트 부스팅 알고리즘을 조작하여 타겟 누수(target leakage)를 개선 합니다. target leakage는 예측 시점에서 사용할 수 없는 데이터가 데이터셋에 포함 되는 오류를 말합니다. 모델이 독립변수들인 $x$만을 활용하여 종속변수인 $y$를 예측해야 하는데, $y$에 대한 정보가 $x$에 포함되어 있는 것이 타겟누수입니다.

 

이제 CatBoost가 범주형 데이터를 처리하는 방식과 타겟누수를 개선하는 방식을 살펴보겠습니다.

 

 

 

 

 Categorical Features 

 

범주형 데이터는 서로 겹치지 않는 그룹으로 구성된 데이터입니다. 예를 들면 와인 데이터셋에서 색깔 변수 (red or white) 가 범주형 데이터입니다. 학습을 위해서는 이러한 범주형 데이터를 숫자형 (numeric) 데이터로 바꾸어야 하는데, 대표적인 방법이 one-hot encoding입니다. 그런데 변수의 범주가 너무 많다면 one-hot encoding을 수행할 때 너무 데이터셋의 크기가 커지게 됩니다. 따라서 이를 방지하기 위해 one-hot encoding 수행 전에, 범주를 군집화 (clustering) 하여 그 수를 줄이거나, 새로운 숫자형 데이터로 변환할 수 있습니다. 본 논문에서는 새로운 숫자형 데이터로 변환하는 target statistics  방식을 소개합니다.

Target Statistics (TS)

먼저 수식으로 TS를 살펴봅시다.

$$\hat{x}_{k}^{i} \approx \mathbb{E} (y | x_i = x_{k}^{i})$$

$i$번 째 feature 값이 $k$번 째 데이터셋의 값과 같은 모든 데이터의 target value $y$ 평균으로 산출합니다. 본 논문에서는 TS 산출 방법으로 Greedy TS, Holdout TS, Leave-one-out TS, Ordered TS를 소개하는데, 하나씩 살펴봅시다. CatBoost는 Ordered TS를 활용합니다.

 

 

1. Greedy TS

단순히 아래와 같은 수식으로 Feature의 각 범주에 TS를 할당하는 것입니다.

 

여기서 $a > 0$는 파라미터이고, $p$는 데이터셋의 target value 평균입니다. $a, p$값을 사용하는 이유는 빈도가 낮은 범주의 경우 데이터의 노이즈가 심해지기 때문에 이를 줄이기 위해서라고 언급하고 있습니다. 이렇게 TS를 할당했을 경우, $\hat{x}_{k}^{i}$가 target value인 $y_k$로부터 산출되기 때문에 target leakage가 발생합니다. 또한 training-test 데이터셋 사이에 분포의 차이로 인한 오류가 생길 수 있습니다. 논문에서 제시한 오류의 예시는 다음과 같습니다.

 

• 범주형 변수 $i$에 대해, 모든 값이 unique하고, 각 범주 $A$에 대해 확률 $P(y=1|x^i = A) = 0.5$ 라고 가정
• training 데이터셋에서는 $\hat{x}_{k}^{i} = \frac{y_k + ap}{1 + a}$,
  test 데이터셋에서는 $\hat{x}_{k}^{i} = \frac{0 + ap}{0 + a} = p$
• training, test 데이터셋의 $x^i$의 분포가 상이한 conditional shift 발생 (conditional shift 관련 논문 링크)

모델을 학습할 때에는 training, test 데이터셋의 분포가 동일한 것이 이상적일 것입니다. 하지만 Greedy TS 방식을 차용하였을 때는 두 데이터셋의 TS값의 분포가 상이해지는 conditional shift가 발생할 수 있습니다.

이를 방지하기 위해 training 데이터셋과 test 데이터셋에서 산출된 TS값의 평균이 서로 같아야 한다 는 다음과 같은 Property를 제안합니다.

 

Property 1.  $\mathbb{E}(\hat{x}^i | y = v) = \mathbb{E}(\hat{x}_{k}^{i} | y_k = v)$ where $(\mathbf{x}_k, y_k)$ is the $k$-th training example.

 

Conditional shift를 방지하기 위한 여러 방법들이 있는데, 일반적인 아이디어는 $k$번 째 데이터 $\mathbf{x}_k$의 TS를 계산할 때, 해당 데이터를 제외하고 TS를 산출하는 것입니다. 즉, 데이터셋 $\mathcal{D}_k \subset \mathcal{D} \setminus \left\{ \mathbf{x}_k \right\}$ 에 대하여 다음과 같이 TS를 산출합니다.

$$\hat{x}_{k}^{i}  = \frac{\sum_{\mathbf{x}_j \in \mathcal{D}_k} \mathbf{1}_{\left\{ x_{j}^{i} = x_{k}^{i} \right\}} \cdot y_j + ap}{\sum_{\mathbf{x}_j \in \mathcal{D}_k} \mathbf{1}_{\left\{ x_{j}^{i} = x_{k}^{i} \right\}} + a} \tag{5}$$

 

2. Holdout TS

Holdout TS는 앞서 설명했던 conditional shift를 방지하기 위해, 아예 training 데이터셋을 두 부분으로 나누어 하나는 TS 계산에, 하나는 학습에 활용하는 방법입니다. 이렇게 되면 Property 1 은 만족하지만, 학습과 TS 계산에 사용하는 데이터가 분리되어 데이터의 양이 줄어든다는 단점이 있습니다. 본 논문에서는 다음의 property를 이어서 제시합니다.

 

Property 2.  Effective usage of all training data for calculating TS features and for learning a model.

 

 

3. Leave-one-out TS

(5)번 식처럼 해당 데이터를 제외하고 TS를 산출하는 것입니다.

 

 

4. Ordered TS

데이터셋에 임의의 시간 값 (random permutation)을 부여하고, $k$번 째 데이터의 TS를 계산할 때, $k-1$번까지 데이터의 target value만을 사용하는 것입니다. 이를 통해 target leakage를 방지할 수 있습니다. 또한 모든 데이터셋을 학습에 사용할 수 있기 때문에 Property 1, 2를 모두 만족합니다. CatBoost에서는 이 Ordered TS 방법을 활용합니다.

 

 

---

 

 

정리하자면 CatBoost는,

 

1. TS 산출 과정에서 target leakage를 방지하는 property 1,

2. 최대한 많은 training data를 TS 산출과 모델 학습에 사용하는 property 2

 

를 모두 만족하는 Ordered TS를 활용합니다.

Ordered TS의 구체적인 작동 예시는 이어지는 챕터의 Ordered Boosting 부분에서 살펴보겠습니다.

 

 

 

 

 Prediction shift and ordered boosting

Prediction Shift

기존의 그래디언트 부스팅 방법들은 손실함수를 target value에 대해 편미분한 그래디언트 값을 활용합니다. 아주 좋은 아이디어이긴 하지만, target value를 활용하여 생기는 target leakage로 인해 training/test 데이터셋의 output의 분포에 차이가 생기게 되고 오버피팅을 발생시킨다 는 고질적인 문제가 있습니다. 이것을 논문에서는 Prediction shift라고 말합니다.

 

Prediction shift의 원인이 되는 target leakage를 방지하기 위해서 CatBoost는 트리를 학습하는 매 스텝마다 다른 데이터셋 (independent samples) 을 활용해야 한다고 말합니다. 논문에서 제시하는 다음 정리를 봅시다.

 

 

 

앞 부분이 생략되어 있긴 하지만, 이 정리의 의미는 독립된 데이터셋 $\mathcal{D}_1, \mathcal{D}_2$를 사용하여 각각의 트리를 구성하였을 때보다 $\mathcal{D}$만을 활용하여 트리를 구성할 때 $-\frac{1}{n-1} c_2 (x^2 - \frac{1}{2} + O(1/2^n))$ 만큼의 bias가 발생할 수 있다는 정리입니다. 여기서 $c_2$는 두 번째 트리를 구성할 때 활용되는 coefficient라고 생각하시면 됩니다.

 

따라서 CatBoost는 매 스텝마다 독립적인 데이터셋을 활용하기 위해, 트리를 구성하는 매 스텝마다 임의의 permutation에 따라 데이터셋을 추출하여 독립적인 데이터셋을 활용하는 것처럼 알고리즘을 구성합니다. 

 

이어서 prediction shift를 방지하는 CatBoost의 부스팅 기법인 Ordered boosting에 대해서 살펴보겠습니다.

 

 

---

Ordered boosting

 

위 그림은 Ordered boosting을 잘 설명하는 그림입니다. 그래디언트 부스팅은 매 트리 생성에 residual(잔차)을 학습합니다. 위 그림에서의 잔차 $r^t (\mathbf{x}_7, y_7)$ 이 $y_7 - M_{6}^{t-1}(\mathbf{x}_7)$ 인데, 잔차를 계산할 때 직전에 학습되었던 모델 $M_{6}^{t-1}$을 사용하는 것을 알 수 있습니다. $t-1$은 $t$번 째 스텝에서 $t-1$번 째에 학습된 모델을 활용한다는 의미입니다.

 

정리하자면, 임의의 permutation (순열) 을 만들고, 순차적으로 잔차를 계산하여 트리를 학습하면서 target leakage를 방지하는 것입니다. 하지만 이러한 방식은 데이터 개수만큼의 서로 다른 학습모델을 필요로 하고, 이는 복잡도와 메모리 요구량을 상승시킵니다. CatBoost의 Ordered boosting은 이를 방지하기 위해 그래디언트 부스팅 알고리즘을 일부 수정하는데, 어떤 방식으로 작동하는지 살펴봅시다.

 

Ordered boosting 작동 방식

Mode = Ordered 를 기준으로 살펴봅시다.

$M_{r, j}(i)$는 permutation $\sigma_r$의 $j$번 째까지 데이터로 학습된 모델의 $i$번 째 데이터에 대한 예측값입니다.

그래디언트는 다음과 같이 계산됩니다.

$$grad_{r,j}(i) = \left. \frac{\partial L(y_i, s)}{\partial s} \right|_{s = M_{r,j}(i)}$$

 

알고리즘을 시작하기 전에, 본 논문에서는 prediction shift를 방지하기 위해서 각 스텝에서 ordered boosting에 사용하는 permutation과 동일한 permutation이 앞에서 설명했던 ordered TS 산출에도 사용되어야 한다고 언급하고 있습니다. 논문에서는 이런 방식이 어떻게 prediction shift를 방지하는지 이론적으로 증명한 것도 제시하고 있습니다.

 

<Ordered Boosting 작동 방식>

 

• 주어진 $L$(손실함수), $M$(모델), $y$(target value)를 활용하여 그래디언트 계산
• 임의의 permutation $\sigma_r$ 선택
• $\sigma_r$에 따라 모든 데이터로부터 그래디언트 계산
• leaf value인 $\Delta (i)$에 대해서, 이전 스텝의 트리의 leaf에 해당하는 부분의 그래디언트 평균을 할당
  여기서 $\sigma_r$의 순서를 따라서 $\Delta (i)$ 할당
• 사전에 계산한 그래디언트와 새로 할당한 $\Delta$ 사이의 cosine similarity가 가장 적은 split point 선정
• 반복

 

추가적으로, CatBoost는 트리를 구성할 때 oblivious decision tree (ODT) 로 구성합니다. ODT는 아래 이미지처럼 트리의 level 마다 동일한 조건을 부여하여 좌우대칭의 형태로 만든 decision tree입니다.

 

출처: https://tex.stackexchange.com/questions/499172/alignment-of-table-and-tikz-figure-in-float

 

ODT 방식은 오버피팅 가능성을 줄여주고, 학습된 모델로부터 테스팅을 수행할 때 소요되는 시간을 줄여준다고 합니다. 

 

 

 

 

 Conclusion

 

CatBoost는 그래디언트 부스팅 모델이 가지고 있는 고질적 문제인 target leakage로 인한 prediction shift (로 인한 오버피팅) 를 다루기 위해 ordered boosting, ordered TS 라는 새로운 알고리즘을 제시했습니다. 많은 방법론들이 간과하고 넘어갔던 target leakage로 인한 오버피팅 문제를 모델 구성 단계에서 다뤘다는 점에서 CatBoost의 우수성을 볼 수 있는 것 같습니다.

 

여러가지 복잡한 증명들이 있어서 하나씩 살펴볼까 했으나 일단 CatBoost가 어떻게 작동하는지 원리만 알고 넘어가자는 나태한 생각에.... 여기까지만 쓰게 됐네요. 다른 포스팅들에 비해 다소 원리 해석이 적었던 것 같습니다. 

 

감사합니다!

 

 

 

참고자료

https://dailyheumsi.tistory.com/136

https://gentlej90.tistory.com/100