An Analysis of Examples and a Search Space for PAC Learning of Simple Deterministic Languages with Membership Queries.
Yasuhiro TajimaYoshiyuki KotaniMatsuaki TeradaPublished in: ICGI (2004)
Keyphrases
- pac learning
- membership queries
- exact learning
- uniform distribution
- computational learning theory
- target concept
- concept classes
- pac model
- sample size
- learning theory
- concept class
- sample complexity
- agnostic learning
- learning problems
- pac learnable
- dnf formulas
- efficient learning
- training examples
- lower bound
- learning algorithm
- statistical queries
- worst case
- supervised learning
- classification noise
- machine learning