Learnability of DNF with representation-specific queries

DOI10.1145/2422436.2422441MaRDI QIDQ2986856zbMATH OpenOpenAlexFDO

Authors Liu Yang, Jaime G. Carbonell, Avrim Blum

Publication date 16 May 2017

Published in Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2422436.2422441

zbMATH Keywords

efficient learninglearning DNFPAC learnabilityqueries

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Recommendations

• Exact learning of DNF formulas using DNF hypotheses
• Algorithmic Learning Theory
• scientific article; zbMATH DE number 1256728
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• More efficient PAC-learning of DNF with membership queries under the uniform distribution

Cites work

• A model of interactive teaching
• A theory of goal-oriented communication
• A theory of the learnable
• Algorithmic Learning Theory
• Derandomizing polynomial identity tests means proving circuit lower bounds
• scientific article; zbMATH DE number 3154781 (Why is no real title available?)
• scientific article; zbMATH DE number 67625 (Why is no real title available?)
• scientific article; zbMATH DE number 67631 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Learning from different teachers
• Measuring teachability using variants of the teaching dimension
• Models of cooperative teaching and learning
• Occam's razor
• On specifying Boolean functions by labelled examples
• On the complexity of teaching
• On the limits of efficient teachability
• On the power of inductive inference from good examples
• Pseudorandom generators for space-bounded computation
• Recent Developments in Algorithmic Teaching
• Teachability in computational learning
• Teaching a smarter learner.
• Teaching Randomized Learners

Cited in

(11)

• Conjunctions of unate DNF formulas: Learning and structure
• A subexponential exact learning algorithm for DNF using equivalence queries
• More efficient PAC-learning of DNF with membership queries under the uniform distribution
• scientific article; zbMATH DE number 5957469 (Why is no real title available?)
• scientific article; zbMATH DE number 1256727 (Why is no real title available?)
• scientific article; zbMATH DE number 1256728 (Why is no real title available?)
• scientific article; zbMATH DE number 2090015 (Why is no real title available?)
• Algorithmic Learning Theory
• Learning Theory
• On the limits of proper learnability of subclasses of DNF formulas
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier

This page was built for publication: Learnability of DNF with representation-specific queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986856)