License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.494
URN: urn:nbn:de:0030-drops-44823
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4482/
Go to the corresponding LIPIcs Volume Portal

Kötzing, Timo

A Solution to Wiehagen's Thesis

pdf-format:
40.pdf (0.6 MB)

Abstract

Wiehagen's Thesis in Inductive Inference (1991) essentially states that, for each learning criterion, learning can be done in a normalized, enumerative way. The thesis was not a formal statement and thus did not allow for a formal proof, but support was given by examples of a number of different learning criteria that can be learned enumeratively.

Building on recent formalizations of learning criteria, we are now able to formalize Wiehagen's Thesis. We prove the thesis for a wide range of learning criteria, including many popular criteria from the literature. We also show the limitations of the thesis by giving four learning criteria for which the thesis does not hold (and, in two cases, was probably not meant to hold). Beyond the original formulation of the thesis, we also prove stronger versions which allow for many corollaries relating to strongly decisive and conservative learning.

BibTeX - Entry

@InProceedings{ktzing:LIPIcs:2014:4482,
  author =	{Timo K{\"o}tzing},
  title =	{{A Solution to Wiehagen's Thesis}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{494--505},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4482},
  URN =		{urn:nbn:de:0030-drops-44823},
  doi =		{10.4230/LIPIcs.STACS.2014.494},
  annote =	{Keywords: Algorithmic Learning Theory, Wiehagen's Thesis, Enumeration Learning}
}

Keywords: Algorithmic Learning Theory, Wiehagen's Thesis, Enumeration Learning
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI