Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Strongly Non-U-Shaped Learning Results by General Techniques


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

Case, J., & Kötzing, T. (2010). Strongly Non-U-Shaped Learning Results by General Techniques. In A. T. Kalai, & M. Mohri (Eds.), COLT 2010 (pp. 181-193). Madison, WI: Omnipress. Retrieved from http://www.colt2010.org/papers/011koetzing.pdf.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-16F3-8
In learning, a semantic or behavioral U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept (on the way to success). Within the framework of Inductive Inference, previous results have shown, for example, that such U-shapes are unnecessary for explanatory learning, but are necessary for behaviorally correct and non-trivial vacillatory learning. Herein we focus more on syntactic U-shapes. This paper introduces two general techniques and applies them especially to syntactic U-shapes in learning: one technique to show when they are necessary and one to show when they are unnecessary. The technique for the former is very general and applicable to a much wider range of learning criteria. It employs so-called \emph{self-learning classes of languages} which are shown to \emph{characterize} completely one criterion learning more than another. We apply these techniques to show that, for set-driven and partially set-driven learning, any kind of U-shapes are unnecessary. Furthermore, we show that U-shapes are \emph{not} unnecessary in a strong way for iterative learning, contrasting an earlier result by Case and Moelius that semantic U-shapes \emph{are} unnecessary for iterative learning.