Language Learning in Dependence on the Space of Hypotheses

Abstract

We study the learnability of indexed families L = (L j ) j2IN of uniformly recursive languages under certain monotonicity constraints. Thereby we distinguish between exact learnability (L has to be learnt with respect to the space L of hypotheses), class preserving learning (L has to be inferred with respect to some space G of hypotheses having the same range as L), and class comprising inference (L has to be learnt with respect to some space G of hypotheses that has a range comprising range(L)). In particular, it is proved that, whenever monotonicity requirements are involved, then exact learning is almost always weaker than class preserving inference which itself turns out to be almost always weaker than class comprising learning. Next, we provide additionally insight into the problem under what conditions, for example, exact and class preserving learning procedures are of equal power. Finally, we deal with the question what kind of languages has to be added to the space of hypo...