On the limits of proper learnability of subclasses of DNF formulas

DOI10.1007/BF00114011MaRDI QIDQ676245zbMATH OpenOpenAlexFDO

Authors Krishnan Pillaipakkamnatt, Vijay Raghavan

Publication date 16 March 1997

Published in Machine Learning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00114011

zbMATH Keywords

proper learningmodels of learning-exactPAC model

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• scientific article; zbMATH DE number 4092808
• scientific article; zbMATH DE number 1256728
• Proper learning of \(k\)-term DNF formulas from satisfying assignments
• Exact learning of DNF formulas using DNF hypotheses
• Learnability of DNF with representation-specific queries
• A subexponential exact learning algorithm for DNF using equivalence queries
• scientific article; zbMATH DE number 2077165
• scientific article; zbMATH DE number 522871
• scientific article; zbMATH DE number 1301800
• On the learnability of disjunctive normal form formulas

Cites work

• scientific article; zbMATH DE number 67615 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256690 (Why is no real title available?)
• scientific article; zbMATH DE number 1263194 (Why is no real title available?)
• A theory of the learnable
• Asking questions to minimize errors
• Computational limitations on learning from examples
• Fast learning of \(k\)-term DNF formulas with queries.
• Learning read-once formulas with queries
• Read-twice DNF formulas are properly learnable
• When won't membership queries help?

Cited in

(15)

• Exact learning of DNF formulas using DNF hypotheses
• Integer equal flows
• On learning formulas in the limit and with assurance.
• An optimal algorithm for proper learning of unions of two rectangles with queries
• The learnability of unions of two rectangles in the two-dimensional discretized space
• A subexponential exact learning algorithm for DNF using equivalence queries
• scientific article; zbMATH DE number 5957469 (Why is no real title available?)
• Learning conditional preference networks
• scientific article; zbMATH DE number 2089369 (Why is no real title available?)
• Proper learning of \(k\)-term DNF formulas from satisfying assignments
• Self-improved gaps almost everywhere for the agnostic approximation of monomials
• 10.1162/153244304322972676
• The complexity of properly learning simple concept classes
• Learning Theory
• The learnability of exclusive-or expansions based on monotone DNF formulas

This page was built for publication: On the limits of proper learnability of subclasses of DNF formulas

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