Catboost

1. Introdunction

Gradient boosting은 weak learner를 loss function상에서 gradient descent라는 최적화 기법으로 기울기가 가장 큰 (greedy procedure) 방향으로 sub tree들을 반복적으로 추가하여 결합하는 방법으로 성능을 향상시키는 boosting 기법의 중 하나이다.

catboost가 다른 gbm 알고리즘보다 좋은 성능을 낼 수 있는 것은 ordering-principle의 개념을 대입하여 기존의 data-leakage로 인한 prediction-shift 에 대한 문제 그리고 high cardinality를 가진 category 변수에 대한 전처리 문제를 해결했다.

첫번째 장점은 범주형변수처리 방법의 개선으로 인한 학습시간 단축이다.

대부분의 GBM은 decision tree를 base predictor로 삼는다. 이건 수치형 변수들에서는 편리하지만 범주형 변수들이 포함된 데이터셋에서는 수치형 변수로 전처리를 해준 후 훈련을 해야하기 때문에 학습 시간이 많이 걸렸던 단점이 있었다.

catboost에서는 이러한 문제점을 모델 훈련시간에 동시에 진행을 하면서 시간을 단축했다.

또 하나의 장점은 leaf value들을 계산하는 과정에서 ordered boosting 기법을 활용해 prediction shift문제를 해결한 것이다.

기존의 일반적인 GBM은 다음 스텝의 새로운 나무(Base learner를 DT로 가정)를 만들때 현재 모델에서 쓰여진 데이터를 Gradient estimate를 하는데 다시 쓰여지기 때문에 overfitting에 취약한 문제점이 있었다. (a.k.a prediction shift)

이러한 문제점을 기존의 tree structure를 먼저 고른 후(internal node에서 cut-off value를 정하는 과정을 말함) leaf value를 구하는 방식에서 역순으로 leaf value를 먼저 구하고 tree structure를 고르는 과정을 ordered principle 개념을 적용해 변형하여 해결하였다.

이렇게 두가지의 장점이 기존의 GBDT(e.g LightGBM, XGBoost)에서 개선된 점이다. 이제 이 두가지 부분을 자세히 공부해보자.

2-1. Categorical features

범주형 변수는 서로 비교가 불가능한 값을 가지고 있기 때문에 바로 Binary decision tree 같은 모형에 쓰일 수 없다. 따라서 일반적으로 범주형변수를 수치형 변수로 전처리를 하는데 일반적으로 낮은 level을 갖는(low-cardinality) 범주형 변수에 가장 많이 쓰이는 방법이 One-Hot encoding이다. 이러한 전처리 과정이 모형을 훈련시키기 전에 일어날 수도 있고 훈련하는 도중에 진행할 수도 있는데 후자가 실험적으로 더 빠르다는 것이 밝혀졌다고한다.

One-hot encoding 외에 수치형 변수로 변환하는 방법이 catboost에서 쓰였는데, 해당 category의 level마다 label value (Y값)의 평균(기대값)를 나타내는 방법이다. 이를 Label encoding (target statistics) 이라고 한다. 이 변환된 변수를 사용한다면 당연히 overfitting이 될 것이다. 따라서 hold-out 기법을 사용해 한파트는 label encoding을 통한 수치(statistics) 변환에 쓰이고 두번째 파트는 실제 모델을 훈련시키는데 쓰인다. 이 방법을 hold-out TS(Target Statistics) 이라고 하는데 이 방법으로 overfitting은 줄일 수 있으나 훈련시키고 statistic을 얻을 수 있는 데이터의 양이 줄어들게 된다.

Catboost에서는 이 방식을 조금 더 개선시켜 TS값을 오직 observed history(여태까지 관찰된 관측치까지만, 즉 4번째 row의 값을 변환시킨다면 1~3까지의 row값만)로만 산출하도록 한 ordered TS방식을 사용했다. 이 개념은 사실 online learning에서 차용된 것인데, 이를 offline learning에 적용하기 위해서는 인공적인 시간을 만들어야 했다. 이 역할을 바로 훈련데이터의 random permutation이 해준다.

여기서 한가지 의문점은 첫 TS를 산출할 때 이전에 쓰인 관찰치가 없어 값을 변환할 수 없게 된다 이를 위해 prior와 이에 대한 가중치 a(알파)를 도입한다. 이 prior는 regression 문제에서는 y값의 평균 binary classification 문제에서는 y값이 positive일 사전확률이다.

여기서 최적의 prior를 찾기 위해 같은 모형에 또 다른 permutation을 사용해야 하는데 이렇게 되면 Target leakage가 발생하기 때문에 사용할 수 없다. 따라서 일단 여러개의 모형을 만든 후 각 모형에 다른 random permutation 데이터를 넣어 학습한 뒤 tree structure를 정한 후, 다시 이 tree structure를 다른 모형에 적용시킨 후 다른 모형에서 prior들의 평균을 구한다. 이렇게 되면 각 모형마다 다른 데이터를 사용했기 때문에 target leakage 문제가 사라지게 된다.

2-2. Feature combination

만약 2 범주형변수간에 상관관계가 있다면 어떻게 해야할까? 단순히 이러한 상관관계를 무시하고 수치변환을 한다면 모델의 설명력에 중요한 Feature를 잃을 수 있다. 논문에서 쓰인 예를 인용하자면 Music recommendation task에서 User Id 와 music genre 라는 2개의 범주형 변수가 있다. 어떤 user는 rock을 좋아할 것이고 어떤 user는 hip-hop을 좋아할 것이다. 즉 두 변수간에 어떤 상관관계가 있을 수 있다. 그러나 단순히 수치화를 시키게 된다면 이 두 변수 사이의 상관성이 무시되어 정보를 잃게 된다. 이러한 문제점을 해결하기 위해 두 변수를 조합(feature combination)을 해 새로운 변수를 만들 수 있다. 그러나 카테고리 변수가 많게 되면 데이터의 크기는 exponential하게 커질 것이다. 이러한 문제를 해결하기 위해 greedy한 방식으로 tree를 학습시킨다. root node에서는 combination을 하지 않고 다음 level에서 2개 변수의 combination을 만들고 이를 수치화 시킨다. 이렇게 수치화된 combination feature를 다음 level에서 다시 다른 범주형 변수와 combination을 하여 수치화시킨다. 이 과정을 반복하는 것이 catboost에서 Feature combination을 만드는 방법이다.

3. ordered boosting

기존의 gbm의 고질적인 문제는 각 iteration마다 이전에 썼던 데이터를 계속 반복해서 쓰기 때문에 target leakage가 나타나 prediction shift 문제가 나오는 데 현실에서는 데이터가 한정적으로 있기 때문에 이 문제를 ordered principle을 적용하여 해결하였다.

위 그림이 이 방식을 도식화한 그림이다. 부연설명을 하자면

1. t-1까지의 permutated observation을 이용해 t-1번째 모형을 학습한다.

2. t번째 데이터를 t-1번째 모형으로 예측하고 t번째 실제 y값과 비교하여 t번째 residual값을 구한다.

3. t번째 residual 값으로 gradient를 update하여 t번째 모형을 만든다.

이 3가지 루프를 반복하여 모형을 만들어 낸다. 하지만 t번째의 모형을 만들기까지 그전의 모형들을 메모리 안에 저장해두어야 하기 때문에 이는 현실적으로 불가능하다. 따라서 obilvious trees 구조를 사용하여 이 문제를 해결했다고 한다.

oblivous의 의미는 현재의 tree level 전체에서 같은 cut-off 값을 사용했다는 의미다. 이를 이해하기 위해서는 tree structure를 알아야 하는데

일단 catboost는 xgb,lightgbm과 다르게 symmetric trees (a.k.a depth or level-wise tree)의 구조를 사용한다. oblivious trees와 같이 균형잡힌 depth-wise trees의 장점은 overfitting을 방지할 수 있다는 것이다. (단점은 당연히 leaf-wise보다는 느림) 여기서 oblivious tree는 한가지 장점을 더 가지게 되는데 root node에서 leaf node까지 만들어진 조건들을 이진화된 벡터로 변환하여 각 index에 leaf value 값을 저장함으로 인해. 전체 tree structure를 메모리에 저장할 필요 없이 evaluation시 이진화된 벡터의 leaf index만으로 leaf value값을 불러낼 수 있기 때문에 빠르고 메모리 효율적인 테스트를 할 수 있다.