Circumventing the Curse of Dimensionality in Prediction: Causal Rate-Distortion for Infinite-Order Markov Processes

Abstract

Predictive rate-distortion analysis suffers from the curse of dimensionality: clustering arbitrarily long pasts to retain information about arbitrarily long futures requires resources that typically grow exponentially with length. The challenge is compounded for infinite-order Markov processes, since conditioning on finite sequences cannot capture all of their past dependencies. Spectral arguments show that algorithms which cluster finite-length sequences fail dramatically when the underlying process has long-range temporal correlations and can fail even for processes generated by finite-memory hidden Markov models. We circumvent the curse of dimensionality in rate-distortion analysis of infinite-order processes by casting predictive rate-distortion objective functions in terms of the forward- and reverse-time causal states of computational mechanics. Examples demonstrate that the resulting causal rate-distortion theory substantially improves current predictive rate-distortion analyses.

arXiv comment25 pages, 14 figures; http://csc.ucdavis.edu/~cmg/compmech/pubs/cn.htm

References in corpus (18)

• Computational Mechanics: Pattern and Prediction, Structure and Simplicity
• Time's Barbed Arrow: Irreversibility, Crypticity, and Stored Information
• Statistical Complexity of Simple 1D Spin Systems
• Prediction, Retrodiction, and The Amount of Information Stored in the Present
• Information theoretic approach to interactive learning
• The Computational Structure of Spike Trains
• Bayesian Structural Inference for Hidden Processes
• Chaos Forgets and Remembers: Measuring Information Creation, Destruction, and Storage
• Information Bottlenecks, Causal States, and Statistical Relevance Bases: How to Represent Relevant Information in Memoryless Transduction
• Informational and Causal Architecture of Discrete-Time Renewal Processes
• Many Roads to Synchrony: Natural Time Scales and Their Algorithms
• The Information Bottleneck EM Algorithm
• Information Symmetries in Irreversible Processes
• Information Anatomy of Stochastic Equilibria
• Excess entropy in natural language: present state and perspectives
• Structure or Noise?
• The Past and the Future in the Present
• Predictive information in a sensory population

Cited by in corpus (2)

• Optimal high-level descriptions of dynamical systems
• Understanding and Designing Complex Systems: Response to "A framework for optimal high-level descriptions in science and engineering---preliminary report"