More efficient PAC-learning of DNF with membership queries under the uniform distribution

DOI10.1016/j.jcss.2003.10.002zbMath1072.68087OpenAlexW2075412780MaRDI QIDQ1878685

Christino Tamon, Jeffrey C. Jackson, Nader H. Bshouty

Publication date: 8 September 2004

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.2003.10.002

zbMATH Keywords

disjunctive normal form

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (13)

On approximating weighted sums with exponentially many terms ⋮ On learning monotone DNF under product distributions ⋮ Learning functions of \(k\) relevant variables ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Learning intersections and thresholds of halfspaces ⋮ Approximate location of relevant variables under the crossover distribution. ⋮ Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions ⋮ Preserving Randomness for Adaptive Algorithms ⋮ On the Fourier spectrum of symmetric Boolean functions ⋮ Improved MCMC sampling methods for estimating weighted sums in Winnow with application to DNF learning ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Learning DNF from random walks

Cites Work

• Unnamed Item
• Unnamed Item
• Attribute-efficient learning in query and mistake-bound models
• Modern cryptography, probabilistic proofs and pseudo-randomness
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• A theory of the learnable
• Learning read-once formulas with queries
• Learning Decision Trees Using the Fourier Spectrum

This page was built for publication: More efficient PAC-learning of DNF with membership queries under the uniform distribution