Recursive teaching dimension, VC-dimension and sample compression.
Thorsten DoliwaGaojian FanHans Ulrich SimonSandra ZillesPublished in: J. Mach. Learn. Res. (2014)
Keyphrases
- vc dimension
- teaching dimension
- concept classes
- sample size
- compression scheme
- concept class
- vapnik chervonenkis dimension
- upper bound
- sample complexity
- lower bound
- image compression
- compression ratio
- data compression
- decision lists
- learning machines
- learning theory
- compression algorithm
- dnf formulas
- target function
- random sampling
- model selection
- worst case
- pac learning
- mistake bound
- efficient learning
- inductive inference
- machine learning
- supervised learning
- uniform distribution
- membership queries
- machine learning algorithms
- special case
- decision trees
- learning algorithm