7.30 인공지능 모델 선택에서의 최소 기술 길이(Minimum Description Length) 원리

1. 최소 기술 길이 원리의 기본 개념

1.1 원리의 진술

최소 기술 길이(Minimum Description Length, MDL) 원리는 요르마 리사넨(Jorma Rissanen)이 1978년에 제안한 모형 선택(model selection) 원리로, 데이터를 가장 짧게 기술(description)하는 모형이 최선의 모형이라고 주장한다. 여기서 ’기술’은 데이터의 규칙성을 포착하는 모형과 그 모형으로 설명되지 않는 잔차의 부호화를 포함한다.

MDL 원리의 핵심 아이디어는 학습을 데이터 압축으로 동일시하는 것이다: 데이터의 패턴을 잘 포착하는 모형은 데이터를 효율적으로 압축할 수 있으며, 역으로 데이터를 효율적으로 압축하는 것은 데이터의 패턴을 발견하는 것과 동등하다.

1.2 부 부호 MDL

가장 기본적인 MDL 형태는 2부 부호(two-part code) MDL이다. 데이터 $D$ 의 총 기술 길이를 모형의 기술 길이와 모형이 주어졌을 때 데이터의 기술 길이의 합으로 분해한다:

$L(D) = L(M) + L(D \vert M)$

$L(M)$ : 모형 $M$ 을 부호화하는 데 필요한 비트 수. 모형의 복잡도를 반영한다.
$L(D \vert M)$ : 모형 $M$ 이 주어졌을 때 데이터 $D$ 를 부호화하는 데 필요한 비트 수. 모형의 적합도(goodness of fit)를 반영한다.

MDL은 $L(D) = L(M) + L(D \vert M)$ 을 최소화하는 모형 $M^*$ 를 선택한다:

$M^* = \arg\min_M [L(M) + L(D \vert M)]$

1.3 오컴의 면도날과의 관계

MDL 원리는 오컴의 면도날(Occam’s razor)의 형식화로 해석된다. 단순한 모형은 $L(M)$ 이 작고, 데이터를 잘 적합하는 모형은 $L(D \vert M)$ 이 작다. MDL은 이 두 요소 사이의 최적 절충을 추구하며, 불필요하게 복잡한 모형과 지나치게 단순한 모형을 모두 배제한다.

2. 정보 이론적 기초

2.1 콜모고로프 복잡도와의 관계

MDL 원리의 이론적 기원은 안드레이 콜모고로프(Andrey Kolmogorov)의 알고리즘적 정보 이론(algorithmic information theory)에 있다. 문자열 $x$ 의 콜모고로프 복잡도(Kolmogorov complexity) $K(x)$ 는 $x$ 를 생성하는 가장 짧은 프로그램의 길이이다. 이상적으로 MDL은 콜모고로프 복잡도를 근사하는 것이나, $K(x)$ 는 계산 불가능(uncomputable)하므로 실용적 MDL은 제한된 모형 클래스 내에서의 최소 기술 길이를 추구한다.

2.2 섀넌 부호화와의 연결

모형 $M$ 이 데이터에 확률 분포 $P_M(D)$ 를 부여할 때, 무잡음 부호화 정리에 의해 최적 부호의 기술 길이는:

$L(D \vert M) = -\log_2 P_M(D)$

따라서 MDL에서의 기술 길이 최소화는 모형이 데이터에 부여하는 확률(우도)의 최대화와 밀접히 관련된다. 그러나 우도 최대화만으로는 과적합이 발생하므로, $L(M)$ 항이 모형 복잡도에 대한 벌칙(penalty)으로 작용한다.

3. 매개변수 모형에서의 MDL

3.1 정규화된 최대 우도

매개변수 $\theta \in \Theta$ 를 가지는 모형 족 $\{P_\theta\}$ 에서, 리사넨은 정규화된 최대 우도(normalized maximum likelihood, NML) 분포를 기반으로 한 정교한 MDL을 제안하였다:

$P_{\text{NML}}(D) = \frac{P_{\hat{\theta}(D)}(D)}{\sum_{D'} P_{\hat{\theta}(D')}(D')}$

여기서 $\hat{\theta}(D)$ 는 데이터 $D$ 에 대한 최대 우도 추정량이다. 분모는 모형 클래스의 복잡도를 반영하는 정규화 상수이다.

3.2 확률적 복잡도

모형 클래스의 확률적 복잡도(stochastic complexity)는:

$\text{SC}(D) = -\log_2 P_{\text{NML}}(D) = -\log_2 P_{\hat{\theta}}(D) + \log_2 \mathcal{C}_n$

여기서 $\mathcal{C}_n = \sum_{D'} P_{\hat{\theta}(D')}(D')$ 는 매개변수 복잡도(parametric complexity)이다.

점근적으로( $n \to \infty$ ), 매개변수 복잡도는:

$\log_2 \mathcal{C}_n \approx \frac{k}{2}\log_2 \frac{n}{2\pi} + \log_2 \int \sqrt{\det \mathcal{I}(\theta)} d\theta$

여기서 $k$ 는 매개변수 수, $\mathcal{I}(\theta)$ 는 피셔 정보 행렬이다.

4. 다른 모형 선택 기준과의 비교

4.1 BIC와의 관계

베이지안 정보 기준(Bayesian Information Criterion, BIC)은:

$\text{BIC} = -2\ln P_{\hat{\theta}}(D) + k \ln n$

MDL의 2부 부호에서 $L(M)$ 이 매개변수 수에 비례하고 $L(D \vert M) = -\log_2 P_{\hat{\theta}}(D)$ 로 설정하면, BIC와 유사한 형태를 얻는다. 실제로 BIC는 베이지안 증거의 라플라스 근사이며, MDL의 점근적 근사와 수학적으로 일치한다.

4.2 AIC와의 차이

아카이케 정보 기준(Akaike Information Criterion, AIC)은:

$\text{AIC} = -2\ln P_{\hat{\theta}}(D) + 2k$

AIC의 복잡도 벌칙 $2k$ 는 표본 크기 $n$ 에 무관한 반면, BIC/MDL의 벌칙 $k \ln n$ 은 $n$ 에 따라 증가한다. 따라서 MDL/BIC는 대표본에서 AIC보다 더 강하게 복잡한 모형을 벌칙하며, 일관적(consistent) 모형 선택을 보장한다. 즉, $n \to \infty$ 에서 참 모형이 모형 후보 집합에 포함되어 있으면 MDL/BIC는 참 모형을 확률 1로 선택한다.

4.3 교차 검증과의 관계

교차 검증(cross-validation)은 데이터를 훈련 집합과 검증 집합으로 분할하여 모형의 일반화 성능을 추정하는 경험적 방법이다. MDL은 데이터 분할 없이 전체 데이터에 대해 모형의 복잡도와 적합도를 동시에 평가한다는 점에서 구별된다. 그러나 두 방법 모두 과적합 방지를 목적으로 하며, 특정 조건 하에서 점근적으로 유사한 모형을 선택함이 알려져 있다.

5. 인공지능에서의 응용

5.1 신경망의 모형 선택

신경망의 구조 선택(층 수, 뉴런 수 등)에 MDL 원리를 적용할 수 있다. 네트워크의 가중치를 부호화하는 데 필요한 비트 수가 $L(M)$ 에 해당하고, 모형이 훈련 데이터에 부여하는 로그 우도의 음이 $L(D \vert M)$ 에 해당한다. 제프리 힌턴(Geoffrey Hinton)과 드루 반 캠프(Drew van Camp)의 “Keeping Neural Networks Simple by Minimizing the Description Length of the Weights” (1993)는 이 접근법의 초기 사례이다.

5.2 정규화의 정보론적 정당화

$L_1$ 정규화(LASSO)와 $L_2$ 정규화(릿지 회귀) 등의 정규화 기법은 MDL의 관점에서 모형의 기술 길이에 대한 벌칙으로 해석된다. 매개변수의 크기가 작을수록 적은 비트로 부호화할 수 있으며, 이는 정규화가 MDL 원리의 실천적 구현임을 보여준다. 가중치 감쇠(weight decay)는 가우시안 사전 분포를 가정한 베이지안 추론과 동치이며, 이는 다시 MDL의 2부 부호와 연결된다.

5.3 결정 트리의 가지치기

결정 트리(decision tree) 학습에서 트리의 크기를 제어하는 문제에 MDL이 적용된다. 트리의 구조를 부호화하는 비용 $L(M)$ 과 트리에 의한 데이터 분류 오류를 부호화하는 비용 $L(D \vert M)$ 의 합을 최소화하는 트리를 선택한다. 이는 과적합을 방지하면서 데이터의 핵심 패턴을 포착하는 최적 트리 크기를 결정하는 원칙적 방법을 제공한다.

6. 결론

최소 기술 길이 원리는 학습을 데이터 압축으로 동일시하는 정보 이론적 관점에서 모형 선택 문제에 접근한다. 모형의 기술 길이와 데이터의 조건부 기술 길이의 합을 최소화함으로써, 모형의 복잡도와 적합도 사이의 최적 절충을 추구한다. 이 원리는 베이지안 모형 선택과 점근적으로 일치하며, 정규화, 가지치기, 구조 선택 등 인공지능의 다양한 문제에서 과적합 방지의 이론적 근거를 제공한다. MDL은 정보 이론이 통계적 학습의 근본 원리에 기여하는 대표적 사례이다.