최소 설명 길이

**최소 설명 길이**(minimum description length, **MDL**)는 데이터에 대한 가장 짧은 설명이 최상의 모델이라고 가정하는 모형 선택 원칙이다. MDL 방법은 데이터 압축 관점에서 학습하며 때로는 오컴의 면도날의 수학적 응용으로 설명되기도 한다. MDL 원칙은 데이터의 단일 모델을 명시적으로 식별하지 않고도 추정 및 순차 예측과 같은 다른 형태의 귀납적 추론 및 학습으로 확장될 수 있다.

MDL은 주로 정보 이론에서 유래했으며 통계학, 이론 컴퓨터 과학, 기계 학습 및 더 좁게는 계산 학습 이론의 일반 분야 내에서 더욱 발전했다.

역사적으로, "최소 설명 길이 원칙"이라는 정관사 명사구는 설명이 의미하는 바에 따라 다르지만 상호 연관된 다양한 사용법을 가지고 있다.
* 요르마 리사넨의 학습 이론(정보 이론의 중심 개념) 내에서 모델은 통계적 가설이며 설명은 보편적 코드로 정의된다.
* 리사넨의 1978년 짧은 설명을 자동으로 도출하려는 실용적인 첫 시도는 베이시안 정보 기준(BIC)과 관련이 있다.
* 알고리즘 정보 이론 내에서 데이터 시퀀스의 설명 길이는 해당 데이터 세트를 출력하는 가장 작은 프로그램의 길이이다. 이 맥락에서 '이상화된' MDL 원칙으로도 알려져 있으며, 데이터 세트의 최상의 모델이 가장 짧은 자체 풀림 압축 파일로 표현된다는 솔로모노프의 귀납적 추론 이론과 밀접한 관련이 있다.

## 개요

사용 가능한 데이터에 대한 최소 길이 설명을 최상의 모델로 선택하는 것은 오컴의 면도날로 식별되는 원칙을 따른다. 컴퓨터 프로그래밍이 등장하기 전에는 그러한 설명을 생성하는 것이 과학 이론가들의 지적 노동이었다. 이는 컴퓨터 시대에 이르러 훨씬 덜 형식화되었다. 두 과학자가 이론적으로 이견이 있을 경우, 그들은 자신의 이론 중에서 선택하기 위해 오컴의 면도날을 형식적으로 적용하는 경우가 거의 없었다. 그들은 서로 다른 데이터 세트와 잠재적으로 다른 서술 언어를 가지고 있었을 것이다. 그럼에도 불구하고 오컴의 면도날은 어떤 모델이 최적인지를 결정하는 비공식적인 지침으로 과학이 발전했다.

형식 언어와 컴퓨터 프로그래밍의 출현으로 오컴의 면도날은 수학적으로 정의되었다. 비트 데이터로 인코딩된 주어진 관찰 세트에 대한 모델은 해당 데이터를 출력하는 컴퓨터 프로그램의 형태로 생성될 수 있었다. 그러면 오컴의 면도날은 이 알고리즘 정보의 비트로 측정된 가장 짧은 프로그램을 최상의 모델로 형식적으로 선택할 수 있었다.

혼동을 피하기 위해, MDL 원칙에 모델이 기계에 의해 생성되어야 한다고 암시하는 것은 아무것도 없다는 점에 유의해야 한다. 그것은 전적으로 인간의 산물일 수 있다. MDL 원칙은 컴퓨터에서 실행될 설명이 인간, 기계 또는 이들의 어떤 조합의 산물이든 상관없이 적용된다. MDL 원칙은 실행될 때 원래 데이터 세트를 오류 없이 생성하는 가장 짧은 설명만을 요구한다.

### 2부 코드

컴퓨터 프로그램에서 프로그램과 리터럴 데이터 간의 구별은 모든 형식적인 설명에 적용되며 때로는 설명의 "두 부분"이라고 불린다. 통계적 MDL 학습에서 이러한 설명은 종종 2부 코드라고 불린다.

## 기계 학습의 MDL

MDL은 알고리즘(기계)이 설명을 생성할 때 기계 학습에 적용된다. 학습은 알고리즘이 동일한 데이터 세트에 대한 더 짧은 설명을 생성할 때 발생한다.

그러나 데이터 세트의 이론적 최소 설명 길이인 콜모고로프 복잡도는 계산할 수 없다. 즉, 임의의 기회가 데이터 세트를 출력하는 모든 프로그램 중 가장 짧은 프로그램을 생성하더라도 자동 정리 증명기는 그러한 더 짧은 프로그램이 없음을 증명할 수 없다. 그럼에도 불구하고 데이터 세트를 출력하는 두 프로그램이 주어지면 MDL 원칙은 두 프로그램 중 더 짧은 프로그램을 최상의 모델로 선택한다.

## 알고리즘 MDL 학습에 대한 최근 연구

최근 통계 데이터 모델과 대조되는 알고리즘 데이터 모델의 기계 MDL 학습은 데이터, 계산 자원 및 이론적 발전의 가용성 증가와 함께 관심이 높아지고 있다. 접근 방식은 급증하는 인공 일반 지능 분야의 영향을 받는다. 사망 직전에 마빈 민스키는 이 연구 방향을 강력히 지지하며 다음과 같이 말했다.

## 통계적 MDL 학습

모든 데이터 세트는 유한한(예를 들어, 이진) 알파벳의 기호 문자열로 표현될 수 있다.


[MDL 원칙]은 다음과 같은 통찰력에 기반을 두고 있다: 주어진 데이터 세트의 모든 규칙성은 데이터를 압축하는 데 사용될 수 있다. 즉, 데이터를 문자 그대로 설명하는 데 필요한 것보다 적은 수의 기호를 사용하여 데이터를 설명할 수 있다. (그룬발트, 2004)


이를 바탕으로 1978년 요르마 리사넨은 알고리즘 정보 대신 정보의 통계적 개념을 사용하는 MDL 학습 알고리즘을 발표했다. 지난 40년 동안 이 알고리즘은 베이시안 모형 선택 및 평균, 라쏘 및 릿지와 같은 페널티 방법 등과 연결된 통계 및 기계 학습 절차의 풍부한 이론으로 발전했다. 그룬발트와 로스(2020)는 모든 현대적 개발을 포함한 소개를 제공한다. 리사넨은 이 아이디어로 시작했다. 모든 통계 학습은 데이터의 규칙성을 찾는 것이며, 데이터의 규칙성을 설명하는 최상의 가설은 데이터를 통계적으로 가장 많이 압축할 수 있는 가설이기도 하다. 다른 통계적 방법과 마찬가지로 일부 데이터를 사용하여 모델의 매개변수를 학습하는 데 사용할 수 있다. 그러나 일반적으로 표준 통계적 방법은 모델의 일반적인 형태가 고정되어 있다고 가정한다. MDL의 주요 강점은 모델의 일반적인 형태와 매개변수를 선택하는 데에도 사용할 수 있다는 것이다. 관심 대상(때로는 모델, 때로는 매개변수, 때로는 둘 다 동시에)을 가설이라고 부른다. 기본 아이디어는 고려 중인 가설 집합 {\cal H}의 가설 H를 먼저 인코딩한 다음 H의 "도움을 받아" 데이터 D를 인코딩하여 길이  {L(D)} 의 손실 없는 2단계 코드를 고려하는 것이다. 가장 간단한 맥락에서 이것은 단순히 "H에 의해 만들어진 예측에서 데이터의 편차를 인코딩"하는 것을 의미한다.

 {L(D)} = \min_{H \in {\cal H}} \ (\ L(H) + L(D|H) \ ) \ 

이 최소값을 달성하는 H는 데이터 D에 대한 최상의 설명으로 간주된다. 간단한 예로 회귀 문제를 들어보자. 데이터 D는 일련의 점 D = (x_1,y_1), \ldots, (x_n,y_n)으로 구성될 수 있으며, 집합  {\cal H} 는 X에서 Y까지의 모든 다항식 집합일 수 있다. 차수가 k인 다항식 H를 설명하려면 먼저 매개변수를 어떤 정밀도로 이산화해야 한다. 그런 다음 이 정밀도(자연수)를 설명해야 한다. 다음으로, 차수 k(다른 자연수)를 설명해야 하며, 마지막 단계에서는 k+1 매개변수를 설명해야 한다. 총 길이는 L(H)가 된다. 그런 다음 D의 점은 x-값에 대한 고정된 코드와 n 편차 y_i - H(x_i)에 대한 코드를 사용하여 설명한다.

실제로 종종 (항상 그런 것은 아니지만) 확률 모델을 사용한다. 예를 들어, 각 다항식 H를 X가 주어졌을 때 Y가 평균 H(X) 및 고정되거나 자유 매개변수로 추가될 수 있는 분산 \sigma^2를 갖는 정규 분포를 따른다는 해당 조건부 분포와 연결한다. 그러면 가설 집합 {\cal H}는 H가 다항식인 선형 모델, Y=H(X)+\epsilon 의 가정으로 축소된다.

또한, 특정 매개변수 값에는 직접적으로 관심이 없고, 예를 들어 다항식의 차수에만 관심이 있는 경우가 많다. 이 경우, {\cal H}는 {\cal H} = \{ {\cal H}_0, {\cal H}_1, \ldots \}로 설정되며, 여기서 각 {\cal H}_j는 데이터가 j차 다항식으로 가장 잘 설명된다는 가설을 나타낸다. 그런 다음 가설 {\cal H}_j가 주어진 데이터 D를 단일 부분 코드를 사용하여 코딩하는데, 이 코드는 어떤 가설 H \in {\cal H}_j가 데이터에 잘 맞을 때마다 코드 길이 L(D|H)가 짧도록 설계된다. 이러한 코드의 설계는 범용 코딩이라고 한다. 사용할 수 있는 다양한 유형의 범용 코드가 있으며, 종종 긴 데이터 시퀀스에 대해 유사한 길이를 제공하지만 짧은 시퀀스에 대해서는 다르다. '최고의' (미니맥스 최적성 속성을 가진다는 의미에서) 코드는 정규화된 최대 가능성(NML) 또는 스타르코프 코드이다. 매우 유용한 코드 클래스는 베이즈 주변 가능성 코드이다. 지수족 분포의 경우, 제프리스 사전 분포가 사용되고 매개변수 공간이 적절하게 제한될 때, 이들은 NML 코드와 점근적으로 일치한다. 이는 MDL 이론을 객관적 베이즈 모델 선택과 밀접하게 연결하는데, 객관적 베이즈 모델 선택에서는 다른 이유로 제프리스 사전 분포를 채택하기도 한다. 모델 선택에 대한 MDL 접근 방식은 많은 수의 샘플에 대해 "BIC 접근 방식과 형식적으로 동일한 선택 기준을 제공한다."

### 통계적 MDL 학습의 예시

동전을 1000번 던지고 앞면과 뒷면의 횟수를 기록한다. 두 가지 모델 클래스를 고려하자.
* 첫 번째는 앞면을 0, 뒷면을 1로 나타내는 코드이다. 이 코드는 동전이 공정하다는 가설을 나타낸다. 이 코드에 따른 코드 길이는 항상 정확히 1000비트이다.
* 두 번째는 특정 편향을 가진 동전에 효율적인 모든 코드로 구성되며, 동전이 공정하지 않다는 가설을 나타낸다. 510개의 앞면과 490개의 뒷면을 관찰했다고 가정해 보자. 그러면 두 번째 모델 클래스에서 가장 좋은 코드에 따른 코드 길이는 1000비트보다 짧다.

이러한 이유로 순진한 통계적 방법은 두 번째 모델을 데이터에 대한 더 나은 설명으로 선택할 수 있다. 그러나 MDL 접근 방식은 단순히 가장 좋은 코드를 사용하는 대신 가설에 기반한 단일 코드를 구성한다. 이 코드는 정규화된 최대 가능성 코드이거나 베이즈 코드일 수 있다. 이러한 코드를 사용하면 두 번째 모델 클래스에 기반한 총 코드 길이는 1000비트보다 길다. 따라서 MDL 접근 방식을 따를 때의 결론은 두 번째 모델 클래스에서 가장 좋은 요소가 데이터에 더 잘 맞더라도 편향된 동전이라는 가설을 뒷받침할 충분한 증거가 없다는 것이다.

### 통계적 MDL 표기법
MDL 이론의 핵심은 코드 길이 함수와 확률 분포 사이의 일대일 대응이다(이는 크래프트-맥밀란 부등식에서 비롯된다). 어떤 확률 분포 P에 대해서든, C(x)의 길이(비트 단위)가 -\log_2 P(x)와 같도록 코드 C를 구성할 수 있다. 이 코드는 예상 코드 길이를 최소화한다. 반대로, 코드 C가 주어지면 동일한 조건을 만족하는 확률 분포 P를 구성할 수 있다. (여기서는 반올림 문제는 무시한다.) 즉, 효율적인 코드를 찾는 것은 좋은 확률 분포를 찾는 것과 동등하다.

### 통계적 MDL 학습의 한계
통계적 MDL의 기술 언어는 계산적으로 보편적이지 않다. 따라서 원론적으로도 재귀적인 자연 과정의 모델을 학습할 수 없다.

### 관련 개념
통계적 MDL 학습은 위에서 언급된 코드와 확률 분포 간의 대응을 통해 확률론 및 통계학과 매우 밀접하게 연결되어 있다. 이로 인해 일부 연구자들은 MDL을 베이즈 추론과 동일하게 본다. MDL에서 모델과 데이터를 함께 설명하는 코드 길이는 베이즈 프레임워크에서 각각 사전 확률과 주변 가능도에 해당한다.

베이즈 기계는 효율적인 MDL 코드를 구성하는 데 종종 유용하지만, MDL 프레임워크는 베이즈적이지 않은 다른 코드도 수용한다. 스타르코프 정규화된 최대 가능성 코드가 그 예인데, 이는 현재 MDL 이론에서 중요한 역할을 하지만 베이즈 추론에는 해당하지 않는다. 또한 리사넨은 실제 데이터 생성 과정에 대해 어떠한 가정도 하지 말아야 한다고 강조한다. 실제로는 모델 클래스가 현실을 단순화한 것이므로 어떤 객관적인 의미에서든 진정한 코드나 확률 분포를 포함하지 않는다는 것이다. 마지막으로 언급된 참고 문헌에서 리사넨은 MDL의 수학적 기초를 콜모고로프 구조 함수에 기반을 둔다.

MDL 철학에 따르면, 베이즈 방법은 나쁜 결과를 초래할 수 있는 안전하지 않은 사전 확률에 기반을 둔다면 기각되어야 한다. MDL 관점에서 받아들일 수 있는 사전 확률은 소위 객관적 베이즈 분석에서도 선호되는 경향이 있지만, 거기에서는 동기가 일반적으로 다르다.

## 다른 시스템
리사넨의 방법이 학습에 대한 첫 정보 이론적 접근은 아니었다. 1968년에 월리스와 볼턴은 최소 메시지 길이(MML)라는 관련 개념을 개척했다. MDL과 MML의 차이는 계속되는 혼란의 원인이다. 표면적으로는 두 방법이 대부분 동등해 보이지만, 특히 해석에 있어 몇 가지 중요한 차이가 있다.
* MML은 완전히 주관적인 베이즈적 접근 방식이다. 데이터 생성 과정에 대한 자신의 믿음을 사전 분포의 형태로 표현한다는 아이디어에서 시작한다. MDL은 데이터 생성 과정에 대한 가정을 피한다.
* 두 방법 모두 2부 코드를 사용한다. 첫 번째 부분은 항상 모델 클래스 색인(모형 선택) 또는 매개변수 값(매개변수 추정)과 같이 학습하려는 정보를 나타내고, 두 번째 부분은 첫 번째 부분의 정보가 주어진 데이터 인코딩이다. 두 방법의 차이점은 MDL 문헌에서는 불필요한 매개변수를 코드의 두 번째 부분으로 이동시켜 데이터를 사용하여 소위 단일 부분 코드로 표현할 수 있도록 권장하는데, 이는 종종 2부 코드보다 효율적이라는 점이다. MML의 원래 설명에서는 모든 매개변수가 첫 번째 부분에 인코딩되므로 모든 매개변수가 학습된다.
* MML 프레임워크 내에서 각 매개변수는 전체 메시지 길이를 최적화하는 정밀도로 정확하게 지정된다. 앞선 예시는 어떤 매개변수가 원래 모델에 "유용할 수 있다"고 고려되었지만 나중에 데이터를 설명하는 데 도움이 되지 않는다는 것이 밝혀진 경우 발생할 수 있다(이러한 매개변수에는 해당 매개변수가 도움이 되지 않는다는 (베이즈적) 사전 확률에 해당하는 코드 길이가 할당된다). MDL 프레임워크에서는 모델보다는 모델 클래스를 비교하는 데 더 중점을 두며, 동일한 질문에 접근하는 방식은 해당 매개변수를 명시적으로 포함하는 모델 클래스와 그렇지 않은 다른 클래스를 비교하는 것이 더 자연스럽다. 차이점은 동일한 결론에 도달하기 위해 적용되는 메커니즘에 있다.

## 같이 보기
* 알고리즘 확률
* 알고리즘 정보 이론
* 귀납적 추론
* 귀납 확률
* 렘펠-지브 복잡도
* 다양체 가설

## 각주

## 추가 자료
* 웹상의 최소 설명 길이, 헬싱키 대학교. 읽을 자료, 시연, 이벤트 및 MDL 연구자 링크를 제공한다.
* 요르마 리사넨 홈페이지, MDL에 대한 강의록 및 기타 최근 자료가 포함되어 있다.
*Advances in Minimum Description Length, MIT 프레스, .

분류:알고리즘 정보 이론