Machine Learning : 모델 선택 방법. 1. Cross validation

ML를 적용할때 여러가지 알고리즘이 있는데 어떤 것을 선택할 것인가?
예를 들어, polynomial regression model을

로 한다면,  k 는 어떤 값으로 하는 것이 좋을 것인가? bias 와 variance 사이의 tradeoff 가 고려 되면서 말이다.
다른 예로써, locally weighted regression 을 위한 bandwidth parameter t (타오) 나 l_1 regularized SVM 을 위한 파라메터 C 를 자동으로 결정하기를 원한다고 생각해보자.

후보가 되는 모델 셋을 M = {M_1 , ... , M_d}  로 정의하자. 첫번째 예를 적용하면 M_i 는 i-order polynomial regression model 일 것이다.

Cross validation 방법

training set을 S 라고 하자.
* 단순 empirical risk minimization 알고리즘:
1. 모델 M_i 를 S로 학습시켜, hypothesis h_i 를 구한다.
2. training error를 최소로 하는 모델을 선택한다.
그런데 이 알고리즘은 좋지 않다. 왜냐하면, 이 방식을 통해서는 S에 가장 fit 하는 모델이 선택되기 때문에, 항상 high-variance, high-degree polynomial model 이 선정될것이고, 이는 종종 안좋은 선택이 된다.

* hold-out cross validation (simple cross validation) :
1. S를 랜덤하게 S_train 과 S_cv 로 나눈다. S_train은 약 70%로 구성하여, 모델 학습용으로 쓰고 나머지 S_cv 는 평가용으로 쓴다.
2. 각 모델 M_i 을 S_train 으로 학습시켜, hypothesis h_i 를 구한다.
3. S_cv(h_i) 를 적용하였을때 error (generation error)를 최소로 하는 모델을 선택한다.
옵션으로, 모델을 선택후 그 모델에 S_cv도 추가로 학습시킨다.
이 방식의 단점은 빼놓은 30%의 데이터를 학습 ~ 평가에 반영하지 않는 다는 것이다. 그리고 0.7 (70%) 가 보편적이긴 한데, 데이터에 따라 부적절할 수 있다.

* k-fold cross validation :
1. S를 k개의 부분집합으로 나눈다.
2. 각 모델 M_i 에 대해 j 번째 ( j = 1,...,k) 집합 S_j 를 제외시키고 학습시켜 h_ij 를 구하고, S_j를 적용하여 generation error 들을 구한다. 모델 M_i 의 에러는 각 j번째의 에러들의 평균으로 한다.
3. 가장 작은 에러를 갖는 모델을 선택한다. 그리고 전체 데이터 S로 학습시킨다.
이 방식의 문제점은, 전형적인 k값은 10이지만, 항상 적절하지는 않고, k값에 따라 계산량이 많아진다는 것이다.

* leave-one-out cross validation :
앞의 k를 매우 크게 하여 데이터 사이즈인 m과 같게 하는 방법이다. 결국 데이터 1개씩을 빼가면서 모든 테스트를 하는 방법이다.

이러한 cross validation 방법은 모델 선택하는 데도 사용할 수 있지만, 자기 알고리즘을 평가하는데에도 사용할 수 있다.


(참고: 스탠포드 Andrew Ng 강의노트)