We consider the problem of predicting the next observation given a sequence of past observations, and consider the extent to which accurate prediction requires complex algorithms that explicitly leverage long-range dependencies. Perhaps surprisingly, our positive results show that for a broad class of sequences, there is an algorithm that predicts well on average, and bases its predictions only on the most recent few observation together with a set of simple summary statistics of the past observations. Specifically, we show that for any distribution over observations, if the mutual information between past observations and future observations is upper bounded by I , then a simple Markov model over the most recent I /ϵ observations obtains expected KL error ϵ-and hence ℓ 1 error √ ϵ-with respect to the optimal predictor that has access to the entire past and knows the data generating distribution. For a Hidden Markov Model with n hidden states, I is bounded by log n, a quantity that does not depend on the mixing time, and we show that the trivial prediction algorithm based on the empirical frequencies of length O (log n/ϵ ) windows of observations achieves this error, provided the length of the sequence is d Ω(log n/ϵ ) , where d is the size of the observation alphabet. We also establish that this result cannot be improved upon, even for the class of HMMs, in the following two senses: First, for HMMs with n hidden states, a window length of log n/ϵ is informationtheoretically necessary to achieve expected KL error ϵ, or ℓ 1 error √ ϵ. Second, the d Θ(log n/ϵ ) samples required to accurately estimate the Markov model when observations are drawn from an alphabet of size d is necessary for any computationally tractable learning/prediction algorithm, assuming the hardness of strongly refuting a certain class of CSPs. * A full version of this paper is available at https://arxiv.org/abs/1612.02526. Vatsal, and Gregory's contributions were supported in part by NSF Award CCF-1704417 and by ONR Award N00014-17-1-2562. Sham's contributions were supported in part by NSF Award CCF-1703574. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.  We consider the problem of predicting the next observation x t given a sequence of past observations, x 1 ,x 2 , . . . ,x t −1 , which could have complex and long-range dependencies. This sequential prediction problem is one of the most basic learning tasks and is encountered throughout natural language modeling, speech synthesis, financial forecasting, and a number of other domains that have a sequential or chronological element. The abstract problem has received much attention over the last half century from multiple communities including TCS, machine learning, and coding theory. The fundamental question is: How do we consolidate and reference memories about the past in order to effectively predict the future? Given the immense practical importance of this prediction problem, there has been an enormous effort to explore different algorithms for storing and referencing information about the sequence, which have led to the development of several popular models such as n-gram models and Hidden Markov Models (HMMs). Recently, there has been significant interest in recurrent neural networks (RNNs) [1]-which encode the past as a real vector of fixed length that is updated after every observation-and specific classes of such networks, such as Long Short-Term Memory (LSTM) networks [2, 3] . Other recently popular models that have explicit notions of memory include neural Turing machines [4], memory networks [5] , differentiable neural computers [6], attention-based models [7, 8] , etc. These models have been quite successful (see e.g. [9, 10] ); nevertheless, consistently learning long-range dependencies, in settings such as natural language, remains an extremely active area of research. In parallel to these efforts to design systems that explicitly use memory, there has been much effort from the neuroscience community to understand how humans and animals are able to make 1074
We note that the recent work of REF addresses the problem of predicting the distribution of the next observation in the data sequence from a different perspective.
Prediction with a short memory
STOC 2018
Mathematics Computer Science