Exact learning of DNF formulas using DNF hypotheses

DOI10.1016/j.jcss.2004.10.001zbMath1073.68035OpenAlexW2050166670MaRDI QIDQ5916223

Lisa Hellerstein, Vijay Raghavan

Publication date: 13 June 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.10.001

zbMATH Keywords

AlgorithmsBoolean functionsComputational learning theoryDNFComplexity theoryCertificatesDisjunctive normal form

Mathematics Subject Classification ID

Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Boolean functions (06E30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Learning conditional preference networks ⋮ A Canonical Form for Testing Boolean Function Properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the limits of proper learnability of subclasses of DNF formulas
• Fast learning of \(k\)-term DNF formulas with queries.
• On the number of prime implicants
• Complexity theoretic hardness results for query learning
• Simple learning algorithms using divide and conquer
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• A simple algorithm for learning O(log n)-term DNF
• Galois theory for minors of finite functions
• On limited nondeterminism and the complexity of the V-C dimension
• On generalized constraints and certificates
• A subexponential exact learning algorithm for DNF using equivalence queries
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• When won't membership queries help?
• Asking questions to minimize errors
• Equational characterizations of Boolean function classes
• Queries and concept learning
• Exact learning Boolean functions via the monotone theory
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Constant depth circuits, Fourier transform, and learnability
• 10.1162/153244304322972676
• Bounds to Complexities of Networks for Sorting and for Switching
• How many queries are needed to learn?
• Exact learning of DNF formulas using DNF hypotheses

This page was built for publication: Exact learning of DNF formulas using DNF hypotheses