On Ordinal VC-Dimension and Some Notions of Complexity.
Eric MartinArun SharmaFrank StephanPublished in: ALT (2003)
Keyphrases
- mind change complexity
- vc dimension
- vapnik chervonenkis dimension
- inductive inference
- vapnik chervonenkis
- upper bound
- worst case
- regular patterns
- covering numbers
- sample size
- sample complexity
- distribution free
- concept classes
- generalization bounds
- bayes net
- statistical learning theory
- lower bound
- pattern languages
- compression scheme
- pac learning
- learning machines
- concept class
- function classes
- empirical risk minimization
- pac learnability
- computational complexity
- high dimensional
- special case
- data points
- principal component analysis
- theoretical analysis
- uniform convergence
- euclidean distance
- euclidean space