콜모고로프 복잡도(Kolmogorov Complexity)는 문자열을 생성하는 가장 짧은 프로그램의 길이로 정보량을 정의하는 이론이다. 알고리즘적 정보 이론의 핵심 개념으로 무작위성, 압축, 학습 이론의 수학적 기반을 제공한다.
핵심 정의
K(x): 문자열 x를 출력하는 최단 프로그램의 길이
(보편 튜링 기계 U 기준)
예시:
x = "aaaa...a" (1000개): K(x) ≈ log(1000) ← 반복 규칙 존재
x = 진정한 난수 문자열: K(x) ≈ |x| ← 규칙 없음
무작위성 정의:
K(x) ≥ |x| - c 인 경우 x는 알고리즘적으로 무작위
(프로그램이 데이터만큼 길다)
계산 불가능성
콜모고로프 복잡도는 계산 불가능(uncomputable)하다.
증명 (비공식):
K(x)를 계산하는 프로그램 P가 존재한다고 가정
→ "K(x) > n인 첫 번째 x를 찾아라"를 실행
→ 해당 x의 K(x) ≤ log(n) + c 가 됨 (베리 역설)
→ 모순!
결과: 실용적으로는 압축 알고리즘(Lempel-Ziv)으로 근사
압축과의 관계
python
import zlib
import bz2
def estimate_kolmogorov(data: bytes) -> int:
"""압축 크기로 콜모고로프 복잡도 근사"""
return len(zlib.compress(data, level=9))
# 실험
repetitive = b"ab" * 1000
random_data = bytes(range(256)) * 10 # 더 무작위적
print(f"반복 데이터: {len(repetitive)} bytes → {estimate_kolmogorov(repetitive)} bytes (K 근사)")
print(f"무작위 데이터: {len(random_data)} bytes → {estimate_kolmogorov(random_data)} bytes (K 근사)")
응용 분야
정규화 압축 거리 (NCD):
NCD(x,y) = [K(xy) - min(K(x),K(y))] / max(K(x),K(y))
→ 텍스트/바이너리 파일의 유사도 측정 (압축으로 근사)
MDL 원리 (Minimum Description Length):
최적 모델 = 데이터 + 모델의 총 기술 길이 최소화
→ Occam의 면도날의 정보론적 구현
머신러닝 이론적 기반:
- VC 차원과의 관계
- 일반화 오차 경계
관련 문서
