Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences

By Cosma Rohilla Shalizi, Kristina Lisa Shalizi. 2004

199 citations recorded by the source corpus.

We present a new method for nonlinear prediction of discrete random sequences under minimal structural assumptions. We give a mathematical construction for optimal predictors of such processes, in the form of hidden Markov models. We then describe an algorithm, CSSR (Causal-State Splitting Reconstruction), which approximates the ideal predictor from data. We discuss the reliability of CSSR, its data requirements, and its performance in simulations. Finally, we compare our approach to existing methods using variable-length Markov models and cross-validated hidden Markov models, and show theoretically and experimentally that our method delivers results superior to the former and at least comparable to the latter.

Subfields: Artificial Intelligence, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Multi-Level Cause-Effect Systems (2015, methodology): “Our approach to the automated construction of causal macro-variables is rooted in the theory of computational mechanics (Shalizi and Crutchfield, 2001; Shalizi, 2001; Shalizi and Shalizi, 2004).”
Dynamics of Bayesian Updating with Dependent Data and Misspecified Models (2009, background): “[58] introduces a frequentist algorithm which consistently reconstructs the hidden-state representation of sofic processes, including the even process.”
On Quitting: Performance and Practice in Online Game Play (2017, methodology): “To maximize the amount of training data the (cid:15) -machine uses (Shalizi and Klinkner 2004), we use 90% of the data for training and reserve 10% for testing.”
Learning Causal State Representations of Partially Observable Environments (2019, methodology): “We exploit the idea of causal states [10, 31, 32, 8], i.e., the coarsest partition of histories into classes that are maximally predictive of the future.”
An information-theoretic primer on complexity, self-organization, and emergence (2009, methodology): “The description of an algorithm which achieves an ǫ -machine reconstruction and calculates the statistical complexity for 1D time series can be found in [57] and for 2D time series in [56].”