Learning random monotone DNF

DOI10.1016/J.DAM.2010.08.022MaRDI QIDQ628302zbMATH OpenOpenAlexFDO

Authors Jeffrey Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan

Publication date 10 March 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.08.022

zbMATH Keywords

Fourier analysiscomputational learning theorymonotone Boolean function

Mathematics Subject Classification ID

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

Recommendations

• Learning Random Monotone DNF
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• On learning random DNF formulas under the uniform distribution
• scientific article; zbMATH DE number 1804125
• Exact learning of random DNF over the uniform distribution

Cites work

• scientific article; zbMATH DE number 1301800 (Why is no real title available?)
• scientific article; zbMATH DE number 1966606 (Why is no real title available?)
• scientific article; zbMATH DE number 774007 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A theory of the learnable
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Computational limitations on learning from examples
• Constant depth circuits, Fourier transform, and learnability
• Exact learning of random DNF over the uniform distribution
• Hardness of approximate two-level logic minimization and PAC learning with membership queries
• Learning Boolean formulas
• Learning Decision Trees Using the Fourier Spectrum
• Learning monotone log-term DNF formulas under the uniform distribution
• Learning random log-depth decision trees under the uniform distribution.
• On learning monotone DNF formulae under uniform distributions
• On learning monotone DNF under product distributions
• On learning random DNF formulas under the uniform distribution
• On the Fourier spectrum of monotone functions
• On the learnability of disjunctive normal form formulas
• On the noise sensitivity of monotone functions
• The complexity of properly learning simple concept classes
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis

Cited in

(7)

• Learning Random Monotone DNF
• Exact learning from an honest teacher that answers membership queries
• Learning Monotone Decision Trees in Polynomial Time
• On using the Fourier transform to learn disjoint DNF
• On learning monotone DNF formulae under uniform distributions
• On learning random DNF formulas under the uniform distribution
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Learning random monotone DNF

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