PAC learning, VC dimension, and the arithmetic hierarchy

DOI10.1007/S00153-015-0445-8MaRDI QIDQ892140zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Wesley Calvert

Publication date 18 November 2015

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

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

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)

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.

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

Cites work

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

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

Describes a project that uses

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)