Volume 2 (2006)
Article 8 pp. 147-172

On Learning Random DNF Formulas Under the Uniform Distribution

Received: March 21, 2006

Published: September 19, 2006

Published: September 19, 2006

**Keywords:**computational learning theory, uniform-distribution learning, PAC learning, DNF formulas, monotone DNF

**Categories:**learning, PAC learning, algorithms, average case, formulas, Boolean formulas, CNF-DNF formulas

**ACM Classification:**I.2.6, F.2.2, G.1.2, G.3

**AMS Classification:**68Q32, 68W20, 68W25, 60C05

**Abstract:**
[Plain Text Version]

We study the average-case learnability of DNF formulas in the model of learning from uniformly distributed random examples. We define a natural model of random monotone DNF formulas and give an efficient algorithm which with high probability can learn, for any fixed constant $\gamma>0$, a random $t$-term monotone DNF for any $t = O(n^{2-\gamma})$. We also define a model of random non-monotone DNF and give an efficient algorithm which with high probability can learn a random $t$-term DNF for any $t=O(n^{3/2 - \gamma})$. These are the first known algorithms that can learn a broad class of polynomial-size DNF in a reasonable average-case model of learning from random examples.