DNF are teachable in the average case

DOI10.1007/S10994-007-5007-9MaRDI QIDQ1009216zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

teaching dimensionDNF formulas

Mathematics Subject Classification ID

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

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

Cites work

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

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)