DNF are teachable in the average case

DOI10.1007/s10994-007-5007-9zbMath1470.68057OpenAlexW2036554083MaRDI QIDQ1009216

Rocco A. Servedio, Andrew Wan, Homin K. Lee

Publication date: 31 March 2009

Published in: Machine Learning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10994-007-5007-9

zbMATH Keywords

teaching dimensionDNF formulas

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• Teachability in computational learning
• Learning sparse multivariate polynomials over a field with queries and counterexamples.
• Learning functions of \(k\) relevant variables
• On the complexity of teaching
• On specifying Boolean functions by labelled examples
• Witness sets for families of binary vectors
• Learning Binary Relations and Total Orders
• Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
• Vector sets for exhaustive testing of logic circuits
• Simple Learning Algorithms for Decision Trees and Multivariate Polynomials
• Learning Theory

This page was built for publication: DNF are teachable in the average case