Paper Info
Title
VC Dimension Bounds for Analytic Algebraic Computations
Abstract
We study the Vapnik-Chervonenkis dimension of concept classes that are defined by computer programs using analytic algebraic functionals (Nash operators) as primitives. Such bounds are of interest in learning theory because of the fundamental role the Vapnik-Chervonenkis dimension plays in characterizing the sample complexity required to learn concept classes. We strengthen previous results by Goldberg and Jerrum giving upper bounds on the VC dimension of concept classes in which the membership test for whether an input belongs to a concept in the class can be performed either by an algebraic computation tree or by an algebraic circuit containing analytic algebraic gates. These new bounds are polynomial both in the height of the tree and in the depth of the circuit. This means in particular that VC dimension of computer programs using Nash operators is polynomial not only in the sequential complexity but also in the parallel complexity what ensures polynomial VC dimension for classes of concepts whose membership test can be defined by well-parallelizable sequential exponential time algorithms using analytic algebraic operators.
Year
DOI
Venue
2008
10.1007/978-3-540-69733-6_7
COCOON
Keywords
Field
DocType
concept class,analytic algebraic computations,computer program,nash operator,algebraic computation tree,analytic algebraic gate,vc dimension bounds,analytic algebraic functionals,algebraic circuit,vapnik-chervonenkis dimension,membership test,vc dimension,algebraic function,upper bound,learning theory
Discrete mathematics,Combinatorics,VC dimension,Dimension of an algebraic variety,Function field of an algebraic variety,Polynomial,Algebraic cycle,Algebraic function,Real algebraic geometry,Algebraic geometry and analytic geometry,Mathematics
Conference
Volume
ISSN
Citations 
5092
0302-9743
1
PageRank 
References 
Authors
0.37
8
3
Name
Order
Citations
PageRank
Josè L. Montaña18215.50
Luis Miguel Pardo214115.63
Mar Callau321.05