DNF are teachable in the average case.

Homin K. Lee Rocco A. Servedio Andrew Wan

Published in: Mach. Learn. (2007)

Keyphrases

average case
uniform distribution
boolean functions
pac learning
membership queries
worst case analysis
learning curves
agnostic learning
target concept
worst case
learning theory
statistical queries
average case complexity
decision trees
dnf formulas