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

learning theoryinductive inferencearithmetic hierarchy

Mathematics Subject Classification ID

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

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

(10)

• On the complexity of learning programs
• An algebra of human concept learning
• The IMP game: learnability, approximability and adversarial learning beyond \(\Sigma^0_1\)
• Learning theory in the arithmetic hierarchy. II.
• Classifying the arithmetical complexity of teaching models
• Computable PAC learning of continuous features
• Learning Theory and Descriptive Set Theory
• Learning families of closed sets in matroids
• Infinitary self-reference in learning theory
• 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)