Predictive Rate-Distortion for Infinite-Order Markov Processes

Sarah Marzen

Redwood Center for Theoretical Neuroscience
Physics Department
University of California at Berkeley
Berkeley, CA 94720


James P. Crutchfield

Complexity Sciences Center
Mathematics Department
Physics Department
University of California at Davis
Davis, CA 95616

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.

Sarah Marzen and James P. Crutchfield, "Predictive Rate-Distortion for Infinite-Order Markov Processes", Journal of Statistical Physics 163:6 (2016) 1312-1338.
[pdf] 974 KB
Santa Fe Institute Working Paper 14-12-047. [cond-mat.stat-mech].