PAC learning, VC dimension, and the arithmetic hierarchy

DOI10.1007/s00153-015-0445-8zbMath1341.03058arXiv1406.1111OpenAlexW2120749747WikidataQ59199669 ScholiaQ59199669MaRDI QIDQ892140

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

VC dimensionindex setsmachine learning theory

Mathematics Subject Classification ID

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

Uses Software

• PRMLT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Results on learnability and the Vapnik-Chervonenkis dimension
• On the learnability of vector spaces
• Computability of Julia sets
• Effective categoricity of abelian \(p\)-groups
• Index sets for \(\Pi^0_1\) classes
• Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
• Effective categoricity of equivalence structures
• LEARNING THEORY IN THE ARITHMETIC HIERARCHY
• The isomorphism problem for computable Abelian _p-groups of bounded length
• Learnability and the Vapnik-Chervonenkis dimension
• Index sets of computable structures
• A theory of the learnable
• The Classification Problem for Compact Computable Metric Spaces
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Language identification in the limit
• Learning algebraic structures from text

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