PAC Learning, VC Dimension, and the Arithmetic Hierarchy

Abstract

We compute that the index set of PAC-learnable concept classes is m-complete ^0_3 within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumerations of computable ^0_1 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.

Tasks

Reproductions