TR07-129 Authors: Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan

Publication: 8th December 2007 23:03

Downloads: 1880

Keywords:

We give an algorithm that with high probability properly learns random monotone t(n)-term

DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF hypothesis. This is the first algorithm that can learn monotone DNF of arbitrary polynomial size in a reasonable average-case model of learning from random examples only.