An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
From MaRDI portal
(Redirected from Publication:1384530)
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
Cites work
- scientific article; zbMATH DE number 1256690 (Why is no real title available?)
- A decision-theoretic generalization of on-line learning and an application to boosting
- A theory of the learnable
- Boosting a weak learning algorithm by majority
- Composite geometric concepts and polynomial predictability
- Constant depth circuits, Fourier transform, and learnability
- Cryptographic hardness of distribution-specific learning
- Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions
- Fast learning of \(k\)-term DNF formulas with queries.
- Harmonic Analysis of Polynomial Threshold Functions
- Learnability and the Vapnik-Chervonenkis dimension
- Learning Decision Trees Using the Fourier Spectrum
- Learning conjunctions of Horn clauses
- Majority gates vs. general weighted threshold gates
- Occam's razor
- On learning visual concepts and DNF formulae
- On the computational power of depth 2 circuits with threshold and modulo gates
- On the computational power of pushdown automata
- Queries and concept learning
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- When won't membership queries help?
Cited in
(44)- A subexponential exact learning algorithm for DNF using equivalence queries
- Pseudo-derandomizing learning and approximation
- Quantum hardness of learning shallow classical circuits
- On PAC learning algorithms for rich Boolean function classes
- Learning intersections and thresholds of halfspaces
- Learning random monotone DNF
- Robust \(k\)-DNF learning via inductive belief merging.
- Hardness of approximate two-level logic minimization and PAC learning with membership queries
- A theory of formal synthesis via inductive learning
- Reliable agnostic learning
- Extremal properties of polynomial threshold functions
- Optimal quantum sample complexity of learning algorithms
- Exact learning from an honest teacher that answers membership queries
- Lifting uniform learners via distributional decomposition
- Learning unions of \(\omega(1)\)-dimensional rectangles
- Approximate learning of limit-average automata
- Learning DNF from random walks
- On learning monotone DNF under product distributions
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- Learning large-alphabet and analog circuits with value injection queries
- On Exact Learning Monotone DNF from Membership Queries
- More efficient PAC-learning of DNF with membership queries under the uniform distribution
- Approximate location of relevant variables under the crossover distribution.
- An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
- The monotone theory for the PAC-model.
- Learning a circuit by injecting values
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Selection of relevant features and examples in machine learning
- On the Fourier spectrum of symmetric Boolean functions
- Learnability of quantified formulas.
- The bounded injury priority method and the learnability of unions of rectangles
- \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
- Quantum algorithms for learning and testing juntas
- A general dimension for query learning
- Pseudorandom functions: three decades later
- Towards a proof of the Fourier-entropy conjecture?
- Agnostic active learning
- Learning functions of \(k\) relevant variables
- Exact learning of DNF formulas using DNF hypotheses
- Private data release via learning thresholds
- PACS, simple-PAC and query learning
- Covert learning: how to learn with an untrusted intermediary
- Proper learning of \(k\)-term DNF formulas from satisfying assignments
- Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
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)
