Exact Learning of Read-Twice DNF Formulas (Extended Abstract)
Howard AizensteinLeonard PittPublished in: FOCS (1991)
Keyphrases
- extended abstract
- membership queries
- dnf formulas
- exact learning
- equivalence queries
- concept class
- uniform distribution
- efficient learning
- learning algorithm
- monotone dnf
- boolean functions
- query complexity
- membership and equivalence queries
- monotone dnf formulas
- pac learning
- version space
- target concept
- concept classes
- number of queries needed
- learning theory
- term dnf
- training data
- vc dimension
- upper bound
- special case
- training set
- objective function