Mind change efficient learning

Luo, Wei and Schulte, Oliver (2006) Mind change efficient learning. Information and Computation, 204 6: 989-1011. doi:10.1016/j.ic.2006.02.004

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Luo, Wei
Schulte, Oliver
Title Mind change efficient learning
Journal name Information and Computation   Check publisher's open access policy
ISSN 0890-5401
1090-2651
Publication date 2006-06
Sub-type Article (original research)
DOI 10.1016/j.ic.2006.02.004
Volume 204
Issue 6
Start page 989
End page 1011
Total pages 23
Place of publication New York, USA
Publisher Academic Press
Language eng
Subject 1702 Cognitive Sciences
Abstract 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 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 is identifiable with α mind changes iff the accumulation order of is at most α. 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.
Keyword Inductive inference
Mind change complexity
Accumulation order
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: Excellence in Research Australia (ERA) - Collection
School of Information Technology and Electrical Engineering Publications
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 10 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 9 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 15 Jan 2010, 16:22:47 EST by Michael Affleck on behalf of Faculty Of Engineering, Architecture & Info Tech