VC-dimensions of random function classes

MaRDI QIDQ5387734zbMATH OpenFDO

Authors Bernard Ycart, Joel Ratsaby

Publication date 27 May 2008

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/464/0.html

zbMATH Keywords

Poisson approximationVC dimensionuniform samplingVapnik Chervonenkis dimensionbiased coin flipsrandom binary functions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Random graphs (graph-theoretic aspects) (05C80) Distribution theory (60Exx)

Recommendations

• Density and dimension
• The Vapnik-Chervonenkis dimension of a random graph
• VC bounds on the cardinality of nearly orthogonal function classes
• Some new maximum VC classes
• On the VC-dimension and boolean functions with long runs

Cited in

(10)

• VC dimension and a union theorem for set systems
• The VC dimension of k‐uniform random hypergraphs
• VC bounds on the cardinality of nearly orthogonal function classes
• On the complexity of binary samples
• The shattering dimension of sets of linear functionals.
• On the complexity of constrained VC-classes
• The VC-dimension of a class of multiples of the primes and a connection to AdaBoost
• Some new maximum VC classes
• On the VC-dimension and boolean functions with long runs
• The Vapnik-Chervonenkis dimension of a random graph

This page was built for publication: VC-dimensions of random function classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387734)