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

On Learning Random DNF Formulas Under the Uniform Distribution

by Jeffrey C. Jackson and Rocco A. Servedio

Received: March 21, 2006
Published: September 19, 2006

Download article from ToC site:
[PDF (265K)]    [PS (449K)]    [PS.GZ (128K)]    [PS.ZIP (128K)]
[Source ZIP]
Misc.:
[About the Author(s)] [HTML Bibliography] [BibTeX]
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 γ > 0, a random t-term monotone DNF for any t = O(n2 - γ). 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(n3/2 - γ). 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.

DOI: 10.4086/toc.2006.v002a008
© 2006 Jeffrey C. Jackson and Rocco A. Servedio
Creative Commons License Licensed under a Creative Commons License