Cat Boost의 이해

참고자료

1. 기존 Gradient Boosting 방법의 문제점

1.1 Prediction Shift

학습 데이터(training data)가 많이 쌓일 수록 실제 test data와 결과가 유사하게 나와야 하는데, 실제 돌려보니 그렇지 못하고 학습 데이터에 대한 조건부 확률(확률 분포)과 테스트 데이터에 대한 조건부 확률(확률 분포)이 다르게 나온다.

1.2 Target Leakage

범주형 변수에서 범주형 값을 수치로 바꿔서 모델링하는데 수치로 바꾸는 과정에서 target value가 포함이 되어버리는 것이다. 즉 학습할 데이터에 정답이 사용이 되어버려 학습 데이터에서는 잘 맞지만 나중 테스트 데이터에서 예측값에 문제가 나오는 것이다. 학습 과정에서 미리 target(정답)이 유출되어 버려 Target Leakage라고 한다.
다음 예를 보자.

범주 A는 A에 대응되는 y값(target값)의 평균인데 위 표에서는 $\frac{1}{2}=0.5$가 된다. 마찬가지로 B는 $\frac{2}{3}=0.67$, C는 $\frac{4}{5}=0.8$ 이다.
(참고로 범주형 데이터에서 값을 수치로 바꾸는데 target의 평균값을 많이 쓴다고 한다.)
범주형 변수의 값을 수치로 바꿀 때 target의 평균을 사용한다는 것 자체가 이미 feature의 값에 target값이 포함이 되었다는 것이다.

2. 기존의 문제점을 해결하기 위한 대안

• Prediction Shift -> Ordered Boosting
• Target Leakage -> Ordered Target Statistics

2.1 Ordered Target Statistics

범주형 변수를 수치로 바꾸는 방법론과 Target Leakage가 나오는 이유, 그리고 Ordered Target Statistics를 설명한다.
one-hot encoding
처음에는 one-hot encoding으로 접근했으나 이렇게 하면 feature의 수가 늘어나는 문제점이 있다.

group categories by target statistics
같은 범주끼리 묶어서 target값의 통계값(평균, 분산 등)을 공통으로 적용한다. 이 방법은 앞에서도 말했듯이 'Target Leakage'가 발생한다.
이 방법에는 smoothing 기법도 같이 적용하는데 다음의 예를 보면

	y=1	y=0	Mean(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의 경우 단 1개만 있는데도 불구하고 값이 1로 할당이 된다. 이렇게 이상치(noise)의 영향을 줄이기 위해서 smoothing이 필요한 것이다.

smoothing 공식인데 $y_i$는 1또는 0의 값이고 a는 hyper parameter로 0보다 큰 값이고 p는 target값 전체의 평균값이다.
smoothing을 적용한 target statistics(TS)의 예는 다음과 같다.

a = 0.1로 정하고 p = 0.7(7/10)이므로,
범주 A는
$\frac{1\,+\,0.1\times0.7}{2\,+\,0.1}=0.5095$
범주 B, C 도 마찬가지 원리로 구한다.

Target Leakage
다음의 예를 보자.

학습(training) 데이터에서 A~F까지 모두 unique한 범주만 있을 때, 각 범주의 변환값은 위 표의 값과 같다.
학습 데이터로 모델링할 때 target값(y값) 1과 0을 구분하는 값은 $\frac{0.5\,+\,ap}{1\,+\,a}$ 이 된다.
다음 테스트 데이터(test data)가 주어질 때 범주의 변환값은 다음과 같이 된다.

앞의 변환 공식에서,

테스트 데이터(Test Set)의 경우는 분모의 $\Sigma$ 부분의 값은 새로운 범주 G~J가 training set에 없기 때문에 0이 된다. 마찬가지로 분모의 $\Sigma$ 부분의 값도 0이 된다. 결국 테스트 데이터의 새로운 범주에 대한 변환값은 모두 $p$만 남게 된다.
테스트 데이터의 범주가 모두 $p$로 같은 것임에 반해 실제 target값(y값)은 G, H는 1이고 I, J는 0이므로 학습 데이터에서와는 달리 테스트 데이터에서는 분류를 할 수 있는 splitting point값을 전혀 찾을 수가 없게된다.
이와 같이 학습 데이터에서 Target Leakage가 발생하면 테스트 데이터에서 제대로된 분류를 할 수 없는 문제가 발생한다.

Ordered Target Statistics
ordered TS는 feature의 data들이 시간 순서와는 상관이 없지만 각 데이터 마다 가상의 시간(artificial time)을 부여하여 부여된 시간 순서대로 범주형 데이터의 값을 설정해 준다.
그리고 학습을 할 때마다 데이터들을 random permutation하여 순서를 섞어주고 섞은 다음에 다시 가상의 시간을 부여하고 범주형 데이터의 값을 설정한다. random permutation하는 이유는 뒤에 설명하겠지만 설정된 값이 시간 순서에 종속적이기 때문에 이를 방지하기 위해 매 학습할 때마다 순서를 다시 섞어준다.
설명을 위해 다음의 예를 보자.

	...	$x^i$	...	TS	y
$I_1$	...	A	...	0.000	1
$I_2$	...	B	...	1.000	1
$I_3$	...	C	...	1.000	1
$I_4$	...	A	...	1.000	0
$I_5$	...	B	...	0.977	1
$I_6$	...	C	...	0.982	1
$I_7$	...	B	...	0.992	0
$I_8$	...	C	...	0.986	1
$I_9$	...	C	...	0.992	0
$I_{10}$	...	C	...	0.748	1

$I_n$은 시간순서를 말하고 TS는 Target Statistics에 의해 정해진 변환된 값이다. $x^i$는 i번째 feature x를 말한다.
a = 0.1로 설정하고 smoothing을 적용한 공식에 대입해서 $I_1$부터 차례로 변환값을 구해보면,
$\widehat{x}_k^i=\frac{\sum_{x_j\in D_k}\textbf{1}_{\{x_j^i=x_k^i\}}\cdot y_j+ap} {\sum_{x_j\in D_k}\textbf{1}_{\{x_j^i=x_k^i\}}+a}$

• $I_1$일 때 :
  $I_1$ 이전의 데이터가 없기 때문에 분자,분모의 합계쪽은 모두 0이고 p도 0이다.
  $\frac{0+0.1\cdot0} {0+0.1}=0$

• $I_2$일 때 :
  $I_2$ 이전에 B 범주가 없다. 분모의 합계부분은 0이고 분자의 y평균값은 0이다. p=1/1=1이다.
  $\frac{0+0.1\cdot1} {0+0.1}=1$

• $I_3$일 때 :
  마찬가지 원리로,
  $\frac{0+0.1\cdot1} {0+0.1}=1$

• $I_4$일 때 :
  $\frac{1+0.1\cdot1} {1+0.1}=1$

• $I_5$일 때 :
  $\frac{1+0.1\cdot 3/4} {1+0.1}=0.977$

• $I_6$일 때 :
  $\frac{1+0.1\cdot 4/5} {1+0.1}=0.982$

• $I_7$일 때 :
  $\frac{2+0.1\cdot 5/6} {2+0.1}=0.992$

• $I_8$일 때 :
  $\frac{2+0.1\cdot 5/7} {2+0.1}=0.986$

• $I_9$일 때 :
  $\frac{3+0.1\cdot 6/8} {3+0.1}=0.992$

• $I_{10}$일 때 :
  $\frac{3+0.1\cdot 6/9} {4+0.1}=0.748$

이렇게 계산된다.
계산하고 보니 같은 범주가 다른 값을 가지는 경우도 있고 다른 범주가 같은 값을 가지는 경우도 생긴다. 그래서 random permutation을 통해서 매번 데이터를 골고루 섞어줘야 한다.

다시 정리하면 Target Leakage를 해결하는 Ordered Target Statistics는 1) 자신의 범주값에 Target의 값을 사용하지 않는다. 2) 가능한 모든 data set를 사용한다는 전제 조건을 만족시켰다.

2.2 Ordered Boosting

개념 설명
Ordered Boosting은 Prediction Shift를 해결하고자 하기 위해서 제안한 방법으로, Prediction Shift는 학습 데이터(training data)의 잔차의 기대값(좀 더 정확히는 잔차의 제곱의 기대값)과 테스트 데이터(test data)의 잔차의 기대값이 다른 것을 말한다. 정상적인 모델이라면 이 둘의 차이가 없어야 한다.(아님 아주 작거나...)
다음 예제를 이용해서 설명하면,

학습한 data set을 random permutation해서 마구잡이로 섞어 준다.

다음에 첫번째 데이터($x_2$)만을 이용해서 분류 모델(의사 결정 트리, decision tree) $M_1$를 만든다. 그리고 두 번째 데이터($x_5$)를 $M_1$ 모델로 예측을 하고 그 잔차를 구한다. 식을 보면 두번째 데이터의 잔차를 구할 때 $y_5$, $x_5$를 이용하는데 이는 첫번째 모델의 학습 데이터로 사용되어지지 않았기 때문에 두 번째 데이터가 첫번째 모델에 전혀 영향을 미치지 못한다.

다음 두 번째 데이터의 잔차($r(x_5, y_5)$)를 통해서 두 번째 데이터가 포함된 모델 $M_2$로 업데이트하고 이 모델을 이용해서 세번째 데이터($x_9$)의 분류값을 예측하고 그 잔차를 구한다. 마찬가지로 잔차를 구할 때 사용된 $y_9$, $x_9$이 모두 $M_2$의 학습에 사용되지 않았기 때문에 세번째 데이터가 모델 $M_2$에 전혀 영향을 미치지 않는다.
이를 같은 방식으로 계속 반복한다.

끝에서 두 번째 데이터도 마찬가지로 직전까지의 데이터를 이용해서 모델 $M_7$을 만들고 이 모델을 이용해서 끝에서 두 번째 데이터 $x_7$의 값을 예측($M_7(x_7)$)하고 잔차를 구한다.

최종적으로 마지막 데이터 하나만 남겨놓고 직전 데이터를 모두 이용해서 모델 $M_8$을 만들고 이 모델로 마지막 데이터 $x_6$의 값을 예측하고 잔차를 구한다.

앞의 ordered TS에서 범주값을 구할 때마다 random permutation을 한다고 했는데 이것과 같은 permutatioin을 ordered boosting에 동일하게 적용한다.

예제를 통한 구체적인 과정 설명
먼저 Ordered Boosting은 oblivious tree를 만든다. 다음 그림과 같다.

그림에서 보면 Asymmetric tree는 무조건 information gain이 가장 큰 것만 기준으로 tree를 확장한다.
그러나 Oblivious tree는 항상 동일한 레벨로 tree를 확장하는 것으로 overfitting을 막을 수 있다고 한다. 그리고 알고리즘상 계산 속도가 더 빠르다고 알려져 있다.

• $\Delta$는 오른쪽 혹은 왼쪽 leaf 노드의 예측값이다.(Gradient의 평균값이다.)
• G(gradient)는 잔차에 음수를 취한 것이라서 '오른쪽 혹은 왼쪽 leaf노드의 예측값(Gradient의 평균값, $\Delta_l\,or\,\Delta_r$) - y이다.

<$I_1$>
1) 첫번째 데이터 $I_1$으로 모델 $M_1$을 만든다. splitting point는 TS < 0.99로 잡는다.(본 예에서는 feature가 $x^i$로 한개라서 tree가 하나만 있다.)
2) $I_1$의 TS는 0.0000이므로 트리의 왼쪽으로 분류된다.
3) $I_1$에서 이전 모델이 없으므로, $\Delta(I_1)$은 0으로 초기화 한다.
4) $I_1$에서 이전 모델이 없으므로, gradient는 0으로 초기화 한다.

<$I_2$>

1) $I_2$의 TS는 1.0000이므로 트리의 오른쪽으로 분류된다.
2) $I_2$에서 이전 모델이 없으므로, $\Delta(I_2)$은 0으로 초기화 한다.
3) $I_2$에서 이전 모델이 없으므로, gradient는 0으로 초기화 한다.

<$I_3$>

1) $I_3$의 TS는 1.0000이므로 트리의 오른쪽으로 분류된다.
2) $\Delta(I_3)$는 오른쪽 leaf 노드의 gradient의 평균값($\Delta_r$)이므로 0/1=0이다.
3) $G(I_3)$=$\Delta_r-y_3=0-1=-1$, 오른쪽 leaf 노드의 $\Delta$값($\Delta_r$)에서 $y_3$를 뺀 값이다.

<$I_4$>

1) $I_4$의 TS는 1.0000이므로 트리의 오른쪽으로 분류된다.
2) $\Delta(I_4)$는 오른쪽 leaf 노드의 gradient의 평균값($\Delta_r$)이므로 0+(-1)/2=-0.5이다.
3) $G(I_4)$=$\Delta_r-y_4=0-0=0$, 오른쪽 leaf 노드의 $\Delta$값($\Delta_r$)에서 $y_4$를 뺀 값이다.

<$I_5$>

1) $I_5$의 TS는 0.977이므로 트리의 왼쪽으로 분류된다.
2) $\Delta(I_5)$는 왼쪽 leaf 노드의 gradient의 평균값($\Delta_l$)이므로 0/1=0이다.
3) $G(I_5)$=$\Delta_l-y_5=0-1=-1$

<$I_6$>

1) $I_6$의 TS는 0.982이므로 트리의 왼쪽으로 분류된다.
2) $\Delta(I_6)$는 왼쪽 leaf 노드의 gradient의 평균값($\Delta_l$)이므로 $\frac{0+(-1)}{2}=-0.5$이다.
3) $G(I_6)$=$\Delta_l-y_6=0-1=-1$

<$I_7$>

1) $I_7$의 TS는 0.992이므로 트리의 오른쪽으로 분류된다.
2) $\Delta(I_7)$는 오른쪽 leaf 노드의 gradient의 평균값($\Delta_r$)이므로 $\frac{0+(-1)+(0)}{3}=-0.33$이다.
3) $G(I_7)$=$\Delta_r-y_7=-0.5-0=-0.5$

<$I_8$>

1) $I_8$의 TS는 0.986이므로 트리의 왼쪽으로 분류된다.
2) $\Delta(I_8)$는 왼쪽 leaf 노드의 gradient의 평균값($\Delta_l$)이므로 $\frac{0+(-1)+(-1)}{3}=-0.67$이다.
3) $G(I_8)$=$\Delta_l-y_8=-0.5-1=-1.5$

<$I_9$>

1) $I_9$의 TS는 0.992이므로 트리의 오른쪽으로 분류된다.
2) $\Delta(I_9)$는 오른쪽 leaf 노드의 gradient의 평균값($\Delta_r$)이므로 $\frac{0+(-1)+(0)+(-0.5)}{4}=-0.38$이다.
3) $G(I_9)$=$\Delta_r-y_9=-0.33-0=-0.33$

<$I_{10}$>

1) $I_{10}$의 TS는 0.748이므로 트리의 왼쪽으로 분류된다.
2) $\Delta(I_{10})$는 왼쪽 leaf 노드의 gradient의 평균값($\Delta_l$)이므로 $\frac{0+(-1)+(-1)+(-1.5)}{4}=-0.88$이다. (그림과는 다른데, youtube 동영상의 설명이 잘못된 듯 하다.)
3) $G(I_{10})$=$\Delta_l-y_{10}=-0.67-1=-1.67$

2.3 Calculate loss function

앞에서 ordered boosting을 통해 모든 데이터의 gradient와 delta값을 모두 구했으면 이들을 각각 vector로 보고 이 두 vector의 cosine값이 loss function이 된다.
표에서 $\Delta$의 vector는 [0, 0, 0, -0.5, 0, -0.5, -0.33, -0.67, -0.38, -0.88]이고 G의 vector는 [0, 0, -1, 0, -1, -1, -0.5, -1.5, -0.33, -1.67]이다.
앞의 예에서는 splitting point를 TS < 0.99로 잡았는데 splitting point를 다양하게 바꾸어 가면서 loss function의 값이 가장 작은 모델을 찾는다.
그림에서는 $cos(\Delta,G)$ 가0.3575라고 나와있는데 $\Delta$의 마지막을 -0.58로 해도 0.3575가 어떻게 나왔는지 모르겠다.(실제로 해 보면 0.7689정도 나온다)