Kolmogorov Complexity
Summary
Kolmogorov complexity는 어떤 문자열이나 대상의 복잡도를 “그 대상을 출력하는 가장 짧은 프로그램의 길이”로 정의하는 개념이다. 쉽게 말해, 어떤 데이터를 얼마나 짧은 설명으로 생성할 수 있는지를 보는 것이다.
한 문장으로 이해하기
Kolmogorov complexity는 “이 데이터를 만들어내는 가장 짧은 레시피는 얼마나 긴가?”를 묻는 개념이다.
예를 들어 다음 두 문자열을 보자.
AAAAAAAAAAAAAAAAAAAAAAAA
K7Q2M9ZP4X1B8R6T3N0V첫 번째 문자열은 아주 짧게 설명할 수 있다.
"A를 24번 출력하라"반면 두 번째 문자열은 특별한 패턴이 없다면 거의 그대로 적어야 한다. 이 경우 두 번째 문자열의 Kolmogorov complexity가 더 높다고 본다.
원 논문과 계보
Kolmogorov complexity라는 이름으로 가장 직접적으로 연결되는 원 논문은 다음이다.
| 항목 | 내용 |
|---|---|
| 제안 논문 | A. N. Kolmogorov, “Three approaches to the quantitative definition of information” |
| 연도 | 1965 |
| 출판 정보 | Problems of Information Transmission, 1(1), 1-7 |
| 핵심 아이디어 | 정보량을 확률분포가 아니라, 개별 대상의 가장 짧은 알고리즘적 설명 길이로 볼 수 있다. |
다만 algorithmic information theory는 한 사람의 단일 논문만으로 생긴 분야는 아니다. 보통 다음 세 흐름을 함께 본다.
| 연구자 | 대표 논문 | 역할 |
|---|---|---|
| Ray Solomonoff | ”A Formal Theory of Inductive Inference” Part I/II (1964) | 알고리즘적 확률과 귀납 추론 관점에서 비슷한 아이디어를 먼저 전개했다. |
| Andrey Kolmogorov | ”Three approaches to the quantitative definition of information” (1965) | 개별 대상의 정보량을 shortest description length로 정의하는 틀을 제시했다. |
| Gregory Chaitin | ”On the Length of Programs for Computing Finite Binary Sequences” (1966) | program-size complexity와 algorithmic randomness를 독립적으로 발전시켰다. |
그래서 정확히는 Solomonoff-Kolmogorov-Chaitin complexity 또는 algorithmic complexity라고도 부른다. 하지만 일반적으로는 Kolmogorov complexity라는 이름이 가장 널리 쓰인다.
왜 “압축”과 관련이 있나?
Kolmogorov complexity는 압축 가능성과 거의 같은 직관을 가진다.
| 데이터 | 짧은 설명 가능? | 복잡도 |
|---|---|---|
0101010101010101 | ”01을 8번 반복” | 낮음 |
123456789101112 | ”1부터 12까지 이어쓰기” | 낮음 |
| 무작위처럼 보이는 문자열 | 거의 그대로 적어야 함 | 높음 |
| 원주율 앞 1,000자리 | 겉보기에는 복잡하지만 “π를 계산해 1,000자리 출력” 가능 | 생각보다 낮음 |
중요한 점은 “겉보기에 복잡한가”가 아니라 짧은 생성 규칙이 있는가다.
Shannon entropy와의 차이
Shannon entropy와 Kolmogorov complexity는 둘 다 정보량을 다루지만, 관심 대상이 다르다.
| 구분 | Shannon entropy | Kolmogorov complexity |
|---|---|---|
| 무엇을 보나 | 확률분포 또는 랜덤 변수 | 개별 문자열 또는 개별 대상 |
| 핵심 질문 | 평균적으로 얼마나 놀라운가? | 이 하나를 생성하는 가장 짧은 프로그램은 얼마나 긴가? |
| 예시 | 동전 던지기의 평균 정보량 | 특정 문자열 하나의 최소 설명 길이 |
| 주요 분야 | 통신, 압축, 확률적 정보이론 | 알고리즘 정보이론, 귀납 추론, 무작위성 |
Shannon entropy는 “분포의 평균 정보량”에 가깝고, Kolmogorov complexity는 “개별 대상의 알고리즘적 설명 길이”에 가깝다.
왜 계산하기 어려운가?
Kolmogorov complexity의 정의는 간단하지만, 일반적으로 정확히 계산할 수 없다.
어떤 문자열 x의 Kolmogorov complexity는 다음처럼 생각할 수 있다.
K(x) = x를 출력하는 가장 짧은 프로그램의 길이문제는 “가장 짧은 프로그램”을 찾으려면 가능한 모든 프로그램을 검사해야 한다는 점이다. 그런데 어떤 프로그램은 멈추지 않을 수 있다. 이 문제는 halting problem과 연결된다. 그래서 일반적으로 Kolmogorov complexity는 uncomputable하다.
다만 근사적으로 생각할 수는 있다. 실제 압축 알고리즘으로 잘 압축되는 데이터는 보통 낮은 Kolmogorov complexity를 가진다고 볼 수 있다. 하지만 실제 압축률은 어디까지나 근사다.
Occam’s razor와의 관계
Kolmogorov complexity는 Occam’s razor를 수학적으로 표현하는 데 자주 쓰인다.
여러 설명이 같은 데이터를 설명한다면, 더 짧은 설명을 선호하라.
이 말은 과학과 머신러닝에서 중요하다. 같은 training data를 설명하는 모델이 여러 개 있을 때, 지나치게 복잡한 설명보다 단순한 규칙을 선호하면 더 잘 일반화할 가능성이 있다.
물론 단순한 설명이 항상 맞는 것은 아니다. 하지만 적은 정보로 많은 현상을 설명하는 모델은 강력한 모델일 가능성이 높다.
AI와 머신러닝에서의 의미
1. 일반화
모델이 training data를 외우는 것은 쉽다. 하지만 외운 규칙은 새 데이터에 잘 맞지 않을 수 있다. Kolmogorov complexity 관점에서는, 좋은 일반화란 데이터를 설명하는 짧고 구조적인 규칙을 찾는 것에 가깝다.
2. Overfitting
Overfitting은 데이터를 너무 길고 복잡한 방식으로 설명하는 경우로 볼 수 있다. 모든 예외를 따로 외우는 모델은 training set에는 잘 맞지만, 설명 길이가 길고 일반화가 약하다.
3. Compression
딥러닝에서도 “좋은 representation은 데이터를 잘 압축한다”는 직관이 자주 나온다. Kolmogorov complexity는 이 직관의 이론적 극한에 해당한다.
4. Inductive bias
Inductive Bias는 어떤 설명을 더 그럴듯하게 볼지 정하는 가정이다. Kolmogorov complexity 관점에서는 “짧은 설명을 선호한다”는 것도 강력한 inductive bias다.
Chollet 논문에서 왜 등장하나?
On the Measure of Intelligence에서 Chollet은 지능을 skill-acquisition efficiency로 정의하려 한다. 이때 필요한 질문은 다음이다.
훈련 예시를 설명하는 프로그램에서 평가 문제를 푸는 프로그램으로 넘어가려면, 얼마나 많은 정보가 추가로 필요한가?
이 “필요한 정보량”을 형식화하기 위해 Kolmogorov complexity가 등장한다.
예를 들어 어떤 ARC task에서 train examples를 푸는 프로그램이 있고, test example까지 푸는 프로그램이 있다고 하자. 두 프로그램이 거의 같다면 일반화 난이도는 낮다. 반대로 test까지 풀려면 프로그램을 크게 바꿔야 한다면 일반화 난이도는 높다.
Chollet은 이 차이를 Generalization Difficulty로 해석한다. 다만 Kolmogorov complexity는 정확히 계산할 수 없기 때문에, Chollet의 수식은 실용적인 측정법이라기보다 “무엇을 측정해야 하는가”를 보여주는 이론적 틀에 가깝다.
직관 예시
예시 1: 쉬운 규칙
Input: 1, 2, 3, 4
Output: 2, 4, 6, 8짧은 규칙:
각 숫자에 2를 곱하라이 경우 설명이 짧다. Kolmogorov complexity가 낮은 편이다.
예시 2: 외운 규칙
Input: 1, 2, 3, 4
Output: 7, 2, 19, 5패턴이 없다면 출력값을 그대로 외워야 한다.
1이면 7, 2이면 2, 3이면 19, 4이면 5를 출력하라이 경우 설명이 길다. Kolmogorov complexity가 높은 편이다.
자주 헷갈리는 점
| 오해 | 정확한 이해 |
|---|---|
| 짧게 압축되면 무조건 단순하다 | 어떤 언어와 기계에서 압축하느냐에 따라 상수 차이가 있다. 그래도 충분히 긴 대상에서는 이 차이가 덜 중요하다. |
| Kolmogorov complexity는 실제로 계산할 수 있다 | 일반적으로 정확한 계산은 불가능하다. |
| 무작위 데이터는 정보가 없으니 복잡도가 낮다 | 반대다. 무작위 문자열은 짧은 규칙으로 생성하기 어려워 복잡도가 높다. |
| π의 숫자열은 무작위처럼 보이니 복잡도가 높다 | π를 계산하는 짧은 프로그램이 있으므로, 앞 n자리는 생각보다 낮은 복잡도를 가질 수 있다. |
| Shannon entropy와 같은 말이다 | 둘 다 정보량을 다루지만, 하나는 분포의 평균 정보량, 다른 하나는 개별 대상의 최소 설명 길이다. |
핵심 요약
| 질문 | 답 |
|---|---|
| Kolmogorov complexity란? | 어떤 대상을 출력하는 가장 짧은 프로그램의 길이 |
| 무엇을 측정하나? | 개별 데이터의 최소 설명 길이 |
| 왜 중요한가? | 단순성, 압축, 무작위성, 일반화를 연결해 준다. |
| 계산 가능한가? | 일반적으로 정확히 계산할 수 없다. |
| Chollet 논문에서 역할은? | generalization difficulty와 skill-acquisition efficiency를 형식화하는 이론적 도구 |
관련 노트
참고
- A. N. Kolmogorov, “Three approaches to the quantitative definition of information”, Problems of Information Transmission, 1965. ML Anthology
- R. J. Solomonoff, “A Formal Theory of Inductive Inference, Part I”, Information and Control, 1964. ML Anthology
- G. J. Chaitin, “On the Length of Programs for Computing Finite Binary Sequences”, Journal of the ACM, 1966. DBLP
태그
AI InformationTheory KolmogorovComplexity AlgorithmicInformationTheory Generalization AGI