Malicious Omissions and Errors in Answers to Membership Queries.
Dana AngluinMartins KrikisRobert H. SloanGyörgy TuránPublished in: Mach. Learn. (1997)
Keyphrases
- membership queries
- exact learning
- dnf formulas
- uniform distribution
- query complexity
- boolean functions
- pac learning
- learning algorithm
- equivalence queries
- read once formulas
- efficient learning
- agnostic learning
- monotone dnf
- target concept
- concept class
- dnf formulae
- remains np hard
- membership and equivalence queries
- classification noise
- concept classes
- lower bound
- monotone dnf formulas
- decision trees