de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Strongly Non-U-Shaped Learning Results by General Techniques

MPS-Authors
http://pubman.mpdl.mpg.de/cone/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). 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: http://hdl.handle.net/11858/00-001M-0000-000F-16F3-8
Abstract
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.