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