Learning DNF formulae under classes of probability distributions
Michele Flammini, Alberto Marchetti-Spaccamela, Luděk Kučera · 1992
We show that 2-term DNF formulae are learnable in quadratic time using only a logarithmic number of positive examples if we assume that examples are drawn from a bounded distribution. We also show that k-term DNF formulae are learnable in polynomial time using positive and negative examples drawn from a bounded distribution.