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

computational learning theoryFourier analysismonotone Boolean function

Mathematics Subject Classification ID

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

Review text

Learning polynomial-time disjunctive normal formulas from random samples is an open problem in learning theory, even with the uniform distribution. A special case is to learn monotone disjunctive normal formulas under the uniform distribution, which is the topic considered in this paper. By studying Fourier properties of monotone functions, the authors give a polynomial-time algorithm to solve an average-case version of this problem for learning monotone disjunctive normal formulas.

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

• 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
• 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?)
• 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

(11)

• On using the Fourier transform to learn disjoint DNF
• On learning monotone DNF formulae under uniform distributions
• Exact learning from an honest teacher that answers membership queries
• On learning random DNF formulas under the uniform distribution
• Learning Monotone Decision Trees in Polynomial Time
• Learning Random Monotone DNF
• scientific article; zbMATH DE number 1263197 (Why is no real title available?)
• scientific article; zbMATH DE number 1301800 (Why is no real title available?)
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Distributional PAC-learning from Nisan's natural proofs
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier

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)