Exact VC-dimension of Boolean monomials

DOI10.1016/0020-0190(96)00084-1MaRDI QIDQ1847362zbMATH OpenOpenAlexFDO

Authors Thomas Natschläger, Michael Schmitt

Publication date 24 June 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(96)00084-1

zbMATH Keywords

monotone monomials

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• The Vapnik-Chervonenkis dimension of decision trees with bounded rank
• The VC-dimension of visibility on the boundary of monotone polygons
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
• On the VC-dimension and boolean functions with long runs
• Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete

Cites work

• A general lower bound on the number of examples needed for learning
• A theory of the learnable
• scientific article; zbMATH DE number 53984 (Why is no real title available?)
• Learnability and the Vapnik-Chervonenkis dimension
• Probably Approximate Learning of Sets and Functions

Cited in

(6)

• The Vapnik-Chervonenkis dimension of decision trees with bounded rank
• The capacity of monotonic functions
• Rivest-Vuillemin conjecture is true for monotone Boolean functions with twelve variables
• On the VC-dimension and boolean functions with long runs
• Neural Networks with Local Receptive Fields and Superlinear VC Dimension
• VE dimension induced by Bayesian networks over the Boolean domain

This page was built for publication: Exact VC-dimension of Boolean monomials

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