Resampling Method & Cross-Validation

Resampling method란 training set으로 부터 반복적으로 샘플을 얻거 내고

각 샘플에 대해서 모델을 여러번 적합시켜 추가적인 정보를 얻는 방법을 뜻합니다.

이번 장에서는 가장 대표적인 resampling method인

cross-validation과 bootstrap을 다룹니다.

Cross-validation은 주로 the test error의 추정에 사용되어

모델의 적절한 flexibility를 결정하는 데에 쓰입니다.

Bootstrap은 주로 parameter estimate나 주어진 statistical learning method의 정확도를

측정하기 위해 사용합니다.

< Cross-Validation >

2장에서 the training error와 the test error의 차이점을 다루었습니다.

궁극적인 목표는 the test error를 줄이는 것이지만

일반적인 상황에서 test set을 얻을 수 없기 때문에
the test error를 측정하는 것에 어려움이 있습니다.

이러한 문제점을 극복하기 위해서 사용하는 방법이

구하기 쉬운 training set을 이용하여 the test error를 추정하는 것입니다.

The training error에 수학적인 변형을 가해

the test error를 추정하는 방법도 있지만 이러한 방법은 6장에서 다룹니다.

대신 이번에는 training observations의 일부 부분집합을 이용하여 모델을 적합시키는 방법을 다루도록 하겠습니다.

Cross-Validation은 observations을 a training set과 a validation set (hold-out set)으로 나눈 뒤

a training set을 이용하여 모델을 적합시킨 다음 a validation set을 이용하여 모델을 평가하는 방식입니다.

Cross-Validation은 간단하며 쉽게 구현할 수 있다는 장점이 있지만

아래와 같은 두 가지 단점이 있습니다.

1. Validation set을 이용하여 추정한 the test error rate는 highly variable하다.

2. Training set의 일부만 모델 적합에 사용되는 것이기 때문에

적합에 사용되는 observations의 개수가 적어진다.

따라서 더 적은 observations를 사용하므로, the validation set error rate는 

전체 data set에 적합한 모델에 대한 the test error rate를 overestimate할 수도 있다.

< LOOCV (Leave-one_out Cross-validation) >

이러한 단점을 극복하기 위해서 사용하는 것이 Leave-one-out Cross-validation (LOOCV)입니다.

LOOCV는 training set과 validation set을 비슷한 크기로 나누지 않고

오직 1개의 observation만 validation set으로 사용합니다.

그러면 n개의 observations가 있는 경우

validation set은 총 n개 만들어질 수 있으므로 test MSE에 대한 추정은 다음과 같습니다.

이때 입니다.

LOOCV는 일반적인 Cross-Validation과 달리 

bias가 낮으며 여러번 반복하여도 거의 동일한 MSE를 제공합니다.

그러나 식을 통해 알 수 있듯이 n이 매우 큰 경우 계산에 많은 시간이 소요됩니다.

이러한 경우를 해결하기 위해 아래와 같이 매우 간단한 방법으로 CV를 구할 수 있습니다.

이때 는 일반적인 least squares fit을 적용하여 구한 값이고

는 leverage입니다.

식을 통해 알 수 있듯이,

번째 residual을 로 나눠준 것을 제외하고는 일반적인 MSE와 동일합니다.

< k-Fold Cross-Validation >

LOOCV 대신 사용할 수 있는 방법으로는 k-fold CV가 있습니다.

이 방법은 observation set를 임의로 동일한 크기의 k 개의 그룹 (= folds)로 나눕니다.

이후 첫번째 fold를 validation set으로 사용하고 나머지 k - 1개의 folds를 이용하여 적합시킵니다.

이후 적합시킨 모델에 첫번째 fold인 validation set을 이용하여 을 구합니다.

이러한 과정을 각각의 fold를 validation set으로 사용하여 k번 반복한 후

LOOCV와 마찬가지로 평균을 구하여 test MSE를 추정합니다.

LOOCV는 적합을 n번 해야하기 때문에 CV 계산에 많은 시간이 소모됩니다.

이와 달리 k-Fold CV는 적합을 k번시키기 때문에 계산에 적은 시간이 소모됩니다.

또한 k-Fold CV에 주로 쓰이는 k값에는 5와 10이 있습니다.

이러한 Cross-Validaton을 사용하여 얻고자 하는 궁극적인 목표는

test MSE가 최소인 모델을 찾는 것입니다.

위에서 언급했듯이 대부분의 상황에서 test MSE를 구하는 것은 불가능하므로

대신 CV를 통해 추정한 test MSE가 최소인 모델을 선택(model selection)합니다.

< Bias-Variance Trade-Off for k-Fold Cross-Validation >

위에서 언급한 k-fold CV의 계산적 장점(computational advantage)를 차치하고

k-fold CV의 더욱 중요한 장점은 LOOCV보다 the test error rate에 대한 더욱 정확한 추정을 할 수 있다는 것입니다.

이번에는 Bias의 관점에서 LOOCV와 k-fold CV를 비교해보록 하겠습니다.

LOOCV는 n-1개의 데이터를 training set으로 사용하기 때문에

(k-1)n/k 개의 데이터를 사용하는 k-fold CV보다 더 작은 bias를 같습니다. (k < n인 경우)

따라서 bias의 관점에서는 k-fold CV보다 LOOCV가 더 좋은 방법입니다.

하지만, 추정을 할 때는 bias뿐만 아니라 variance도 고려해주어야 합니다.

Variance의 경우, 1개의 observation만 validation set으로 사용하는 LOOCV는

k-fold CV보다 더 큰 varaince를 가지므로 k-fold CV가 LOOCV보다 더 좋은 방법입니다.

결론적으로, k-fold CV에서 k의 선택과 관련된 bias-variance trade off로 인해서

일반적으로 k =5 혹은 k = 10을 이용하여 k-fold CV를 적용합니다.

그 이후는 k = 5 또는 k = 10의 경우

과도하게 큰 bias 혹은 과도하게 큰 variance를 갖는 경우를 방지할 수 있기 때문입니다.

< Cross-Validation on Classification Problems >

지금까지 Y가 quantitatve한 regression에서의 CV을 다루었으므로 MSE가 test error의 척도였습니다.

하지만 CV은 Y가 qualitative한 classification에서도 쓰일 수 있으므로 이에 대해서 정리하도록 하겠습니다.

Classification에서 LOOCV error rate는 아래와 같습니다.

이때 입니다.

위의 그림에서 하늘색 선은 training error, 검은색 선은 10-fold CV error, 그리고 갈색 선은 test error입니다.

왼쪽 그림은 logistic regression의 order of polynomials used에 따른 Error rate를 나타낸 것이고

오른쪽 그림은 KNN에서 사용된 K값의 역수에 따른 Error rate를 나타낸 것입니다.

그림을 통해 할 수 있듯이 10-fold CV error가 최소인 지점과 test error가 최소인 지점은 거의 비슷한 것을 알 수 있습니다.

따라서 k-fold CV error를 이용하여 test error를 추정하는 것은 좋은 성능을 보입니다.