Computational Mechanics: Pattern and Prediction, Structure and Simplicity

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 $\epsilon$-machine--is the minimal one consistent with accurate prediction. We establish several results on $\epsilon$-machine optimality and uniqueness and on how $\epsilon$-machines compare to alternative representations. Further results relate measures of randomness and structural complexity obtained from $\epsilon$-machines to those from ergodic and information theories.

29 pages, 4 EPS figures, http://www.santafe.edu/projects/CompMech/papers/cmppss.html Revision: Typos fixed, minor tweaks to wording, a few references updated

References in corpus (3)

• Information-Theoretic Limits of Control
• Predictive Information
• Kolmogorov Complexity, Cosmic Microwave Background Maps and the Curvature of the Universe

Cited by in corpus (159)

• Quantum stochastic processes and quantum non-Markovian phenomena
• Quantifying Self-Organization with Optimal Predictors
• Complexity and Information: Measuring Emergence, Self-organization, and Homeostasis at Multiple Scales
• Weak Values are Interference Phenomena
• Unifying Thermodynamic Uncertainty Relations
• The Organization of Intrinsic Computation: Complexity-Entropy Diagrams and the Diversity of Natural Information Processing
• Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
• Anatomy of a Bit: Information in a Time Series Observation
• Prediction, Retrodiction, and The Amount of Information Stored in the Present
• Automatic Filters for the Detection of Coherent Structure in Spatiotemporal Systems
• Dynamics of Bayesian Updating with Dependent Data and Misspecified Models
• An Algorithm for Pattern Discovery in Time Series
• Model-free quantification of time-series predictability
• What Is a Macrostate? Subjective Observations and Objective Dynamics
• Complementarity in classical dynamical systems
• The Structure of Quantum Stochastic Processes with Finite Markov Order
• A practical, unitary simulator for non-Markovian complex processes
• A framework for the local information dynamics of distributed computation in complex systems
• A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions
• The Computational Structure of Spike Trains
• Computational Mechanics of Input-Output Processes: Structured transformations and the $\epsilon$-transducer
• Bayesian Structural Inference for Hidden Processes
• Experimental quantum processing enhancement in modelling stochastic processes
• Visual Causal Feature Learning
• Inferring hidden Markov models from noisy time sequences: a method to alleviate degeneracy in molecular dynamics
• Extreme dimensionality reduction with quantum modelling
• Discovering Planar Disorder in Close-Packed Structures from X-Ray Diffraction: Beyond the Fault Model
• Does the brain behave like a (complex) network? I. Dynamics
• Complexity analysis of the stock market
• A Closed-Form Shave from Occam's Quantum Razor: Exact Results for Quantum Compression
• Optimal stochastic modelling with unitary quantum dynamics
• Exact Synchronization for Finite-State Sources
• The application of computational mechanics to the analysis of geomagnetic data
• Optimal classical simulation of state-independent quantum contextuality
• Thermodynamical cost of some interpretations of quantum theory
• The market efficiency in the stock markets
• Optimal Nonlinear Prediction of Random Fields on Networks
• Information Bottlenecks, Causal States, and Statistical Relevance Bases: How to Represent Relevant Information in Memoryless Transduction
• Thermodynamics of complexity and pattern manipulation
• Many Roads to Synchrony: Natural Time Scales and Their Algorithms
• Using quantum theory to reduce the complexity of input-output processes
• Extreme Quantum Advantage for Rare-Event Sampling
• Informational and Causal Architecture of Continuous-time Renewal and Hidden Semi-Markov Processes
• Informational and Causal Architecture of Discrete-Time Renewal Processes
• Changing the Environment Based on Empowerment as Intrinsic Motivation
• Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes
• Fisher information of correlated stochastic processes
• Synchronization and Control in Intrinsic and Designed Computation: An Information-Theoretic Analysis of Competing Models of Stochastic Computation
• Information Symmetries in Irreversible Processes
• Unbounded memory advantage in stochastic simulation using quantum mechanics
• Leveraging Environmental Correlations: The Thermodynamics of Requisite Variety
• The classical-quantum divergence of complexity in modelling spin chains
• Towards Quantifying Complexity with Quantum Mechanics
• Matrix Product States for Quantum Stochastic Modelling
• Causal Asymmetry in a Quantum World
• Structure and Randomness of Continuous-Time Discrete-Event Processes
• Nearly Maximally Predictive Features and Their Dimensions
• Meta-trained agents implement Bayes-optimal agents
• Shannon Entropy Rate of Hidden Markov Processes
• Information Anatomy of Stochastic Equilibria
• Interfering trajectories in experimental quantum-enhanced stochastic simulation
• Excess entropy in natural language: present state and perspectives
• How Hidden are Hidden Processes? A Primer on Crypticity and Entropy Convergence
• Information-theoretic bound on the energy cost of stochastic simulation
• A Markovian dynamics for C. elegans behavior across scales
• Optimized Bacteria are Environmental Prediction Engines
• Analysis of the phase transition in the $2D$ Ising ferromagnet using a Lempel-Ziv string parsing scheme and black-box data-compression utilities
• Statistical Signatures of Structural Organization: The case of long memory in renewal processes
• Memory compression and thermal efficiency of quantum implementations of non-deterministic hidden Markov models
• Single-shot quantum memory advantage in the simulation of stochastic processes
• Nonequilibrium Statistical Mechanics and Optimal Prediction of Partially-Observed Complex Systems
• Strong and Weak Optimizations in Classical and Quantum Models of Stochastic Processes
• Memory-efficient tracking of complex temporal and symbolic dynamics with quantum simulators
• Local Causal States and Discrete Coherent Structures
• Divergent Predictive States: The Statistical Complexity Dimension of Stationary, Ergodic Hidden Markov Processes
• Approximate information state for approximate planning and reinforcement learning in partially observed systems
• Graph-based Predictable Feature Analysis
• Quantum adaptive agents with efficient long-term memories
• LICORS: Light Cone Reconstruction of States for Non-parametric Forecasting of Spatio-Temporal Systems
• Temporal correlations in the simplest measurement sequences
• On Hidden Markov Processes with Infinite Excess Entropy
• Implementing quantum dimensionality reduction for non-Markovian stochastic simulation
• Robust inference of memory structure for efficient quantum modelling of stochastic processes
• Spectral Simplicity of Apparent Complexity, Part I: The Nondiagonalizable Metadynamics of Prediction
• Mixing, Ergodic, and Nonergodic Processes with Rapidly Growing Information between Blocks
• Discovering Causal Structure with Reproducing-Kernel Hilbert Space $\epsilon$-Machines
• Quantifying Non-Markovianity in Open Quantum Dynamics
• Biochemical Szilard engines for memory-limited inference
• Information theory and learning: a physical approach
• Information theoretic approach to ground-state phase transitions for two and three-dimensional frustrated spin systems
• On $g$-functions for subshifts
• Prediction and Generation of Binary Markov Processes: Can a Finite-State Fox Catch a Markov Mouse?
• Quantifying the complexity of random Boolean networks
• Hierarchical Model of Human Guidance Performance Based on Interaction Patterns in Behavior
• Reductions of Hidden Information Sources
• Quantum coarse-graining for extreme dimension reduction in modelling stochastic temporal dynamics
• State aggregations in Markov chains and block models of networks
• Reconstructing Non-Markovian Open Quantum Evolution From Multi-time Measurements
• Measures of distinguishability between stochastic processes
• Accuracy vs Memory Advantage in the Quantum Simulation of Stochastic Processes
• Point Information Gain and Multidimensional Data Analysis
• Ultimate limit on time signal generation
• Minimum and maximum entropy distributions for binary systems with known means and pairwise correlations
• The Markov Memory for Generating Rare Events
• Randomised benchmarking for characterizing and forecasting correlated processes
• A Unified Paradigm of Organized Complexity and Semantic Information Theory
• Thermodynamically-Efficient Local Computation and the Inefficiency of Quantum Memory Compression
• Increasing complexity with quantum physics
• Circumventing the Curse of Dimensionality in Prediction: Causal Rate-Distortion for Infinite-Order Markov Processes
• Provable superior accuracy in machine learned quantum models
• Predictive information in a nonequilibrium critical model
• Trimming the Independent Fat: Sufficient Statistics, Mutual Information, and Predictability from Effective Channel States
• Algebraic Theory of Patterns as Generalized Symmetries
• Understanding the Predictive Power of Computational Mechanics and Echo State Networks in Social Media
• Unsupervised model-free representation learning
• Engines for predictive work extraction from memoryful quantum stochastic processes
• Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences
• Surveying structural complexity in quantum many-body systems
• Embedding memory-efficient stochastic simulators as quantum trajectories
• Individual-driven versus interaction-driven burstiness in human dynamics: The case of Wikipedia edit history
• Quantum-inspired identification of complex cellular automata
• Physical Computing: A Category Theoretic Perspective on Physical Computation and System Compositionality
• A Physics-Based Approach to Unsupervised Discovery of Coherent Structures in Spatiotemporal Systems
• Error-tolerant witnessing of divergences in classical and quantum statistical complexity
• Foundations of Stochastic Thermodynamics
• Towards Unsupervised Segmentation of Extreme Weather Events
• Quantum Reservoir Computing for Realized Volatility Forecasting
• Multi-Level Cause-Effect Systems
• The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications
• Learning zero-cost portfolio selection with pattern matching
• Optimality and Complexity in Measured Quantum-State Stochastic Processes
• Exploring Predictive States via Cantor Embeddings and Wasserstein Distance
• What Is a Pattern in Statistical Mechanics? Formalizing Structure and Patterns in One-Dimensional Spin Lattice Models with Computational Mechanics
• Boosting on the shoulders of giants in quantum device calibration
• Memory Lens: How Much Memory Does an Agent Use?
• A partial ordering of sets, making mean entropy monotone
• Optimizing Quantum Models of Classical Channels: The reverse Holevo problem
• The fundamental thermodynamic bounds on finite models
• Intrinsic computation of a Monod-Wyman-Changeux molecule
• Measuring complexity
• Close packed structure with finite range interaction: computational mechanics of layer pair interaction
• The LICORS Cabinet: Nonparametric Algorithms for Spatio-temporal Prediction
• Quantifying Self-Organization in Cyclic Cellular Automata
• Minimum Probabilistic Finite State Learning Problem on Finite Data Sets: Complexity, Solution and Approximations
• Tools for network dynamics
• Predictive complexity of quantum subsystems
• A method for inferring hierarchical dynamics in stochastic processes
• Energetic advantages for quantum agents in online execution of complex strategies
• Quantum Dimension Reduction of Hidden Markov Models
• Ideal stochastic process modeling with post-quantum quasiprobabilistic theories
• Project Dynamics and Emergent Complexity
• Subgoal Planning Algorithm for Autonomous Vehicle Guidance
• A Non-equilibrium Thermodynamic Framework of Consciousness
• Structural Drift: The Population Dynamics of Sequential Learning
• Quantum-inspired memory-enhanced stochastic algorithms
• Memory shapes time perception and intertemporal choices
• Specific Differential Entropy Rate Estimation for Continuous-Valued Time Series
• Understanding and Designing Complex Systems: Response to "A framework for optimal high-level descriptions in science and engineering---preliminary report"
• Finitary Process Evolution I: Information Geometry of Configuration Space and the Process-Replicator Dynamics