P-Sufficient Statistics for PAC Learning k-term-DNF Formulas through Enumeration.
Bruno ApolloniClaudio GentilePublished in: Theor. Comput. Sci. (2000)
Keyphrases
- pac learning
- dnf formulas
- statistical queries
- uniform distribution
- membership queries
- concept class
- term dnf
- learning theory
- concept classes
- boolean functions
- target concept
- sample size
- sample complexity
- learning problems
- vc dimension
- pac model
- agnostic learning
- upper and lower bounds
- equivalence queries
- lower bound
- decision lists
- machine learning