File(s) under permanent embargo
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 uniform mind change optimality. We characterize the structure of language classes that can be identified with at most α mind changes by some learner (not necessarily effective): A language class L is identifiable with α mind changes iff the accumulation order of L is at most α. Accumulation order is a classic concept from point-set topology. To aid the construction of learning algorithms, we show that the characteristic property of uniformly mind change optimal learners is that they output conjectures (languages) with maximal accumulation order. We illustrate the theory by describing mind change optimal learners for various problems such as identifying linear subspaces and one-variable patterns.
History
Event
Conference on Computational Learning Theory (18th : 2005 : Bertinoro, Italy)Pagination
398 - 412Publisher
SpringerLocation
Bertinoro, ItalyPlace of publication
Berlin, GermanyPublisher DOI
Start date
2005-06-27End date
2005-06-30ISBN-13
9783540265566ISBN-10
3540265562Language
engPublication classification
E1.1 Full written paper - refereedCopyright notice
2005, SpringerEditor/Contributor(s)
P Auer, R MeirTitle of proceedings
COLT 2005 : Learning Theory : 18th annual conference on learning theory, COLT 2005 Bertinoro, Italy June 27-30, 2005 : proceedingsUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC