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


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
03/17/2011 04:32:33 PM
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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section