PAC learning, VC dimension, and the arithmetic hierarchy.
Wesley CalvertPublished in: Arch. Math. Log. (2015)
Keyphrases
- pac learning
- vc dimension
- sample complexity
- upper bound
- computational learning theory
- concept classes
- sample size
- lower bound
- pac learnability
- inductive inference
- worst case
- theoretical analysis
- statistical queries
- decision lists
- instance space
- mistake bound
- concept class
- learning problems
- agnostic learning
- supervised learning
- target concept
- compression scheme
- learning algorithm
- active learning
- euclidean space
- pairwise
- uniform distribution
- generalization error
- learning theory
- data compression