불완전한 압축 하에서의 예측: 근사 MDL 이론

최소 기술 길이 (Minimum Description Length, MDL)는 전체 기술 길이인 $L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$를 최적화함으로써 오컴의 면도날 (Occam's razor) 원칙을 공식화합니다. 순차적 예측 (sequential prediction)을 위해, MDL 방법은 다음 단계의 예측을 위해 관찰된 접두사 (prefix)에 대한 최소 목적 점수 (objective score)를 가진 모델을 반복적으로 선택합니다. 고전적인 MDL 예측 이론은 MDL 목적 함수의 정확한 최적화가 실제로 신뢰할 수 있는 예측을 뒷받침하는 강력한 압축 보장 (compression guarantee)을 제공한다는 것을 보여줍니다. 그러나 실제 머신러닝 (machine learning)에서는 대개 목적 함수를 근사적으로 최적화함으로써만 모델을 찾을 수 있습니다. 이러한 격차를 메우기 위해, 본 논문은 다음과 같은 근본적인 질문을 다룹니다: 어떤 형태의 근사 (approximation) 및 규제화 (regularization) 하에서 근사 MDL이 여전히 신뢰할 수 있는 순차적 예측을 보장하는가? 본 연구는 원칙적인 특성화를 제공합니다. 우리는 더 일반적인 형태인 균형 잡힌 MDL 목적 함수 $λ\cdot L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$에 대해 가산 슬랙 (additive slack) $C$를 갖는 모든 근사에 대하여, 모든 $λ\ge1$에 대해 누적 기대 제곱 예측 오차 (cumulative expected squared prediction error)가 유한함을 증명합니다. $λ>1$인 경우는 친화성 텔레스코핑 (affinity-telescoping) 논증을 통해 증명되었으며, 경계 사례인 $λ=1$은 정확한 정적 MDL 경계 (exact static MDL bounds)에 기반한 우도비 정지 (likelihood-ratio stopping) 논증을 통해 증명되었습니다. 우리의 결과는 고전적인 MDL 규제화가 어떠한 고정된 가산 최적화 오차 (fixed additive optimization error)에 대해서도 견고하게 유지됨을 입증합니다. 나아가, 우리는 근사 MDL 프레임워크에 대한 우리의 특성화가 정밀함을 입증합니다: $0<λ<1$일 때, 추정 가능한 측도 (estimable measures)의 보편적 클래스 (universal class)에서 과적합 (overfit)이 발생하여 무한한 누적 기대 오차를 초래할 수 있으며, 따라서 강력한 형태의 모델 복잡도 규제화 (model-complexity regularization)가 필요합니다. 또한, 승법적 근사 (multiplicative approximation) 하에서는 모든 규제화 영역 $λ>0$에서 모델 선택이 실패할 수 있으므로, 가산 근사 (additive approximation)는 충분조건이자 필요조건입니다.