CatBoost란? unbiased boosting with categorical features - 2

1편 https://data-newbie.tistory.com/manage/newpost/131?type=post&returnURL=https%3A%2F%2Fdata-newbie.tistory.com%2Fmanage%2Fposts 

TISTORY

2편입니다.

 

 

4 Prediction shift and ordered boosting

4.1 Prediction shift

왜 Gradient Boosting에 Prediction Shift가 발생하는지 설명하는 장입니다.

Prediction shift는 특별한 종류의 target leakage에 의해서 발생합니다.

Our solution is called ordered boosting and resembles the ordered TS method.

1. 보지 않은 데이터를 넣게 되면 gradient의 조건부 분포는 이동하게 될 것입니다. 

2. 결국 그렇게 됨으로써 편향이 발생하게 되고

3. 결국에는 일반화하는 능력에 영향을 주게 됩니다.

이렇게 되는 것은 target leakage에 의해서 발생합니다. 

결국 조건부 분포가 train data와는 다른 test data가 들어올 때 조건부 분포가 달라지고 이때 predciton shift가 발생한다고 합니다.

 

뒤에 여러 가지 증명이 나와서 결국 prediction shift가 발생하는 것에 대한 이야기가 나오지만... 저는 무식하므로 패스...

 

4.2 Ordered boosting

데이터가 무한하다고 했을 때 독립성을 만족하는 데이터가 들어오고  이것을 샘플링해서 각 스탭에 넣어서 새로운 train에 적용함으로써 unshifted residual를 얻을 수 있게 된다는데요.

그러나 실제로는 데이터 양은 정해져있지요...

반복 반복

1. 밑에 예제를 들어서 보면은 t-1까지는 permutated observation을 이용해 t-1번째 모형을 학습합니다.

2. 그다음 t번째 데이터를 t-1번째 모형으로 예측하고 t번째 실제 y와 비교해 r_t(x_7, y_7)을 residual을 구합니다

3. 그리고 t번째 residual 값으로 gradient를 업데이트합니다.

하지만 이것을 메모리에 넣어야 하는데 그렇게 하기는 현실적으로 안되는데,

Catboost에서는 Gradient Bossting 알고리즘을 기반으로 한 방법으로 수정했다고 합니다. 

트리를 만들 때는 Oblivious 기반으로 한 decision table을 만들었다고 합니다. 이것은 같은 cutoff 기준으로 나눴다고 합니다. 

그래서 이러한 방법을 통해서 균현이 잡히고 Overfitting도 막아준다고 꽤 막아준다고 합니다.

root에서 leaf까지 이진 분류를 통해 해 주기 때문에 메모리 저장할 필요 없다. 

Feature combinations

만약 두 상관계수 유저랑 클릭한 곳이랑 같이 상관관계가 있다면? 이러한 것을 그냥 쓰게 되면 중요한 Feature를 잃을 수 있습니다. 그래서 단순히 이 두 개를 수치화하는 것보다 잘 결합해 새로운 파생변수를 만드는 게 중요한데, 그것이 catboost는 가능하다고 합니다! 

그러나 너무 많으면 데이터의 크기는 기하급수적으로 커지게 됩니다. 

그래서 이 방식을 해결하기 위해 Greedy 한 방식으로 학습합니다. 

root node에는 결합하지 않고 그다음에서 결합하여 수치화하는 과정을 반복해서 Feature Combination을 할 수 있게 됩니다.

 

 

결론은 이처럼 tree model에서 Categorcial 데이터를 더 잘 처리할 수 있는 알고리즘이 Catboost인 것 같습니다.

target leakage와 Prediction shift라는 발생을 ordered boostring(Ordered Principle)를 통해 해결합니다.

 

좀 더 잘 이해하고 싶지만, 너무 어려운 것ㅠㅠ