epsilon-machine

epsilon-machine

English

Alternative forms

• ϵ-machine
• ε-machine

Etymology

epsilon +‎ machine. Coined by James Crutchfield and Karl Young in their 1989 paper “Inferring Statistical Complexity”.[1]

Noun

epsilon-machine (plural epsilon-machines)

1. (computational mechanics) A deterministic automaton consisting of a system of causal states and the transitions between them, functioning as the smallest possible maximally predictive model of a stochastic process
   • 1989, James Crutchfield and Karl Young, “Inferring Statistical Complexity”:

     With a direct measure of an ε-machine’s complexity, the theory gives a computation-theoretic foundation to the notions of model optimality and, most importantly, a measure of the computational complexity of estimated models.

   • 2001, Cosma Rohilla Shalizi, Causal Architecture, Complexity and Self-Organization in Time Series and Cellular Automata:

     The ϵ-machine is the organization of the process, or at least of the part of it which is relevant to our measurements. It leads to a natural measure of the statistical complexity of processes, namely the amount of information needed to specify the state of the ϵ-machine. […] Using the ϵ-machine, we see that the causal states always form a Markov process. This is satisfying ideologically, and has interesting information-theoretic and ergodic consequences.

   • 2010, Sean Harrison Whalen, “Security applications of the epsilon-machine”, abstract:

     These predictors, called ε-machines, are a subset of a well known statistical model class called the Hidden Markov Model (HMM). Despite being a subset, ε-machines have several important advantages over traditional HMMs. This dissertation illustrates these advantages by applying ε-machines to several problems in computer security: anomaly-based intrusion detection in High Performance Computing (HPC) environments, automated protocol reverse engineering, and structural drift.

   • 2011, Nicolas Brodu, “Reconstruction of epsilon-machines in predictive frameworks and decisional states” in Advances in Complex Systems, volume 14, number 05:

     This article introduces both a new algorithm for reconstructing epsilon-machines from data, as well as the decisional states. These are defined as the internal states of a system that lead to the same decision, based on a user-provided utility or pay-off function. […] The intrinsic underlying structure of the system is modeled by an epsilon-machine and its causal states.

References

1. Shalizi, Cosma Rohilla (2001), Causal Architecture, Complexity and Self-Organization in Time Series and Cellular Automata, page 5