License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.350
URN: urn:nbn:de:0030-drops-33936
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3393/
Go to the corresponding LIPIcs Volume Portal

Jain, Sanjay ; Kinber, Efim

Mind Change Speed-up for Learning Languages from Positive Data

pdf-format:
9.pdf (0.5 MB)

Abstract

Within the frameworks of learning in the limit of indexed classes of
recursive languages from positive data and automatic learning in the
limit of indexed classes of regular languages (with automatically
computable sets of indices), we study the problem of minimizing the
maximum number of mind changes F_M(n) by a learner M on all languages
with indices not exceeding n. For inductive inference of recursive
languages, we establish two conditions under which F_M(n) can be made
smaller than any recursive unbounded non-decreasing function. We also
establish how F_M(n) is affected if at least one of these two
conditions does not hold. In the case of automatic learning, some
partial results addressing speeding up the function F_M(n) are obtained.

BibTeX - Entry

@InProceedings{jain_et_al:LIPIcs:2012:3393,
  author =	{Sanjay Jain and Efim Kinber},
  title =	{{Mind Change Speed-up for Learning Languages from Positive Data}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{350--361},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3393},
  URN =		{urn:nbn:de:0030-drops-33936},
  doi =		{10.4230/LIPIcs.STACS.2012.350},
  annote =	{Keywords: Algorithmic and automatic learning, mind changes, speedup}
}

Keywords: Algorithmic and automatic learning, mind changes, speedup
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI