Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries.
Valery N. ShevchenkoNikolai Yu. ZolotykhPublished in: ALT (1998)
Keyphrases
- half spaces
- membership queries
- concept class
- exact learning
- read once formulas
- lower bound
- concept classes
- learning algorithm
- learning theory
- reinforcement learning
- worst case
- efficient learning
- query complexity
- equivalence queries
- version space
- uniform distribution
- vc dimension
- target concept
- concept learning
- boolean functions
- relational learning
- learning models
- statistical queries
- inductive learning
- learning tasks
- dnf formulas
- supervised learning
- semi supervised
- term dnf
- np hard
- equivalence and membership queries