Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries.
Carlos DomingoNina MishraLeonard PittPublished in: Mach. Learn. (1999)
Keyphrases
- boolean functions
- membership queries
- read once formulas
- exact learning
- learning algorithm
- term dnf
- uniform distribution
- efficient learning
- version space
- dnf formulas
- learning dnf
- learning problems
- pac learning
- disjunctive normal form
- monotone dnf
- agnostic learning
- decision lists
- pac model
- equivalence queries
- linear threshold
- target concept
- np complete
- monotone dnf formulas
- statistical queries
- dnf formulae
- equivalence and membership queries
- remains np hard
- polynomial size
- concept classes
- pattern languages
- phase transition
- training examples
- active learning