아래 '세계방정식'에 덧글을 달다가 입실론-기계가 떠올랐습니다. 예전 블로그에 공부한 내용을 정리해둔 게 있었는데 그 중 글 하나를 꺼내어 놓습니다. 가장 중요한 '인과상태'의 정의 부분의 수식이 지저분한데 이쁘게 다시 넣으려다가 말았습니다;;; 설명이 좀 지저분하기도 하고 해서 일단 이 글은 올려놓고 다시 간단히 정리해보려고 합니다.
세계방정식을 푸는 것보다 세계방정식을 세우는 일이 당연히 먼저 이루어져야 하는데, 결국 세계에 대한 관찰로부터 상태들과 상태들 사이의 전이율을 구해야 합니다. 즉 패턴을 발견해야 하는데 이건 입실론-기계의 구성 알고리즘을 통해 이루어질 수 있습니다. 아... 뭔가 끈이 하나 이어진 느낌이 듭니다.
* 2005/06/06
더이상 수식이 난무하는 포스팅은 자제해야겠다는 생각을 하면서도... 시작을 했으니 끝을 봐야 하지 않겠는가. 여기까지만 대충 정리하고 다른 것도 좀 봐야겠다. 수학 없는 물리는 불가능해도 수식 없는 물리는 가능하지 않을까 라는 생각도 해봤는데 아직 결론을 내릴 수는 없다.
역시 0과 1로만 이루어진 시계열을 떠올려보자. 인간이 0과 1을 알고나서부터 날마다 신의 계시를 받아 0 또는 1을 기록해왔다고 하자. (시계열을 기록한 계시록?) 그러면 내일 신이 내릴 계시는 0일까 1일까. 뭐 대충 이런 문제를 푸는 것이 계산역학(computational mechanics)이라고 하면 너무 단순화했다는 비판을 면하기 어렵겠지만, 그렇다고 하자. (아인슈타인의 이야기를 패러디하여, '설명은 가능한 한 단순해야 한다, 하지만 더 단순해서는 안된다.' - 낙타)
안을 전혀 들여다볼 수 없는 블랙박스에서 나오는 시계열로부터 그 내부구조(패턴)를 발견해내는 것, 그래서 계산역학의 목적 중의 하나는 패턴발견(pattern discovery)이다. 어떠한 방법으로 패턴을 발견할 것인가? 입실론-머신(ε-machine)이라는 알고리즘이 있으며, 살리지는 '인과상태쪼개어재구성(Causal State Splitting Reconstruction; CSSR, 대충 우리말로 옮겼는데 맞는건가?)' 방법을 새로 제안했다. 또한 직접 C++로 짜서 프로그램을 공개하기도 했는데 아래 홈페이지에서 다운받을 수 있다.
http://www.cscs.umich.edu/~crshalizi/CSSR/ [2009년 1월 31일 현재, 코드 업데이트 중이어서 다운로드 못함]
C라면 그래도 좀 들여다보겠는데 C++이라 땀만 삐질삐질 흘리고 말았다. 가야할 길이 멀구나. (장광효 디자이너 말투로)
우선 우리는 과거의 사건들을 적당히 분류해야 한다. '밤을 새고' '술을 마시고' '시험을 잘 봤다'고 하자. 각 따옴표는 하나의 사건을 나타낸다. 또한 시험을 보기 직전을 '현재'라고 한다면 앞의 두 사건을 묶어 '과거'라고 하고 뒤의 하나는 '미래'라고 할 수 있다. 그런데 '일찍 자고' '좋은 꿈을 꾸고' '시험을 잘 본' 일도 있었다고 하자. 즉 두 종류의 과거로부터 똑같은 미래가 이어졌다고 하자. 똑같은 미래를 야기한 과거들은 하나의 묶음으로 묶어서 보는 것이 편하다. 이러한 과정을 분할(partition)이라고도 하며, 이렇게 해서 만들어진 묶음들을 인과상태(causal state)라고 한다. 수식을 이용하면 다음과 같이 쓸 수 있다. 수식을 보기 싫으신 분들은 바로 검은 글자로 넘어가시기를.
ε(s-) = { s-' | P(S+ ∈ F | S- = s-) = P(S+ ∈ F | S- = s-'), for all F ∈ μ(S+), s-' ∈ S- }
대문자 S는 확률변수를 뜻하고 소문자 s는 그 변수의 특정한 값을 나타낸다. -는 과거를 뜻하고 +는 미래를 뜻한다. P(X = x)는 확률변수 X가 특정한 x라는 값을 가질 확률이다. P(A | B)라고 하면 B가 주어졌을 때 A의 확률, 즉 조건확률이다. μ(S+)는 위의 예처럼 '미래'라는 사건들을 모두 모아놓은 집합이며 F는 그 중 하나의 원소이다. 또한 { a | f(a) }는 조건 f를 만족시키는 원소 a들의 집합을 나타낸다.
그래서 위의 식이 뜻하는 것은, 어떤 특정한 과거 s-가 주어졌을 때 그로부터 야기되는 미래의 확률분포(P)가 다른 과거 s-'이 주어졌을 때 그로부터 야기되는 미래의 확률분포와 같다면 s-와 s-'은 같은 인과상태에 포함된다는 것이다. 즉 여기서 함수 ε은 모든 과거들을 과거들의 집합들로 대응시키는 함수이며 이들 집합 각각을 인과상태라고 한다. P를 확률이라고 해놓고 뒤에서 확률분포라고 말한 것은 특정한 미래에 대해서만 같은 확률이 나오는 것이 아니라 모든 미래에 대해 같은 확률이 나와야 하므로 각각의 미래에 대한 확률들의 집합이 같아야 한다는 것이고 그래서 이를 확률분포라고 부른 것이다. (아, 이 지저분한 설명이라니...)
과거의 모든 사건들을 다 조사하여 똑같은 결과를 야기시키는 것들끼리 묶어야 하는데 '과거의 사건'의 길이는 어떻게 정해지는가. 즉 위의 예에서 '시험을 잘 봤다'를 야기한 것을 그 전날 밤부터만 따졌는데 일주일 전부터 일어난 사건들까지 '과거'라고 볼 수도 있다는 것이다. 실제로 우리는 모든 길이의 과거를 다 조사해야 한다. '저녁을 먹고' '오락을 하다가' '밤을 새고' '술을 마시고' '시험을 잘 봤다'에서 과거는 앞의 네 사건이 된다. 위의 수식에서는 무한히 긴 과거와 무한히 긴 미래를 가정했는데 실제로는 길이가 L인 과거와 길이가 1인 미래만을 조사한다. 그래서 각각의 인과상태는 길이가 제각각인 과거들을 포함한다.
'밤을 새고' '술을 마시고' '시험을 잘 봐서' '기분이 좋았다'고 해보자. 이제 시험을 잘 본 것까지가 과거이며 기분이 좋은 것이 미래가 된다. 시험을 잘 본 것까지의 과거는 또 다른 인과상태의 원소가 될 수 있다. '밤새' '술마셔' '시험잘봐'라는 과거는 '로또당첨'이라는 과거와 같은 인과상태에 속할 수 있는데 둘 다 '기분좋아'라는 미래를 야기할 수 있기 때문이다. '밤새' '술마셔'라는 과거가 속해 있던 인과상태와 '밤새' '술마셔' '시험잘봐'라는 과거가 속한 인과상태가 다를 수 있는데 이를 인과전이(causal transition)로 정의할 수 있다.
즉 '밤새' '술마셔'가 속한 인과상태에서 '시험잘봐'라는 사건을 생성하며 '밤새' '술마셔' '시험잘봐'라는 인과상태로 전이하는 것이다. 그말이 그말 같지만 이건 원소(과거)들을 중심으로 얘기했기 때문이고, 실제로는 인과상태 i로부터 인과상태 j로 전이한다는 것은 인과상태 i의 모든 과거들이 모두 '시험잘봐'라는 사건을 생성해야 한다는 것을 말한다. 다시 수식으로 정리해보자.
T_ij^(s) = P(S' = S_j, S1+ = s | S = S_i )
여기서 대문자 S는 인과상태이며 소문자 s는 특정한 사건이다. S1+는 길이가 1인 미래를 나타낸다. 예를 들어, 0과 1로 이루어진 계시록의 경우 S1+는 0 아니면 1이다. 위의 조건확률이 뜻하는 것은 지금 S_i라는 인과상태에 있으며 s라는 사건을 생성하며 S_j라는 인과상태가 나타날 확률이며 이것이 곧 전이확률 T_ij^(s)다. T_ij^(s)는 i에서 j로 가면서 s를 생성한다는 뜻이다.
이제 입실론-기계가 완성되었다. 즉 과거의 사건들을 여러 개의 인과상태 집합들에 차곡차곡 분류했고 이 인과상태들 사이의 전이확률까지 구한 것이다. 인과상태들 + 전이확률들 = 입실론-기계. 입실론-기계는 점과 선으로 이루어진 그래프로 그릴 수 있다. 각 인과상태가 점이고 전이확률이 선이 되는 것이다.
http://www.graphviz.org/
이 홈페이지는 입실론-기계를 그릴 수 있는 도구 중의 하나에 관련된 것이다. 사실 다른 도구로도 그릴 수 있는데 살리지의 프로그램은 입실론-기계 결과를 이 도구에서 볼 수 있게 맞추어놓았다.
마지막으로, 이 전이확률들로부터 통계적 복잡성(statistical complexity)을 계산해낼 수 있다. 그리고 다음에 소개할 내용은 과거의 모든 사건들을 인과상태 집합으로 분류하는 방법이다. 위에서는 개념만 소개한 것인데, 실제 알고리즘을 보아야 제대로 이해할 수 있을 것 같다.
