DNF are teachable in the average case

DOI10.1007/S10994-007-5007-9zbMATH Open1470.68057OpenAlexW2036554083MaRDI QIDQ1009216FDOQ1009216

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

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

Recommendations

• DNF Are Teachable in the Average Case
• Learning Theory
• On learning random DNF formulas under the uniform distribution
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Measuring teachability using variants of the teaching dimension

zbMATH Keywords

teaching dimensionDNF formulas

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• DNF Are Teachable in the Average Case

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

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