When Won't Membership Queries Help? (Extended Abstract)
Dana AngluinMichael KharitonovPublished in: STOC (1991)
Keyphrases
- extended abstract
- membership queries
- exact learning
- uniform distribution
- boolean functions
- dnf formulas
- learning algorithm
- target concept
- equivalence queries
- query complexity
- efficient learning
- read once formulas
- pac learning
- concept class
- agnostic learning
- monotone dnf
- concept classes
- remains np hard
- membership and equivalence queries
- dnf formulae
- multi class
- decision trees
- machine learning
- data mining