CatBoost: unbiased boosting with categorical features

논문

• https://arxiv.org/pdf/1706.09516.pdf

 

Reference

• https://gentlej90.tistory.com/100

 

Abstract

이 논문은 새로운 그라디언트 부스팅 (Gradient Boosting) Toolkit인 CatBoost의 핵심 알고리즘 기술들을 설명함.

• 이 기술들의 조합으로 인해 CatBoost는 다양한 Dataset의 품질 면에서 공개적으로 사용 가능한 다른 구현들 보다 좋은 성능을 냄.
• CatBoost에서 소개되는 두 가지 중요한 알고리즘적 진보는 고전 (Classic) 알고리즘에 대한 순열 기반 대안 인 순서형 부스팅 (Ordered Boosting) 및 범주형 (Categorical) Feature를 처리하는 혁신적인 알고리즘임.
• 두 기술 모두 현재 존재하는 모든 그라디언트 부스팅 알고리즘의 구현에 존재하는 특별한 종류의 목표 누수 (Target Leakage) 로 인해 발생되는 예측 변화 (Prediction Shift) 와 맞서기 위해 만들어졌음.
• 이 논문에서, 우리는 이 문제의 세부적인 분석을 제공하고, 제시된 알고리즘이 그 문제를 효과적으로 해결하여 훌륭한 경험적 결과를 도출 한다는 것을 증명함.

 

1. Introduction

그라디언트 부스팅 (Gradient Boosting) 은 다양한 실무 작업에서 최첨단 (State-of-the-Art) 결과를 달성하는 강력한 머신러닝 기술임. 

• 오랜 기간 동안, 그라디언트 부스팅은 이질적인 (Heterogeneous) Feature, 노이즈 (Noisy) 데이터, 복잡한 종속성을 가진 문제들을 학습하는 데 주된 방법으로 남아 왔음 :
  • 웹 검색 (Web Search).
  • 추천 시스템 (Recommendation System).
  • 날씨 예측 (Weather Forcasting).
  • 그 외 많은 다른 것들 (Many Others).
• 그라디언트 부스팅은 본질적으로 기능적 (Functional) 공간에서 그라디언트 하강을 수행하여, 앙상블 예측기 (Predictor) 를 구성하는 과정임.
• 어떻게 탐욕적인 방식 (Greedy Manner) 에서 반복적으로 약한 모델들 (기본 예측기들) 을 조합하여 강한 예측기를 만들 수 있는지를 설명하는 단단한 이론적 결과들에 의해 뒷받침됨.

우리는 기존의 모든 그라디언트 부스팅 구현은 다음과 같은 통계적 이슈에 직면하고 있음을 이 논문에서 보여줌.

• 부스팅의 일부 단계를 거친 후 얻어진 예측 모델 F 는 모든 훈련 예제들의 목표 (Target) 에 의존함.
• 우리는 이 것이 실제로 테스트 예제 x 의 F(x) | x 분포에서 훈련 예제 x_k 의 F(x_k) | x_k 분포로의 이동 (a Shift of the Distribution) 을 야기하는 것을 증명함.
• 결국, 이러한 점이 학습된 모델의 예측 변화 (Prediction Shift) 를 초래함.
• 우리는 이 문제를 섹션 4에서 특별한 종류의 목표 누수로 정의함.
• 게다가, 범주형 Feature를 전처리 하는 기존 알고리즘에서도 유사한 이슈가 있음.
• 그라디언트 부스팅에서 범주형 Feature를 사용하는 가장 효과적인 방법 중 하나는 범주를 목표 통계량으로 변환하는 것임.
• 목표 통계량은 간단한 통계적 모델 자체이며, 또한 목표 누수와 예측 변화를 유발할 수 있음.
• 우리는 섹션 3에서 이를 분석함.

이 논문에서, 우리는 두 가지 문제를 모두 해결하는 순서형 원칙 (Ordered Principle) 을 제시함.

• 이에 의존하여, 우리는 순서형 부스팅 (Ordered Boosting) 을 도출하며, 이는 목표 누수를 피하는 표준 그라디언트 부스팅 알고리즘의 수정이고 (섹션 4), 범주형 Feature를 처리하는 새로운 알고리즘임 (섹션 3).
• 이들의 조합은 CatBoost (Categorical Boosting) 로 불리는 오픈 소스 라이브러리로 구현되며, XGBoost와 LightGBM 같은 기존에 최첨단으로 구현된 그라디언트 부스팅 의사 결정 나무 (Gradient Boosted Decision Tree) 보다 다양하고 유명한 머신 러닝 작업에서 (섹션 6을 보면 됨) 좋은 성능을 냄.

 

2. Background

우리가 예제 Dataset (아래) 을 관찰한다고 가정하겠음.

• x_k  = (x^1_k, ..., x^m_k) 는 m개의 Feature를 가진 무작위 벡터이며, y_k ∈ R 은 목표 (Target) 이고, 이진형 (Binary) 또는 수치형 (Numerical) 반응변수 일 수 있음.
• 예제들 (x_k, y_k) 는 독립적이며, 일부 알려지지 않은 P(·,·) 분포에 따라 동일하게 분산됨.
• 학습 업무의 목표는 함수 (Function) F : R^m -> R 을 훈련하는 것이며, F는 아래의 추정된 Loss를 최소화시킴.

• L(·,·) 은 평활화 (Smooth) 손실 함수이며, (x, y) 는 훈련 집합 D 와 독립적으로, P 에서 Sample된 테스트 예제임.

그라디언트 부스팅 절차는 탐욕적 방법 (Greedy Fashion) 으로 일련의 근사치 F^t : R^m -> R, t = 0.1, ... 를 반복적으로 구축함.

• 즉, F^t 는 추가 방식에서 이전의 근사치 F^(t - 1) 에서 얻어짐 (아래의 식) :

• α 는 단계 크기 (Step Size) 이며, 함수  h^t : R^m -> R (기본 예측기, Base Predictor) 는 예측된 손실을 최소화 하기 위해 함수의 집합 (Family of Functions) H에서 선택됨.

• 최소화 문제는 보통 아래의 두번째 근사치를 사용한 뉴턴 방법 (Newton Method) 또는 (음수) 그라디언트 스텝을 취하여 접근함.

• 두 방법 모두 기능적 (Functional) 그라디언트 감소의 종류임.
• 특히, 그라디언트 스텝 h^t 는 h^t (x) 가 g^t (x, y) 를 근사하는 그러한 방법에서 선택되며, g^t (x, y) 는 아래와 같음.

• 보통, 다음과 같은 최소 제곱 근사치가 사용됨 :

CatBoost는 그라디언트 부스팅의 구현이며, 기본 예측기 (Base Predictor) 로써 이진 의사결정나무를 사용함.

• 의사결정나무는 Feature 공간 R^m 을 일부 분할 속성 a 의 값에 따라 여러 분할 영역 (Disjoint Region) (Tree Nodes) 으로 재귀적으로 분할하여 구축되는 모델임.
• 속성은 보통 일부 Feature x^k 가 일부 임계값 t 를 초과하는 것을 정의하는 이진 변수이며, 따라서 아래와 같음.

• x^k 는 수치형 (Numerical) 또는 이진형 (Binary) Feature이고, 후자의 사례 (이진형) 에서 t = 0.5임.
• 각 최종 영역 (트리의 Leaf) 은 값을 할당받으며, 이 값은 회귀 작업에 대한 회귀의 반응 변수 y 의 추정 값 또는 분류 문제 사례에서 예측된 클래스 레이블임.
• 이러한 방법으로, 의사결정나무 h 는 다음과 같이 쓰여질 수 있음 :

• R_j 는 트리의 Leaves에 해당하는 분할 영역임.

 

3. Categorical features

3-1. Related work on categorical features

범주형 Feature는 서로 비교할 수 없는 범주 (Categories) 라 불리는 이산형 값의 집합을 가진 것임.

• 부스팅 트리에서 범주형 Feature를 다루는 유명한 기술 중 하나는 One-hot Encoding이며, 각 범주 (Category) 에 대해 Feature를 나타내는 새로운 이진 (Binary) Feature를 추가하는 것임.
• 그러나, 높은 카디널리티 (Cardinality) Feature의 경우 ("user ID" Feature 같은), 그러한 기법은 헤아릴 수 없을 정도로 많은 새로운 Feature의 수를 초래함.
• 이 이슈를 다루기 위해서, 제한된 클러스터 수로 범주를 그룹화한 다음 One-hot Encoding을 적용하는 방법이 있음.
• 또 하나의 유명한 방법은 각 범주의 예상 목표 값을 추정하는 목표 통계량 (TS, Target Statistics) 별로 범주를 그룹화하는 것임.
• Micci-Barreca는 대신 TS를 새로운 수치 Feature로 고려할 것을 제안함.
• 중요한 것은, 가능한 모든 범주 분할 (Partition) 중에서, MSE (Mean Square Error), Gini Index, Logloss의 관점에서 훈련 데이터의 최적의 분할은 수치 TS Feature에 대한 임계값 (Threshold) 중에서 발견될 수 있음.
• LightGBM의 경우, 범주형 Feature는 그라디언트 부스팅의 각 단계에서 그라디언트 통계량으로 변환 됨.
• 트리를 구축하는 데 있어서 중요한 정보를 제공하지만, 이 접근법은 다음과 같은 것들을 극적으로 증가시킬 수 있음 :
  1. 각 단계에서 각 범주 값에 대한 통계량을 계산하기 때문에, 계산 시간 (Computation Time).
  2. 한 범주 Feature를 기반으로 분할된 각 노드에 속하는 범주를 저장하는 메모리 소모 (Memory Consumption).
• 이 이슈를 극복하기 위해서, LightGBM은 꼬리 (Tail) 범주들을 한 개의 클러스터로 그룹화하고, 정보의 일부를 순환 (Loose) 시킴.
• 게다가, 저자들은 높은 카디널리티를 가진 범주형 Feature를 수치형 Feature로 변환하는 것이 여전히 더 좋다고 주장함.
• TS Feature는 하나의 범주당 하나의 숫자만 계산하고 저장하면 된다는 점을 주목해야함.

따라서, 새로운 수치형 Feature로써 TS를 사용하는 것은 최소한의 정보 손실을 가지고 범주형 Feature를 다루는 가장 효율적인 방법으로 보임.

• TS는 클릭 예측 작업 (클릭율) 에서 널리 사용되며, 여기서 사용자, 지역, 광고, 출판사와 같은 범주형 Feature가 중요한 역할을 함.
• 우리는 또한 TS를 계산하는데 초점을 두고, One-hot Encoding과 그라디언트 통계량은 현재 논문의 범위에 포함되지 않음.
• 동시에, 우리는 이 논문에서 제시한 순서형 원칙 (Ordering Principle) 이 또한 그라디언트 통계량에 대해 효과적이라고 생각함.

 

3-2. Target statistics

섹션 3-1에서 논의 한것처럼, 범주형 Feature i 를 다루는 효과적이고 효율적인 방법은 k 번째 훈련 예제의 범주 x^_K 를 일부 목표 통계량 (TS) x^^i_k 와 동일한 하나의 수치형 Feature로 대체하는 것임.

• 일반적으로, 그것은 아래와 같은 범주에 의해 조건화 되는 예상 목표 y 를 추정함.

Greedy TS

• 한 간단한 방법은 동일한 범주 x^i_k 를 가지고 훈련 예제들에 대한 y 의 평균값으로써 E(y | x^i = x^i_k) 를 추정하는 것임.
• 이 추정은 낮은 빈도수를 가진 범주에 대해 Noisy 하며, 보통 그것을 아래와 같이 p 이전 까지 평활화 (Smooth) 함.

• a 는 0보다 큰 파라미터임.
• p 에 대한 공통된 설정은 Dataset의 평균 목표 값임.
• 그러한 Greedy 접근법의 문제는 목표 누설임 : Feature x^^i_k 는 x_k 의 목표 (Target) 인 y_k 를 사용하여 계산됨.
• 이러한 점은 조건부 변화를 야기함 : x^^i | y 의 분포는 훈련과 테스트 예제에 따라 다름.
• 다음에 나오는 극단적인 예제는 어떻게 이러한 점이 학습된 모델의 일반화 오류에 극적으로 영향을 미칠 수 있는지를 보여줌.
• i 번째 Feature가 범주형이고, 그러한 모든 값은 유일하며, 각 범주 A에 대해, 우리는 분류 작업에 대해 P(y =  1 | x^i = A) = 0.5가 있다고 가정함.
• 그런 다음, 훈련 Dataset에서 x^^i_k = (y_k + ap) / (1 + a) 를 사용하므로, 임계값 t = (0.5 + ap) / (1 + a) 을 사용하여 한 개만 분할하면 모든 훈련 예제들을 완벽하게 분류할 수 있음.
• 그러나, 모든 테스트 예제들의 경우, 탐욕 TS의 값은 p 이며, 얻어진 모델은 이 예졔들이 p < t 를 만족하면 0, 그렇지 않으면 1로 예측하며, 따라서, 두 사례 모두 0.5의 정확도를 가짐.
• 결국, 우리는 이를 위해 TS에 대해 다음과 같은 원하는 (Desired) 속성을 공식화함.

• 위의 우리 예시에서, 아래의 두 식은 서로 다름.

• 이 조건부 변화를 피하는 일부 방법이 있음.
• 이 방법들의 일반적인 아이디어는 x_k 를 제외한 D_k ⊂ D \ {x_k} 예제의 부분집합에서 x_k에 대한 TS를 계산하는 것임.

Holdout TS

• 한 가지 방법은 훈련 Dataset을 두 부분 D = D^_0 ∪ D^_1 로 나누고, (5) 에 따라 TS를 계산하는 경우 D_k = D^_0, 훈련의 경우 D^_1 을 사용함.
• 그러한 Holdout TS는 P1 을 만족시키지만, 이 접근법은 TS를 계산하고 모델을 훈련하는 데 사용되는 데이터의 양을 상당히 감소시킴.
• 그래서, 다음과 같은 원하는 (Desired) 속성을 위반함
  • P2 - 모델을 학습시키고, TS Feature를 계산하는 경우의 모든 훈련 데이터의 효과적인 사용

Leave-one-out TS

• 얼핏보면, Leave-one-out 기술은 잘 동작할 수 있음 : 훈련 예제는 D_k = D \ x_k, 테스트 예제는 D_k = D 를 취하면 됨.
• 놀랍게도, 이 것은 목표 누수를 예방해주지 않음.
• 결국, 일정한 (Constant) 범주형 Feature를 고려해야함 : 모든 예제에 대한 x^i_k = A.
• n^+ 를 y = 1을 가진 예제의 수라 하고, 그런 다음 x^^i_k 와 함께 임계값 t를 이용하여 분할함으로써 훈련 Dataset을 완벽하게 분류할 수 있음.

Ordered TS

• CatBoost는 더 효과적인 전략을 사용함.
• 이 것은 이 논문의 중심 아이디어인 순서 원칙 (Ordering Principle) 에 의존하며, 훈련 예제들을 제시간에 연속적으로 얻는 온라인 학습 알고리즘에서 영감을 얻음.
• 분명하게, 각 예제들의 TS 값은 관측된 내역 (History) 에만 의존함.
• 표준 오프라인 설정에 이 아이디어를 적용하기 위해서, 우리는 인위적인 "시간 (Time)" 을 도입함 (즉, 훈련 예제들의 무작위 순열σ).
• 그런 다음, 각 예제의 경우, 우리는 예제자신의 TS를 계산하기 위해 이용 가능한 모든 "내역 (History)" 을 사용함 (즉, 훈련 예제의 경우 (5)의 식에서 D_k = { x_j : σ(j) < σ(k) }, 테스트 예제의 경우 D_k = D).
• 얻은 Ordered TS는 요구사항 P1 을 만족하며, 모델 (P2) 을 학습하기 위해서 모든 훈련 데이터를 사용할 수 있음.
• 우리가 무작위 순열을 하나만 사용한다면, 이전 예제들은 다음 예제들보다 훨씬 더 높은 분산을 가진 TS를 가짐.
• 결국, CatBoost는 그라디언트 부스팅의 서로 다른 단계에서 서로 다른 순열들을 사용하며, 섹션 5에 세부사항이 나와있음.

 

4. Prediction shift and ordered boosting

4-1. Prediction shift

이 섹션에서, 우리는 그라디언트 부스팅에서 예측 변화의 문제를 나타내며, 인식되거나 이전에 다루지 않았음.

• TS의 사례와 같이, 예측 변화는 특별한 종류의 목표 누수에 의해 발생됨.
• 우리의 Solution은 순서형 부스팅 (Ordered Boosting) 으로 불리며, 순서형 TS 방법과 닮음.

섹션 2에서 설명한 그라디언트 부스팅 절차로 돌아가 보겠음.

• 실제로, (2) 의 기대치는 알 수 없으며, 보통 동일한 Dataset D 를 사용하여 근사치를 구함 :

이제 우리는 다음과 같은 교대 체인 (Chain of Shifts) 을 분석하고 설명함 :

1. 그라디언트의 조건부 분포 g^t (x_k, y_k) | x_k ( D \ {x_k} 의 무작위성에 대한 계산 ) 는 테스트 예제 g^t (x, y) | x 에서 해당 분포로 변화됨.
2. 결국, 식 (6) 에서 정의된 기본 예측기 h^t 는 식 (2) 의 Solution에서 편향됨.
3. 이것은 마지막으로 훈련된 모델 F^t 의 일반화 능력에 영향을 미침.

TS의 사례 처럼, 이러한 문제들은 목표 누수에 의해 일어남.

• 실제로, 각 단계에서 사용된 그라디언트는 현재 모델 F^(t-1) 이 구축된 동일한 데이터 포인트의 목표값을 사용하여 추정됨.
• 그러나, 일반적으로 훈련 예제 x_k 의 조건부 분포 F^(t-1) (x_k) | x_k 는 테스트 예제 x 에 대한 분포 F^(t-1) (x) | x 에서 변화 (Shift)됨.
• 우리는 이것을 예측 변화 (Prediction Shift) 라고 부름.

Related work on prediction shift

• 그라디언트 조건부 분포 g^t (x_k, y_k) | x_k 의 변화는 이전에 부스팅의 논문에서 언급됐지만, 공식적으로 정의되지는 않았음.
• 게다가, 0이 아닌 변화 조차도 이론적으로 증명되지 않았음.
• OOB (Out-of-Bag) 추정치에 기반하여, Breiman은 반복된 배깅 (Iterated Bagging) 을 제시했으며, 이는 "OOB" 잔차 추정치 근거 (the Basis of "Out-of-Bag" Residual Estimates) 에 기반하여 각 반복에서 배깅된 약한 학습기를 구축함.
• 그러나, 우리가 공식적으로 부록 E에서 보여준 것과 같이, 그러한 잔차 추정치가 여전히 변화됨.
• 게다가, 배깅 방법 (Scheme) 은 데이터 Bucket의 수에 따라 학습 시간을 증가시킴.
• Friedman이 제시한 각 반복에서 Dataset의 Subsampling은 문제를 훨씬 더 경험적으로 (Heuristically) 다루고, 또한 완화시킬 뿐임.

Analysis of prediction shift

• 우리는 공식적으로 2차 (Quadratic) 손실 함수 L(y, y^) = (y - y^)^2 를 이용한 간단한 회귀 작업 사례에서 예측 변화의 문제를 분석함.
• 이 사례에서, 식 (6) 의 음수 그라디언트 -g^t (x_k, y_k) 는 잔차 함수 r^(t-1) (x_k, y_k) := y_k - F^(t - 1) (x_k) 에 의해 대체될 수 있음.
• 우리가 p = 1 / 2, y = f^* (x) = c_1 * x^1 + c_2 * x^2 를 가진 i.i.d 베르누이 무작위 변수들인 m = 2 Feature x^1, x^2 를 가진다고 가정해보겠음.
• 우리는 Decision Stumps (트리의 깊이 1) 와 단계 크기 α = 1 을 가진 N = 2 인 그라디언트 부스팅 단계를 만든다고 가정해보겠음.
• 우리는 모델 F = F^2 = h^1 + h^2 를 획득함.
• 우리는 h^1 이 x^1 에 기초하고, h^2 가 x^2 기초한다고 가정하며, 이것은 |c_1| > |c_2| 로 대표함 (What is Typical for) (여기서 우리는 x^1 과 x^2 사이의 약간의 비대칭성 (Asymmetry) 을 설정함).

Theorem 1

1. 크기 n 을 가진 두 개의 독립적인 샘플들 D_1 과 D_2 가 h^1 과 h^2 를 식 (6) 을 사용하여 개별적으로 추정하는데 사용됐다면, 모든 x ∈ {0, 1}^2 에 대해 E_(D_1, D_2) F^2 (x) = f^* (x) + O(1 / 2^n) 를 사용함.
2. 동일한 Dataset D = D_1 = D_2 가 h^1 과 h^2 에 대해 식 (6) 에서 사용되는 경우, E_D F^2 (x) = f^* (x) - (1 / (n - 1)) * c_2 (x^2 - 1 / 2) + O(1 / 2^n) 를 사용함.

이 Theorem은 훈련된 모델이 각 그라디언트 단계에서 우리가 독립적인 Dataset을 사용할 때, 참 의존 (True Dependency) y = f^* (x) 의 편향되지 않은 추정치라는 것을 의미함.

• 반면에, 우리가 각 단계에서 동일한 Dataset을 사용하면, 우리는 편향 -(1 / (n - 1)) * c_2 (x^2 - 1 / 2)) 를 겪으며, 이는 데이터 크기 n에 반비례함.
• 또한, 편향값이 우리 예제에서 관계 f^* 에 따라 달라질 수 있으며, 이는 c_2 와 비례함.
• 우리는 Theorm 1의 두 번째 부분의 Chain of Shifts 을 아래의 Sketch of the proof 에서 추적하며, Theorem 1의 전체 증명은 부록 A에서 이용 가능함.

Sketch of the proof

• ε_st, s, t ∈ {0, 1}, x_k = (s, t) 를 가진 예제 (x_k, y_k) ∈ D 의 수로 나타냄.
• 우리는 h^1 (s, t) = c_1 * s + (c_2 * ξ_s1) / (ξ_s0 + ξ_s1) 을 가짐.
• 테스트 예제 x 에서의 기대값 E( h^1 (x) ) 은  c_1 * x^1 + c_2 / 2 와 동일함.
• 동시에, 훈련 예제 x_k 에서의 기대값 E( h^1 (x_k) ) 는 다르며, (c_1  * x ^1 + c_2 / 2) - c_2 * ((2*x^2 - 1) / n) + O(2^(-n)) 과 동일함.
• 즉, 우리는 h^1 의 예측 변동을 경험함.
• 결과적으로, h^2 (x) 의 기대값은 테스트 예제 x 에서 E( h^2 (x) ) = c_2 * (x^2 - 1 / 2) * (1 - 1 / (n - 1)) + O(2^(-n)) 및 E( h^1 (x) + h^2 (x) ) = f^* (x) - (1 / (n - 1)) * c_2 * (x^2 - 1 / 2) + O(1 / 2^n) 임.

결국, 탐욕적인 TS x^^i 가 목표 y 를 예측하는 간단한 통계적인 모델로써 간주될 수 있고, 목표 누수에 의해 야기되는 조건부 변화 x^^i_k | y_k, 즉, y_k 를 이용하여 x^^i_k 를 계산하는 것과 유사한 문제를 겪고 있다는 점을 상기함.

 

4-2. Ordered boosting

여기서 우리는 섹션 4-1에서 설명한 예측 변화 문제를 겪지 않는 부스팅 알고리즘을 제시함.

• 훈련 데이터를 무제한으로 이용할 수 있다고 가정할 때, 우리는 쉽게 그러한 알고리즘을 구축할 수 있음.
• 부스팅의 각 단계에서, 우리는 독립적으로 새로운 Dataset D_t 를 Sample 하고, 현재 모델을 새로운 훈련 예제들에 적용하여 변화되지 않는 잔차를 얻음.
• 그러나, 실제로 레이블이 있는 데이터는 제한적임.
• 우리가 I 개의 트리를 가지고 모델을 학습한다고 가정하겠음.
• 변화되지 않는 잔차 r^(I - 1) (x_k, y_k) 를 만들기 위해서, 우리는 예제 x_k 없이 훈련된 F^(I - 1) 이 필요함.
• 우리가 모든 훈련 예제들에 대해 편향되지 않은 잔차들이 필요하기 때문에, 어떤 예제들도 훈련 F^(I - 1) 에 대해 사용될 수 없으며, 이는 언뜻 보기에 훈련 과정이 불가능하게 만듬.
• 그러나, 모델 훈련에 사용된 예제들에 따라 다양화된 모델의 집합을 유지하는 것이 가능함.
• 그런 다음, 예제의 잔차를 계산하는 경우, 우리는 잔차 없이 훈련된 모델을 사용함.
• 그러한 모델의 집합을 구축하기 위해서, 우리는 섹션 3-2 에서 이전에 TS에 적용된 순서형 원칙 (Ordering Principle) 을 사용할 수 있음.
• 이 아이디어를 설명하기 위해서, 우리는 훈련 예제 중 무작위 순열 σ 하나를 취하고, 서로 다른 n개의 지원 모델 M_1, ..., M_n 를 유지한다고 가정하며, 그러한 모델 M_i 는 순열 (Permutation) 의 처음 i 예제만을 사용하여 학습됨.
• 각 단계에서, j 번째 샘플에 대한 잔차를 얻기 위해서 , 우리는 모델 M_(j - 1) 모델을 사용함 (Figure 1을 보면 됨).

• 결과 Algorithm 1을 아래의 순서형 부스팅 (Ordered Boosting) 이라고 부름.
• 불행하게도, 이 알고리즘은 n개의 서로 다른 모델들을 훈련시킬 필요가 있기 때문에 대부분의 실무 작업들에서 실현 가능하지 않으며, 이러한 점은 복잡성과 메모리 요구를 n배 만큼 증가시킴.
• CatBoost에서, 우리는 섹션 5에서 설명한 기본 예측기로 의사결정나무를 이용한 그라디언트 부스팅 알고리즘 (GBDT) 을 기반으로 이 알고리즘의 수정판을 구현했음.

Ordered boosting with categorical features

• 섹션 3-2 와 4-2에서, 우리는 개별적으로 Ordered Boosting과 TS 계산에 대해 훈련 예제들의 무작위 순열 σ_cat 과 σ_boost 을 사용하는 것을 제시함.
• 이들을 조합하여 하나의 알고리즘을 만들면, 우리는 예측변화를 피하기 위해 σ_cat = σ_boost 를 사용해야 함.
• 이러한 점은 목표 y_i 가 훈련 모델 M_i 에서 사용되지 않는 다는 것을 보장함 (TS 계산이나 그라디언트 추정 모두).
• 이론적인 보장에 대한 것은 부록 F를 보면 됨.
• σ_cat = σ_boost 의 중요성을 확인하는 경험적인 결과들은 부록 G에 제시되어 있음.

 

5. Practical implementation of ordered boosting

CatBoost는 두 가지 모드를 가짐.

1. Ordered
2. Plain

• 후자의 모드 (Plain) 는 내장형 Ordered TS를 가진 표준 GBDT 알고리즘임.
• 전자의 모드 (Ordered) 는 Algorithm 1의 효율적인 수정판을 제시함.

• 알고리즘의 공식적인 설명은 부록 B에 포함되어 있음.
• 이 섹션에서, 우리는 가장 중요한 구현 세부사항을 검토함.

시작할 때, CatBoost는 훈련 Dataset의 독립적인 s + 1개의 무작위 순열을 생성함.

• 순열 σ_1, ..., σ_s 는 트리 구조 (즉, 내부 노드 (Internal Node)) 를 정의하는 분할 평가에 사용되는 반면, σ_0 은 획득한 트리의 Leaf 값 b_j 를 선택하는 역할을 수행함 (식 (3) 을 보면 됨).
• 예를 들어 주어진 순열의 짧은 내역 (History) 을 가지고, Ordered Boosting (Algorithm 1의 M_(σ(i) - 1) (x_i)) 에 사용된 TS와 예측 모두 높은 분산 (Variance) 을 가짐.
• 따라서, 한 개의 순열만 사용하는 것은 최종 모델 예측의 분산을 증가시킬 수 있는 반면, 일부 순열은 우리가 추가로 설명한 방법에서 이러한 영향을 감소시킬 수 있음을 보여줌.
• 일부 순열에 대한 이점은 섹션 6에서 우리 실험에 의해 확인됨.

Building a tree

• CatBoost에서, 기본 예측기들은 의사결정테이블 (Decision Table) 라고도 불리는 망각 의사결정나무 (Oblivious Decision Tree) 임.
• Oblivious 용어는 동일한 분할 기준이 트리의 전체 레벨에 걸쳐 사용되는 것을 의미함.
• 그러한 트리들은 균형 잡히고, 지나치게 Overfitting이 되지 않으며, 테스트 실행 시간을 상당히 가속화할 수 있음.
• CatBoost의 트리 구축 절차는 Algorithm 2에서 설명됨.

Ordered Boosting 모드에서 학습 과정동안, 우리는 지원 모델 M_(r, j) 를 유지하며, M_(r, j) 는 순열 σ_r 에서 첫 번째 j 예제를 기반으로 i 번째 예제에 대한 현재 예측임.

• 알고리즘의 각 반복 t 에서, 우리는 {σ_1, ..., σ_s} 에서 무작위 순열 σ_r 을 Sample하고, 이 것을 기반으로 트리 T_t 를 구축함.
• 첫 번째로, 범주형 Feature의 경우, 모든 TS가 이 순열에 관하여 계산됨.
• 두 번째로, 순열이 트리 학습 절차에 영향을 끼침.
• 즉, M_(r, j) (i) 를 기반으로, 우리는 해당하는 그라디언트 (아래) 를 계산함.

 

• 그런 다음, 트리를 구축하는 동안, 우리는 그라디언트 G 를 코사인 유사도 cos( , ) 의 관점에서 대략적으로 추정하며, 여기서 각 예제 i에 대해 우리는 그라디언트 grad_(r, σ(i) - 1) (i) 를 취함 (이 것은 σ_r 에서 이전 예제만을 기반으로 함).
• 후보 분할 추정 단계에서, 예를 들어 i의 Leaf 값 ∆(i) 는 예제 i 가 속한 동일한 Leaf leaf_r (i) 에 놓여있는 이전 예제 p의 그라디언트 grad_(r, σ(i) - 1) 을 평균하여, 개별적으로 구함.
• leaf_r (i) 가 선택된 순열 σ_r 에 따라 달라지는 것을 주목 해야 하며, σ_r 이 예제 i에 대한 Ordered TS의 값에 영향을 미칠 수 있기 때문임.
• 트리 구조 T_i (즉, 분할 속성 시퀀스) 가 구축되었을 때, 우리는 모든 모델 M_(r', j) 을 부스트 하기 위해 이 것을 사용함.
• 하나의 공통 트리 구조 T_i 가 모든 모델에서 사용된다는 것을 강조하지만, 이 트리는 r' 과 j에 따라 서로 다른 Leaf 값의 집합을 가진 다른 M_(r', j) 에 추가되며, Algorithm 2에서 설명되어있음.

일반 부스팅 모드는 표준 GBDT 절차와 유사하게 작동하지만, 범주형 Feature가 있는 경우, σ_1, ..., σ_s 를 기반한 TS에 해당하는 모델 M_r을 지원하는 s를 유지함.

Choosing leaf values

• 모든 구축된 트리가 주어질 때, 최종 모델 F 의 Leaf 값은 두 모드에 대해 동일한 표준 그라디언트 부스팅 절차에 의해 계산됨.
• 훈련 예제 i가 Leaves leaf_0 (i) 와 일치하며 , 즉, 우리는 여기서 TS 계산하기 위해 순열 σ_0 을 사용함.
• 최종 모델 F가 테스팅 시간에서 새로운 예제에 적용되었을 경우, 우리는 섹션 3-2에 따라 전체 훈련 데이터에 대해 계산된 TS를 사용함.

Complexity

• 우리의 실제 구현에서, 우리는 한가지 중요한 트릭을 사용하며, 이는 상당히 알고리즘의 계산 복잡성을 감소시킴.
• 즉, Ordered 모드에서, O(s n^2) 값 M_(r, j) (i) 대신, 우리는 j = 1, ..., [log2n] 과 σ_r (i) <= 2^(j + 1) 을 가진 모든 i 에 대한 값 M'_(r, j) (i) := M_(r, 2^j) (i) 만을 저장하고 갱신하며, 이는 O(s n)에 대한 유지된 지지 예측의 수를 감소시킴.
• 이 알고리즘 2 수정 유사코드는 부록 B에 있음.

Table 1에서, 우리는 한 반복당 두 개의 CatBoost 모드의 서로 다른 구성요소의 계산 복잡도를 제시함 (증명은 부록 C.1을 참조).

• N_(TS, t) 는 반복 t에서 계산할 TS의 수이며, C는 주어진 반복에서 고려될 후보 분할의 집합임.
• 따라서, 의사결정나무를 이용한 Ordered Boosting을 구현하는 것은 Ordered TS를 이용한 표준 GBDT와 동일한 유사 복잡성을 가짐.
• 다른 종류의 TS와 비교하기 위해서 (섹션 3-2), Ordered TS는 CalcGradient 절차, 지원 모델 M 갱신, TS 계산에 대해 s배만큼 느려짐.

Feature combinations

• CatBoost의 또 다른 중요한 세부사항은 광고 클릭율 예측의 작업에서 광고 토픽과 userID의 공동 정보 같은 고차 (High-Order) 의존성을 포착하는 추가적인 범주형 Feature로 범주형 Feature의 조합을 사용하는 것임.
• 가능한 조합의 수는 Dataset에서 범주형 Feature의 수에 따라 기하급수적으로 증가하며, 모든 조합을 처리하는 것은 불가능함.
• CatBoost는 탐욕적 방법으로 조합을 구성함.
• 즉, 트리의 각 분할에서, CatBoost는 현재 트리 이전에 사용된 모든 범주형 Feature (그리고 이들의 조합) 를 Dataset의 모든 범주형 Feature와 조합 (combine) (연결, Concatenate) 함.
• 조합은 즉시 TS로 전환됨.

Other important details

• 마지막으로, 우리는 위에서 다루지 않은 CatBoost 알고리즘의 두 가지 옵션을 논의해야함.
• 첫 번째는, Friedman에 의해 제시된 부스팅 절차의 각 반복에서 Dataset의 Subsampling임.
• 우리는 섹션 4-1에서 미리 이 접근법만으로는 예측 변화 문제를 완벽하게 피할 수 없다는 것을 주장했음.
• 그러나, 그것이 효과적인 것이 증명되었기 때문에, 우리는 베이지안 부트스트랩 절차로서, CatBoost의 두 모드에서 그것을 구현했음.
• 구체적으로, Algorithm 2에 따라 트리를 훈련하기 전에, 우리는 가중치 w_i = a^_i 를 각 예제 i에 할당하며, a^t_i 는 베이지안 부트스트랩 절차에 따라 생성됨 (섹션 2, 28에 나타남).
• 이러한 가중치들은 우리가 ∆(i) 와 벡터 ∆ - G 의 구성요소를 계산하여 loss(T_c) 를 정의할 때, 그라디언트 grad_r (i) 와 grad_(r, j) (i) 에 대한 승수 (Multiplier) 로 사용됨.
• 두 번째 옵션은 우선 순열에서 일부 예제들을 다룸.
• 작은 값 σ_r (i) 을 가진 예제 i의 경우, grad_(r, σ_r (i) - 1) (i) 의 분산이 높을 수 있음.
• 따라서, 우리는 Algorithm 2에서 loss(T_c) 를 계산할 때, 순열의 시작부터 ∆(i)를 버림.
• 특히, 우리는 벡터 G 와 ∆ 사이에서 코사인 유사도를 계산할 때, 해당 구성요소를 제거함.

 

6. Experiments

Comparison with baselines

• 우리는 일부 잘 알려진 머신러닝 작업들에서 XGBoost와 LightGBM 같은 가장 유명한 오픈소스 라이브러리와 우리 알고리즘을 비교함.
• Dataset 설명과 함께 실험 설정에 대한 세부적인 설명은 부록 D에서 사용가능함.
• 실험의 소스코드는 사용가능하며, 결과들은 재현할 수 있음.
• 모든 학습 알고리즘의 경우, 우리는 섹션 3-2에서 설명한 Ordered TS 방법을 사용하여 범주형 Feature를 전처리 함.
• 파라미터 튜닝과 훈련은 데이터의 80% (4 / 5), 테스팅은 남은 20% (1 / 5) 에서 수행됐음.
• Logloss와 Zero-one loss로 측정된 결과들은 Table 2에 제시됨 (Baseline의 절댓값은 부록 G에 있음).

• CatBoost의 경우, 우리는 이 실험에서 Ordred Boosting 모드를 사용했음.
• CatBoost가 고려된 모든 Dataset에서 다른 알고리즘보다 나은 성능을 발휘한 것을 볼 수 있음.
• 또한, 우리는 Table 2에 제시된 개선사항의 통계적 유의성을 측정했음 : 단, 세 Dataset을 제외하고 (Appetency, Churn, Upselling) 개선사항은 Paired one-tailed t-test로 측정된 p-value << 0.1에서 통계적으로 유의함.
• 우리는 우리의 평범한 부스팅 구현이 우리 연구에서 적절한 Baseline 이라는 것을 증명하기 위해서, CatBoost의 초기 설정 (Raw Setting) 이 최첨단 품질을 제공해준다는 것을 보여줌.
• 특히, 우리는 CatBoost의 설정을 취하는데, 이것은 고전적인 GBDT와 밀접하며, 부록 G의 Baseline 부스팅 구현과 이 것을 비교함.
• 실험은 이 초기 설정이 Baseline과 크게 다르지 않다는 것을 보여줌.

또한, 우리는 경험적으로 Epsilon Dataset에서 알고리즘의 실행 시간을 분석했음.

• 비교의 세부사항은 부록 C.2에서 찾을 수 있음.
• 요약하자면, 우리는 CatBoost Plain과 LightGBM이 가장 빠르다는 사실을 얻었으며, 약 1.7배 더 느린 Ordered mode가 그 다음으로 따라왔음.

Ordered and Plain modes

• 이 섹션에서, 우리는 CatBoost의 두 가지 필수적인 부스팅 모드를 비교함 :
  • Plain
  • Ordered
• 첫 번째로, 우리는 고려된 모든 Dataset에서 이 모드들의 성능을 비교했으며, 결과는 Table 3에 제시됨.

• Ordered 모드가 특히 작은 Dataset에서 유용하다는 것을 분명하게 볼 수 있음.
• 실제로, Ordered의 가장 큰 이점은 상대적으로 작은 (40K 미만 훈련 예제) Adult와 Internet Dataset에서 관찰되며, 이러한 점은 더 높은 편향 (Bias) 가 성능에 부정적으로 영향을 미친다는 우리의 가정을 지지함.
• 사실, Section 4-1의 추론과 Theorem 1에 따르면, 편향은 더 작은 Dataset에서 더 커질 것으로 기대됨 (그러나, 그것은 또한 Dataset의 다른 속성에 따라 달라질 수 있음 (ex. Feature와 목표 (Target) 사이의 의존성).
• 이 가정을 추가로 검증하기 위해서, 우리는 다음과 같은 실험을 구성함 : 우리는 Ordered와 Plain 모드에서 무작위로 걸러진 Dataset으로 CatBoost를 훈련하고 획득된 Loss를 비교하며, Figure 2를 보면됨.
• 우리가 기대했던 것처럼, 더 작은 Dataset의 경우에서 Plain 모드의 상대적인 성능이 더 악화됨.
• 공간을 절약하기 위해서, 여기에서 우리는 Logloss에 대한 결과만 제시하며, Zero-one Loss의 Figure는 이와 유사함.

• 우리는 또한 부록 G에서 위에서 언급한 초기 설정 CatBoost의 Ordered와 Plain 모드를 비교하고, Ordered 모드의 이점은 구체적인 CatBoost 옵션과의 상호작용에 의해 야기되지 않는 다는 결론을 지음.

Analysis of target statistics

• 우리는 모든 다른 알고리즘적 세부사항은 동일하게 유지하며, 섹션 3-2에 Ordered Boosting 모드에서 CatBoost의 옵션으로 소개된 서로 다른 TS를 비교함.
• 결과들은 Table 4에서 찾을 수 있음.
• 공간을 절약하기 위해서, 우리는 Ordered TS를 가진 CatBoost와 비교하여 각 알고리즘에 대한 Loss Function의 상대적인 증가량만 제시함.

• CatBoost에서 사용된 Ordered TS가 다른 모든 방법들보다 나은 성능을 발휘한다는 것을 주목해야함.
• 또한, Baseline 중에서, Holdout TS가 섹션 3-2에서 논의된 조건부 변화 (P1) 를 겪지 않기 때문에 대부분의 Dataset에서 가장 좋음.
• 여전히, 이것은 훈련 데이터의 덜 효과적인 사용 (P2) 때문에 CatBoost보다 더 나쁨.
• Leave-one-out은 보통 Greedy TS보다 더 좋지만, 일부 Dataset (ex. Adult) 에서는 더 나쁠 수 있음.
• 그 이유는 Greedy TS가 낮은 빈발도 (Low-Frequency) 범주를 겪는 반면, Leave-one-out TS는 또한 높은 빈발도 (High-Frequency) 를 겪고 있으며, Adult Dataset에서는 모든 Feature가 높은 빈발도를 가짐.

결국, Table 4에서 우리는 서로 다른 TS와 Ordered 모드 CatBoost를 조합한다는 점에 주목해야함.

• 이러한 결과들을 일반화시키기 위해서, 우리는 또한 표준 그라디언트 부스팅에서 사용된 서로 다른 TS와 Plain 모드를 조합하여 유사한 실험을 구성했음.
• 획득한 결과와 결론은 위에서 논의한 것들과 매우 유사하다는 것으로 판명났음.

Feature combinations

• 섹션 5에서 논의된 Feature 조합의 효과는 부록 G의 Figure 3에서 증명됨.
• 평균적으로, 1 ~ 2에서 조합할 수 있는 Feature의 수 c_max 를 변경하는 것은 Logloss가 1.86% 개선되며 (최대 11.3%), 1 ~ 3으로 변경되는 것은 2.04%를 내며, 더 이상의 c_max 증가는 성능에 큰 영향을 미치지 않음.

Number of permutations

• CatBoost의 성능에 대한 순열의 수 s의 효과는 부록 G의 Figure 4에 제시됨.
• 평균적으로, s를 증가시키는 것은 Logloss를 약간 감소시킴 (ex. s = 3이면 0.19%, s = 9의 경우 s = 1과 비교하여 0.38% 감소함).

 

7. Conclusion

이 논문에서, 우리는 그라디언트 부스팅의 기존 모든 구현에서 나타난 예측변화의 문제를 정의하고 분석함.

• 우리는 Ordered TS를 이용한 Ordered Boosting의 일반적인 솔루션을 제시하며, 이는 문제를 해결함.
• 이 아이디어는 CatBoost에서 구현되며, CatBoost는 새로운 그라디언트 부스팅 라이브러리임.
• 경험적 결과들은 CatBoost가 선도적인 GBDT 패키지 보다 나은 성능을 이끌고, 일반적인 벤치마크 (Benchmark) 에서 새로운 최첨단 결과를 이끌어 낸다는 것을 증명함.