On a generalized notion of mistake bounds

This paper proposes the use of constructive ordinals as mistake bounds in t he on-line learning model. This approach elegantly generalizes the applicab ility of the on-line mistake bound model to learnability analysis of very e xpressive concept classes like pattern languages, unions of pattern languag es, elementary formal systems, and minimal models of logic programs. The ma in result in the paper shows that the topological property of effective fin ite bounded thickness is a sufficient condition for on-line learnability wi th a certain ordinal mistake bound. An interesting characterization of the on-line learning model is shown in terms of the identification in the limit framework. It is established that the classes of languages learnable in th e on-line model with a mistake bound of alpha are exactly the same as the c lasses of languages learnable in the limit from both positive and negative data by a Popperian, consistent learner with a mind change bound of alpha. This result nicely builds a bridge between the two models. (C) 2001 Academi c Press.