Pattern Discovery in Complex System: Review of Epsilon Machine
Jing Jiang · 2006
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: sub-tree 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.