E. Kinber et F. Stephan, LANGUAGE-LEARNING FROM TEXTS - MINDCHANGES, LIMITED MEMORY, AND MONOTONICITY, Information and computation, 123(2), 1995, pp. 224-241
Citations number
23
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
The paper explores language learning in the limit under various constr
aints on the number of mindchanges, memory, and monotonicity. We defin
e language learning with limited (long term) memory and prove that lea
rning with limited memory is exactly the same as learning via set driv
en machines (when the order of the input string is not taken into acco
unt). Further we show that every language learnable via a set driven m
achine is learnable via a conservative machine (making only justifiabl
e mindchanges). We get a variety of separation results for learning wi
th bounded number of mindchanges or limited memory under restrictions
on monotonicity. A surprising result is that there are families of lan
guages that can be monotonically learned with at most one mindchange,
but can neither be weak-monotonically nor conservatively learned. Many
separation results have a variant: If a criterion A can be separated
from B, then often it is possible to find a family L of languages such
that L is A and B learnable, but while it is possible to restrict the
number of mindchanges or long term memory on criterion A, this is imp
ossible for B. (C) 1995 Academic Press, Inc.