Learning theory in the arithmetic hierarchy

DOI10.1017/JSL.2014.23MaRDI QIDQ2933682zbMATH OpenOpenAlexFDO

Authors Achilles A. Beros

Publication date 5 December 2014

Published in Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

arithmetic hierarchyinductive inferencelearning theory

Mathematics Subject Classification ID

Applications of computability and recursion theory (03D80) Computational learning theory (68Q32)

Abstract: We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity of these sets for the standard notions of finite learning, learning in the limit, behaviorally correct learning and anomalous learning in the limit. In proving the $Sigm{a}_5^0$-completeness result for behaviorally correct learning we prove a result of independent interest; if a uniformly computably enumerable family is not learnable, then for any computable learner there is a $Delt{a}_2^0$ enumeration witnessing failure.

Recommendations

• Learning theory in the arithmetic hierarchy. II.
• Learning Theory and Descriptive Set Theory
• PAC learning, VC dimension, and the arithmetic hierarchy
• Inductive inference and computable numberings
• Numberings and learnability

Cites work

• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• Language identification in the limit

Cited in

(11)

• An algebra of human concept learning
• Learning theory in the arithmetic hierarchy. II.
• Classifying the arithmetical complexity of teaching models
• Learning families of closed sets in matroids
• The IMP game: learnability, approximability and adversarial learning beyond ^0_1
• Learning Theory and Descriptive Set Theory
• Infinitary self-reference in learning theory
• On the Turing complexity of learning finite families of algebraic structures
• On the complexity of learning programs
• Computable PAC learning of continuous features
• PAC learning, VC dimension, and the arithmetic hierarchy

This page was built for publication: Learning theory in the arithmetic hierarchy

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