Abstract：System complexity means hybridity and emergence. Pattern discovery is to find the hidden pattern of complex system which is a new way to analyze and understand the complex system. Epsilon machine is an achievement of theoretical physics, which could discover the hidden pattern of the process by formal language. In this paper, the basic theory of epsilon machine is firstly presented and its properties and merits are summarized. Epsilon machine has two reconstruction algorithms: subtree merging and causal state splitting reconstruction which are compared in this paper. Then, a simple example about reconstruction of even process is given. As a measurement of nature structure, statistical complexity and its computation are introduced based on epsilon machine reconstruction. Finally, all the progress and application of epsilon machine in the past are reviewed, and the recommendation of the future research is given.
[1] Shalizi C R, Crutchfield J P. Computational Mechanics: Pattern and Prediction, Structure and Simplicity. Journal of Statistical Physics, 2001, 104(3): 817-879 [2] Shalizi C R. Causal Architecture, Complexity and Self-Organization in Time Series and Cellular Automata. Ph.D Dissertation. Madison, USA: University of Wisconsin. Physics Department, 2001 [3] Crutchfield J P. The Calculi of Emergence: Computation, Dynamics and Induction. Physica D: Nonlinear Phenomena, 1994, 75(1/2/3): 11-54 [4] Shalizi C R, Shalizi K L, Crutchfield J P. An Algorithm for Pattern Discovery in Time Series [EB/OL]. [2002-10-06]. http://arxiv.org/ps.cache/cs/pdf/0210/0210025.pdf [5] Crutchfield J P, Young K. Inferring Statistical Complexity. Physical Review Letters, 1989, 63(2): 105-108 [6] Klinkner K, Shalizi C. An Algorithm for Building Markov Models from Time Series [EB/OL]. [2003-08-07]. http://www.cscs.umich. edu/ -crshalizi/CSSR [7] Feldman D P, Crutchfield J. Measure of Statistical Complexity: Why? Physics Letters A, 1998, 238(4/5): 244-252 [8] Perry N, Binder P M. Finite Statistical Complexity for Sofic Systems. Physical Review E, 1999, 60(1): 459-463 [9] Crutchfield J P. Is Anything Ever New? Considering Emergence // Cowan G, Pines D, Melzner D, eds. Complexity: Metaphors, Models, and Reality. Redwood City, USA: Addison Wesley, 1994: 479-497 [10] Hanson J E. Computational Mechanics of Cellular Automata. Ph.D Dissertation. Berkeley, USA: University of California Berkeley. Physics Department, 1993 [11] Upper D R. Theory and Algorithms for Hidden Markov Models and Generalized Hidden Markov Models. Ph.D Dissertation. Berkeley, USA: University of California Berkeley. Mathematics Department, 1997 [12] Feldman D P. Computational Mechanics of Classical Spin Systems. Ph.D Dissertation. Davis, USA: University of California. Physics Department, 1998 [13] Feldman D P, Crutchfield J P. Synchronizing to Periodicity: the Transient Information and Synchronization Time of Periodic Sequences. Advances in Complex Systems. 2004, 7(3/4): 329-355 [14] Crutchfield J P, Feldman D P. Synchronizing to the Environment: Information Theoretic Constraints on Agent Learning. Advances in Complex Systems, 2001, 4(2): 251-264 [15] Varn D P. Language Extraction from ZnS. Ph.D Dissertation. Knoxville, USA: University of Tennessee. Physics College, 2001 [16] Delgado J, Sole R V. Collective-Induced Computation. Physical Review E, 1997, 55(3): 2338-2344 [17] Delgado J, Sole R V. Characterizing Turbulence in Globally Coupled Maps with Stochastic Finite Automata. Physics Letters A, 2000, 270(12): 314-319 [18] Goncalves W M, Pinto R D, Sartorelli J C, et al. Inferring Statistical Complexity in the Dripping Faucet Experiment. Physica A: Statistical Mechanics and Its Applications, 1998, 257(1): 385-389 [19] Palmer A J, Fairall C W, Brewer W A. Complexity in the Atmosphere. IEEE Trans on Geoscience and Remote Sensing, 2000, 38(4): 2056-2063 [20] Palmer A J, Schneider T L, Benjamin A L. Inference Versus Imprint in Climate Modeling. Advances in Complex Systems, 2002, 5(1): 73-89 [21] Nerukh D, Karvounis G, Glen R C. Complexity of Classical Dynamics of Molecular Systems: I. Methodology. Journal of Chemical Physics, 2002, 117(21): 9611-9617 [22] Nerukh D, Karvounis G, Glen R C. Complexity of Classical Dynamics of Molecular Systems: II. Finite Statistical Complexity of Water-Na+ System. Journal of Chemical Physics, 2002, 117(21): 9618-9622 [23] Nerukh D, Karvounis G, Glen R C. Dynamic Complexity of Chaotic Transitions in High-Dimensional Classical Dynamics: Leu-Enkephalin Folding[EB/OL]. [2005-11-23]. http://www.chem.pwf.cam.ac.uk/-dn232/ pub/ec.pdf [24] Wessel N, Schwarz U, Saparin P I, et al. Symbolic Dynamics for Medical Data Analysis // Klonowski W ed. Attractors, Signals, and Synergetic. Lengerich, Germany: Pabst Science Publishers, 2002: 45-61 [25] Clarke R W, Freeman M P, Watkins N W. Application of Computational Mechanics to the Analysis of Natural Data: An Example in Geomagnetism. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 2003, 67(2): 126-203 [26] Chin S C. Real Time Anomaly Detection in Complex Dynamic Systems. Ph.D Dissertation. Park, USA: The Pennsylvania State University. Department of Electrical Engineering, 2004 [27] Ray A. Symbolic Dynamic Analysis of Complex Systems for Anomaly Detection. Signal Processing, 2004, 84(7): 1115-1130 [28] Patil G. Geoinformatic Surveillance for Hotspot Detection and Prioritization [EB/OL]. [2005-11-23]. http://www.stat.psu.edu/~gpp/ pdfs /Prospectus%2016%20overview.pdf [29] Amit S, Soundar K, Mark G, et al. Supply-Chain Networks: A Complex Adaptive Systems Perspective. International Journal of Production Research, 2005, 43(20): 4235-4265 [30] Bochmann O. Probabilistic Approaches in Multi-Agent Systems for Manufacturing Coordination and Control. Ph.D Dissertation. Louvain, Belgium: Katholieke Universiteit Leuven. Department of Mechanical Engineering, 2005 [31] Bertello G, Arduin P J, Boschetti F, et al. First Experiments in the Application of Computational Mechanics to the Analysis of Seismic Time Series [EB/OL]. [2005-11-23]. http://www.per.marine. csiro.au/staff/Fabio.Boschetti/3054CO/papers/epsilon_final.pdf [32] Pei Wenjiang, Yang Lüxi. A Statistical Complexity Measure and Its Applications to the Analysis of Heart Rate Variability. Acta Biophysica Sinica, 2000, 16(3): 562-568 (in Chinese) (裴文江, 杨绿溪. 一种统计复杂性测度及在心率变异信号分析中的应用. 生物物理学报, 2000, 16(3): 562-568) [33] Ay N, Crutchfield J P. Reductions of Hidden Information Sources. Journal of Statistical Physics, 2005, 120(3/4): 659-684 [34] Blum L. Lectures on Theory of Computation and Complexity over the Reals (or an Arbitrary Ring) // Jen E, ed. Lectures in the Sciences of Complexity. Milano, Italy: Addison Wesley, 1990: 1-47 [35] Doya K. Reinforcement Learning in Continuous Time and Space. Neural Computation, 2000, 12(1): 219-245
2006, Vol. 19 
