Computational Mechanics: Pattern and Prediction, Structure and Simplicity

By Cosma Rohilla Shalizi, James P. Crutchfield. 1999

Computational mechanics, an approach to structural complexity, defines a process's causal states and gives a procedure for finding them. We show that the causal-state representation—an ∈-machine—is the minimal one consistent with accurate prediction. We establish several results on ∈-machine optimality and uniqueness and on how ∈-machines compare to alternative representations. Further results relate measures of randomness and structural complexity obtained from ∈-machines to those from ergodic and information theories.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Multi-Level Cause-Effect Systems (2015, methodology): “Our approach to the automated construction of causal macro-variables is rooted in the theory of computational mechanics (Shalizi and Crutchfield, 2001; Shalizi, 2001; Shalizi and Shalizi, 2004).”
Visual Causal Feature Learning (2014, methodology): “Our approach derives its theoretical underpinnings from computational mechanics (Shalizi and Crutchfield, 2001; Shalizi, 2001), but supports a more explicitly causal interpretation by incorporating the possibility of confounding and interventions.”
Dynamics of Bayesian Updating with Dependent Data and Misspecified Models (2009, background): “Despite their simplicity, these models arise naturally when studying the time series of chaotic dynamical systems [3, 15, 57, 16], as well as problems in statistical mechanics [50] and crystallography [62].”
Causal feature learning: an overview (2017, unknown): “The framework draws heavily on ideas developed in computational mechanics (Shalizi and Crutchfield 2001; Shalizi 2001; Shalizi and Moore 2003) and connects them with the framework of causal graphical models (Spirtes et al.”
Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences (2004, background): “The causal states have some important properties [ 6 ].”
Predictability, Complexity, and Learning (2000, background): “In the spirit of its thermodynamic origins, information theory (Shannon 1948) characterizes the potentialities and limitations of all possible prediction algorithms, as well as unifying the analysis of extrapolation with the more general notion of predictability. Specifically, we can define a quanti”
Learning Causal State Representations of Partially Observable Environments (2019, methodology): “Deﬁnition 1 [10, 31] The causal states of a stochastic process are partitions σ ∈ S of the space of feasible pasts ←− Y induced by the causal equivalence ∼ (cid:15) : Which implies: where S t is the variable denoting causal state at time t , overwriting the deﬁnition in Sec.”
Supply-chain networks: a complex adaptive systems perspective (2005, background): “Similar to " -machine reconstruction, techniques exist which can be used to discover casual architecture in memoryless transducers, transducers with memory and spatially extended systems (Shalizi and Crutchﬁeld 2001).”
Integrated Information in Discrete Dynamical Systems: Motivation and Theoretical Framework (2008, background): “This suggests that φ is related to the notion of an ε-machine (Shalizi and Crutchfield 2001) introduced in computational mechanics, which captures the minimal causal architecture that can generate a given pattern.”
An information integration theory of consciousness (2004, methodology): “A related measure could be constructed using the formalism of ε-machines [63].”
On Quitting: Performance and Practice in Online Game Play (2017, methodology): “First, it is optimally predictive, meaning it produces the least uncertainly (entropy) about the future behavior of players (Shalizi and Crutchﬁeld 2001).”