PAC learning, VC dimension, and the arithmetic hierarchy

DOI10.1007/S00153-015-0445-8zbMATH Open1341.03058DBLPjournals/aml/Calvert15arXiv1406.1111OpenAlexW2120749747WikidataQ59199669 ScholiaQ59199669MaRDI QIDQ892140FDOQ892140

Authors: Wesley Calvert 

Publication date: 18 November 2015

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Abstract: We compute that the index set of PAC-learnable concept classes is $m$-complete $Sigm{a}_3^0$ within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumerations of computable $P{i}_1^0$ classes, in a sense made precise here. This family of concept classes is sufficient to cover all standard examples, and also has the property that PAC learnability is equivalent to finite VC dimension.

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

Recommendations

• Higher dimensional PAC learning
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
• Results on learnability and the Vapnik-Chervonenkis dimension
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete

zbMATH Keywords

index setsVC dimensionmachine learning theory

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32) Theory of numerations, effectively presented structures (03D45) Applications of computability and recursion theory (03D80)

Cites Work

• Pattern recognition and machine learning.
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Learnability and the Vapnik-Chervonenkis dimension
• Title not available (Why is that?)
• Title not available (Why is that?)
• Language identification in the limit
• The isomorphism problem for computable Abelian _p-groups of bounded length
• Index sets of computable structures
• A theory of the learnable
• Title not available (Why is that?)
• Title not available (Why is that?)
• Results on learnability and the Vapnik-Chervonenkis dimension
• Effective categoricity of abelian \(p\)-groups
• Effective categoricity of equivalence structures
• Title not available (Why is that?)
• Computability of Julia sets
• Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
• Index sets for \(\Pi^0_1\) classes
• The classification problem for compact computable metric spaces
• Learning algebraic structures from text
• On the learnability of vector spaces
• Learning theory in the arithmetic hierarchy
• Introduction to the philosophy and mathematics of algorithmic learning theory

Cited In (7)

• Counting extensional differences in BC-learning
• Higher dimensional PAC learning
• Learning theory in the arithmetic hierarchy. II.
• Computable PAC learning of continuous features
• Learning theory in the arithmetic hierarchy
• PAC learnability of a concept class under non-atomic measures: a problem by Vidyasagar
• PAC learnability under non-atomic measures: a problem by Vidyasagar

Uses Software

• PRMLT

This page was built for publication: PAC learning, VC dimension, and the arithmetic hierarchy

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