Help Guide Disclaimer Contact us Login
  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;

There are no locators available
Fulltext (public)
There are no public fulltexts available
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

Cite as:
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.