Exact learning of DNF formulas using DNF hypotheses.
Lisa HellersteinVijay RaghavanPublished in: J. Comput. Syst. Sci. (2005)
Keyphrases
- membership queries
- dnf formulas
- exact learning
- monotone dnf
- equivalence queries
- uniform distribution
- learning algorithm
- boolean functions
- concept class
- target concept
- efficient learning
- pac learning
- query complexity
- monotone dnf formulas
- version space
- agnostic learning
- term dnf
- hypothesis space
- membership and equivalence queries
- concept classes
- number of queries needed
- disjunctive normal form
- lower bound