🐱 CatBoost: unbiased boosting with categorical features

Abstract

본 논문은 CatBoost라는 새로운 그래디언트 부스팅의 주요 알고리즘 기법을 소개함. CatBoost는 다양한 데이터셋의 품질 측면에서 다른 공개적으로 가능한 부스팅을 능가함. CatBoost에서 소개된 두 가지 중요한 알고리즘: (1) Ordered Boosting - 순열 기반, 클래식 알고리즘의 대안 (2) categorical feature를 처리하는데 있어서 혁신적인 알고리즘임. 이러한 기술은 모든 그래디언트 부스팅 알고리즘에서 발생하는 Prediction shift 문제(타겟 누출로 인한)를 해결하기 위하여 제안되었음.

1. Introduction

그래디언트 부스팅: 실전 작업에서 강력한 기계 학습 기법이지만, 기존의 구현에서는 한 종류의 타겟을 누출한다는 문제를 겪고 있음.

=> 경사하강법을 이용하여 앙상블 예측기를 구성하는 과정

• 해당 문제로 인하여 학습된 모델의 예측에 이상 발생 가능: 본 논문은 순열 기반 부스팅과 범주형 feature 처리를 개선한 CatBoost를 제안함.

🐱 CatBoost는 XGBoost, LightGBM과 같은 기존의 최첨단 모델을 능가하는 성능을 보였음.

2. Background

주어진 데이터셋에서 feature 벡터 xk와 이에 해당하는 목표값 yk로 이루어져 있음.

• 그래디언트 부스팅 절차: Greedy하게 이전 근사치에서 현재 근사치를 추가적으로 빌드하며, ht는 기대 손실을 최소화하기 위해 선택됨.

=> Catboost는 기본 예측자로 binary decision tree 형성하여 공간을 분할하여 예측 수행함.

Categorical features

3.1 Related works on categorical features

이산 집합의 범주를 가지는 범주형 특성은 서로 비교할 수 없음.

=> 해당 특성을 다루는 기법 중 하나는 원-핫 인코딩

📌 그러나 고차원의 특성(ex. "사용자 ID" 특성)의 경우, 이 기법은 너무 많은 새로운 특성을 생성함.

=> 이 문제를 해결하기 위해 범주를 제한된 수의 클러스터로 그룹화한 다음 원-핫 인코딩을 적용할 수 있음. (TS를 사용하여 범주를 그룹화하는 것)

• TS를 새로운 수치 특성으로 간주함으로써 이 문제를 해결할 수 있음.

3.2 Target statistics

범주형 특성 i를 처리하는 효과적이고 효율적인 방법은 k번째 데이터의 범주 xik를 어떤 TS의 xˆik로 대체하는 것임. 일반적으로, 이는 해당 범주에 대해 조건부로 예상되는 타겟 y를 추정하는 것과 동일함.

Greedy TS

• 범주형 특성의 타겟 통계를 해당 범주에 대한 training example의 평균으로 추정하는 방법

📌 문제: 타겟 누출로 인해 conditional shift를 유발할 수 있음. 이를 피하기 위해 training set에서 해당 데이터를 제외한 하위 집합을 사용하여 TS를 계산하는 방법이 제안되고 있음.

Holdout TS

• 훈련 데이터셋을 Dˆ0과 Dˆ1로 분할하여 TS를 계산하는 데에는 Dˆ0을 사용하고, 모델 훈련에는 Dˆ1을 사용하는 방식

📌 문제: 모델 훈련과 TS 계산에 사용되는 데이터 양을 크게 줄이므로, 모든 훈련 데이터를 효과적으로 활용하는 것을 제한하여 보완할 수 있음.

Leave-one-out TS

• Training examples로는 Dk = D \ xk를, testing example로는 xk and Dk = D를 선택하는 방식

📌 문제: 타겟 누출을 막지 못함.

Ordered TS

CatBoost는 더 효과적인 ordered 원리에 바탕을 두었음

• TS의 값들은 관찰된 이력에 의존하게 되는데, 이 아이디어를 적용하여 '인공적인 시간'을 도입함.

=> 사용가능한 이력을 사용하여 TS를 각각 계산하고, training example로는 Dk = {xj : σ(j) < σ(k)}를, testing 용으로는 Dk = D를 적용함.

⭐ Ordered TS는 P1 조건을 만족하고, P2 조건이었던 모든 데이터셋 사용 또한 만족시킬 수 있게 됨.

4. Prediction shift and ordered boosting

4.1 Prediction shift

그레이디언트 부스팅에서의 예측 변화 문제 - 이전에 다루어지지 않았음.

📌 이러한 예측 변화는 TS와 마찬가지로 특정 유형의 타겟 누출로 인해 발생함 => 해결책은 Ordered TS 방법과 유사한 Ordered boosting

4.2 Ordered boosting

Ordered boosting은 예측 변화 문제를 겪지 않음.

• 이 알고리즘은 각 단계에서 새로운 데이터셋을 독립적으로 샘플링하고 현재 모델을 새로운 training example에 적용하여 변화되지 않은 residual를 얻음.

⭐️ 하지만 이러한 알고리즘은 대부분의 실제 작업에서는 실행 뷴가 - CatBoost에서는 이러한 알고리즘의 변형을 구현하여 이 문제를 해결

Ordered boosting with categorical features

TS 계산 및 Ordered boosting에 대한 training example 임의 순열 σcat 및 σboost를 사용하는 것을 제안함.

• 이 두 가지를 하나의 알고리즘으로 결합할 때, 예측 변화를 피하기 위해 σcat = σboost가 필요 -> 타겟 yi가 Mi의 훈련에 사용되지 않음을 보장

5. Practical implementation of ordered boosting

CatBoost에는 두 가지 부스팅 모드인 Ordered와 Plain 존재

• Plain: Ordered TS를 사용하는 표준 GBDT 알고리즘
• Ordered: 알고리즘 1의 효율적인 수정본을 제공

⭐️ 알고리즘 설명

1. CatBoost은 훈련 데이터셋의 s + 1개의 독립적인 랜덤 순열을 생성
2. 순열 σ1, ..., σs는 트리 구조를 정의하는 분할을 평가하는 데 사용 -> σ0은 얻은 트리의 잎 값 bj를 선택하는 데 사용

+) 특정 순열에서 짧은 가진 예제의 경우, ordered boosting에서 사용되는 TS 및 예측값 => 모두 고분산

• 따라서 하나의 순열만 사용하는 것은 최종 모델 예측의 분산을 증가시킴 -> 여러 순열을 사용하여 해당 효과를 줄일 수 있음.

6. Experiments

높은 성능을 보이는 것으로 알려진 XGBoost와 LightGBM과의 알고리즘을 비교

• 모든 학습 알고리즘에 대해 범주형 특성은 Ordered TS 방법을 사용하여 전처리
• CatBoost의 Ordered 부스팅 모드를 사용

📌 CatBoost가 모든 고려된 데이터셋에서 다른 알고리즘보다 우수한 성능을 보였음.

+) 일부 데이터셋을 제외하고 모든 개선 사항은 연결된 일방향 t-검정으로 측정된 p-값이 ≪ 0.01로 통계적으로 유의함도 확인함.

7. Conclusion

본 논문에서는 현재 있는 Gradient boosting에 모두 존재하는 prediction shift의 문제를 다루었음. Ordered TS를 사용하는 Ordered Boosting을 제안하여 해당 문제를 해결함.

🐵 논의해보고 싶은 점: 해당 논문은 19년도에 발행되었는데, 지금도 딥러닝이 아닌 기계학습 영역에서 연구가 활발하게 진행되고 있는지 궁금해졌다.