PDF《Learning random monotone DNF》

brie?y, the reader should think of our random t-term monotone DNFs as being obtained by independently drawing t monotone conjunctions uniformly from the set of all conjunctions of length log2 t over variables x1,xn. Although many other distributions could be considered, this seems a natural starting point. Some justi?cation for the choice of term length is given in Sections

5 and 7.) Theorem 1. [Informally] Let t(n) be any function such that t(n) ≤ poly(n), and let c >

0 be any ?xed constant. Then random monotone t(n)-term DNFs are PAC learnable (with failure probability δ = n?c) to accuracy ? in poly(n, 1/?) time under the uniform distribution. The algorithm outputs

1 a monotone DNF as its hypothesis. 1.4 Our technique. Jackson and Servedio [JS06] showed that for any γ >

0, a result similar to Theorem

1 holds for random t-term monotone DNF with t ≤ n2?γ. The main open problem stated in [JS06] was to prove Theorem 1. Our work solves this problem by using the previous algorithm to handle t ≤ n3/2, developing new Fourier lemmas for monotone DNF, and using these lemmas together with more general versions of techniques from [JS06] to handle t ≥ n3/2. The crux of our strategy is to establish a connection between the term structure of certain monotone DNFs and their low-order Fourier coe?cients. There is an extensive body of research on Fourier properties of monotone Boolean functions [BT96, MO03, BBL98], polynomial-size DNF [Jac97, Man94], and related classes such as constant-depth circuits and decision trees [LMN93, KM93, JKS02, OS06]. These results typically establish that every function in the class has a Fourier spectrum with certain properties;

unfortunately, the Fourier properties that have been obtainable to date for general statements of this sort have not been su?cient to yield polynomial-time learning algorithms. We take a di?erent approach by carefully de?ning a set of conditions, and showing that if a monotone DNF f satis?es these conditions then the structure of the terms of f will be re?ected in the low-order Fourier coe?cients of f. In [JS06], the degree two Fourier coe?cients were shown to reveal the structure of the terms for certain (including random) monotone DNFs having at most n2?γ terms. In this work we develop new lemmas about the Fourier coe?cients of more general monotone DNF, and use these new lemmas to establish a connection between term structure and constant degree Fourier coe?cients for monotone DNFs with any polynomial number of terms. Roughly speaki........