Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution
Nader H. BshoutyJeffrey C. JacksonChristino TamonPublished in: Electron. Colloquium Comput. Complex. (1998)
Keyphrases
- uniform distribution
- pac learning
- membership queries
- boolean functions
- efficient learning
- agnostic learning
- target concept
- exact learning
- computational learning theory
- dnf formulas
- concept classes
- concept class
- equivalence queries
- learning algorithm
- remains np hard
- monotone dnf
- monotone boolean functions
- attribute efficient learning
- version space
- term dnf
- mistake bound
- decision lists
- statistical queries
- pac model
- learning theory
- upper bound
- monotone dnf formulas
- lower bound