catboost

xgboost 로 gbm 의 시대가 왔지만(정규화와 분산성?)
lightgbm 이 leaf wise gbm 으로 속도와 정확성 두마리 토끼를 잡았다고 생각했는데
boosting 모델의 parameter tuning 은 항상 문제였다
overfitting 이 되기 쉬워 조정을 잘 했어야하는데
오늘 catboost 에 대한 글을 읽으면서 논문을 대충 훑어봤는데 무릎이 탁 쳐진다.

기본설정이 좋아서 파라미터 튜닝이 별반 차이 없다고 하는데
그 이유를 알 것 같았다.
https://arxiv.org/abs/1706.09516
Fighting biases with dynamic boosting

catboost 의 구현 알고리즘이다.

all current implementations are susceptible to a non-trivial but damaging form of label leakage.
부스팅 알고리즘들은 누출의 손상된 형태를 가지고 있다.

Gradients used at each step are estimated using the same data points that produced the model built so far. This causes an undesirable dependency between the data used for the gradient estimation and the model approximation.
그라디언트 부스팅 방법은 같은 데이터를 사용해 매 잔차를 계산하고
이것은 잔차와 모델 근사 사이의 의존성을 야기한다 .

그래서 보지않은 데이터(unseen data [test data]) 때 발생할 수 있는 잔차보다 더 작은 잔차를 갖는 경향이 있다

Formal analysis of the gradient bias problem allows us to propose a dynamic boosting approach that avoids the estimation bias at a minimal cost of the variance of the gradient estimation
잔차 추정의 분산을 최소로 하면서 바이어스를 피하는  다이나믹 부스팅 방법을 제시한다.

다이나믹 부스팅 방법이란
sample unbiased residual 을 추정하기 위해
loocv(leave one out cross validation) 로 매 부스팅 모델마다 학습해서
unbiased residual 을 추정하고 그걸로 학습하는 것이다

논문의 핵심은 단순히 관찰치가 포함된 채로 계속 부스팅을 하지 말고
그 관찰치를 뺀채로 학습해서 그 관찰치에 대한 불편 잔차를 구하고 학습하자는 것인데
이것은 I개의 모델이 있다면 I 개의 모델을 관찰치 갯수 n 번 학습해야하는 문제가 있다

이 논문은 그 문제를 해결하는 방법을 제시한다.
M개의 모델만을 가지고
mi를 학습할때는 첫 i 개 관찰치만를 사용해서 학습을 한다
그다음엔 j 번째 관찰치에 대해선 mj-1 로 잔차를 얻어서 학습한다.

이러면 복잡도가 2차가 되고 ordered dynamic boosting 이라고 말한단다
근데 만약 매 모델마다 기본 학습자가 하나라면 편향 잔차를 피할 수 없기 때문에
기본학습자로 gbm 을 쓴다.

이를 내 멋대로 이해해보자면
gbm로 oob를 이용해 meta feature(prediction for unseen data) 를 구하고 그것으로 다시 학습

바이어스 잔차가 일으키는 과적합을 해결하기 위해 굉장히 복잡도가 높은 모델을 사용해야하는데
이 복잡도를 해결한 논문이라고 본다.

기술적인 구현은 살펴봐야겠지만 아이디어가 무척 좋네

제대로 잘 이해못했을 수도 있고
아예 잘못 이해했을 수도 있다.