MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Case, John
Kötzing, Timo		dblp
dblp
Not MPG Author(s):
Case, John
Editor(s):
Kalai, Adam Tauman
Mohri, Mehryar		dblp
dblp
Not MPII Editor(s):
Kalai, Adam Tauman
Mohri, Mehryar
BibTeX cite key*:
Koetzing2010NUTechniques
Title, Booktitle
Title*:
Strongly Non-U-Shaped Learning Results by General Techniques
Booktitle*:
COLT 2010 : The 23rd Conference on Learning Theory
Event, URLs
Conference URL::
Downloading URL:
http://www.colt2010.org/papers/011koetzing.pdf
Event Address*:
Haifa, Israel
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
27 June 2010
Event End Date:
29 June 2010
Publisher
Name*:
Omnipress
URL:
Address*:
Madison, WI
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
181-193
Year*:
2010
VG Wort Pages:
ISBN/ISSN:
978-0-9822529-2-5
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Koetzing2010NUTechniques,
AUTHOR = {Case, John and K{\"o}tzing, Timo},
 EDITOR = {Kalai, Adam Tauman and Mohri, Mehryar},
 TITLE = {Strongly Non-{U}-Shaped Learning Results by General Techniques},
 BOOKTITLE = {COLT 2010 : The 23rd Conference on Learning Theory},
 PUBLISHER = {Omnipress},
 YEAR = {2010},
 PAGES = {181--193},
 ADDRESS = {Haifa, Israel},
 ISBN = {978-0-9822529-2-5},
}

Entry last modified by Anja Becker, 02/24/2011
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
12/13/2010 15:55:00
Revisions
6.
5.
4.
3.
2.		Editor(s)
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Anja Becker		Edit Dates
24.02.2011 14:03:27
15.02.2011 13:57:54
15.02.2011 13:57:37
11.01.2011 14:12:44
12/13/2010 04:03:16 PM