[1. 알고리즘 설명] CatBoost : unbiased boosting with categorical features

📌 CatBoost?

 

CatBoost는 부스팅 모델의 하나로, 이름의 Cat은 Categorical의 줄임말이다. 이름에서 볼 수 있듯이 범주형 변수를 대상으로 자주 사용되며 예측 성능도 우수한 편이다. 그럼 CatBoost를 소개하는 본 논문 CatBoost : unbiased boosting with categorical features를 리류해보자.

 

📌 1. Introduction

 

일반적인 GBM(Gradient Boosting Model)은 실제 많이 사용되었었다(본 논문이 published된 2019년 기준). 부스팅 모델의 특성처럼 약한 모델들을 가법적으로 결합하여 함수 공간에서 그레디언트 하강법을 수행하는 모델이다.

 

본 논문에서는 기존 GBM 구현이 아래와 같은 통계적 문제에 직면한다고 제시한다.

 

(1) Prediction Shift 문제

: 부스팅 단계를 거쳐 생성된 최종 예측 모델은 훈련 데이터에 의존하기 때문에 테스트 데이터 혹은 실제 새로운 데이터가 사용될 때에는 훈련 분포에서 테스트 분포로의 이동(shift)를 초래하게 된다.

 

쉽게 설명하면, 시험공부 할 때 기출문제만 달달외워서, 실제 시험에서 비슷하지만 약간 다른 문제가 나오면 풀지 못하는거

 

(2) 범주형 데이터 처리 문제

: 범주형 특성을 그레디언트 부스팅에서 사용하는 가장 효과적인 방법 중 하나는 범주를 목표 통계량으로 변환하는 것.
(예를 들어, '도시'라는 변수에 서울이 있고 구매액이 100, 150, 200이라는 값을 가지는 3 개의 인스턴스가 있다면? 이들을 모두 150이라는 평균 값으로 변환하는 것)

문제는 해당 방법 또한 1번 문제와 비슷하게 훈련 데이터에 의존하게 된다. 

 

1번과 2번의 문제를 해결하기 위해 본 논문에서는 순서화 원리(ordering principle)를 제안한다.

 

📌 2. Background (GBM)

 

백그라운드 파트에서는 기본적인 GBM을 설명하고 있습니다. 아마 다들 아실거라고 생각하는데 풀어보자면,

 

데이터 셋 $D = {(\mathbf{x}_k, y_k)}_{k=1..n}$가 있으며 여기서 $\mathbf{x}_k = (x^1_k,...,x^m_k)$인 m개 feature가 있는 랜덤 벡터입니다. target 변수는 $y_k \in \mathbb{R}$

여기서 인스턴스 $(\mathbf{x}_k, y_k)$는 알 수 없는 분포 $P(\cdot, \cdot)$에 따라 독립적이고 동일하게 분포되어 있다.

 

당연하게도 모델 학습의 목표는 기대 손실 함수 $\mathcal{L}(F) := \mathbb{E}L(y, F(x))$를 최소화하는 함수 $F^t : \mathbb{R}^m \rightarrow \mathbb{R}, t =0,1,...$를 훈련시키는 것.

 

그레디언트 부스팅 절차는 탐욕적 방식으로 근사치들의 수열 $F^t : \mathbb{R}^m \rightarrow \mathbb{R}, t =0,1,...$을 반복적으로 구축. 즉 가법적이라는 이야기로 $F^t$는 이전의 근사치 $F^{t-1}$에서 저해지는 방식으로 얻어진다 ($F^t = F^{t-1} + \alpha h^t$ [$\alpha$는 스텝 크기, $h^t : \mathbb{R}^m \rightarrow \mathbb{R}$은 기대 손실 최소화하기 위해 family of functions $H$에서 선택])

 

$$
h^t = \arg \min_{h \in H} \mathcal{L}(F^{t-1} + h) = \arg \min_{h \in H} \mathbb{E}L(y, F^{t-1}(\mathbf{x}) + h(\mathbf{x}))
$$

 

위 식의 최소화 문제는 보통 $\mathcal{L}(F^{t-1} + h^t)$의 2차 근사를 사용하는 Newton method나 음의 그레디언트 스텝을 취함으로써 접근한다. 왜 음의 그레디언트를 사용하는지는 많이 알것이라 판단하고 설명하지는 않겠습니다.

 

그래서 CatBoost는 기본 예측기로 이진(binary) 결정 트리를 사용하는 그레디언트 부스팅의 구현체이다.

> 쉽게 설명하면 어쨋든 CatBoost도 GBM에 기반하고 있고, 약한 예측기로 이진 결정 트리를 사용한다는 것.

 

📌 3. Categorical features

◼️ 3.1 related work on categorical features

 

우선 부스팅에서 범주형 특성을 다루기 위해 쓰는 방법 중 하나가 원-핫 인코딩이다. 문제는 '사용자 ID'와 같은 특성에 사용하기에는 무수히 많은 변수가 생성된다는 문제가 있다.

 

예를 들어 '남성, 여성'으로 이루어진 성별 변수는 원=핫 인코딩을 통해 2개의 변수로 나뉘어 지지만 정보를 포함하고 있는 여러 숫자와 알파벳으로 이루어진 ID의 경우 수많은 변수가 만들어진다.

 

이를 해결하는 방법 중 하나가 각 범주에서 예상되는 target 값을 추정하는 target statistics(TS)로 범주를 그룹화하는 것.

 

TS 특성은 범주당 단 하나의 숫자만 계산하고 저장하면 된다는 점. 따라서 TS를 새로운 수치형 특성으로 사용하는 것이 최소한의 정보 손실로 범주형 특성을 처리하는 가장 효율적인 방법으로 판단.

 

그래서 TS는 뭐지??

 

예를 들어 아래와 같이 데이터가 있다고 해보자

data = {
	'city' : ['A', 'B', 'A', 'C', 'A', 'B'],
    'target' : [1, 0, 1, 0, 1, 1]
}

 

이때 범주형 변수인 city를 아래와 같이 계산하는 것이다.

 

A's TS = (1 + 1 + 1)/3 = 1.0
B's TS = (0 + 1)/2 = 0.5
C's TS = 0 / 1 = 0.0

 

CatBoost에선 이를 순서화 원리를 통해 사용합니다.

 

◼️ 3.2 Target statistics

 

(1) 탐욕적 TS (Greedy TS)

TS의 단순한 접근 방법은 $\mathcal{E}(y | x^i = x^i_k)$를 같은 범주 $x^i_k$를 가진 훈련 인스턴스들의 $y$의 평균값으로 추정하는 것. 해당 추정치는 낮은 빈도의 범주들에 대해서는 노이즈가 있을 수밖에 없고 보통 이를 사전 확률 $p$로 스무딩한다.

 

$$
\hat{x}^i_k = \dfrac{\sum^n_{j=1} \mathbb{1}_{x^i_j = x^i_k} \cdot y_j + ap}{\sum^n_{j=1} \mathbb{1}_{x^i_j = x^i_k} + a}
$$

여기서 $a( > 0)$은 매개변수이고, $p$의 일반적 설정은 데이터셋의 평균 타겟값임.

 

그래서 탐욕적 TS의 문제가 무엇이냐? 바로 타켓 유출. 쉽게 설명하면 애초에 범주형 변수를 수치형으로 변화할 때 target 값을 기준으로 사용하기 떄문에 변환하는 범주형 변수에 타겟값의 정보가 들어가버린다.

 

이럴경우 train data에 대해 성능이 당연히 좋아지지만, test data에 대해서 일반화가 잘 될지는 미지수이다.

 

그래서 이러한 한계를 피하기 위해 사용되는 일반적인 방법은 $\mathbf{x}_k$를 제외한 예제들의 부분집합 $\mathcal{D}_k \in D \setminus {{\mathbf{x}}_k}$에서 $\mathbf{x}_k$를 계산하는 것.

 

$$
\hat{x}^i_k = \dfrac{\sum_{\mathbf{x} \in \mathcal{D}_k} \mathbb{1}_{x^i_j = x^i_k} \cdot y_j + ap}{ \sum_{\mathbf{x} \in \mathcal{D}_k} \mathbb{1}_{x^i_j = x^i_k} + a}
$$

 

(2) 홀드아웃 TS (Holdout TS)

 

우리가 아는 홀드아웃 방법. 훈련 데이터셋을 두 부분으로 나누고 한 부분은 훈련에 한 부분은 테스트에 사용하는것.

당연히 문제는 훈련 데이터의 양이 그만큼 감소된다는 것

 

(3) 리브원아웃 TS (Leave-one-out TS)

 

이또한 우리가 아는 LOO 방법. 홀드아웃보다는 괜찮지만 어쨋든 target 정보 유출을 막지는 못함

 

(4) 순서화된 TS (Ordered TS)

 

Catboost에서 사용되는 방법. 순서 원칙에 기반. 시간 순차적으로 훈련 인스턴스를 받는 온라인 학습 알고리즘에서 영감을 받았다고 한다.

 

구체적으로 보면, 훈련 인스턴스들의 무작위 순열 $\sigma$를 도입한다.

 

그 다음, Greedy TS에서 보았던 마지막 수식에서 훈련 인스턴스에 대해  $\mathcal{D}_k = \{\mathbf{x}_j : \sigma(j) < \sigma(k) \}$ 이고 테스트 인스턴스에 대해 $\mathcal{D}_k = \mathcal{D}$인 모든 가용한 'history'를 TS를 계산하는데 사용한다.

 

해당 방법을 사용하면 타겟 유출 방지도 가능하고 모든 훈련 데이터를 효과적으로 사용할 수 있다. 그렇지만 단 하나의 무작위 순열만 사용할 경우, 선행 인스턴스들은 후속 인스턴스들보다 훨씬 더 큰 분산을 가진 TS를 자기데 된다. 이를 위해 CatBoost에서는 부스팅의 서로 다른 단계에 대해 서로 다른 순열을 사용한다.

 

말로만 들으면 이해안갈수도 있다. 한번 직접 확인해보자.

 

만약 우리의 데이터가 아래와 같이 되어있다고 가정해보자.

ID	Color	Target
1	Red	1
2	Red	1
3	Red	0
4	Blue	1
5	Blue	0
6	Blue	0

 

일반적인 TS 방법이라면 

- 빨강 : (1 + 1 + 0)/3 = 0.67
- 파랑 : (1 + 0 + 0)/3 = 0.33

의 값을 가지게 된다. > 명백한 target 정보 유출

 

그럼 순서화된 TS는? 아래와 같이 작동한다.

 

먼저, 데이터를 무작위 순열로 섞는다.

예) 무작위 순열(순서) : 2 - 4 - 1 - 6 - 3 - 5

 

여기서 중요한 점은 각 데이터의 TS를 계산할 때는 오직 이전 순서의 데이터만 사용한다.

 

- ID 2 (빨강) : 이전 데이터 없음 -> 사전 정의된 TS로 계산

- ID 4 (파랑) : 빨강 데이터 1개(1) -> 파랑 데이터 없음 사전 정의된 TS로 계산

- ID 1 (빨강) : 빨강 1개(1), 파랑 1개(1) -> 빨강의 TS = 1.0

- ID 6 (파랑) : 빨강 2개(1,1), 파랑 1개(1) -> 파랑의 TS = 1.0

- ID 3 (빨강) : 빨강 2개(1,1), 파랑 2개(1,0) -> 빨강의 TS = 1.0

- ID 5 (파랑) : 빨강 3개(1,1,0), 파랑 2개(1,0) -> 파랑의 TS = 0.5

 

이런식으로 각 데이터의 TS를 계산할 때 해당 데이터 자신의 타겟값을 사용하지 않음으로써 타겟 유출을 방지하고, 뒤로 갈 수록 더 많은 데이터를 사용하여 데이터 효율성을 높일 수 있다.

단, 여기서 앞에 있는 데이터 인스턴스 일수록 정보가 적기때문에 분산이 높아질수밖에 없다. 때문에 CatBoost에서는 여러 번의 무작위 순열을 사용하는 것.

 

 

📌 4. Prediction shift and ordered boosting

◼️ 4,1 prediction shift

 

그레디언트 부스팅에서는 예측 이동(prediction shift)의 문제가 있다. TS의 경우와 마찬가지로, 예측 이동은 특별한 종류의 타겟 유출에 의해 발생한다. 본 논문에서는 순서화된 부스팅(ordered boosting)을 사용하여 해결하고자 한다.

 

위 GBM을 설명하는데 사용되었던 식을 풀어 계산할 때, 일반적으로 같은 데이터셋 $\mathcal{D}$를 사용하여 근사화된다.

> 이게 무슨소리냐면, 우리가 흔히 생각하는 이상적인 '기댓값'은 데이터에 대한 평균을 의미함. 그러니까 모수에 대한 평균을 의미하는데, 실제로 모수를 알수는 없다.

 

때문에 우리가 가진 데이터를 사용하여 이 기대값을 근사한다는 것.

 

$$
h^t = \arg \min_{h \in H} \frac{1}{n} \sum^n_{k=1} (-g^t(\mathbf{x}_k, y_k) - h(\mathbf{x}_k))^2
$$

 

이게 어떤 문제가 있느냐?

(1) $\mathbf{x}_k$가 주어졌을 때 그레디언트 $g^t(\mathbf{x}_k, y_k)$의 조건부 분포는 테스트 인스턴스($\mathbf{x}$)가 주어졌을 때의 분포 $g^t(mathbf{x}, y)$와 다르다.

(2) 이에 따라서 그레디언트 분포가 이동되었기 때문에, 이를 바탕으로 학습되는 $h^t$도 편향될 수밖에 없다.

(3) 이는 최종적으로 훈련된 모델 $F^t$의 일반화 능력에 자연스럽게 영향을 주어 편향될수밖에 없다.

 

◼️ 4.2 ordered boosting

 

본 논문에서 이러한 predictiong shift 문제를 해결하기 위해 제시하는 방법은? 무제한의 학습 데이터에 접근할 수 있다고 논리적으로 가정하는 것.

 

부스팅의 각 단계에서, 새로운 데이터셋 $\mathcal{D}_i$를 독립적으로 샘플링하고 현재 모델을 새로운 학습 인스턴스에 적용하면 편향되지 않은 잔차를 얻는다. 이게 가능한가??

 

우선, 실제로는 레이블이 있는 데이터가 제한적이다.

 

$I$개의 트리로 모델을 학습한다고 가정해보자. 잔차 $r^{I-1}(\mathbf{x}_k, y_k)$를 편향되지 않게 만들기 위해서는, F^{I-1} 학습에 인스턴스를 사용할 수 없다. 그럼 학습이 불가능한건가??

 

하지만 학습에 사용되는 인스턴스들이 서로 다른 모델들의 집합을 유지하는 것이 가능하다. 그러면 인스턴스에 대한 잔차를 계산할 때 해당 인스턴스 없이 학습된 모델을 사용한다.

 

이를 이해하기 쉽게 보자면 데이터가 A, B, C 세개가 있다고 해보자.

- 모델1 : A로 학습

- 모델2 : A, B로 학습

- 모델3 : A, B, C로 학습

 

이런식으로 진행하게 되면 C의 잔차를 계산할때는 모델 2를 사용하면되고, B의 잔차를 계산할 때는 모델1을 사용하면 되는 거다. (데이터를 학습할 때 사용하지 않았으니 편향되지 않은 잔차를 얻을 수 있음.)

 

이를 위해 ordered boosting은 ordered TS와 유사한 방식을 사용한다. 

 

학습 인스턴스들의 임의의 순열 $\sigma$를 하나 선택하고, 각기 다른 n개의 서포딩 모델 $M_1,..., M_n$을 유지한다고 가정하자. 이 때 모델 $M_i$는 순열에서 처음 $i$개의 인스턴스만을 사용하여 학습된다. 

 

그럼 잔차를 구할 때 각 단계에서 $j$번째 인스턴스의 잔차를 얻기위해 모델 $M_{j-1}$을 사용하면 된다. 

 

여기서 문제점은 $n$개의 서로 다른 모델을 학습해야 하므로 복잡도와 메모리 요구사항이 $n$배로 증가해버린다. 이를 해결하기 위한 방법은 5장에서 설명.

 

 

📌 5. 순차적 부스팅의 실제 구현

 

CatBoost는 Ordered와 Plain 두가지 모드를 가지고 있고, Plain의 경우 내장된 ordered TS를 포함한 표준 GBDT 알고리즘이다. Ordered의 경우 효율적인 수정 버전.

 

앞서 설명했듯 알고리즘은

(1) 학습 데이터셋의 $s + 1$개의 독립적인 무작위 순열을 생성. 순열 $\sigma 1, ..., \sigma s$은 트리 구조(내부 노드)를 정의하는 분항을 평가하는 데 사용되고, $\sigma 0$은 학습된 트리의 리프 값 $b_j$를 선택하는 데 사용된다. 

(2) 이를 여러 순열로 사용.

 

- 트리 생성 알고리즘은 다음 편에 -