On the VC-dimension and boolean functions with long runs

被引:2
作者
Ratsaby, Joel [1 ]
机构
[1] Ben Gurion Univ Negev, POB 653, IL-84105 Beer Sheva, Israel
关键词
Boolean functions; VC-dimension; poisson approximation;
D O I
10.1080/09720529.2007.10698116
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The Vapnik-Chervonenkis (VC) dimension and the Sauer-Shelah lemma have found applications in numerous areas including set theory, combinatorial geometry, graph theory and statistical learning theory. Estimation of the complexity of discrete structures associated with the search space of algorithms often amounts to estimating the cardinality of a simpler class which is effectively induced by some restrictive property of the search. In this paper we study the complexity of Boolean-function classes of finite VC-dimension which satisfy a local 'smoothness' property expressed as having long runs of repeated values. As in Sauer's lemma, a bound is obtained on the cardinality of such classes.
引用
收藏
页码:205 / 225
页数:21
相关论文
共 19 条
[1]   Scale-sensitive dimensions, uniform convergence, and learnability [J].
Alon, N ;
BenDavid, S ;
CesaBianchi, N ;
Haussler, D .
JOURNAL OF THE ACM, 1997, 44 (04) :615-631
[2]   ON THE DENSITY OF SETS OF VECTORS [J].
ALON, N .
DISCRETE MATHEMATICS, 1983, 46 (02) :199-202
[3]  
Anthony M., 1995, VAPNIK CHERVONENKIS, P616
[4]  
Anthony Martin, 1999, NEURAL NETWORK LEARN, V9
[5]  
Arratia R., 1990, STAT SCI, V5, P403, DOI [10.1214/ss/1177012015, DOI 10.1214/SS/1177012015]
[6]  
Barbour AD, 2001, ANN APPL PROBAB, V11, P964
[7]  
Bollobas B., 1986, COMBINATORICS SET SY
[8]   ON THE TRACE OF FINITE SETS [J].
FRANKL, P .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1983, 34 (01) :41-45
[9]  
Frankl P., 1987, SURV COMB, V123, P81
[10]   EPSILON-NETS AND SIMPLEX RANGE QUERIES [J].
HAUSSLER, D ;
WELZL, E .
DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (02) :127-151