Mind change efficient learning
This paper studies efficient learning with respect to mind changes. Our starting point is the idea that a learner that is efficient with respect to mind changes minimizes mind changes not only globally in the entire learning problem, but also locally in subproblems after receiving some evidence. Formalizing this idea leads to the notion of strong mind change optiniality. We characterize the structure of language classes that can be identified with at most alpha mind changes by some learner (not necessarily effective): a language class L is identifiable with a mind changes iff the accumulation order of L is at most alpha. Accumulation order is a classic concept from point-set topology. We show that accumulation order is related to other established notions of structural complexity, such as thickness and intrinsic complexity. To aid the construction of learning algorithms, we show that the characteristic property of strongly mind change optimal learners is that they output conjectures (languages) with maximal accumulation order. We illustrate the theory by describing strongly mind change optimal learners for various problems such as identifying linear subspaces, one-variable patterns, and fixed-length patterns. (C) 2006 Elsevier Inc. All rights reserved.
accumulation order inductive inference mind change complexity