왜 단순한 게 맞는가 — Ockham에서 Solomonoff까지

"단순한 가설을 골라라"는 격언은 14세기 William of Ockham부터 21세기 ML까지 살아남았다. 살아남은 이유는 후대가 이 격언을 점점 깊게 형식화했기 때문 — 처음엔 직관이었지만, 정보이론을 거쳐 계산이론까지 도달하면서 "왜?"라는 질문이 답을 얻기 시작한다. 이 노트는 그 deepening의 흐름을 따라간다.

한 그림으로

각 단계는 이전 단계의 모호함을 한 층 걷어낸다. "단순"의 정의를 점점 모델·언어·표기에 무관하게 만들어가는 여정이다.

1단계 — Ockham: "필요 이상의 entity를 만들지 마라"

Pluralitas non est ponenda sine necessitate.

14세기 William of Ockham이 신학 논쟁에서 쓴 원칙. 동일한 현상을 두 설명이 똑같이 잘 설명한다면 더 단순한 쪽을 택하라.

약점이 곧장 보임:

"단순"이 무엇인지 정의가 없다. entity 수? 가정의 수? 글자 수?
두 설명이 "똑같이 잘" 설명하는 일이 실제로 있는가? 보통은 한쪽이 더 잘 맞는다.
단순함이 왜 옳은가에 답하지 못한다. 그저 미적 선호일 수도 있다.

이 약점들이 700년에 걸쳐 도전받으며 다음 단계가 나온다.

2단계 — MDL: "코드 길이로 단순함을 측정한다"

Jorma Rissanen (1978). 정보이론의 도구를 끌어와 "단순"을 코드 길이로 정의한다.

기본 발상:

데이터 $D$ 가 주어졌을 때, 가설 $h$ 의 좋음을 두 항의 합으로 측정한다.

$\text{MDL}(h) = L(h) + L(D \mid h)$

$L(h)$ — 가설 $h$ 자체를 기술하는 데 필요한 비트 수 (단순함)
$L(D \mid h)$ — 가설 $h$ 를 알 때 데이터 $D$ 를 기술하는 데 필요한 비트 수 (적합도)

두 항을 합쳐 데이터 + 가설을 통째로 기술하는 가장 짧은 코드를 찾는다. 단순한 가설은 $L(h)$ 가 작고, 복잡한 가설은 데이터를 잘 압축해 $L(D \mid h)$ 가 작다. 둘의 trade-off.

Ockham을 넘어 얻은 것

"단순"이 비트 수라는 객관적 단위로 측정된다
단순함의 가치가 수학적으로 정당화된다 — 짧게 기술 가능하면 그만큼 데이터에 정보가 적게 필요하다 = 일반화 가능성
regularization과 직접 연결된다 — $L(h)$ 가 곧 penalty

남은 약점

어떤 코드체계를 쓸 것인가? Huffman, Shannon-Fano, arithmetic coding... 코드체계마다 $L(h)$ 가 다르다
코드체계를 고른 시점에 이미 prior가 들어간 셈. "단순함"을 코드체계에 의존시킨 것
절대적 단순함 척도가 아니라 상대적

이게 다음 단계의 출발점이다 — "가능한 모든 코드체계를 통틀어 가장 짧은 길이"를 정의할 수 있는가?

3단계 — Kolmogorov complexity: "가능한 모든 코드의 lower bound"

Kolmogorov, Chaitin, Solomonoff (1960s, 독립적으로). MDL의 코드체계 의존성을 제거한다.

정의:

문자열 $x$ 의 Kolmogorov complexity $K(x)$ 는 $x$ 를 출력하는 가장 짧은 프로그램의 길이.

$K(x) = \min_{p : U(p) = x} |p|$

여기서 $U$ 는 universal Turing machine, $p$ 는 프로그램.

Kolmogorov가 결정적인 이유

코드체계 의존성을 없앤다. 어떤 universal Turing machine을 골라도, 다른 machine과의 차이는 상수만큼으로 제한된다 (invariance theorem). 따라서 $K(x)$ 는 표기·언어 무관한 단순함 척도.

Ockham에 답하는 것

"단순한 게 왜 옳은가?" → 짧은 프로그램이 출력하는 패턴은 우연이 아닐 가능성이 높다. 길이 $n$ 의 random string은 $K(x) \approx n$ 이지만, 패턴이 있으면 $K(x) \ll n$ 이 된다
"단순"이 모델·언어·표기에 무관하게 정의된다
정보이론 + 계산이론의 다리 — 패턴 = 압축 가능성 = 짧은 프로그램

약점 — incomputable

여기서 큰 함정이 있다. $K(x)$ 는 일반적으로 계산 불가능하다.

이유: $x$ 를 출력하는 프로그램이 무한히 많고, 그 중 가장 짧은 걸 찾으려면 모든 프로그램을 돌려봐야 하는데 — halting problem 때문에 어떤 프로그램이 정지하는지조차 알 수 없다.

즉 Kolmogorov complexity는 이론적 lower bound로서는 완벽하지만 실무에서 직접 계산할 수는 없다. 이게 다음 단계인 Solomonoff induction이 풀려는 문제 + 결국 풀지 못하는 문제이기도 하다.

4단계 — Solomonoff induction: "짧은 프로그램에 더 큰 prior"

Ray Solomonoff (1964). Kolmogorov complexity를 prediction과 연결한다.

기본 아이디어:

데이터 $x$ 를 봤을 때 다음 비트 $b$ 의 확률을 어떻게 정할까? Bayesian 식으로 풀면 $P(h)$ 가 필요한데 — Solomonoff prior는 이를 다음과 같이 정의한다.

$P(h) \propto 2^{-K(h)}$

가설(여기서는 프로그램)의 prior를 그 가설의 Kolmogorov complexity에 반비례시키는 것. 짧은 프로그램이 더 그럴듯하다는 정량적 명제.

이게 결정적인 이유

귀납의 universal prior — 도메인·모델 무관한 prior를 정의했다
Solomonoff는 이 prior로 도출한 prediction이 어떤 computable distribution에 대해서도 점근적으로 optimal임을 증명. 즉 "충분히 데이터가 많으면 진짜 분포로 수렴"
ML에서 우리가 쓰는 prior(L2 = Gaussian prior, dropout = ensemble prior, ...)는 모두 Solomonoff prior의 실용 근사로 볼 수 있다

약점 — 역시 incomputable

$K(h)$ 가 incomputable이라 Solomonoff prior도 incomputable
그래서 실제 학습에는 직접 쓸 수 없고, 근사가 필요

5단계 — 실무 근사: BIC, AIC, regularization

Solomonoff까지가 이론의 정점. 실무는 그 그림자만 사용한다.

도구	Solomonoff prior와의 관계
BIC (Bayesian Information Criterion)	파라미터 수를 단순함 척도로 — Kolmogorov의 모델별 근사
AIC	KL divergence 관점이지만 형태는 비슷
L2 regularization	Gaussian prior — $K(w) \approx \\|w\\|^2$ 로 근사
L1 regularization	Laplace prior — sparsity가 단순함
Decision tree pruning	노드 수가 단순함
Bayesian model with prior	prior 분산이 작을수록 단순

각 근사는 자기 모델 안에서만 작동하지만, 공통 뿌리는 Solomonoff prior라는 점이 중요. 다른 도구들이 같은 가족이라는 사실이 regularization-as-unified-pattern에서 확장된다.

약점·열린 질문 정리

이 흐름의 한계를 한 표로:

단계	강점	약점
Ockham	직관적, 보편적	"단순"의 정의 없음, 정당화 없음
MDL	정량화, 정당화 시작	코드체계 의존성
Kolmogorov	코드체계 무관, 보편적	incomputable
Solomonoff	귀납에 직접 적용	incomputable
실무 근사	계산 가능	모델별로 단순함 정의가 다시 갈라짐

→ 이론이 깊어질수록 정당화는 강해지지만 계산 가능성은 약해진다. 실무에서는 결국 모델별 근사로 돌아온다 — 그러나 그 근사가 왜 작동하는지 설명하는 뿌리가 Solomonoff prior에 있다는 게 이 흐름의 의미.

대안적 시각 — 단순함은 prior, 복잡한 데이터는 likelihood

이 깊이 있는 정당화가 core-thesis-expressive-then-simple의 Bayesian 뼈대를 단단하게 만든다.

$P(h \mid D) \propto P(D \mid h) \cdot P(h)$

$P(h)$ 는 Ockham에서 시작해 Solomonoff에서 universal prior로 정점에 도달한 것
$P(D \mid h)$ 는 hypothesis space의 표현력 안에서 데이터에 대한 적합도

→ Bayesian 형식이 깊은 의미를 가지는 이유: prior가 임의 가정이 아니라 universal한 단순함 척도의 근사라는 정당화가 Solomonoff에서 나온다.

인사이트

이 흐름이 가르치는 것 세 가지.

단순함은 미적 선호가 아니라 정보이론적 명제. 짧게 기술 가능한 패턴은 우연이 아닐 확률이 높다. Ockham이 700년을 살아남은 이유가 여기 있다.
이론이 깊어질수록 incomputable에 접근한다. 가장 깊은 정당화(Solomonoff)는 직접 쓸 수 없다. 우리는 그 그림자를 모델별로 구현한다 (regularization). 따라서 regularization이 임의 hack이 아니라 이론적 깊이를 가진 근사라고 봐야 한다.
모델 무관한 단순함은 이론 안에만 산다. 실무에서는 모델 안의 단순함(파라미터 norm, 트리 깊이, ...)으로 갈라진다. 두 모델 사이의 단순함 비교가 어려운 게 우연이 아니다 — 이론적으로도 그렇다.

다음 노트

단순함이 generalization에 도움이 된다는 수학적 형식화 → vc-dimension-and-generalization
단순함 prior의 다양한 발현이 같은 뿌리임을 보이기 → regularization-as-unified-pattern
단순함 prior가 흔들리는 영역 (over-parameterization) → 4번 축 follow-up