An O(nlog log n) Learning Algorithm for DNF under the Uniform Distribution

✍ Scribed by Y. Mansour

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 571 KB
• Volume: 50
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1995.1043

✦ Synopsis

We show that a DNF with terms of size at most (d) can be approximated by a function at most (d^{O(d \log 1 / \epsilon)}) nonzero Fourier coefficients such that the expected error squared, with respect to the uniform distribution, is at most (\epsilon). This property is used to derive a learning algorithm for DNF, under the uniform distribution. The learning algorithm uses queries and learns, with respect to the uniform distribution, a DNF with terms of size at most (d) in time polynomial in (n) and (d^{0(d i 0 g 1 / \epsilon)}). The interesting implications are for the case when (\epsilon) is constant. In this case our algorithm learns a DNF with a polynomial number of terms in time (n^{0(\log \log n)}), and a DNF with terms of size at most (O(\log n / \log \log n)) in polynomial time. © 1995 Academic Press. Inc.