de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Solutions to Open Questions for Non-U-Shaped Learning with Memory Limitations

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44814

Kötzing,  Timo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Case, J., & Kötzing, T. (2010). Solutions to Open Questions for Non-U-Shaped Learning with Memory Limitations. In M. Hutter, F. Stephan, V. Vovk, & T. Zeugmann (Eds.), Algorithmic Learning Theory (pp. 285-299). Berlin: Springer. doi:10.1007/978-3-642-16108-7_24.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-16E6-6
Zusammenfassung
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.