[분류 예측 스터디] CatBoost: unbiased boosting with categorical features

본 포스팅은 CatBoost: unbiased boosting with categorical features 논문을 참고하여 작성되었습니다.

 

작성자: 반민정

 

 

위 논문은 Gradient Boosting인 CatBoost에 대해서 설명하고 있다.

 

1. Introduction

 

Boosting은 Ensemble 기법 중 하나이며,

Emsemble 기법에는 Voting(hard, soft, weighted), Stacking, Bagging(decision/ randomforest), Boosting이 있다.

 

Boosting에는 Ada Boost, GBM, XGBoost, LightGBM 등이 있으며,

Gradient Boosting에는 Xgboost, Lightgbm, CatBoost 등이 있다.

 

 

Boosting은 weak model을 boosting하여 strong model로 제작하는 방식이며

Gradient Boosting(GBM)은 weak learner를 loss function 상에서 Gradient Descent를 최적화 기법으로 기울기가 가장 큰 방향으로 tree들을 결합하는 방법이다.

 

 

CatBoost 이전에 GBM 모델들에서는 다음과 같은 문제들이 발생하고 있다.

 

1. Prediction shift

  training data에서 학습한 것과 test data에서 학습한 모델과 많이 다르다. (overfitting)

2. Target leakage (타겟 누수)

  범주형 데이터를 다룰 때, feature의 정보를 input에 넣을 때 정답인 Y값을 이용한다.

 

 

따라서 CatBoost에서는 ordering principle을 통해 이를 해결한다. ordered boosting을 통해 prediction shift의 문제를 해결하고(Section4) ordered TS를 통해 범주형 변수들을 처리하는 알고리즘 또한 개선을 한다(Section3).

 

2. Background

Gradient Boosting의 방법

기존 Gradient Boosting은 loss를 최소화 할 때, Newton Method를 사용하여 gradient descent를 진행한다.

 

CatBoost는 binary decision tree를 베이스로 하는 gradient boosting으로 작동한다. 이때, decision tree h는 아래와 같이 나타낼 수 있다.

decision tree h(x)

 

3. Categorical Features

사람의 이름 등 서로 연결되어 있지 않고 비교할 수 없는 값을 categories(범주형)이라고 한다. 이런 범주형 feature을 다룰 때 제일 보편적인 방법은 one-hot encoding이다. 그러나 만약 고유한 ID 같이 범주형 데이터의 범주가 많아지게 되면(high cardinality) 새롭게 생겨나는 features들이 무수히 많아지게 된다. (ex. 사람이 1억명이면 새로운 feature가 1억개가 생김) 이렇게 되면 실질적으로 분석에 활용되기 어렵다.

 

따라서 categories를 clustering한 후(그룹을 지은 후), one-hot encoding을 적용하는 방법으로 이를 해결할 수 있다. Target statistics(TS)는 categorical feature들을 이들의 target 값의 statistic으로 대체한다. 그리고 TS를 새로운 수치형 feature처럼 취급한다. 

 

LightGBM에서는 gradient boosting의 각 과정마다 categorical feautures들이 gradient statistics로 전환된다. 그러나 이런 방식은 전환을 매 과정마다 해야하므로 계산 과정과 메모리 소비를 크게 증가시킨다. 

 

즉, "using TS as numerical features"가 짱이다~

 

 

* Target Statistics

 

와 같은 Category에 속하는 모든 instance들의 target값의 기대값(평균)으로 categorical feature i를 대체한다.

TS 도출 과정

각각의 category 하나 당 하나의 numerical value가 할당되기 때문에 high carinality feature에 효과적이다.

 

그러나 예측 시점에서는 알 수 없는 정보인 target y 값이 쓰이고 있으므로 target leakage가 일어난다.

 

따라서 이 논문에서는 Ordered TS를 사용하여 CatBoost를 구현했다.

 

 

1. Greedy TS

Greedy TS

  낮은 빈도로 나타나는 category의 noisy 한 것을 추정하는 것을 막기 위해 해당 a와 p를 통해 noise를 smooting 한다.

  이때, a는 양수의 파라미터이고 p는 주로 전체 taget value의 평균으로 사용한다.

 

  그러나 이때 사용하는 y값은 예측 시점에서는 알 수 없는 정보이므로 target leakage가 발생한다. 이는 train set과 test  set의 차이를 불러오고 오버피팅된 결과를 가져올 수 있다.

 

-Target Leakage 예시

   <가정>

     -feature i는 categorical이고 이의 모든 값은 유일하다.

traing set의 Greedy TS

 이때, threshold t를 다음과 같이 두면 traing set에 있는 모든 변수들을 완벽하게 분류할 수 있게 된다.

threshold

test dataset

  그러나 test dataset에서는 가정에 의해 greedy TS의 값을 모두 0.5를 가지며 threshold가 0.5보다 커지면 모두 0으로      예측하고, 0.5보다 작아지면 모두 1로 예측하기 때문에 traing 때와는 다르게 결과를 잘 예측하지 못한다. 

  즉, prediction shift 문제가 일어나게 된다.

 

  따라서 이러한 문제를 피하기 위해 TS에 대한 property를 정의한다.

  P1: traing set에 대한 TS 기대값과 test set에 대한 TS 기대값이 같아야 한다. (Greedy TS는 이를 만족하지 않음)

 

conditional shift를 피하는 일반적인 방법은 다음과 같다.

  Xk의 TS를 계산할 때, Xk를 제외한 subset Dk로부터 구하는 것이다. 이는 다음과 같이 할 수 있다.

 

 2. Holdout TS

  :training dataset을 두 개로 분할 후 하나는 TS를 계산하는 것에 쓰고, 하나는 training하는 것에 쓴다.

  이는 P1을 만족하지만 TS계산과 Training에 쓰이는 데이터의 양이 줄어든다는 단점이 있다.

 

  따라서 두번째 property를 정의했다.

 

 3. Leave-one-out TS

  : Xk를 제외한 data set으로 training TS를 계산하고, 전체 training data set을 test에 사용한다.

 이는 instance를 하나씩만 빼므로 P2를 만족하지만, training set과는 달리 test set에서는 결과가 잘 나오지 않을 수 있   기 때문에  P1은 만족하지 않는다.

 

 따라서 CatBoost에서는 Ordered TS를 사용한다.

 

 4. Ordered TS

  : ordering principle을 적용한 TS

시간개념이 없는 offline setting에 도입하기 위해 "가상의 시간을 도입한다."  

random permutation을 도입하여 해당 시점(순열) 전까지의 데이터들을 TS 계산에 사용한다.

training set TS 계산

이는 target leakage가 발생하지 않고(P1 만족), TS를 계산하고 model을 학습하는 데 training data를 효율적으로 사용한다(P2 만족).

 

이때, gradient boosting을 하는 동안 동일한 permutation을 적용하게 되면 분산이 커지게 되므로(앞에 있는 instance들의 TS 계산에 쓰이는 데이터들이 적으므로) CatBoost에서는 각 step마다 다른 permutation을 사용한다.

 

 

 

4. Prediction shift and Ordered boosting

4.1 Prediction shift

앞서 설명했던 prediction shift를 ordered boosting과 ordered TS를 통해 해결할 수 있다.

 

먼저, gradient boosting에서 prediction shift가 일어나는 과정을 보자.

보지 않은 데이터를 넣으면 gradient의 conditional distribution은 shift되고 편향이 발생하게 된다. 이는 trained model Ft의 일반화 능력에 영향을 주게 된다.

 

즉, train data와 다른 test data가 들어오면 conditional distribution이 달라지고 이때 prediction shift가 발생한다.

 

따라서 각 boosting 단계에서 학습에 사용하는 dataset은 independent 해야한다.

prediction shift를 해결하기 위한 방법

=> 각 boosting 단계에서 gradient 계산에 쓰이는 dataset과 model Ft를 train하는 dataset은 independent 해야 prediction shift를 피할 수 있다.

 

그러나 모든 k에 대해 unbiased gradient를 구하려면 model을 training 하는데 사용할 수 있는 instance가 남지 않는다.

따라서 이는 불가능한 방법이므로 Ordered Boosting으로 넘어간다.

 

4.2 Ordered boosting

: Random permutation 앞쪽의 i개의 instance만을 이용하여 training한 n개의 모델들을 생성한다.

Ordered Boosting

Ordered boosting 알고리즘

 

 

 

n개의 모델에 대해서 다음 과정을 반복한다.

i번째의 residual(-gradient)은 i-1번째의 model(M)로부터 구하고,

j번째 모델은 j-1까지의 instance들로부터 learned되어

model을 업데이트 한다.

 

 

 

 

그러나 이는 n개의 다른 model들을 training하므로 복잡도가 높아지고 메모리도 증가하기 때문에 현실적으로 쉽지않다.

 

따라서 CatBoost에서는 gradient boosting algorithm with decision tree을 기반으로 위 알고리즘을 수정하여 사용한다.

 

* ordered boosting with categorical features

: TS 계산과 ordered boosting을 하나의 알고리즘으로 합칠 때 각각의 permutation이 같다고 해야 prediction shift를 피할 수 있다.

이는 taget y가 model M을 training하는데 쓰이지 않는다는 것을 보장해준다.

 

 

5. Practical implementation of ordered boosting

CatBoost에는 plain mode와 ordered mode 두가지의 mode가 있다.

 

Plain mode: standard GBDT algorithm & ordered TS

Ordered mode: ordered boosting & ordered TS

 

* Base Predictor: oblivious decision trees(decision tables)

 -oblivious : tree의 모든 level에서 같은 spliting criterion을 사용한다.

 oblivious decision tree는 아래와 같이 트리의 level마다 동일한 조건을 부여해 좌우대칭의 형태로 만든다.

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

oblivious decision tree는 balanced 되어있고, overfitting에 강하며 testing time이 단축된다.

 

 

oblivious decision tree를 기반으로 하는 CatBoost의 tree를 만드는 알고리즘은 다음과 같다.

 

M: 모델, L: 손실함수, y: target value

 

r <- 각 iteration마다 다른 permutation을 쓴다.

그리고 categorical feature을 해당 permuataion에 따른 ordered TS로 대체한다.

 

plain mode에서는 ordered boosting을 하지 않기 때문에 기존 GBM 처럼 training data셋에 구분을 두지 않고 gradient를 구한다.

 

반면, ordered mode에서는 순열 r에서 instance i 앞에 위치한 instance들로 training하여 모델의 gradient를 구한다.

-M_r,j: 순열 r에서 앞 j개의 instance를 사용하여 training한 model이다.

-M_r,j(i): M_r,j model의 i번째 instance에 대한 예측값이다.

 

 

-leaf_r(i): 순열 r에서 앞 i개의 instance를 사용하여 training한 model

 

-leaf value △(i): 순열 r에서 instance i보다 앞에 위치하면서 동시에 leaf_r(i)에 속하는 instance p들의 gradient의 평균

 

-T: loss를 최소화하는 split들로 구성된 tree structure

 

 

위와 같이 tree structure T가 만들어지면 T를 model들을 boosting하는 것에 사용한다.

앞서 얻어진 T를 기반으로 M_r',j(i)를 update한다.

 

plain boosting은 기존 gradient boosting과 같게 진행되지만

만약 training data에 categorical feature이 있으면, 순열 r에 기반해 cateforical feature을 ordered TS로 대체한 후 학습한

s개의 model M_r을 생성한다.

 

 

 

6. Experiments

*기존 GBM VS CatBoost

LightGBM, XGBoost < CatBoost

 

* Plain mode VS Ordered mode

-small dataset인 경우 ordered mode의 성능이 더 좋다.

 

작은 dataset에서는 썼던 데이터를 다시 쓸 확률이 높아서 bias가 더 클 수 밖에 없는데,

ordered mode에서는 model을 학습하고 gradient를 계산할 때 같은 데이터를 쓰지 않게하기 때문에 plane mode에 비해 bias가 더 줄어들어 성능이 더 좋다.

 

 

* Target statistics(TS) 비교

-Greedy TS, Leave-one-out TS< Holdout TS< ordered TS

model 학습 데이터와 gradient 계산 데이터가 겹칠 수 있음 < training 데이터가 비효율적으로 사용됨< Ordered가 최고

 

 

CatBoost를 통해 Gradient Boosting을 개선한 점

 

1. Prediction shift: train data set과 test data set의 output이 다르다. (overfitting)

 => Ordered Boosting을 통해 해결

Ordered Boosting

2. Target leakage: model training 시점에서 알 수 없는 target 값을 이용하여 발생한다.

 => Ordered TS를 통해 해결

Ordered TS

 

high cardinality categorical feature을 다룰 때 유용하다.

model tuning이 간소화되어 있으며 예측성능이 좋아서 최근에 많이 쓰인다.

 

 

______________________________________________________________________________________________________________________________

참고자료

 

https://www.youtube.com/watch?v=-w_6wDJQCZY

https://kicarussays.tistory.com/m/40

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

https://data-newbie.tistory.com/132?category=750846

CatBoost란? unbiased boosting with categorical features - 2