PAC learning, VC dimension, and the arithmetic hierarchy

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

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

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

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

Cited In (3)

• Counting extensional differences in BC-learning
• Learning theory in the arithmetic hierarchy. II.
• Computable PAC learning of continuous features

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)