VC Dimension Bounds for Analytic Algebraic Computations
We study the Vapnik-Chervonenkis dimension of concept classes that are defined by computer programs using analytic algebraic functional (Nash operators) as primitives. Such bounds are of interest in learning theory because of the fundamental role the VapnikChervonenkis 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 denned by well-parallelizable sequential exponential time algorithms using analytic algebraic operators.
Jose Luis Montana Luis Miguel Pardo Mar Callau
Departamento de Matematicas, Estadistica y Computation Universidad de Cantabria Departamento de Matematicas,Estadistica y Computation Universidad de Cantabria
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
62-71
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）