A Model of Sequence Extrapolation

摘要

We study sequence extrapolation as an abstract learning problem. The task is to learn a stream - a semi-infinite sequence (S1, S2,...Sn) of values all of the same data type - from a finite initial segment (S1, S2,..Sm). We assume that all elements of the stream are of the same type (e.g., integers, strings, etc.). In order to represent the hypotheses, we define a language for streams called elementary stream descriptions and present an algorithm that learns in the limit elementary streams over an extensive family of data types. The complexity of the algorithm depends on the type and on a stream property known as the delay. In general, the complexity is exponential or worse, but for streams with bounded delay over freely generated types the algorithm runs in time polynomial in the size of the examples. Sample size analysis is difficult, but for streams of delay 2 over applicative pairs, we calculate exactly the sample size required in the worst case to identify the stream uniquely. This bound helps explain why sequence extrapolation requires so few examples compared to statistical learning.