English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

MPS-Authors
/persons/resource/persons44814

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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

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.


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