TY - JOUR
T1 - VC-dimensions of random function classes
AU - Ycart, Bernard
AU - Ratsaby, Joel
PY - 2008
Y1 - 2008
N2 - For any class of binary functions on [n] = {1,..., n} a classical result by Sauer states a sufficient condition for its VC-dimension to be at least d: its cardinality should be at least O(nd-1). A necessary condition is that its cardinality be at least 2d (which is O(1) with respect to n). How does the size of a 'typical' class of VC-dimension d compare to these two extreme thresholds? To answer this, we consider classes generated randomly by two methods, repeated biased coin flips on the n-dimensional hypercube or uniform sampling over the space of all possible classes of cardinality k on [n]. As it turns out, the typical behavior of such classes is much more similar to the necessary condition; the cardinality k need only be larger than a threshold of 2d for its VC-dimension to be at least d with high probability. If its expected size is greater than a threshold of O(log n) (which is still significantly smaller than the sufficient size of O(nd-1)) then it shatters every set of size d with high probability. The behavior in the neighborhood of these thresholds is described by the asymptotic probability distribution of the VC-dimension and of the largest d such that all sets of size d are shattered.
AB - For any class of binary functions on [n] = {1,..., n} a classical result by Sauer states a sufficient condition for its VC-dimension to be at least d: its cardinality should be at least O(nd-1). A necessary condition is that its cardinality be at least 2d (which is O(1) with respect to n). How does the size of a 'typical' class of VC-dimension d compare to these two extreme thresholds? To answer this, we consider classes generated randomly by two methods, repeated biased coin flips on the n-dimensional hypercube or uniform sampling over the space of all possible classes of cardinality k on [n]. As it turns out, the typical behavior of such classes is much more similar to the necessary condition; the cardinality k need only be larger than a threshold of 2d for its VC-dimension to be at least d with high probability. If its expected size is greater than a threshold of O(log n) (which is still significantly smaller than the sufficient size of O(nd-1)) then it shatters every set of size d with high probability. The behavior in the neighborhood of these thresholds is described by the asymptotic probability distribution of the VC-dimension and of the largest d such that all sets of size d are shattered.
KW - Poisson approximation
KW - Random binary functions
KW - Vapnik-Chervonenkis dimension
UR - http://www.scopus.com/inward/record.url?scp=45849147344&partnerID=8YFLogxK
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:45849147344
SN - 1462-7264
VL - 10
SP - 113
EP - 128
JO - Discrete Mathematics and Theoretical Computer Science
JF - Discrete Mathematics and Theoretical Computer Science
IS - 1
ER -