文章基本信息

标题：A Solution to Wiehagen's Thesis
本地全文：下载
作者：Timo K{\"o}tzing
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：25
页码：494-505
DOI：10.4230/LIPIcs.STACS.2014.494
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Algorithmic Learning Theory; Wiehagen's Thesis; Enumeration Learning