Exact learning of DNF formulas using DNF hypotheses
From MaRDI portal
Publication:5916223
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
Algorithms; Boolean functions; Computational learning theory; DNF; Complexity theory; Certificates; Disjunctive normal form
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
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