Theory of Computing
-------------------
Title : On Learning Random DNF Formulas Under the Uniform Distribution
Authors : Jeffrey C. Jackson and Rocco A. Servedio
Volume : 2
Number : 8
Pages : 147-172
URL : https://theoryofcomputing.org/articles/v002a008
Abstract
--------
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.