[ML] Unbiased boosting : CatBoost

이번 포스팅에서는 Boosting 계열의 알고리즘 중에서 GBM(Gradient Boosting Machines) 알고리즘에 기반하여 만들어진  CatBoost 알고리즘에 대해 알아보려고 한다. CatBoost는 2017년 논문에서 소개되었으며 현재까지 현업에서도 활발하게 사용되고 있다고 한다. 우선 CatBoost 를 본격적으로 소개하기 전에 GBM에 대한 개념부터 살펴보고 들어가자.

 

Catboost = Cat + boost 인가? 🤔

---

1. Gradient Boosting = Residual Boosting 

Gradient Boosting의 기본적인 아이디어는 주어진 데이터의 일부를 학습시켜 만든 모델로 다른 데이터를 예측한 후 알게되는 잔차를 이용하는 것이다. 이렇게 주어진 데이터에 대해 계속적으로 학습 후 모델을 만들고 다른 데이터를 예측함으로써 결국 잔차를 줄여나가보자는 아이디어에서 개발되었다.

 

그런데 모두가 알다시피 Gradient는 머신러닝 분야에서 자주 접하며 최적화 기법 중 하나인 SGD(Stochastic Gradient Descent)의 Gradient 와 동일한 것을 의미한다. 그렇다면 Gradient란 직관적으로 무엇일까? 바로 어떠한 함수를 '미분'하는 것을 의미한다. 그렇다면 미분한다는 것은 무엇일까? 바로 변화량을 의미한다. 아마 고등학교 수학 시간에 이차함수에 대한 기울기를 구하면서 수학 선생님이 변화량이라고 말씀하시는 것을 들어본 적이 있을 것이다. 만약 들어보지 못했다면 다음 그림을 보면 직관적으로 이해가 될 것이다.

 

Gradient는 얼마나 변화했는지 변화량을 의미한다.

자, 이제 그렇다면 왜 변화량, 미분을 의미하는 Gradient가 Residual(잔차)와 동일하다는 것일까? 이에 대해서는 Loss function과의 관계를 통해 이해할 수 있다. 잠깐 예시를 들어보자. 현재 주어진 데이터가 10개의 데이터가 존재한다. 머신러닝 모델은 1개의 데이터를 학습시키면서 Loss function에 기반하여 실제값과 예측값의 차이(Error)가 얼마인지 확인하고 Loss function을 미분하면서 최적의 파라미터를 찾아가는 방향으로 학습하게 된다. 이 때 1개의 데이터를 학습한 후 Loss function이 다음과 같다고 가정해보자.(여기서 Loss function은 MSE(Mean Squared Error)라고 가정하자)

$$ Loss(L) = {1 \over 2} \sum_{i=1}^n {\left\{ y_i - f(x_i)\right\}}^2$$

이 때, 위 Loss function을 $f(x_i)$를 기준으로 미분을 취해주면 다음과 같은 수식이 전개된다.

$$ {\partial L \over \partial f(x_i) } = - \left\{ y_i - f(x_i) \right\} $$

위 수식에서 우변에서 음수(-)를 떼어보면 우리가 흔히 아는 실제값에서 예측값을 뺀 잔차(Residual = Error)값이 되게 된다. 그리고 위 수식에서 양 변에 음수(-)를 곱해준다면 최종적으로 다음과 같은 수식으로 변하게 된다.

$$ y_i - f(x_i) = - { {\partial L \over \partial f(x_i)} } $$

결국 좌변의 잔차(Residual)은 Loss function을 미분한 값에 음수를 붙인 Negative Gradient 값이 되게 된다. 그래서 잔차를 쓰되 잔차는 Gradient이기 때문에 모델의 이름이 GBM(Gradient Boosting Machine)이 된 것이다.

 

그렇다면 잔차를 계속적으로 이용해서 잔차를 줄여간다는 것을 어떤 것을 의미하는 걸까? 아래의 과정을 살펴보자.

 

GBM은 잔차에 포커스를 맞추어 학습하는 모델이다.

 

위 그림처럼 GBM은 최초의 데이터를 하나 학습할 때만 예측값을 기반으로 하고 그 이후의 데이터를 학습할 때는 예측값을 활용해서 계산한 잔차에만 포커스를 맞추어서 학습하게 된다. 하지만 이렇게 잔차에만 포커스를 맞추어 학습하는 것이 매우 이상적이라고 보일지도 모르겠지만 모델이 본적 없는 데이터에는 예측을 잘 하지 못하는 과적합(Overfitting) 문제를 유발할 가능성이 매우 높다는 것이 치명적인 단점이다.

2. GBM의 문제점을 개선한 CatBoost

방금도 언급했다시피 GBM의 치명적인 문제점 중 하나로 과적합 문제가 존재한다. CatBoost는 이 과적합 문제를 해결하면서 동시에 기존 GBM 계열 알고리즘인 XGBoost, LightGBM 알고리즘보다 학습 속도를 개선하는 장점을 앞세워 개발되었다. 또한 XGBoost, LightGBM이 Hyper-parameter에 따라 성능이 달라지는 민감한 문제를 해결하는 것에도 초점을 맞추었다. 이제 CatBoost에 대해서 하나씩 알아보자. CatBoost에 대한 내용 정리는 이 블로그를 읽어가면서 정리를 해서 글을 작성함을 먼저 알린다.

2-1. Symmetric Tree 구조

XGBoost는 Level-wise, LightGBM은 Leaf-wise를 기반으로 트리 구조를 형성한다. 다음 그림을 보자.

 

Catboost vs XGBoost vs LightGBM

 

우선 LightGBM은 알고리즘 종류 중 DFS(깊이 우선 탐색) 처럼 트리를 우선적으로 깊게 형성하는 방식을 취한다. 반면에 XGBoost는 BFS(너비 우선 탐색)처럼 우선적으로 넓게 트리를 형성하게 된다. 이 때 XGBoost 와 CatBoost와 차이점이 없는 것처럼 보이지만 자세히 보면 트리가 나누어지는 Feature들이 대칭인지 여부에 따라 차이점이 드러난다. CatBoost는 이렇게 Feature를 모두 동일하게 대칭적인 트리 구조를 형성하게 된다. 겉으로 보기에 이러한 대칭 트리 형성 구조가 비합리적이라고 보일 수 있지만 이는 예측 시간을 감소시킴으로써 기존 Boosting 계열 알고리즘이 느린 학습속도라는 측면에서는 CatBoost 만의 장점이 된다.

2-2. CatBoost는 어떻게 동작하는가?

다음과 같은 시계열 특성이 존재하는 예시 데이터가 있다고 가정해보자.

 

출처: Medium 블로그

 

• Step 1 : CatBoost가 x5에 대한 잔차를 계산하기 위해 x1, x2, x3, x4 데이터를 활용해 학습을 시켜 모델을 만든다.
• Step 2 : 학습한 모델을 가지고 x6에 대해 class label을 예측한다.
• Step 3 : Step 1 ~ 2 번을 반복한다. 예를 들어 x6에 대한 잔차를 계산하기 위해 x1, x2, x3, x4, x5 데이터를 활용해 학습을 시켜 모델을 만들고 x7에 대한 class label을 예측한다. 이러한 과정을 모든 데이터 포인트에 대해 반복한다.

참고로 CatBoost는 위와 같이 시계열이 포함되어 있지 않은 일반적인 비시계열 데이터라도 CatBoost가 임의적으로 시계열을 형성해 위와 같은 과정으로 Boosting을 진행한다. 그래서 어쨌거나 순서가 있는 부스팅이라고 하여 Ordered Boosting 이라고 불린다. 그러나 위와 같이 1개의 데이터 포인트들 마다 학습을 하게 되면 만약 10만개의 데이터가 존재하면 10만개의 모델을 학습시켜야만 한다. 따라서 연산 비용에 있어서 심각한 문제가 발생한다. 보통 이를 해결하기 위해 $log(Number \,of \,datapoints)$ 개수만큼의 모델을 학습하게 된다. 

 

위 데이터로 잠깐 예시를 들어보자면, 만약 주어진 데이터를 가지고 2개의 모델을 만든다고 한다면 다음과 같은 2가지 모델이 만들어진다.

 

1. x1, x2, x3 학습 후 x4, x5, x6에 대한 잔차 계산한 모델
2. x4, x5, x6 학습 후 x7, x8, x9에 대한 잔차 계산한 모델

그리고 x10을 최종 테스트 데이터로서 예측하게 된다.

2-3. Random Permutations

CatBoost는 주어진 전체 데이터를 임의적으로 $N$개의 Fold로 나누어서 각 Fold에 속한 데이터셋들에 Ordered Boosting을 적용한다. 마치 K-fold Cross Validation 과정처럼 말이다. 예를 들어, 100개의 데이터가 존재할 때, CatBoost는 4개의 Fold로 나누기로 했으면 주어진 데이터셋을 25개씩 나누고 각 25개의 데이터셋 마다 Ordered Boosting을 적용하게 된다. 이러한 방식은 부스팅 계열 알고리즘의 단점인 과적합 문제를 예방하는 데 도움이 된다. 

2-4. 범주형 변수 인코딩하기

범주형 변수가 존재한다면 수치형 변수로 변환을 해주어야 한다. 이 때 CatBoost는 Response Encoding(=Mean Encoding = Target Encoding) 방법을 사용하게 된다. 해당 인코딩 방법에 대해서는 기존 블로그 글을 참고하자. 그런데 이 인코딩 방법을 사용할 때 주의해야 할 점이 있다. 평균(Mean)이라는 것을 사용하기 때문에 자칫하면 과거의 데이터를 인코딩 할 때 미래의 값을 사용하여 Data Leakage 문제를 일으킬 수 있다. 예를 들어, 학습 데이터의 범주형 변수를 변환시킬 때 검증(또는 테스트) 데이터의 범주형 변수를 활용한다는 것이다. 하지만 CatBoost는 2-2 목차에서 언급했던 것처럼 자체적으로 데이터셋에 시계열을 부여한다고 했다. 이러한 특성으로 인해 CatBoost 알고리즘 내부적으로 범주형 변수를 인코딩할 때 Data Leakage 문제를 일으키지 않도록 한다. 또한 다음과 같은 0으로 나누게 되는 수학적인 문제를 예방하기 위해서 분자, 분모에 매우 작은 스칼라값을 추가하는 라플라스 스무딩 기법을 사용하기도 한다.

 

출처 : Medium 블로그

2-5. 중복되는 범주형 변수 처리

CatBoost는 데이터셋의 Class를 명확하게 구분할 수 있는 중복되는 변수가 2개 이상 존재한다고 할 때, 이를 하나의 변수로 통합해 처리한다. 이렇게 함으로써 Feature가 늘어나는 문제를 예방함으로써 연산 비용도 줄일 수 있게 된다. 바로 다음과 같은 예시일 때이다.

 

출처 : Medium 블로그

2-6. One-Hot Encdoing 처리

CatBoost는 Hyper-parameter로서 one_hot_max_size = $N$ 라는 값을 따로 설정해주면 범주형 변수들 중 값의 level 개수가 $N$ 개수보다 작다면 해당 범주형 변수를 자동으로 One-Hot Encoding으로 처리해준다. 즉, Cardinality가 낮은(중복도가 높은) 범주형 변수들에게 적용하게 된다.

2-7. 수치형 변수 처리

일반 Tree-based 알고리즘 처럼 Information Gain을 활용해서 최적의 Split 기준을 계산하게 된다.

2-8. CatBoost의 한계

Sparse Matrix 즉, 결측치가 매우 많은 데이터셋에는 부적합한 모델이다. 예를 들어, 추천시스템에 자주 사용되는 사용자-아이템 행렬 데이터를 살펴보면 보통 Sparse한 형태로 이루어져 있다. 만약 이러한 데이터를 활용하려면 Sparse한 특성이 없도록 Embedding을 적용한다던지 등 데이터를 변형한 후 CatBoost에 활용하는 것이 적합할 것이다. 또한 애초에 수치형 변수가 매우 많은 데이터라면 LightGBM 보다 학습 속도가 오래 걸린다.(아마 그래서 범주형 변수가 많을 때 적합한 알고리즘이라는 의미로 CatBoost의 Cat이 Categorical의 Cat이 아닐까 한다)

---

다음은 이 글을 작성할 때 번역한 블로그의 저자가 추천하는 CatBoost 파라미터 활용 방식에 대해 소개하려고 한다. 블로그 저자가 다양한 상황에 맞추어서 CatBoost를 활용한 방법들에 대해 제안해놓았는데 인상적이어서 이 내용에 대해서도 기록해보고자 한다.

 

• 데이터가 시간이 지나면서 매우 변화하는 특성일 때(아마 현실세계의 데이터가 모두 이럴 것이다) has_time 이라는 파라미터를 True로 설정하는 것을 권고
• 만약 빨리 학습하고 예측 결과값을 서빙해야 하는 비즈니스일 때(Low Latency)
• 특정 데이터 포인트에 더 가중치를 줌으로써 CatBoost에서 Random Permutation을 수행할 때 해당 데이터 포인트들이 선택될 확률을 높게 하도록 설정할 수 있음
• 작은 데이터셋일 때, fold_len_multiplier 파라미터 값을 1에 근접하게 설정(해당 파라미터값은 무조건 1보다 커야 한다) 하고 approx_on_full_history 파라미터를 True로 설정
• 큰 데이터셋일 때, task_type = GPU 로 설정함으로써 학습 시 GPU 사용 가능
• Error 모니터링을 하기 위해 custom_metric 파라미터에 메트릭을 설정 가능. ex) custom_metric=['AUC', 'Logloss']
• 특정 Stage에서 예측한 모델을 활용 가능. 최종 파라미터 모델이 중간에 학습한 모델 보다 성능이 안좋을 경우 중간에 학습시킨 모델을 shrink 메소드로 불러올 수 있다. 
• 특정 Stage에서 예측한 모델의 성능을 볼 수 있음. staget_predict 메소드로 확인 가능
• 현실 세계의 시계열 데이터에서 특정 기간동안만 나타나는 특성이 있을 수 있음. 예를 들어 주말 기간에만 나타나는 특징, 여름/겨울에 나타나는 특징 등.. 이러한 기간을 나누어서 개별 모델을 만들어서 학습시키고 sum_models 메소드로 여러 모델들을 결합할 수 있음
• ord_type 파라미터를 Iter 로 설정 시 교차검증 시 Early Stopping 가능
• class_weights 파라미터로 클래스 불균형 문제 해소 가능
• 중요한 Feature가 무엇인지 확인 가능
• 추가적으로 Learning rate, random_strength, L2_regularizer 같은 파라미터가 있지만 이 파라미터들에 성능이 크게 달라지지 않는다고 함