On Learning Random DNF Formulas Under the Uniform Distribution.
Jeffrey C. JacksonRocco A. ServedioPublished in: Theory Comput. (2006)
Keyphrases
- uniform distribution
- term dnf
- learning dnf
- dnf formulas
- membership queries
- pac learning
- pac model
- boolean functions
- exact learning
- statistical queries
- decision lists
- agnostic learning
- monotone dnf
- concept learning
- dnf formulae
- learning algorithm
- target concept
- learning problems
- machine learning
- concept class
- supervised learning
- version space
- inductive inference
- learning theory
- polynomial size
- reinforcement learning