Polynomial-sample learnability about distance-0 and 1 DNF formulas.
Shinichi YanagiMineichi KudoMasaru ShimboPublished in: KES (2) (1998)
Keyphrases
- dnf formulas
- membership queries
- monotone dnf formulas
- polynomial size
- upper and lower bounds
- boolean functions
- monotone dnf
- truth table
- term dnf
- equivalence queries
- uniform distribution
- concept class
- randomly chosen
- sample size
- upper bound
- learning algorithm
- statistical queries
- membership and equivalence queries
- dnf formulae
- machine learning algorithms
- equivalence and membership queries