CatBoost란? unbiased boosting with categorical features - 1

논문 및 Document

https://arxiv.org/abs/1706.09516

https://catboost.ai/docs/concepts/python-reference_catboostclassifier_fit.html

 

현재 Xgboost , lightgbm , gbm 계열인 Gradient Boosting 은 weak learner를 loss function 상에서 Gradient Desecnet를 최적화 기법으로 기울기가 가장 큰 방향으로 tree들을 결합하는 방법입니다.

 

논문에선 catboost를 새로운 Gradient Descent 방법이라 합니다. 

catboost는 다른 gbm알고리즘보다 더 좋은 성능을 낼 수 있는 것은

• ordering-principle 개념을 대입하여 기존의 Data 누수(leakage)로 인한 Prediction-shift에 대한 문제 해결
• High Cardinarity를 가진 Category 변수에 대한 전처리 문제 해결

Gradient Boosting 방식은 현재 많은 곳에서 사용하고 있는데요.   그렇지만 아직 여러가지 문제에 대해선 이슈가 있다 합니다. 저자는 다음과 같이 말했는데요.

For many years, it has remained the primary method for learning problems with heterogeneous features, noisy data, and complex dependencies: web search, recommendation systems, weather forecasting, and many others

Gradient boosting is essentially a process of constructing an ensemble predictor by performing gradient descent in a functional space
함수 공간에서 Gradient Descent를 수행함으로써 앙상블 예측자를 만드는 것입니다.

저 방법은 강한 예측자 뒤에 여러개의 탐욕적 방법(greedy manner)으로 weak learner를 결합해서 사용합니다.

저자는 논문에서 F라는 예측 모델이 몇단계를 걸쳐서 모든 트레이닝 데이터의 타깃에 의존하게 되는데요. 

이러한 방법이 실제로 테스트 타겟 분포로 만든 F(x_test)와 트레인 타깃으로 한 F(x_train)의 분포가 shift 되는 것을 설명할 수 있다고 하네요.

이처럼 실제 train와 test간의 분포 모형이 동일하다는 가정에서 검정을 하는데, 이처럼 다르다고 하면 안 되겠죠?

이러한 문제는 저자는 4 Prediction shift and ordered boosting에서 target leakage 같은 문제와 동일하다고 하네요. 이러한 이슈로는 Categorical Features 전처리 과정 중에서 발생한다고 하는데요.

원래 gradient boosting에서 이것을 효율적으로 처리하는 방법 중 하나는 Categories를 타깃 통계량로 변환시키는 것이라고 합니다. 하지만 이럴 때 target leakage과 prediction shift가 발생한다고 합니다.

target leakage과 prediction shift 결국 이 2가지가 먼지랑 어떻게 발생하는지 그리고 어떻게 해결하는지 알아야 Catboost를 알겠네요...

 

Prediction Shift

일반 GBM은 다음 스텝의 새로운 트리를 만들 때 현재 모델에서 쓰인 데이터를 Gradient로 다시 쓰기 때문에 Overfitting이 발생하는 현상

-> 기존의 tree structure를 고른 후 leaf 구하는 방식을 반대로 해서 leaf 구하고 tree structure 고르는 과정을 통해 해결한다고 함 (Ordered Principle)

 

 

저자는 이러한 문제들을 Ordering Principle로 해결한다 합니다. (Ordered Boosting)

 

배경

 

기존의 방법은 Newton Method를 사용해서 최소화하는 방식입니다.

CatBoost is an implementation of gradient boosting, which uses binary decision trees as base
predictors.

3 Categorical features

정의는 Discrete value지만, 각각의 변수들이 서로 비교할 수 없는 데이터를 말한다.

그래서 보통 OneHot를 통해 처리하는데요. (USER ID  , 성별 ) 같은 것이 있는데 USER ID 같은 것이 매우 많은 집합의 크기를 가지는 수가 됩니다(ID는 고유하니 고객이 1억 명이면 1억 개? onehot??) 

그래서 이러한 문제를 해결하기 위해 일단 Clusetring을 하고 그것에 대해서 Onehot을 해서 줄이려고 한다고 합니다.

A popular method is to group categories by target  statistics (TS) that estimate expected target value in each category [D.
 Micci-Barreca. A preprocessing scheme for high-cardinality categorical attributes in classification
and prediction problems. ACM SIGKDD Explorations Newsletter,]이런 식으로
해서 결국 onehot -> numerical feature로 대신 쓴다는 겁니다.

Lightgbm에 경우에는 Categorical Features를 Gradient Boosting 각 스텝에서 Gradient Statistics로 전환해준다고 합니다. 하지만 이러한 방식에는 단점이 있다는데요.

• computation time ( 각 스탭에서 각각의 categorical 값의 통계량을 계산해야 합니다)
• memory consumption (categorical feature를 Split 하는 지점에 대해서 저장을 해야 하니 메모리 문제도 생깁니다)
  • 이러한 문제를 해결하기 위해 끝 부분에 있는 것은 하나의 클러스터로 그룹화하게 되어 정보를 잃게 됩니다.
• 저자들은 그리고 너무 많은 Cardinality(집합)인 경우 범주형으로 변환하는 것이 더 낫다고 합니다.

Thus, using TS as new numerical features seems to be the most efficient method of handling 
categorical features with minimum information loss. 그래서
결국 자기네가 주장하는 ordering priciple 방법이 짱이라 합니다.

 

3.2  Target statistics

해당 categorical에 따라서 Y의 기댓값으로 쓴다 

 

이러한 Greedy Approach 들의 문제는 ``target leakage``입니다.

결국 말하고자 하는 것은 이렇게 가지고 있는 데이터에 충실하게 하다 보면 train , test가 다른 경우가 있을 때 다른 분포를 만든다는 것이다 (conditional shift) 발생!

이러한 문제를 해결하는 방법이 몇 개가 있는데, 일반적인 아이디어는 x_k를 배제하고 하는 것이다.

 

Holdout TS

train을 2개로 나눕니다.(D = D_0 + D_1) 그리고 TS를 계산하기 위해 TS를 계산하기 위해 D_k = D_0

학습은 D_1으로 합니다. 이렇게 하면  Modeling 할 데이터와 TS를 계산하는 것이 줄어들어됩니다

다음 성질을 위반하게 되고요! Effective
usage of all training data for calculating TS features and for learning a model.

Leave-one-out TS

이것은 하나만 빼고 계산하는 건데, 계산량이 너무 늘어나겠죠?

저자들은 Ordered TS를 제안합니다

순차적으로 학습하는 Online Learning에시 영감을 받았다고 합니다.

5번째를 보고 있다면 (1~4까지만 이용합니다)

이것을 offline learning에 적용하기 위해 가짜 시간을 만들어야 했고 이 방법이 ``Random Permutation을 해주는 것이라 합니다.``