More Efficient PAC-Learning of DNF with Membership Queries Under the Uniform Distribution.
Nader H. BshoutyJeffrey C. JacksonChristino TamonPublished in: COLT (1999)
Keyphrases
- uniform distribution
- pac learning
- membership queries
- boolean functions
- computational learning theory
- efficient learning
- agnostic learning
- target concept
- exact learning
- dnf formulas
- monotone boolean functions
- concept classes
- equivalence queries
- version space
- monotone dnf
- term dnf
- attribute efficient learning
- remains np hard
- mistake bound
- statistical queries
- concept class
- learning theory
- learning algorithm
- decision lists
- monotone dnf formulas
- pac model
- classification noise
- disjunctive normal form
- efficiently learnable
- supervised learning
- decision trees