Identifying Codes in Hereditary Classes of Graphs and VC-Dimension.
Nicolas BousquetAurélie LagoutteZhentao LiAline ParreauStéphan ThomasséPublished in: SIAM J. Discret. Math. (2015)
Keyphrases
- vc dimension
- pac learnability
- vapnik chervonenkis
- sample size
- sample complexity
- upper bound
- covering numbers
- concept classes
- statistical learning theory
- lower bound
- inductive inference
- function classes
- vapnik chervonenkis dimension
- generalization bounds
- efficiently learnable
- concept class
- uniform convergence
- worst case
- pac learning
- efficient learning
- compression scheme
- learning problems
- data sets