MPI-INF D1 Publications: Electronic Proceedings Article: Measuring Learning Complexity with Criteria Epitomizers

Electronic Proceedings Article
@InProceedings
Internet-Beitrag in Tagungsband, Workshop

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Library locked

Goto entry point

Author, Editor

Author(s):

Case, John
Kötzing, Timo

dblp
dblp

Not MPG Author(s):

Case, John

Editor(s):

Schwentick, Thomas
Dürr, Christoph

dblp
dblp

Not MPII Editor(s):

Schwentick, Thomas
Dürr, Christoph

BibTeX cite key*:

Cas-Koe:c:11:StacsEpit

Title, Conference

Title*:	Measuring Learning Complexity with Criteria Epitomizers
Booktitle*:	28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Event Address*:	Dortmund, Germany	URL of the conference:	http://www.stacs2011.de/
Event Date*: (no longer used):		URL for downloading the paper:	http://drops.dagstuhl.de/opus/volltexte/2011/3023/
Event Start Date:	10 March 2011	Event End Date:	12 March 2011
Language:	English	Organization:

Publisher

Publisher's Name:	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik	Publisher's URL:
Address*:	Dagstuhl	Type:

Vol, No, pp., Year

Series:	Leibniz International Proceedings in Informatics (LIPIcs)
Volume:	9	Number:
Month:		Pages:	320-331
		Sequence Number:
Year*:	2011	ISBN/ISSN:	978-3-939897-25-5
	10.4230/LIPIcs.STACS.2011.320

Abstract, Links, ©

URL for Reference:
Note:
(LaTeX) Abstract:	In prior papers, beginning with the seminal work by Freivalds et al. 1995, the notion of intrinsic complexity is used to analyze the learning complexity of sets of functions in a Gold-style learning setting. Herein are pointed out some weaknesses of this notion. Offered is an alternative based on epitomizing sets of functions -- sets, which are learnable under a given learning criterion, but not under other criteria which are not at least as powerful. To capture the idea of epitomizing sets, new reducibility notions are given based on robust learning (closure of learning under certain classes of operators). Various degrees of epitomizing sets are characterized as the sets complete with respect to corresponding reducibility notions! These characterizations also provide an easy method for showing sets to be epitomizers, and they are, then, employed to prove several sets to be epitomizing. Furthermore, a scheme is provided to generate easily very strong epitomizers for a multitude of learning criteria. These strong epitomizers are so-called self-learning sets, previously applied by Case & Koetzing, 2010. These strong epitomizers can be generated and employed in a myriad of settings to witness the strict separation in learning power between the criteria so epitomized and other not as powerful criteria!
URL for the Abstract:

Tags, Categories, Keywords:
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
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{Cas-Koe:c:11:StacsEpit,
AUTHOR = {Case, John and K{\"o}tzing, Timo},
EDITOR = {Schwentick, Thomas and D{\"u}rr, Christoph},
TITLE = {Measuring Learning Complexity with Criteria Epitomizers},
BOOKTITLE = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
PUBLISHER = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
YEAR = {2011},
VOLUME = {9},
PAGES = {320--331},
SERIES = {Leibniz International Proceedings in Informatics (LIPIcs)},
ADDRESS = {Dortmund, Germany},
ISBN = {978-3-939897-25-5},
ISBN = {1868-8969},
DOI = {10.4230/LIPIcs.STACS.2011.320},
}

Entry last modified by Anja Becker, 02/02/2012

Edit History (please click the blue arrow to see the details)

	Editor(s) [Library]	Created 03/17/2011 16:32:33
Revisions 2. 1. 0.	Editor(s) Anja Becker Anja Becker Timo Kötzing	Edit Dates 02.02.2012 11:05:46 02.02.2012 10:49:36 17.03.2011 16:32:33

Attachment Section