Hilfe Wegweiser Impressum Kontakt Einloggen





Strongly Non-U-Shaped Learning Results by General Techniques


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

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

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.