MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Case, John
Kötzing, Timo		dblp
dblp
Not MPG Author(s):
Case, John
Editor(s):
Hutter, Marcus
Stephan, Frank
Vovk, Vladimir
Zeugmann, Thomas		dblp
dblp
dblp
dblp
Not MPII Editor(s):
Hutter, Marcus
Stephan, Frank
Vovk, Vladimir
Zeugmann, Thomas
BibTeX cite key*:
Koetzing2010NUMemLimited
Title, Booktitle
Title*:
Solutions to Open Questions for Non-U-Shaped Learning with Memory Limitations
Booktitle*:
Algorithmic Learning Theory : 21st International Conference, ALT 2010
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Canberra, Australia
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
13 December 2010
Event End Date:
13 December 2010
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Artificial Intelligence
Volume:
6331
Number:
Month:
October
Pages:
285-299
Year*:
2010
VG Wort Pages:
35
ISBN/ISSN:
978-3-642-16107-0
Sequence Number:
DOI:
10.1007/978-3-642-16108-7_24
Note, Abstract, ©
(LaTeX) Abstract:
A U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. Within the framework of Inductive Inference, previous results have shown, for example, that U-shapes are unnecessary for explanatory learning, but are necessary for behaviorally correct learning.

This paper solves the following
two problems regarding non-U-shaped learning posed in the prior literature.

First, it is shown that there are classes learnable with three memory states that are not learnable non-U-shapedly with any finite number of memory states. This result is surprising, as for learning with one or two memory states, U-shapes are known to be unnecessary.

Secondly, it is shown that there is a class learnable memorylessly with a
single feedback query such that this class is not learnable non-U-shapedly
memorylessly with any finite number of feedback queries. This result is
complemented by the result that any class of \emph{infinite} languages
learnable memorylessly with finitely many feedback queries is so learnable
without U-shapes -- in fact, all classes of infinite languages learnable with
\emph{complete} memory are learnable memorylessly with finitely many feedback
queries and without U-shapes. On the other hand, we show that there is a
class of infinite languages learnable memorylessly with a single feedback
query, which is \emph{not} learnable with\emph{out} U-shapes by any particular bounded number of feedback queries.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Koetzing2010NUMemLimited,
AUTHOR = {Case, John and K{\"o}tzing, Timo},
 EDITOR = {Hutter, Marcus and Stephan, Frank and Vovk, Vladimir and Zeugmann, Thomas},
 TITLE = {Solutions to Open Questions for Non-{U}-Shaped Learning with Memory Limitations},
 BOOKTITLE = {Algorithmic Learning Theory : 21st International Conference, ALT 2010},
 PUBLISHER = {Springer},
 YEAR = {2010},
 VOLUME = {6331},
 PAGES = {285--299},
 SERIES = {Lecture Notes in Artificial Intelligence},
 ADDRESS = {Canberra, Australia},
 MONTH = {October},
 ISBN = {978-3-642-16107-0},
 DOI = {10.1007/978-3-642-16108-7_24},
}

Entry last modified by Anja Becker, 02/24/2011
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
12/13/2010 16:10:08
Revisions
4.
3.
2.
1.
0.		Editor(s)
Anja Becker
Anja Becker
Timo Kötzing
Timo Kötzing
Timo Kötzing		Edit Dates
24.02.2011 14:03:11
17.12.2010 13:01:29
12/15/2010 04:22:56 PM
12/13/2010 04:10:47 PM
12/13/2010 04:10:08 PM