Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
전산물리학:입실론_기계 [2019/01/22 12:37] – [$L=1$의 통계] admin | 전산물리학:입실론_기계 [2023/09/05 15:46] (current) – external edit 127.0.0.1 | ||
---|---|---|---|
Line 2: | Line 2: | ||
입실론 기계(epsilon machine)은 시계열의 패턴을 찾기 위해 개발된 방법이다. 주어진 과거들에 대해 앞으로 나올 기호의 확률 분포를 보고 통계적으로 충분히 비슷할 경우 묶어서 하나의 ' | 입실론 기계(epsilon machine)은 시계열의 패턴을 찾기 위해 개발된 방법이다. 주어진 과거들에 대해 앞으로 나올 기호의 확률 분포를 보고 통계적으로 충분히 비슷할 경우 묶어서 하나의 ' | ||
- | ======원인 상태 분할 구축 (Causual State Splitting Reconstruction, | + | ======알고리듬====== |
- | 입실론 기계를 만들기 위한 | + | 입실론 기계를 만들기 위한 |
- | =====예: 짝수 과정(Even process)===== | + | =====짝수 과정(Even process)의 실행 예===== |
이 예는 참고문헌 항목의 첫 번째인 Shalizi 등의 논문에서 가져온 것이며, 입실론 기계 구축의 세부적인 설명은 두 번째 참고문헌인 Cirera의 학위논문에서 가져온 것이다. | 이 예는 참고문헌 항목의 첫 번째인 Shalizi 등의 논문에서 가져온 것이며, 입실론 기계 구축의 세부적인 설명은 두 번째 참고문헌인 Cirera의 학위논문에서 가져온 것이다. | ||
Line 14: | Line 14: | ||
짝수 과정이 특히 흥미로운 것은, 우리가 A와 B라는 숨은 상태를 찾지 않고 0과 1의 시계열 자체만을 본다면 절대로 마르코프 연쇄로 표현할 수 없는 과정이라는 점이다. 이는 1의 연쇄가 아무리 길게 이어져도 짝수와 홀수를 구분한다는 점에서 기억의 길이가 사실상 무한대이기 때문에 그러하다. | 짝수 과정이 특히 흥미로운 것은, 우리가 A와 B라는 숨은 상태를 찾지 않고 0과 1의 시계열 자체만을 본다면 절대로 마르코프 연쇄로 표현할 수 없는 과정이라는 점이다. 이는 1의 연쇄가 아무리 길게 이어져도 짝수와 홀수를 구분한다는 점에서 기억의 길이가 사실상 무한대이기 때문에 그러하다. | ||
- | 이 짝수 과정을 통해 길이가 | + | 이 짝수 과정을 통해 길이가 |
{{:: | {{:: | ||
+ | 우리는 길이가 $L_\text{max}=3$인 문자열 후에 등장하는 문자까지만 보려고 한다. 그렇기 때문에 위의 표는 길이 4인 문자열의 빈도까지 기록하고 있다. 이것이 짝수 과정을 올바로 재구축하기 위한 최소한의 길이이다. | ||
====$L=0$의 통계==== | ====$L=0$의 통계==== | ||
CSSR 알고리듬은 가장 간단한 가정에서부터 시작한다. 즉 아무런 기억 없이 일정한 확률로 0과 1이 나온다고 가정하는 것이다. 아무 기억이 없다는 뜻에서 $\emptyset$을 써놓고, 계의 상태가 이것 하나만 존재하므로 그 이름을 $A=\{ \emptyset \}$으로 놓자. 표의 가장 왼쪽을 보면, 상태 $A$에 있을 때 1이 따라나올 확률은 66.9%이다. | CSSR 알고리듬은 가장 간단한 가정에서부터 시작한다. 즉 아무런 기억 없이 일정한 확률로 0과 1이 나온다고 가정하는 것이다. 아무 기억이 없다는 뜻에서 $\emptyset$을 써놓고, 계의 상태가 이것 하나만 존재하므로 그 이름을 $A=\{ \emptyset \}$으로 놓자. 표의 가장 왼쪽을 보면, 상태 $A$에 있을 때 1이 따라나올 확률은 66.9%이다. | ||
Line 41: | Line 42: | ||
마찬가지로 따져보면, | 마찬가지로 따져보면, | ||
* $P(1|000) = 422/836 = 50.5\% \longrightarrow B=\{0, | * $P(1|000) = 422/836 = 50.5\% \longrightarrow B=\{0, | ||
+ | * $P(1|001) = 818/818 = 100 \% \longrightarrow D=\{01, | ||
+ | * $P(1|010) = 0/0$ | ||
+ | * $P(1|011) = 841/1655 = 50.8\% \longrightarrow B=\{0, | ||
+ | * $P(1|100) = 396/818 = 48.4\% \longrightarrow B=\{0, | ||
+ | * $P(1|101) = 837/837 = 100\% \longrightarrow D=\{01, | ||
+ | * $P(1|110) = 836/1654 = 50.5\% \longrightarrow B=\{0, | ||
+ | * $P(1|111) = 2537/3378 = 75.1\% \longrightarrow F=\{111\}$ | ||
+ | 이 때 011과 111이 다른 상태로 분류되었으므로 $E=\{11\}$은 예측력을 잃어서 제거되어야 한다. | ||
+ | 또 길이가 1인 문자열들은 길이가 2인 문자열들보다 새로운 정보를 담고 있지 않으므로 제거될 수 있다. | ||
+ | 우리가 가지고 있는 상태는 $B=\{00, | ||
+ | |||
+ | 우리는 여기까지 상태를 나누겠다고 결정해놓았으므로 이제 이 세 상태 사이의 전이를 결정해야 한다. 이 때 길이 $L_\text{max}-1$인 문자열로부터 시작하여 어느 상태로 가는지를 보는 것이 원칙이다. 예컨대 00 뒤에 0이 오면 (1/2의 확률) 000이므로 $B$에서 $B$로의 전이가 있다는 뜻이고, 나머지 1/2의 확률로 00 뒤에 1이 오면 001이 되므로 $B$에서 $D$로 가는 전이가 있다는 뜻이다. | ||
+ | |||
+ | 반면 길이 $L_\text{max}$인 문자열을 가지고 이 과정을 수행하는 것은 문제가 되는데, 예컨대 011 다음에 1을 붙이고 앞의 0을 잊어버리면 (가정상 우리에겐 $L_\text{max}=3$의 기억 제한이 있으므로) 111이 되어 F로 간다고 놓을 수도 있지만, 이 경우 1이 지금까지 몇 개나 나왔었는지에 대한 정보는 영원히 사라져버리고 만다. 그러면 짝수 과정의 기본 성질은 소실될 것이다. 이는 data closure라고 불리는 일반적인 문제에 속한다. | ||
+ | |||
+ | 물론 $F$처럼 어떤 상태가 길이 $L_\text{max}$인 문자열 하나만을 가지고 있다면 어쩔 수 없이 이로부터 전이를 말해야 할 것이지만 이는 예외적인 상황이다. | ||
+ | |||
+ | 아래 그림은 세 상태 사이의 전이까지 그려넣은 그림이다(Cirera): | ||
+ | |||
+ | {{:: | ||
+ | |||
+ | 여기에서 $F$로 들어가는 전이가 없으므로 $F$는 조금만 시간이 지나도 별 역할을 하지 못하는 과도적(transient) 상태이다. 이를 그림에서 지우고 정리해서 그린다(Cirera): | ||
+ | |||
+ | {{:: | ||
+ | |||
+ | 이는 제일 위에서 보여주었던 짝수 과정의 전이 도표를 성공적으로 재구축한 것이다. | ||
+ | |||
+ | ======코드====== | ||
+ | 제안자들이 직접 개발한 CMPy1.0은 비공개이다. 그 대안으로서 David Darmon의 공개 코드가 있다: | ||
+ | https:// | ||
+ | |||
+ | 이를 사용하기 위해서는 | ||
+ | * 분석하고 싶은 시계열을 data라는 디렉토리에 저장하고 | ||
+ | * demo_CSSR.py를 편집, 실행한다. | ||
+ | * transCSSR_results라는 디렉토리에 생성된 .dot 파일을 그래프로 변환한다. | ||
+ | * .dat_results라는 확장자를 가지는 파일 안에는 그래프에 대한 더 자세한 정보가 담겨있다. | ||
+ | |||
+ | 짝수 과정에 대해 실행해보면 다음과 같은 그래프를 얻는다. | ||
+ | |||
+ | {{:: | ||
======참고문헌====== | ======참고문헌====== | ||
* [[https:// | * [[https:// | ||
* [[http:// | * [[http:// | ||
+ | * http:// | ||
+ | * https:// | ||