Mind change efficient learning

Luo, Wei and Schulte, Oliver 2005, Mind change efficient learning, in COLT 2005 : Learning Theory : 18th annual conference on learning theory, COLT 2005 Bertinoro, Italy June 27-30, 2005 : proceedings, Springer, Berlin, Germany, pp. 398-412, doi: 10.1007/11503415_27.

Attached Files
Name Description MIMEType Size Downloads

Title Mind change efficient learning
Author(s) Luo, WeiORCID iD for Luo, Wei orcid.org/0000-0002-4711-7543
Schulte, Oliver
Conference name Conference on Computational Learning Theory (18th : 2005 : Bertinoro, Italy)
Conference location Bertinoro, Italy
Conference dates 27-30 Jun. 2005
Title of proceedings COLT 2005 : Learning Theory : 18th annual conference on learning theory, COLT 2005 Bertinoro, Italy June 27-30, 2005 : proceedings
Editor(s) Auer, Peter
Meir, Ron
Publication date 2005
Conference series Conference on Computational Learning Theory
Start page 398
End page 412
Total pages 15
Publisher Springer
Place of publication Berlin, Germany
Summary 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.
ISBN 9783540265566
Language eng
DOI 10.1007/11503415_27
Field of Research 170203 Knowledge Representation and Machine Learning
Socio Economic Objective 970108 Expanding Knowledge in the Information and Computing Sciences
HERDC Research category E1.1 Full written paper - refereed
Copyright notice ©2005, Springer
Persistent URL http://hdl.handle.net/10536/DRO/DU:30052502

Connect to link resolver
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 5 times in TR Web of Science
Scopus Citation Count Cited 4 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 610 Abstract Views, 0 File Downloads  -  Detailed Statistics
Created: Tue, 14 May 2013, 13:51:50 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.