Computational Mechanics: Pattern and Prediction, Structure and Simplicity

1999/07/13 by Cosma Rohilla Shalizi, James P. Crutchfield · 2 voices · 32 citations
Computer Science · #Computability, Logic, AI Algorithms #Cellular Automata and Applications #Complexity and Algorithms in Graphs

paper · pdf · doi:10.1023/a:1010388907793

Abstract

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.

Citations

• Pattern formation outside of equilibrium

Cited by

• Stochastic Thermodynamics for Autoregressive Generative Models: A Non-Markovian Perspective
• Memory shapes time perception and intertemporal choices
• Cognitive Distinctions as a Language for Cognitive Science: Comparing Methods of Description in a Model of Referential Communication
• A Unified Paradigm of Organized Complexity and Semantic Information Theory
• Provable superior accuracy in machine learned quantum models
• Multi-Level Cause-Effect Systems
• Complementary Characterization of Agent-Based Models via Computational Mechanics and Diffusion Models
• From monoliths to modules: Decomposing transducers for efficient world modelling
• An Adaptive, Data-Integrated Agent-Based Modeling Framework for Explainable and Contestable Policy Design
• Complexity as Advantage: A Regret-Based Perspective on Emergent Structure
• Block-hierarchical covariance decompositions for finite-block additive functionals
• Ultimate limit on time signal generation
• An Algorithm for Pattern Discovery in Time Series
• Characterizing Agent-Based Model Dynamics via ε-Machines and Kolmogorov-Style Complexity
• Meta-trained agents implement Bayes-optimal agents
• The LICORS Cabinet: Nonparametric Algorithms for Spatio-temporal Prediction
• Between order and chaos
• Structural Drift: The Population Dynamics of Sequential Learning
• Towards Unsupervised Segmentation of Extreme Weather Events
• Identifiability and minimality bounds of quantum and post-quantum models of classical stochastic processes
• A Law of Emergence: Maximum Causal Power at the Mesoscale
• Quantum-inspired memory-enhanced stochastic algorithms
• Circumventing the Curse of Dimensionality in Prediction: Causal Rate-Distortion for Infinite-Order Markov Processes
• Understanding and Designing Complex Systems: Response to "A framework for optimal\n high-level descriptions in science and engineering---preliminary report"
• Project Dynamics and Emergent Complexity
• Boosting on the shoulders of giants in quantum device calibration
• Information theory and learning: a physical approach
• Way More Than the Sum of Their Parts: From Statistical to Structural Mixtures
• The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications
• A method for inferring hierarchical dynamics in stochastic processes
• Capturing the emergent dynamical structure in biophysical neural models
• Learning Causal State Representations of Partially Observable Environments

Discussions

• If you want lo learn about statistical complexity and epsilon-machines, you’ll have to look elsewhere. arxiv.org/abs/cond-mat... [bsky, 23 points, 2 comments]
• for the heck of it, Shalizi & Crutchfield on this distinction from their big Journal of Statistical Physics piece arxiv.org/abs/cond-mat... [bsky, 0 points, 0 comments]

Related

• Pattern Discovery and Computational Mechanics
• Some comments on computational mechanics, complexity measures, and all that
• Inferring Kernel ε-Machines: Discovering Structure in Complex Systems
• Thermodynamic Depth of Causal States: When Paddling around in Occam's Pool Shallowness Is a Virtue
• The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications