참고자료

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

1.1 Prediction Shift


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

1.2 Target Leakage

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

범주 A는 A에 대응되는 y값(target값)의 평균인데 위 표에서는 12=0.5\frac{1}{2}=0.5가 된다. 마찬가지로 B는 23=0.67\frac{2}{3}=0.67, C는 45=0.8\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=1y=0Mean(TS)
A10100.5
B40100.8
C10400.2
D25250.5
E101

범주 E의 경우 단 1개만 있는데도 불구하고 값이 1로 할당이 된다. 이렇게 이상치(noise)의 영향을 줄이기 위해서 smoothing이 필요한 것이다.

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

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

Target Leakage
다음의 예를 보자.

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

앞의 변환 공식에서,

테스트 데이터(Test Set)의 경우는 분모의 Σ\Sigma 부분의 값은 새로운 범주 G~J가 training set에 없기 때문에 0이 된다. 마찬가지로 분모의 Σ\Sigma 부분의 값도 0이 된다. 결국 테스트 데이터의 새로운 범주에 대한 변환값은 모두 pp만 남게 된다.
테스트 데이터의 범주가 모두 pp로 같은 것임에 반해 실제 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하는 이유는 뒤에 설명하겠지만 설정된 값이 시간 순서에 종속적이기 때문에 이를 방지하기 위해 매 학습할 때마다 순서를 다시 섞어준다.
설명을 위해 다음의 예를 보자.

...xix^i...TSy
I1I_1...A...0.0001
I2I_2...B...1.0001
I3I_3...C...1.0001
I4I_4...A...1.0000
I5I_5...B...0.9771
I6I_6...C...0.9821
I7I_7...B...0.9920
I8I_8...C...0.9861
I9I_9...C...0.9920
I10I_{10}...C...0.7481

InI_n은 시간순서를 말하고 TS는 Target Statistics에 의해 정해진 변환된 값이다. xix^i는 i번째 feature x를 말한다.
a = 0.1로 설정하고 smoothing을 적용한 공식에 대입해서 I1I_1부터 차례로 변환값을 구해보면,
x^ki=xjDk1{xji=xki}yj+apxjDk1{xji=xki}+a\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}

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

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

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

  • I4I_4일 때 :
    1+0.111+0.1=1\frac{1+0.1\cdot1} {1+0.1}=1

  • I5I_5일 때 :
    1+0.13/41+0.1=0.977\frac{1+0.1\cdot 3/4} {1+0.1}=0.977

  • I6I_6일 때 :
    1+0.14/51+0.1=0.982\frac{1+0.1\cdot 4/5} {1+0.1}=0.982

  • I7I_7일 때 :
    2+0.15/62+0.1=0.992\frac{2+0.1\cdot 5/6} {2+0.1}=0.992

  • I8I_8일 때 :
    2+0.15/72+0.1=0.986\frac{2+0.1\cdot 5/7} {2+0.1}=0.986

  • I9I_9일 때 :
    3+0.16/83+0.1=0.992\frac{3+0.1\cdot 6/8} {3+0.1}=0.992

  • I10I_{10}일 때 :
    3+0.16/94+0.1=0.748\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해서 마구잡이로 섞어 준다.

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

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

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

최종적으로 마지막 데이터 하나만 남겨놓고 직전 데이터를 모두 이용해서 모델 M8M_8을 만들고 이 모델로 마지막 데이터 x6x_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의 평균값, ΔlorΔr\Delta_l\,or\,\Delta_r) - y이다.

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

<I2I_2>

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

<I3I_3>

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

<I4I_4>

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

<I5I_5>

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

<I6I_6>

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

<I7I_7>

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

<I8I_8>

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

<I9I_9>

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

<I10I_{10}>

1) I10I_{10}의 TS는 0.748이므로 트리의 왼쪽으로 분류된다.
2) Δ(I10)\Delta(I_{10})는 왼쪽 leaf 노드의 gradient의 평균값(Δl\Delta_l)이므로 0+(1)+(1)+(1.5)4=0.88\frac{0+(-1)+(-1)+(-1.5)}{4}=-0.88이다. (그림과는 다른데, youtube 동영상의 설명이 잘못된 듯 하다.)
3) G(I10)G(I_{10})=Δly10=0.671=1.67\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(Δ,G)cos(\Delta,G) 가0.3575라고 나와있는데 Δ\Delta의 마지막을 -0.58로 해도 0.3575가 어떻게 나왔는지 모르겠다.(실제로 해 보면 0.7689정도 나온다)

profile
바쁘게 부지런하게 논리적으로 살자!!!

0개의 댓글