일반화 오차

기계학습 및 통계적 학습이론의 지도학습 응용에서 일반화 오차(一般化誤差, generalization error) 또는 표본 외 오차(標本外誤差, out-of-sample)는 알고리즘이 전례가 없는 데이터에 대한 결과값을 얼마나 정확하게 예측할 수 있는지의 정도이다. 학습 알고리즘은 유한표본에서 평가되기 때문에, 학습 알고리즘 평가는 표본오차에 민감할 수 있다. 결과적으로, 현재 데이터에 관한 예측오차의 측정값은, 새로운 데이터를 예측하는 데 있어서 많은 정보를 제공하지 않을 수 있다. 일반화 오차는 학습 알고리즘의 과적합을 피함으로써 최소화될 수 있다. 기계학습 알고리즘의 성능은 학습과정을 통한 일반화 오차값의 플롯, 학습곡선으로 측정된다.

정의

학습문제에서의 목표는, 입력 데이터 $x$를 기반으로 출력값 $y$를 예측하는 함수 $f(x)$를 개발하는 것입니다. $x$와 $y$의 모든 값에서 함수 $f_{n}$의 예상 오차 $I[f_{n}]$는 다음과 같다.

$I[f_{n}]=\int _{X\times Y}V(f_{n}(x),y)\rho (x,y)dxdy,$

이 때 $V$는 손실함수를 나타내고, $\rho (x,y)$는 $x$와 $y$의 미지의 결합확률분포이다.

결합확률분포를 알 수 없으면 $I[f]$의 계산은 불가능하지만, 대신에 표본 데이터에 대한 경험적 오차를 계산할 수 있다. 기준점 $n$가 주어졌을 때의 경험적 오차는 다음과 같다.

$I_{S}[f_{n}]={\frac {1}{n}}\sum _{i=1}^{n}V(f_{n}(x_{i}),y_{i})$

일반화 오차는 예상오차와 경험오차와의 차이이다. 이는 훈련 집합(training dataset)의 오차와 결합확률분포의 오차 사이의 차이이며, 다음과 같이 정의된다.

$G=I[f_{n}]-I_{S}[f_{n}]$

알고리즘은 다음과 같은 경우에 「일반화」되었다고 한다.

$\lim _{n\rightarrow \infty }I[f_{n}]-I_{S}[f_{n}]=0$

$I[f_{n}]$는 미지의 결합확률분포로 계산될 수 없기 때문에 일반화 오차는 도출될 수 없다. 대신에, 통계적 학습이론에서 제문제의 목적은 일반화 오차를 확률의 범위로 제한하거나 특성화하는 것이다.

$P_{G}=P(I[f_{n}]-I_{S}[f_{n}]\leq \epsilon )\geq 1-\delta _{n}$

즉, 일반화 오차가 어떠한 오차범위 $\epsilon$보다 작은 확률 $1-\delta _{n}$의 특성을 부여하는 것이 목적이다. 이는 학습률로 알려져 있으며, 일반적으로 $\delta$와 $n$에 의존한다.

안정성과의 관계

여러 유형의 알고리즘에 대하여, 알고리즘이 일정한 안정성 기준을 충족하면 일반화 한계를 갖는 것으로 나타났다. 특히, 알고리즘이 대칭이고(입력 순서가 결과에 영향을 미치지 않음), 손실이 한정되어 있고, 두 가지 안정성 조건을 충족하면 알고리즘은 일반화된다. 첫 번째 안정성 조건인 LOOCV(Leave-one-out cross-validation) 안정성은, 알고리즘이 안정적이기 위해서는 LOOCV를 사용할 때에 각 데이터 포인트에 대한 예측오차가 $n\rightarrow \infty$일 때 0에 수렴해야 한다고 한다. 두 번째 조건인 예측된 LOO 오차 안정성(expected-to-leave-one-out error stability; $L_{1}$ 노름에서 작동하는 경우의 가설 안정성)은 훈련 집합에서 단일 데이터 지점을 제거해도 남은 데이터에 대한 예측에 변함이 없을 때 충족된다.

이러한 조건들은 다음과 같이 공식화될 수 있다.

LOOCV 안정성

알고리즘 $L$은 각 $n$에 대하여, 이하와 같은 $\beta _{CV}^{(n)}$와 $\delta _{CV}^{(n)}$가 존재할 경우 $CVloo$ 안정성을 갖는다.

$\forall i\in \{1,...,n\},\mathbb {P} _{S}\{|V(f_{S^{i}},z_{i})-V(f_{S},z_{i})|\leq \beta _{CV}^{(n)}\}\geq 1-\delta _{CV}^{(n)}$

그리고 $\beta _{CV}^{(n)}$와 $\delta _{CV}^{(n)}$는 $n$이 무한대로 갈 때 0에 수렴한다.

예측된 LOO 오차 안정성

알고리즘 $L$은 각 $n$에 대하여, 이하와 같은 $\beta _{EL}^{m}$와 $\delta _{EL}^{m}$가 존재할 경우 $Eloo_{err}$ 안정성을 갖는다.

$\forall i\in \{1,...,n\},\mathbb {P} _{S}\{|I[f_{S}]-{\frac {1}{n}}\sum _{i=1}^{N}V(f_{S^{i}},z_{i})|\leq \beta _{EL}^{(n)}\}\geq 1-\delta _{EL}^{(n)}$

이 때, $\beta _{EL}^{(n)}$와 $\delta _{EL}^{(n)}$는 $n\rightarrow \infty$일 때 0에 수렴한다.

$L_{1}$ 노름에서의 LOO 안정성에 대하여, 다음은 가설 안정성(Hypothesis Stability)과 같다.

$\mathbb {E} _{S,z}[|V(f_{S},z)-V(f_{S^{i}},z)|]\leq \beta _{H}^{(n)}$

이 때, $\beta _{H}^{(n)}$는 $n$가 무한대로 갈 때 0에 수렴한다.

안정성이 입증된 알고리즘

여러 알고리즘은 안정적이라는 것이 증명되었고, 그 결과 일반화 오차가 제한되었다. 이러한 알고리즘의 목록과 안정성을 입증한 논문의 목록은 이곳에서 열람가능하다.

과적합과의 관계

 과적합 문서를 참고하십시오.

이 그림은 과적합과 일반화 오차의 관계 I[f_n] - I_S[f_n]를 나타낸다. 데이터 지점은 y값에 white noise가 추가된 관계식 y = x에서 생성되었다. 왼쪽 열에는 일련의 훈련 포인트가 푸른색으로 표시되어 있다. 일곱 번째 다항함수는 훈련 데이터에 적합하다. 오른쪽 열에서 함수는 x와 y의 잠재적인 결합확률분포에서 샘플된 데이터를 통하여 테스트된다. 맨 위의 행에서 함수는 10개 데이터 지점의 샘플 세트에 적합하다. 바닥 행에서 함수는 100개 데이터 지점의 샘플 세트에 적합하다. 이렇듯, 작은 표본 크기와 복잡한 함수의 경우, 훈련 집합의 오차는 작지만 잠재적인 데이터 분포에 대한 오차는 크고, 데이터를 과도적합시키게 된다. 결과적으로, 일반화 오차는 커진다. 샘플링 지점의 수가 증가함에 따라, 훈련 및 테스트 데이트의 예측오차가 수렴되고, 일반화 오차는 0에 수렴한다.

일반화 오차와 과적합의 개념은 밀접하게 연관되어 있다. 과적합은 학습된 함수 $f_{S}$가 샘플 내 노이즈에 과민해졌을 때 발생한다. 결과적으로, 함수는 훈련 집합에서 잘 수행되겠지만, 결합확률분포 $x$와 $y$에서의 다른 데이터에 대해서는 그렇지 않을 것이다. 그러므로, 과적합될수록 일반화 오차는 커진다.

과적합의 양은, 교차검증 방법을 사용하여 테스트할 수 있으며, 이 방법은 샘플을 시뮬레이션된 훈련 샘플과 테스트 샘플로 분할한다. 그런 다음, 모델을 훈련 샘플을 통해 교육하고, 테스트 샘플에서 평가된다. 테스트 샘플은 이전 알고리즘에서 보여지지 않은, 즉 결합확률분포 $x$와 $y$에서의 임의의 샘플을 나타낸다. 이 테스트 샘플은 예상오차를 근사적으로 계산할 수 있게 해주며, 그 결과 일반화 오차의 특정 형태에 근사하게 된다.

과적합을 방지하기 위한 많은 알고리즘이 존재한다. 최소화 알고리즘은 더 복잡한 함수에 불이익을 주거나(티호노프 정칙화), 가설 공간(hypothesis space)은 함수의 형태로 명시적으로 제약될 수 있거나, 최소화 함수에 제약조건을 추가함으로써 제약될 수 있다(이바노프 정규화).

과적합하지 않는 함수를 찾는 접근방식은, 데이터의 특정된 특성을 포착하기에 충분히 복잡한 함수를 찾는 목표와 상충된다. 이는 편향-분산 트레이드오프로도 알려져 있다. 함수를 단순히 하여 과적합을 회피하면, 결과로서 얻어지는 예측에 편향이 생길 가능성이 있으나, 그것을 보다 복잡하게 만들면, 과적합과 예측의 변동이 커진다. 이 둘을 동시에 최소화하는 것은 불가능하다.

관련 문헌

• Bousquet, O., S. Boucheron and G. Lugosi. Introduction to Statistical Learning Theory. Advanced Lectures on Machine Learning Lecture Notes in Artificial Intelligence 3176, 169-207. (Eds.) Bousquet, O., U. von Luxburg and G. Ratsch, Springer, Heidelberg, Germany (2004)
• Bousquet, O. and A. Elisseef (2002), Stability and Generalization, Journal of Machine Learning Research, 499-526.
• Devroye L. , L. Gyorfi, and G. Lugosi (1996). A Probabilistic Theory of Pattern Recognition. Springer-Verlag. ISBN 978-0387946184.
• Poggio T. and S. Smale. The Mathematics of Learning: Dealing with Data. Notices of the AMS, 2003
• Vapnik, V. (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. ISBN 978-0-387-98780-4.
• Bishop, C.M. (1995), Neural Networks for Pattern Recognition, Oxford: Oxford University Press, especially section 6.4.
• Finke, M., and Müller, K.-R. (1994), "Estimating a-posteriori probabilities using stochastic network models," in Mozer, Smolensky, Touretzky, Elman, & Weigend, eds., Proceedings of the 1993 Connectionist Models Summer School, Hillsdale, NJ: Lawrence Erlbaum Associates, pp. 324–331.
• Geman, S., Bienenstock, E. and Doursat, R. (1992), "Neural Networks and the Bias/Variance Dilemma", Neural Computation, 4, 1-58.
• Husmeier, D. (1999), Neural Networks for Conditional Probability Estimation: Forecasting Beyond Point Predictions, Berlin: Springer Verlag, ISBN 1-85233-095-3.
• McCullagh, P. and Nelder, J.A. (1989) Generalized Linear Models, 2nd ed., London: Chapman & Hall.
• Moody, J.E. (1992), "The Effective Number of Parameters: An Analysis of Generalization and Regularization in Nonlinear Learning Systems", in Moody, J.E., Hanson, S.J., and Lippmann, R.P., Advances in Neural Information Processing Systems 4, 847-854.
• Ripley, B.D. (1996) Pattern Recognition and Neural Networks, Cambridge: Cambridge University Press.
• Rohwer, R., and van der Rest, J.C. (1996), "Minimum description length, regularization, and multimodal data," Neural Computation, 8, 595-609.
• Rojas, R. (1996), "A short proof of the posterior probability property of classifier neural networks," Neural Computation, 8, 41-43.
• White, H. (1990), "Connectionist Nonparametric Regression: Multilayer Feedforward Networks Can Learn Arbitrary Mappings," Neural Networks, 3, 535-550. Reprinted in White (1992).
• White, H. (1992a), "Nonparametric Estimation of Conditional Quantiles Using Neural Networks," in Page, C. and Le Page, R. (eds.), Proceedings of the 23rd Sympsium on the Interface: Computing Science and Statistics, Alexandria, VA: American Statistical Association, pp. 190–199. Reprinted in White (1992b).
• White, H. (1992b), Artificial Neural Networks: Approximation and Learning Theory, Blackwell.