A Polynomial Time Learning Algorithm Simple Deterministic Languages via Membership Queries and a Representative Sample.
Yasuhiro TajimaEtsuji TomitaPublished in: ICGI (2000)
Keyphrases
- membership queries
- learning algorithm
- exact learning
- dnf formulas
- equivalence queries
- query complexity
- read once formulas
- membership and equivalence queries
- target concept
- boolean functions
- monotone boolean functions
- pac learning
- dnf formulae
- monotone dnf formulas
- uniform distribution
- efficient learning
- monotone dnf
- concept class
- truth table
- machine learning
- axis parallel rectangles
- agnostic learning
- pattern languages
- expressive power
- boolean formula
- concept classes
- equivalence and membership queries
- perceptron algorithm
- special case
- lower bound
- decision trees