Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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

URL of the conference:


URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 04:10:08 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section