Predictive rate-distortion for infinite-order Markov processes

DOI10.1007/S10955-016-1520-1zbMATH Open1398.60101arXiv1412.2859OpenAlexW2345543116MaRDI QIDQ310017FDOQ310017

Authors: Sarah Marzen, James P. Crutchfield 

Publication date: 7 September 2016

Published in: Journal of Statistical Physics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1412.2859

Recommendations

• Adaptive Coding and Prediction of Sources With Large and Infinite Alphabets
• On asymptotically optimal methods of prediction and adaptive coding for Markov sources
• Prediction with a short memory
• On the Entropy Rate of Pattern Processes
• The complexity and effectiveness of prediction algorithms

zbMATH Keywords

causal statescomputational mechanicsepsilon-machineinformation bottleneckoptimal causal filteringpredictive rate-distortion

Mathematics Subject Classification ID

Processes in random environments (60K37)

Cites Work

• Elements of Information Theory
• Hidden Markov processes
• A Mathematical Theory of Communication
• Title not available (Why is that?)
• Hidden Markov Models for Speech Recognition
• Title not available (Why is that?)
• Predictability, complexity, and learning
• Regularities unseen, randomness observed: Levels of entropy convergence
• Title not available (Why is that?)
• Prediction, retrodiction, and the amount of information stored in the present
• Information anatomy of stochastic equilibria
• Computational mechanics: pattern and prediction, structure and simplicity.
• Properties of the statistical complexity functional and partially deterministic HMMs
• Fluctuation spectroscopy
• Bifurcation structure of a class of \(S_N\)-invariant constrained optimization problems
• The calculi of emergence: Computation, dynamics and induction
• Exact complexity: the spectral decomposition of intrinsic computation
• The computational structure of spike trains
• Title not available (Why is that?)
• INFORMATION BOTTLENECKS, CAUSAL STATES, AND STATISTICAL RELEVANCE BASES: HOW TO REPRESENT RELEVANT INFORMATION IN MEMORYLESS TRANSDUCTION
• A mapping approach to rate-distortion computation and analysis
• Symmetry Breaking in Soft Clustering Decoding of Neural Codes
• Optimal causal inference: estimating stored information and approximating causal architecture
• Excess entropy in natural language: present state and perspectives
• Information symmetries in irreversible processes
• Predictive Coding and the Slowness Principle: An Information-Theoretic Approach

Cited In (9)

• Discovering causal structure with reproducing-kernel Hilbert space \(\epsilon\)-machines
• On asymptotically optimal methods of prediction and adaptive coding for Markov sources
• Shannon entropy rate of hidden Markov processes
• Rate distortion function for \(N\)th-order Gaussian Markov process
• Correction to: ``Predictive rate-distortion for infinite-order Markov processes
• Predictive information in Gaussian processes with application to music analysis
• Topology, convergence, and reconstruction of predictive states
• Prediction and dissipation in nonequilibrium molecular sensors: conditionally Markovian channels driven by memoryful environments
• Spectral simplicity of apparent complexity. I: The nondiagonalizable metadynamics of prediction

This page was built for publication: Predictive rate-distortion for infinite-order Markov processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q310017)