Exact learning of DNF formulas using DNF hypotheses

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

Vijay Raghavan, Lisa Hellerstein

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

Algorithms; Boolean functions; Computational learning theory; DNF; Complexity theory; Certificates; Disjunctive normal form

Mathematics Subject Classification ID

68Q32: Computational learning theory

68Q25: Analysis of algorithms and problem complexity

68T05: Learning and adaptive systems in artificial intelligence

06E30: Boolean functions

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

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