AI summaryⓘ
The authors study how well a learner can generate new examples of a language when they have limited memory. They find that even without memory, it is often possible to generate examples correctly if the languages follow certain rules, but if not, there are precise limits to what can be done. Their work also shows that keeping a small selected set of past examples helps improve performance, while just remembering the last few does not. Finally, they explore learning where the learner only remembers its last guess, showing that exact identification is hard but approximate identification works under some conditions. Overall, they highlight how memory limits affect different learning tasks in various ways.
language generationbounded memorymemoryless generatorsidentification in the limitminimax densitySperner's theoremsliding windowapproximate identificationlearning theory
Authors
Jon Kleinberg, Anay Mehrotra, Amin Saberi, Grigoris Velegkas
Abstract
We study language generation in the limit under bounded memory. In this task, a learner observes examples from an unknown target language one at a time and must eventually output only new valid examples. Prior work assumes access to the entire history, a strong assumption since realistic algorithms retain limited past information. Classical work in learning theory shows memory constraints dramatically alter learnability; we extend this to language generation. First, we study memoryless generators. Under a mild enumeration restriction, every countable collection of infinite languages remains generable without memory. Without this restriction, we exactly characterize when memoryless generation is possible. For finite collections, we characterize the optimal minimax density achievable by memoryless generators -- the best density guaranteed against any collection of a given size. This combinatorial bound relies on Sperner's theorem and symmetric chain decompositions. We further show that a sliding window of the last $W$ examples does not improve this worst-case density, whereas allowing it to store $b$ adaptively chosen past examples improves the achievable density for every $b \geq 1$. Finally, we revisit identification in the limit, where the learner must converge to a single correct hypothesis for the target language. We focus on its incremental variant, where the learner remembers only its previous guess. Here, although exact identification fails on a collection of just three languages, a mild relaxation requiring convergence to an ``approximate'' version of the target is achievable for every finite collection. These results show bounded memory affects these tasks differently: generation remains achievable for every countable collection, while density and identification are confined to finite collections, with guarantees weakening as the collection grows.