Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes.
Lunjia HuRuihan WuTianhong LiLiwei WangPublished in: CoRR (2017)
Keyphrases
- upper bound
- teaching dimension
- vc dimension
- concept classes
- concept class
- vapnik chervonenkis dimension
- lower bound
- sample complexity
- decision lists
- worst case
- sample size
- pairwise
- upper and lower bounds
- target function
- dnf formulas
- linear functions
- pac learning
- lower and upper bounds
- learning machines
- agnostic learning
- recursively enumerable
- term dnf
- statistical queries
- inductive inference
- generalization error
- learning theory
- monotone dnf
- monotone dnf formulas