English
 
User Manual Privacy Policy Disclaimer Contact us
  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;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
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: http://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.