Approximate polytope membership queries.
Sunil AryaGuilherme Dias da FonsecaDavid M. MountPublished in: STOC (2011)
Keyphrases
- membership queries
- exact learning
- boolean functions
- dnf formulas
- uniform distribution
- learning algorithm
- target concept
- read once formulas
- query complexity
- efficient learning
- pac learning
- equivalence queries
- agnostic learning
- concept class
- monotone dnf
- dnf formulae
- concept classes
- remains np hard
- membership and equivalence queries
- multi class
- machine learning
- classification noise
- number of queries needed