Monotonicity Versus Efficiency for Learning Languages from Texts

Abstract

One of the central, problems of learning languages from texts is: how various restrictions on the behaviour of a learner limit the learning abilities. We consider restrictions of two types. Restrictions of the first type concern monotonicity of learning. Monotonicity means actually that the learner, fed more and more positive examples of the language, produces better and better generalizations. Our second assumption is that of restricted efficiency of the learner. We consider limits on two types of efficiency: number of mind changes and (long-term) memory. Restrictions on monotonicity and efficiency are combined to answer the following question: how much one can gain in the number of mind changes, or memory, by weakening monotonicity constraints ? We show that, weakening monotonicity constraints, a (uniformly bounded) constant number of mind changes can replace indefinitely many. As concerns learning with limited memory, it turns out that, weakening monotonicity requirements from one level to another, we can gain in memory (at least) exponentially. Some open problems are also formulated.