교차 검증과 일반화(Cross-validation and generalization)

점이 20개뿐인 자료에 다항식⁠(polynomial)⁠을 맞추려 합니다. 차수를 몇으로 할까요? 학습 오차는 차수를 올릴수록 줄어들 뿐 늘지 않으니 잣대가 되지 못합니다(과적합⁠(overfitting)⁠). 몇 개를 떼어 두고 나머지로 맞춘 뒤 떼어 둔 점에서 오차를 재면 되지만, 20개에서 5개를 떼면 맞출 자료가 줄고, 어느 5개를 떼느냐에 따라 값이 크게 흔들립니다. k겹 교차 검증⁠(k-fold cross-validation)⁠은 자료를 k조각으로 나누고 조각마다 한 번씩 시험 자료가 되게 합니다. 한 조각을 빼고 나머지로 맞춘 뒤, 뺀 조각에서 오차를 잽니다. 이것을 k번 되풀이해 모든 점의 오차를 평균합니다.

$$\mathrm{CV}_k = \frac{1}{n}\sum_{i=1}^{n}\Bigl(y_i - \hat f^{(-\kappa(i))}(x_i)\Bigr)^2$$

여기서 $\kappa(i)$는 점 i가 속한 조각이고, $\hat f^{(-\kappa)}$는 그 조각을 빼고 맞춘 모형입니다. 조각 수 k = , 차수 d = 로 정하고 한 조각씩 넘겨 보세요. 새 자료

이 차수의 교차 검증⁠(cross-validation)⁠ 오차는 입니다. 이 자료는 $y = \sin 3x$(흐린 점선)에 표준편차⁠(standard deviation)⁠ 0.3의 잡음을 더해 만든 것이라, 모든 점으로 맞춘 곡선이 새 자료(x는 [−1, 1]에서 고르게, 잡음은 새로)에서 낼 오차의 기댓값⁠(expected value)⁠을 계산할 수 있습니다. 그 값은 이고, 같은 곡선의 학습 오차는 입니다. 교차 검증 오차가 가장 작은 차수는 d = 입니다. 실제 문제에서는 참 함수⁠(function)⁠를 모르니 둘째 그림의 청록 점선은 볼 수 없고, 노란 곡선만 보고 골라야 합니다.

학습 오차가 얼마나 낙관적인지는 정확히 계산할 수 있습니다. x 자리를 고정하고, 모형이 참 함수를 담을 수 있으며, 계수가 p개인 최소제곱⁠(least squares)⁠이라면

$$\mathbb E[\text{학습 오차}] = \sigma^2\Bigl(1 - \frac{p}{n}\Bigr), \qquad \mathbb E[\text{같은 x에서 새로 잰 y의 오차}] = \sigma^2\Bigl(1 + \frac{p}{n}\Bigr)$$

입니다. n = 20, p = 4(삼차식)이면 학습 오차는 평균 $0.8\sigma^2$인데 새 자료의 오차는 $1.2\sigma^2$입니다. 잔차⁠(residual)⁠ 벡터⁠(vector)⁠는 잡음을 계수 p개로 설명할 수 없는 방향에 내린 정사영⁠(orthogonal projection)⁠이라 그 제곱 길이의 기댓값이 $\sigma^2(n-p)$이기 때문입니다(편향–분산 분해⁠, bias–variance decomposition⁠). 둘의 차이 $2p\sigma^2/n$를 학습 오차에 더해 주는 것이 맬로스의 $C_p$와 아카이케 정보 기준(AIC, 1973)의 생각입니다. 교차 검증은 이런 공식을 쓸 수 없는 복잡한 모형에서도 같은 일을 자료로 해냅니다.

k = n이면 점을 하나씩 빼는 셈이라 하나 빼기 교차 검증⁠(leave-one-out cross-validation)⁠이라 부릅니다. 최소제곱에서는 n번 다시 맞출 필요가 없습니다. 모든 점으로 한 번 맞춘 잔차 $y_i - \hat y_i$와, 점 i가 자기 예측값에 주는 영향 $h_{ii}$만 있으면 됩니다. 맞춘 값은 $\hat{\vec y} = H\vec y$처럼 행렬⁠(matrix)⁠ H(y에 모자를 씌운다고 모자 행렬⁠(hat matrix)⁠)를 곱해 얻는데, 그 대각 성분 $h_{ii}$를 지렛대 값⁠(leverage)⁠이라 부릅니다. 이 둘만으로 하나 빼기 교차 검증 오차가 정확히 나옵니다.

$$\mathrm{CV}_n = \frac{1}{n}\sum_{i=1}^{n}\left(\frac{y_i - \hat y_i}{1 - h_{ii}}\right)^2$$

이 공식으로 계산한 지금 차수의 값은 인데, k = 20으로 두고 한 점씩 빼 가며 계산한 값과 같습니다. 점 i를 빼고 다시 맞추면 그 점에서의 잔차가 정확히 $1/(1 - h_{ii})$배로 커지기 때문입니다. 그래서 지렛대 값이 큰 점(대개 양 끝의 외딴 점)일수록 잔차가 크게 부풀려집니다.

교차 검증이 어림하는 것은 '지금 모형'의 오차가 아니라 '이 방법으로 자료 $n(k-1)/k$개를 맞추면 나올 모형'의 평균 오차입니다. k가 작으면 맞출 자료가 적어 오차를 부풀립니다. k = 2에서 d = 9를 보세요. 점 10개에 계수 10개짜리 다항식을 맞추면 점을 모두 지나가므로 떼어 둔 점에서 크게 빗나갑니다. k = n이면 이 치우침은 거의 없지만, n번의 맞춤이 거의 같은 자료를 쓰니 오차들이 서로 강하게 얽혀 추정값이 크게 흔들릴 수 있습니다. 그래서 k = 5나 10이 경험적인 절충으로 널리 쓰입니다. 그림의 표준오차 막대도 어림일 뿐입니다. 조각들이 자료를 나눠 쓰므로 서로 독립⁠(independence)⁠이 아니고, 2004년 벤지오와 그랑발레는 k겹 교차 검증 추정값의 분산⁠(variance)⁠을 편향 없이 추정하는 방법은 일반적으로 없다는 것을 보였습니다. 흔한 선택 규칙 하나는 오차가 가장 작은 모형의 1 표준오차 안에 드는 모형 가운데 가장 단순한 것을 고르는 것입니다.

가장 흔한 잘못은 자료 누설입니다. 자료를 보고 내리는 결정은 모두, 곧 특성 고르기, λ나 차수 정하기, 심지어 평균과 분산으로 크기를 맞추는 일까지, 조각마다 학습용 부분만으로 다시 해야 합니다. 2002년 앙브루아즈와 매클라클런은 유전자 발현 자료에서 전체 자료로 유전자를 먼저 고른 뒤 교차 검증하면 오류율이 실제보다 크게 낮게 나온다는 것(선택 편향⁠, selection bias⁠)을 보였습니다. 같은 환자의 측정이 학습 조각과 시험 조각에 나뉘어 들어가거나, 시계열에서 미래의 자료로 맞춘 모형으로 과거를 예측하는 것도 누설입니다. 모형을 고르는 데 교차 검증을 썼다면 그 값은 고른 모형의 성능으로는 낙관적이므로, 최종 성능은 한 번도 보지 않은 시험 자료나 바깥에 교차 검증을 한 겹 더 두는 중첩 교차 검증⁠(nested cross-validation)⁠으로 잽니다.

시험 자료로 잰 오류율은 얼마나 믿을 만할까요? 시험 자료를 보기 전에 정해 둔 분류기 하나가 있고, 시험 예 m개가 서로 독립으로 뽑혔다면 호에프딩 부등식⁠(Hoeffding's inequality)⁠에 따라 잰 오류율이 참 오류율과 ε보다 더 차이 날 확률⁠(probability)⁠은 $2e^{-2m\varepsilon^2}$ 이하입니다. m = 1000, ε = 0.05이면 약 1.35% 이하입니다. 큰 수의 법칙⁠(law of large numbers)⁠을 유한한 m에서 정량으로 만든 것입니다. 그러나 같은 시험 자료로 모형 M개를 비교해 가장 좋은 것을 고르면, 고른 모형에 대해 보장할 수 있는 것은 이 상한⁠(upper bound)⁠에 M을 곱한 값뿐입니다. 그러니 시험 자료를 여러 번 들여다볼수록 보장이 약해집니다. 모형이 무한히 많은 경우에도 쓸 수 있게 이 논리를 넓힌 것이 바프니크와 체르보넨키스의 이론입니다. 교차 검증이라는 생각은 1968년 모스텔러와 튜키의 글에 소개되었고, 1974년과 1975년에 머빈 스톤과 시모어 가이서가 체계적으로 정리했습니다.

이어지는 곳. 정규화의 λ와 서포트 벡터 머신⁠(support vector machine)⁠의 C처럼 학습이 스스로 정하지 못하는 손잡이(초매개변수⁠, hyperparameter⁠)는 대개 교차 검증으로 고릅니다. 서포트 벡터 머신에는 하나 빼기 오류율이 서포트 벡터⁠(support vector)⁠의 비율을 넘지 않는다는 깔끔한 한계도 있습니다. 랜덤 포레스트⁠(random forest)⁠는 나무마다 뽑히지 않은 자료로 오차를 재는 방법(OOB 오차⁠, out-of-bag error⁠)으로 교차 검증을 거의 공짜로 얻습니다. 교차 검증이 재는 오차는 편향–분산 분해의 세 조각을 합한 것이고, 그 어림 자체도 분산을 가진 확률 변수라는 점을 잊지 않아야 합니다.