Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension
University of California, Santa Cruz, Computer Research Laboratory, 1991 - Computers - 14 pages
Abstract: "Let V [subset] [0,1][superscript n] have Vapnik- Chervonenkis dimension d. Let M(k/n, V) denote the cardinality of the largest W [subset] V such that any two distinct vectors in W differ on at least k indices. We show that M(k/n, V) [
What people are saying - Write a review
We haven't found any reviews in the usual places.
Bayes risk Bernoulli random variable Boolean n-Cube bound of Theorem Chazelle claim Combinatorics Computational Geometry Computational Learning Theory Computer Research Laboratory David Haussler David Pollard direct the edges distance k/n Dudley's result e-separated subset eliminate all vectors empirical processes equivalence class graph Hence index sequence indices is shattered indices t'i integer Journal of Combinatorial Lemma 3 implies Let V C 0,1 machine learning Manfred Warmuth Morgan Kaufmann n-cube induced natural number non-trivial shift number of edges number of indices outdegree P(Bm P(vim Peter Frankl Phil Long posterior probabilities probability distribution Proc proof of Theorem pseudodimension R. M. Dudley random without replacement remaining vectors San Mateo Santa Cruz Sauer/VC lemma Lemma selected at random selected uniformly set of edges sets of vectors shattered by 5,(V Si(E Si(V Siy(v sphere packing numbers theorems for empirical uniformly at random upper bound Vapnik Vapnik-Chervonenkis dimension Welzl Workshop on Computational