The Vapnik-Chervonenkis dimension of decision trees with bounded rank

DOI10.1016/0020-0190(91)90109-UzbMath0735.68072WikidataQ127946119 ScholiaQ127946119MaRDI QIDQ1182084

Hans Ulrich Simon

Publication date: 27 June 1992

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

zbMATH Keywords

sample complexityboolean concept learning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Combinatorics in computer science (68R05)

Related Items

Cellular tree classifiers ⋮ On multivariate randomized classification trees: \(l_0\)-based sparsity, VC dimension and decomposition methods

Cites Work

• Occam's razor
• Some special Vapnik-Chervonenkis classes
• Learning decision trees from random examples
• A general lower bound on the number of examples needed for learning
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Necessary and Sufficient Conditions for the Uniform Convergence of Means to their Expectations
• Enumeration of Seven-Argument Threshold Functions