4-9 : Ensemble Learning - CatBoost

자료 출처

 

catboost의 저자들은 categorical feature를 처리하는데 사용되는 target statistic이 target leakage와 prediction shift 문제가 발생하며 이를 각각 ordered target statistics와 ordered boosting을 사용함으로써 해결할 수 있다고 주장한다.

 

그럼 먼저 기존에 사용되던 target statistics(TS)에 대해서 알아보자.

 

Categorical features in boosted tree

Greedy TS without smoothing

각 카테고리에 대해서 expected target value를 계산하며 수식은 다음과 같다.

i는 categorical feature이며 k는 training example index이다.

 

Greedy TS with smoothing

smoothing이 적용된 수식은 다음과 같다.

• a는 0보다 큰 파라미터이다.
• p는 데이터셋으로부터 계산된 target value의 기대값이다.
• 이 방법은 low frequency를 가진 noisy categories의 부정적인 효과를 줄이는데 사용된다.

이 부분은 index가 k인 example과 값이 같은 example의 개수를 의미한다.

 

low frequency를 가진 noisy categories는 다음과 같은 경우이다.

	y=1	y=0	TS
A	10	10	0.5
B	40	10	0.8
C	10	40	0.2
D	25	25	0.5
E	1	0	1

 

카테고리 E가 noisy category로 볼 수 있는데 많이 등장하는 다른 카테고리들에 비해서 TS가 극단적인 값이 발생할 수 있다.

 

a=0.1로 설정하고 greedy TS with smoothing을 적용한 예시는 다음과 같다.

 

 

Target leakage

• $\hat {x}_{k}^{i}$을 계산하는데 $x_k$의 target인 $y_k$가 사용된다.
• 이는 training examples와 test examples의 조건부 확률 $\hat {x}^{i}|y$를 다르게 만든다.

왜냐하면 raining examples 에서는 target 값을 사용하여 TS를 계산하지만 test examples에서는 target 값을 사용할 수 없기 때문이다.

 

한 가지 예시를 살펴보자. 아래 예시는 카테고리 값들이 모두 유니크한 경우이다.

training set의 $x_i$값은 y가 1인 경우에 $\frac{1+ap}{1+a}$로 같고 y가 0인 경우에는 $\frac{0+ap}{1+a}$로 같다. 그러면 split criterion을 $\frac{0.5+ap}{1+a}$로 설정하면 training set의 경우에는 완벽하게 분류가 가능하다. 하지만 test set에서 등장한 카테고리 값들은 training set에서 한 번도 등장한 적 없기 때문에 TS 값이 p가 된다. training에서 학습한 split으로는 test를 제대로 분류해낼 수 없다.

 

그래서 저자들이 제안하는 이상적인 TS는 다음 2가지 property를 만족하여야 한다고 한다.

• 학습 데이터와 테스트 데이터의 기대값이 같아야한다.
• TS를 계산하고 모델을 학습하는데 있어서 모든 학습 데이터를 효과적으로 사용해야 한다.

 

Ordered TS

가상의 시간 개념을 도입한 것인데 예를 들어 i+1번째 example의 TS를 계산할 때는 i번 째까지 등장한 examples에 대한 정보만 사용한다.

이 방법은 모델의 variance를 높이게 된다. 이를 방지하기 위해 뒤에서 서술할 Ordered Boosting은 random permutation을 여러개 사용한다.

 

예시를 살펴보자.

이전에 아무것도 등장한게 없기 때문에 summation 부분이 0이되고 p 또한 0이다.

 

이 전에 등장한 샘플들($I_1$ 샘플)에 대한 target value의 기대값은 1이라서 p=1이다. 카테고리 B는 이전에 등장한 적이 없기 때문에 summation 부분은 여전히 0이다.

 

이 전에 등장한 샘플들( $I_1, I_2$ 샘플)에 대한 target value의 기대값 p=1이다. 카테고리 C는 이전에 등장한 적이 없기 때문에 summation 부분은 여전히 0이다.

 

이 전에 등장한 샘플들( $I_1, I_2, I_3$ 샘플)에 대한 target value의 기대값 p=1이다. 카테고리 A는 이전에 한 번 등장하였으므로 summation 부분은 1이다.

5, 6번 째 샘플은 생략하고 7번 째 샘플을 보자.

 

이 전에 등장한 샘플들에 대한 target value의 기대값은 1이 5번 0이 1번이라서 p=5/6이다. 카테고리 B는 이전에 2번 등장하였으므로 분모의 summation은 2이고, 두 번 모두 y=1이기 때문에 분자의 summation도 2이다.

마지막 10번 째 샘플을 보자.

 

p=6/9이다. 카테고리 C는 이전에 총 4번 등장하여서 분모의 summation은 4이다. 그 중 y=1인 경우는 3번이기 때문에 분자의 summation은 3이다.

 

Ordered Boosting

prediction shift

• 기대값을 최소화하는 가설은 수식으로 다음과 같이 나타낸다.

• 기대값은 알 수 없기 때문에 dataset으로 각 example의 gradient를 계산하여 평균내어 근사한다.

• 그렇지만 training example의 gradient의 조건부 확률은 일반적으로 test example의 gradient와 다르다. 그래서 솔루션으로 부터 가설이 편향되어 있다. 이는 최종적으로 모델의 일반화에 영향을 미치게 된다.
• 따라서 우리가 I개의 tree로 모델을 학습할 때, $x_k$에 의해 만들어진 잔차 $r^{I-1}$가 shift되지 않도록 하려면 example $x_k$없이 학습된 모델 $F^{I-1}$을 필요로 한다.

 

이를 그림으로 설명하면 다음과 같다.

 

모델 1을 학습할 때는 $x_2$로만 학습하고 이를 가지고 $x_5$의 잔차를 계산한다. 그리고 모델 2를 학습할 때는 $x_2, x_5$를 가지고 학습하고 이를 가지고 $x_9$의 잔차를 계산한다.

 

TS를 계산할 때와 ordered boosting은 같은 permutation을 사용한다.

 

Catboost Procedure

• 초기에 학습 데이터셋으로부터 독립적인 random permutation을 s+1개 만든다.
  • s개는 split을 평가하는데 사용된다
  • 나머지 1개는 제일 마지막 단계에서 만들어진 트리들의 leaf value를 계산하는데 사용된다.
• ordered booting에 사용된 TS와 예측 모두 높은 variance를 갖는다. 그래서 permutation을 여러번 반복하여 variance를 줄일 수 있다.
• base tree로 oblivious tree를 사용한다. 이는 트리의 같은 레벨에서는 동일한 split critertion을 사용하는 트리이다.
  • oblivious tree로 supporting model을 만든다.
  • 매 iteration에서 하나의 random permutation을 사용하고 이를 가지고 트리를 구성한다.
  • 각 exmaple은 각각의 gradient를 갖고 있다.
  • loss는 각 example들의 leaf value와 gradient의 cosine similarity로 계산된다.
  • leaf value는 같은 leaf node에 속해있으면서 이전에 등장했던 example들에 대한 gradient의 평균이다.

oblivious tree는 다음과 같은 tree이다.

 

설명이 복잡한데 예시를 통해 이해해보자.

 

1, 2번 샘플은 이전에 leaf node에 속해있는 샘플이 없기 때문에 gradient와 leaf value를 모두 0으로 초기화 한다.

 

$I_3$은 오른쪽 leaf node에 포함된다. $I_3$의 gradient는 가장 최근에 들어온 $I_2$의 leaf value에서 y값을 뺀 값으로 -1 이다. 

$I_3$의 leaf value는 오른쪽 leaf node에 포함된 샘플들의 gradient의 평균이므로 0이다.

 

동일한 방법으로 순차적으로 $I_{10}$까지 계산하면 다음과 같다.

loss는 다음과 같이 gradient와 leaf value를 벡터로 취급하여 cosine similarity를 계산한다.

 

구성된 모든 트리가 주어지면 최종 모델 F의 leaf value는 표준 그래디언트 부스팅 절차에 의해 계산된다. 이를 계산할 때는 마지막에 1개 남겨놓은 permutation을 사용한다.

test data의 예측을 수행할 때는 모든 train data를 사용하여 TS를 계산한다.