What Sperner Family Concept Class is Easy to Be Enumerated?
Atsuyoshi NakamuraMineichi KudoPublished in: ICDM (2008)
Keyphrases
- concept class
- concept classes
- learning theory
- upper bound
- membership queries
- vc dimension
- distribution free
- vapnik chervonenkis dimension
- dnf formulas
- lower bound
- concept learning
- half spaces
- uniform distribution
- pac learning
- query complexity
- target concept
- special case
- efficient learning
- sample complexity
- sample size
- domain knowledge
- np hard
- exact learning