Divergent Predictive States: The Statistical Complexity Dimension of Stationary, Ergodic Hidden Markov Processes

Abstract

Even simply-defined, finite-state generators produce stochastic processes that require tracking an uncountable infinity of probabilistic features for optimal prediction. For processes generated by hidden Markov chains the consequences are dramatic. Their predictive models are generically infinite-state. And, until recently, one could determine neither their intrinsic randomness nor structural complexity. The prequel, though, introduced methods to accurately calculate the Shannon entropy rate (randomness) and to constructively determine their minimal (though, infinite) set of predictive features. Leveraging this, we address the complementary challenge of determining how structured hidden Markov processes are by calculating their statistical complexity dimension -- the information dimension of the minimal set of predictive features. This tracks the divergence rate of the minimal memory resources required to optimally predict a broad class of truly complex processes.

arXiv comment16 pages, 6 figures; Supplementary Material, 6 pages, 2 figures; http://csc.ucdavis.edu/~cmg/compmech/pubs/icfshmp.htm

References in corpus (14)

• Computational Mechanics: Pattern and Prediction, Structure and Simplicity
• Time series analysis via mechanistic models
• Hidden Markov models for stochastic thermodynamics
• Entropy computing via integration over fractal measures
• Many Roads to Synchrony: Natural Time Scales and Their Algorithms
• Nearly Maximally Predictive Features and Their Dimensions
• Shannon Entropy Rate of Hidden Markov Processes
• Excess entropy in natural language: present state and perspectives
• On the Ledrappier-Young formula for self-affine measures
• On Hidden Markov Processes with Infinite Excess Entropy
• Functional Thermodynamics of Maxwellian Ratchets: Constructing and Deconstructing Patterns, Randomizing and Derandomizing Behaviors
• On the Hausdorff dimension of invariant measures of weakly contracting on average measurable IFS
• Hidden Markov Process: A New Representation, Entropy Rate and Estimation Entropy
• Measurement-Induced Randomness and Structure in Controlled Qubit Processes

Cited by in corpus (7)

• Shannon Entropy Rate of Hidden Markov Processes
• Discovering Causal Structure with Reproducing-Kernel Hilbert Space $\epsilon$-Machines
• Ambiguity Rate of Hidden Markov Processes
• Embedding memory-efficient stochastic simulators as quantum trajectories
• First and Second Laws of Information Processing by Nonequilibrium Dynamical States
• Optimality and Complexity in Measured Quantum-State Stochastic Processes
• Predictive complexity of quantum subsystems