An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
From MaRDI portal
Publication:1384530
DOI10.1006/jcss.1997.1533zbMath0897.68051OpenAlexW2088390444MaRDI QIDQ1384530
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
Learning and adaptive systems in artificial intelligence (68T05) Parallel algorithms in computer science (68W10)
Related Items (40)
More efficient PAC-learning of DNF with membership queries under the uniform distribution ⋮ On learning monotone DNF under product distributions ⋮ PACS, simple-PAC and query learning ⋮ Learning functions of \(k\) relevant variables ⋮ Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ Exact learning from an honest teacher that answers membership queries ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ A general dimension for query learning ⋮ Learning intersections and thresholds of halfspaces ⋮ 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 ⋮ A theory of formal synthesis via inductive learning ⋮ Selection of relevant features and examples in machine learning ⋮ Learning random monotone DNF ⋮ Unnamed Item ⋮ Covert learning: how to learn with an untrusted intermediary ⋮ Reliable agnostic learning ⋮ Approximate location of relevant variables under the crossover distribution. ⋮ Towards a proof of the Fourier-entropy conjecture? ⋮ The monotone theory for the PAC-model. ⋮ Learnability of quantified formulas. ⋮ Quantum algorithms for learning and testing juntas ⋮ Pseudo-Derandomizing Learning and Approximation ⋮ Learning unions of \(\omega(1)\)-dimensional rectangles ⋮ Extremal properties of polynomial threshold functions ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ On the Fourier spectrum of symmetric Boolean functions ⋮ Exact learning of DNF formulas using DNF hypotheses ⋮ Agnostic active learning ⋮ Learning large-alphabet and analog circuits with value injection queries ⋮ Hardness of approximate two-level logic minimization and PAC learning with membership queries ⋮ Learning a circuit by injecting values ⋮ Unnamed Item ⋮ Proper learning of \(k\)-term DNF formulas from satisfying assignments ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Learning DNF from random walks ⋮ Unnamed Item ⋮ Pseudorandom Functions: Three Decades Later
Uses Software
Cites Work
- Unnamed Item
- Fast learning of \(k\)-term DNF formulas with queries.
- Occam's razor
- Learning conjunctions of Horn clauses
- Majority gates vs. general weighted threshold gates
- Composite geometric concepts and polynomial predictability
- A decision-theoretic generalization of on-line learning and an application to boosting
- When won't membership queries help?
- Boosting a weak learning algorithm by majority
- On learning visual concepts and DNF formulae
- Queries and concept learning
- On the computational power of pushdown automata
- On the computational power of depth 2 circuits with threshold and modulo gates
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions
- Constant depth circuits, Fourier transform, and learnability
- Harmonic Analysis of Polynomial Threshold Functions
- Learnability and the Vapnik-Chervonenkis dimension
- A theory of the learnable
- Learning Decision Trees Using the Fourier Spectrum
- Cryptographic hardness of distribution-specific learning
This page was built for publication: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
