An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
From MaRDI portal
Publication:1384530
DOI10.1006/JCSS.1997.1533zbMATH Open0897.68051OpenAlexW2088390444MaRDI QIDQ1384530FDOQ1384530
Publication date: 4 August 1998
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1997.1533
Recommendations
- More efficient PAC-learning of DNF with membership queries under the uniform distribution
- An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
- Algorithmic Learning Theory
- On Exact Learning Monotone DNF from Membership Queries
- scientific article; zbMATH DE number 2077165
- On learning random DNF formulas under the uniform distribution
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Exact learning of random DNF over the uniform distribution
- scientific article; zbMATH DE number 1256727
- On learning monotone DNF formulae under uniform distributions
Learning and adaptive systems in artificial intelligence (68T05) Parallel algorithms in computer science (68W10)
Cites Work
- A decision-theoretic generalization of on-line learning and an application to boosting
- Learnability and the Vapnik-Chervonenkis dimension
- Learning Decision Trees Using the Fourier Spectrum
- Learning conjunctions of Horn clauses
- Queries and concept learning
- Boosting a weak learning algorithm by majority
- On the computational power of pushdown automata
- Constant depth circuits, Fourier transform, and learnability
- Harmonic Analysis of Polynomial Threshold Functions
- A theory of the learnable
- Majority gates vs. general weighted threshold gates
- On the computational power of depth 2 circuits with threshold and modulo gates
- Occam's razor
- Composite geometric concepts and polynomial predictability
- When won't membership queries help?
- Fast learning of \(k\)-term DNF formulas with queries.
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- Cryptographic hardness of distribution-specific learning
- Title not available (Why is that?)
- Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions
- On learning visual concepts and DNF formulae
Cited In (44)
- Learning DNF from random walks
- Quantum Hardness of Learning Shallow Classical Circuits
- Learnability of quantified formulas.
- Extremal properties of polynomial threshold functions
- Pseudorandom Functions: Three Decades Later
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- The bounded injury priority method and the learnability of unions of rectangles
- Quantum algorithms for learning and testing juntas
- Title not available (Why is that?)
- Learning a circuit by injecting values
- A subexponential exact learning algorithm for DNF using equivalence queries
- Learning large-alphabet and analog circuits with value injection queries
- On Exact Learning Monotone DNF from Membership Queries
- A theory of formal synthesis via inductive learning
- Approximate location of relevant variables under the crossover distribution.
- The monotone theory for the PAC-model.
- PACS, simple-PAC and query learning
- Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
- Proper learning of \(k\)-term DNF formulas from satisfying assignments
- Reliable agnostic learning
- Exact learning from an honest teacher that answers membership queries
- Towards a proof of the Fourier-entropy conjecture?
- Learning functions of \(k\) relevant variables
- Hardness of approximate two-level logic minimization and PAC learning with membership queries
- Learning random monotone DNF
- Title not available (Why is that?)
- \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
- Pseudo-Derandomizing Learning and Approximation
- More efficient PAC-learning of DNF with membership queries under the uniform distribution
- On the Fourier spectrum of symmetric Boolean functions
- On PAC learning algorithms for rich Boolean function classes
- Title not available (Why is that?)
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
- Lifting uniform learners via distributional decomposition
- Covert learning: how to learn with an untrusted intermediary
- Agnostic active learning
- Selection of relevant features and examples in machine learning
- A general dimension for query learning
- Learning intersections and thresholds of halfspaces
- On learning monotone DNF under product distributions
- Learning unions of \(\omega(1)\)-dimensional rectangles
- An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
- Exact learning of DNF formulas using DNF hypotheses
Uses Software
This page was built for publication: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1384530)
