Combining models of approximation with partial learning

DOI10.1007/978-3-319-24486-0_4MaRDI QIDQ2835617zbMATH OpenOpenAlexFDO

Authors Ziyuan Gao, Sandra Zilles, Frank Stephan

Publication date 30 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.01215

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Computational learning theory (68Q32) Formal languages and automata (68Q45)

Abstract: In Gold's framework of inductive inference, the model of partial learning requires the learner to output exactly one correct index for the target object and only the target object infinitely often. Since infinitely many of the learner's hypotheses may be incorrect, it is not obvious whether a partial learner can be modifed to "approximate" the target object. Fulk and Jain (Approximate inference and scientific method. Information and Computation 114(2):179--191, 1994) introduced a model of approximate learning of recursive functions. The present work extends their research and solves an open problem of Fulk and Jain by showing that there is a learner which approximates and partially identifies every recursive function by outputting a sequence of hypotheses which, in addition, are also almost all finite variants of the target function. The subsequent study is dedicated to the question how these findings generalise to the learning of r.e. languages from positive data. Here three variants of approximate learning will be introduced and investigated with respect to the question whether they can be combined with partial learning. Following the line of Fulk and Jain's research, further investigations provide conditions under which partial language learners can eventually output only finite variants of the target language. The combinabilities of other partial learning criteria will also be briefly studied.

Recommendations

• A survey on recent results on partial learning
• Confident and Consistent Partial Learning of Recursive Functions
• Confident and consistent partial learning of recursive functions
• Partial learning of recursively enumerable languages
• Partial learning of recursively enumerable languages

Cites work

• Approximate inference and scientific method
• Belief revision in the service of scientific discovery
• Comparison of identification criteria for machine inductive inference
• scientific article; zbMATH DE number 3932417 (Why is no real title available?)
• Inductive inference of formal languages from positive data
• Language identification in the limit
• Learning and classifying
• Learning strategies
• On conservative learning of recursively enumerable languages
• Partial learning of recursively enumerable languages

Cited in

(2)

• Intrinsic complexity of partial learning
• Intrinsic complexity of partial learning

This page was built for publication: Combining models of approximation with partial learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835617)