📄CatBoost: unbiased boosting with categorical features
written by Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev,Anna Veronika Dorogush, Andrey Gulin
Introduction
본 논문에서는 gradient boosting의 기존 구현에서 발생하는 통계적 문제를 해결하기 위한 방법으로 ordered principle을 제안함
이를 통해 기존의 gradient boosting algorithm을 수정하여 목표 누출을 피하고 범주형 특징 처리에 새로운 접근 방식을 도입함. 해당 방법은 CatBoost라는 오픈 소스 라이브러리를 통해 구현되었으며 기존의 XGBoost 및 LightGBM보다 뛰어난 성능을 보임
Background
gradient boosting 절차를 사용하여 함수 F : R^m → R의 근사값을 반복적으로 구성함
각 단계에서 F는 이전 근사값에 함수 h를 더하는 식으로 만들어지며, h는 손실을 최소화하기 위해 선택됨. 이러한 gradient boosting은 CatBoost와 같은 구현을 사용하여 binary decision tree를 기반 예측자로 사용함. binary decision tree는 특징 공간을 재귀적으로 분할하여 모델을 구성하며, 각 영역에는 응답의 추정치가 할당됨
Categorical features
카테고리 특성은 서로 비교할 수 없는 카테괼 값으로 구성된 특성임
boosting tree에서 카테고리 특성을 처리하는 인기 있는 기술 중 하나는 one-hot encoding이지만 높은 cardinality features의 경우 너무 많은 새로운 features를 생성하게 됨. 해당 문제를 해결하기 위해 카테고리를 제한된 개수의 cluster로 그룹화한 다음 one-hot encoding을 적용할 수 있음
일반적 방법 중 하나는 카테고리별 타겟 통계를 사용하여 카테고리를 그룹화하는 것으로 카테고리에 따른 기대값을 추정하는 간단한 통계 모델로, 특정 카테고리에 대해 같은 카테고리를 갖는 학습 예제의 평균 타겟 값을 추정함
그러나 해당 방법은 타겟 누설과 예측 변이를 일으킬 수 있음. 따라서 효과적인 방법은 카테고리에 대한 TS를 계산할 때 훈련 세트의 부분 집합을 사용하는 것으로, 이를 위해 훈련 데이터 세트를 두 부분으로 나누고 각 부분에 대해 별토의 TS를 계산하는 Holdout TS 방법을 사용할 수 있음. 또는 Leave-one-out TS 기법을 사용할 수 있지만, 타겟 누설을 방지하지 못함
이러한 문제를 효과적으로 해결하기 위해 CatBoost는 Ordered TS를 도입하여 타겟 누설을 방지하고 모든 학습 데이터를 효율적으로 활용함. Ordered TS는 표준 오프라인 설정에 시간 순서를 적용한 것으로, 각 예제에 대한 TS값은 관측된 역사에만 의존함.
이를 통해 CatBoost는 모든 훈련 데이터를 사용하여 모델을 학습하고, 타겟 누설을 효과적으로 방지함
Prediction shift and ordered boosting
Prediction shift
예측 변이에 대한 이전 연구에서는 gradient 조건부 분포 g_t(xk, yk) | xk의 변이가 언급되었지만 공식적으로 정의되지 않았음. 더하여 이러한 변이가 0이 아닌지도 이론적으로 증명되지 않았음
예측 변이의 문제를 형식적으로 분석하기 위해 이차 손실 함수를 갖는 회귀 작업의 간단한 경우를 고려함. 이 경우, 동일한 데이터셋을 각 단계에서 사용하면 편향이 발생하는 것으로 나타남. 또한 이러한 편향은 데이터 크기에 역비례하며 편향의 값은 f와 관계에 따라 달라짐. 이러한 변이의 체인을 추적하고 해결책에 대한 흔적을 보여주는 이론적인 결과들이 제시됨
Ordered boosting
카테고리 특성을 사용한 순서 있는 부스팅에서 훈련 예제의 무작위 순열 σcat 및 σboost를 TS 계산 및 순서 있는 부스팅에 사용하는 것을 제안했음. 이를 하나의 알고리즘으로 결합할 때, 예측 변이를 피하기 위해 σcat = σboost를 취해야 함. 이는 대상 yi가 Mi를 훈련하는 데 사용되지 않음을 보장함(기술적으로도 TS 계산 및 gradient 추정에 사용되지 않음)
Practical implementation of ordered boosting
CatBoost는 ordered와 plain 두 가지 boosting 모드를 가지고 있음
Ordered mode는 알고리즘 1의 효율적인 수정 버전을 제공하며, 여러 순열을 사용하여 tree를 구성함. 해당 모드에서는 각 예제의 기울기를 계산할 때, 순열에 따라 영향을 받음
Plain mode는 표준 GBDT 절차와 유사하게 작동하지만, TS에 해당하는 여러 지원 모델을 유지함
CatBoost는 범주형 특성의 고차원 의존성을 포착하기 위해 트리를 구축하고, 알고리즘의 복잡성을 줄이기 위해 중요한 기법을 사용함
Experiments
Conclusion
본 논문에서는 기존의 모든 gradient boosting implementation에 존재하는 prediction shift 문제에 대해 정의하고 분석함
본 논문에서는 이를 해결하기 위한 general solution인 ordered boosting with ordered TS를 제안함.
해당 아이디어는 새로운 gradient boosting library인 CatBoost를 통해 구현됨
경험적 결과에 따르면 CatBoost는 leading GBDT 패키지를 능가하고 일반적인 벤치마크에서 새로운 state-of-the-art 결과를 이끌어냄
