PAC learning, VC dimension, and the arithmetic hierarchy

Archive for Mathematical Logic 54 (7-8):871-883 (2015)
  Copy   BIBTEX


We compute that the index set of PAC-learnable concept classes is m-complete Σ30\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^{0}_{3}}$$\end{document} within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumerations of computable Π10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^{0}_{1}}$$\end{document} 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.



    Upload a copy of this work     Papers currently archived: 86,403

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
More on Generic Dimension Groups.Philip Scowcroft - 2015 - Notre Dame Journal of Formal Logic 56 (4):511-553.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Poincare on Mathematics, Intuition and the Foundations of Science.Janet Folina - 1994 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1994:217 - 226.
Multifunction algebras and the provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
Fragments of arithmetic.Wilfried Sieg - 1985 - Annals of Pure and Applied Logic 28 (1):33-71.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Strengths and Weaknesses of LH Arithmetic.Chris Pollett & Randall Pruim - 2002 - Mathematical Logic Quarterly 48 (2):221-243.
Admissible closures of polynomial time computable arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5):643-660.
A constructive analysis of learning in Peano Arithmetic.Federico Aschieri - 2012 - Annals of Pure and Applied Logic 163 (11):1448-1470.
On two questions about feasibly constructive arithmetic.Morteza Moniri - 2003 - Mathematical Logic Quarterly 49 (4):425.


Added to PP

17 (#711,220)

6 months
1 (#868,485)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations