Nearly Maximally Predictive Features and Their Dimensions

Abstract

Scientific explanation often requires inferring maximally predictive features from a given data set. Unfortunately, the collection of minimal maximally predictive features for most stochastic processes is uncountably infinite. In such cases, one compromises and instead seeks nearly maximally predictive features. Here, we derive upper-bounds on the rates at which the number and the coding cost of nearly maximally predictive features scales with desired predictive power. The rates are determined by the fractal dimensions of a process' mixed-state distribution. These results, in turn, show how widely-used finite-order Markov models can fail as predictors and that mixed-state predictive features offer a substantial improvement.

arXiv comment6 pages, 2 figures; Supplementary materials, 5 pages, 1 figure; http://csc.ucdavis.edu/~cmg/compmech/pubs/nmpf.htm

References in corpus (7)

• Computational Mechanics: Pattern and Prediction, Structure and Simplicity
• Prediction, Retrodiction, and The Amount of Information Stored in the Present
• Information theoretic approach to interactive learning
• Bayesian Structural Inference for Hidden Processes
• Informational and Causal Architecture of Discrete-Time Renewal Processes
• Statistical Signatures of Structural Organization: The case of long memory in renewal processes
• The Elusive Present: Hidden Past and Future Dependency and Why We Build Models

Cited by in corpus (16)

• Shannon Entropy Rate of Hidden Markov Processes
• Optimized Bacteria are Environmental Prediction Engines
• Divergent Predictive States: The Statistical Complexity Dimension of Stationary, Ergodic Hidden Markov Processes
• Local Causal States and Discrete Coherent Structures
• Spectral Simplicity of Apparent Complexity, Part II: Exact Complexities and Complexity Spectra
• Spectral Simplicity of Apparent Complexity, Part I: The Nondiagonalizable Metadynamics of Prediction
• Discovering Causal Structure with Reproducing-Kernel Hilbert Space $\epsilon$-Machines
• Functional Thermodynamics of Maxwellian Ratchets: Constructing and Deconstructing Patterns, Randomizing and Derandomizing Behaviors
• Unsupervised Discovery of Temporal Structure in Noisy Data with Dynamical Components Analysis
• Measurement-Induced Randomness and Structure in Controlled Qubit Processes
• Provable superior accuracy in machine learned quantum models
• Ambiguity Rate of Hidden Markov Processes
• Engines for predictive work extraction from memoryful quantum stochastic processes
• The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications
• Optimality and Complexity in Measured Quantum-State Stochastic Processes
• Intrinsic computation of a Monod-Wyman-Changeux molecule