[Paper Review] Quantifying the Rise and Fall of Complexity in Closed Systems

논문 링크: Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton

논문 정보

핵심 아이디어

이 논문은 닫힌 시스템에서 entropy는 증가하지만 "흥미로운 복잡도"는 중간에 올라갔다가 다시 내려갈 수 있다는 생각을 실험적으로 모델링한다. 커피와 우유가 섞이는 과정을 cellular automaton 비슷한 2D grid로 단순화한다.

무질서도가 계속 증가하더라도, 우리가 복잡하다고 느끼는 구조는 질서와 무질서 사이의 중간 단계에서 가장 크게 나타날 수 있다.

왜 중요한가

이 논문은 Kolmogorov complexity, compression, entropy, apparent complexity를 연결한다. AI reading list 안에서는 intelligence와 compression, complexity 사이의 이론적 배경을 이해하는 데 쓰인다.

수식으로 보는 핵심

Entropy는 distribution $p$에 대해 다음처럼 정의된다.

Closed system에서 entropy는 증가할 수 있지만, 이 값이 우리가 말하는 "흥미로운 복잡도"와 같지는 않다. 완전한 random noise는 entropy가 높지만 구조적으로 흥미롭지는 않다.

Kolmogorov complexity는 object $x$를 출력하는 가장 짧은 program의 길이다.

하지만 $K(x)$는 계산 불가능하므로 논문은 압축 크기 같은 근사를 사용한다.

Apparent complexity는 원래 상태 $x$가 아니라 coarse-grained 상태 $C(x)$의 복잡도를 본다.

이 논문의 핵심 수식은 복잡도를 microstate 자체가 아니라 coarse-grained representation의 description length로 본다는 점이다.

따라서 초기의 단순한 분리 상태와 마지막의 완전히 섞인 상태는 낮고, 중간의 swirl pattern에서 apparent complexity가 높아질 수 있다.

Entropy와 Complexity는 다르다

뜨거운 커피에 우유를 떨어뜨리면 처음에는 질서정연한 상태다. 시간이 지나면 소용돌이와 무늬가 생기고, 더 지나면 완전히 섞여 균일해진다. Entropy는 대체로 증가하지만, 사람이 보기에 흥미로운 pattern은 중간 단계에서 가장 많다.

이 논문은 이 차이를 apparent complexity라는 개념으로 설명하려 한다.

Coffee Automaton

Coffee Automaton은 커피와 우유가 섞이는 과정을 단순한 격자 시스템으로 모델링한다. 초기 상태는 한쪽에 structure가 있고, dynamics가 진행되며 점점 섞인다. 각 시간의 grid 상태를 이미지처럼 보고, 압축 알고리즘으로 복잡도를 근사한다.

완전히 질서 있는 상태와 완전히 무작위인 상태는 모두 설명이 단순할 수 있고, 흥미로운 복잡도는 그 사이에서 커진다.

Compression으로 Complexity 측정하기

Kolmogorov complexity는 어떤 object를 출력하는 가장 짧은 program의 길이다. 정확히 계산할 수는 없기 때문에 논문은 gzip 같은 압축 크기를 근사치로 사용한다. 압축이 잘 되면 반복 구조가 많다는 뜻이고, 압축이 잘 안 되면 무작위성이 많다는 뜻이다.

하지만 완전한 random noise는 압축이 어렵지만 우리가 보기에 구조적이지 않다. 그래서 논문은 coarse-graining을 통해 미시적 무작위성을 제거하고, 거시적으로 보이는 structure를 포착하려 한다.

왜 AI Reading List에 들어갈 만한가

Learning은 data에서 structure를 찾는 과정이다. 그런데 structure는 단순 질서와 완전 무작위 사이에 있다. 이 논문은 complexity, compression, entropy를 구분해 생각하게 해주므로 representation learning이나 model selection을 이론적으로 바라보는 데 도움이 된다.

한계

gzip 압축 크기는 Kolmogorov complexity의 거친 근사일 뿐이다. 또 Coffee Automaton은 실제 물리 시스템을 단순화한 toy model이다. 하지만 목적은 정확한 유체 시뮬레이션이 아니라, complexity가 시간에 따라 어떻게 rise and fall할 수 있는지 보여주는 것이다.

읽을 포인트

• entropy와 apparent complexity의 구분
• gzip 압축 크기로 complexity를 근사하는 방식
• coarse-graining이 "interesting structure"를 포착하는 이유
• 복잡도 개념이 학습/모델 선택과 연결되는 방식

정리

이 논문은 entropy가 증가한다는 말만으로는 "복잡한 구조"를 설명하기 어렵다는 점을 보여준다. 학습과 지능을 compression 관점에서 이해하려면, 무작위성 자체가 아니라 압축 가능한 structure와 그 scale을 함께 봐야 한다.