✦ LIBER ✦

An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution

✍ Scribed by Jeffrey C Jackson

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 566 KB
Volume: 55
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1997.1533

No coin nor oath required. For personal study only.

✦ Synopsis

We present a membership-query algorithm for efficiently learning DNF with respect to the uniform distribution. In fact, the algorithm properly learns with respect to uniform the class TOP of Boolean functions expressed as a majority vote over parity functions. We also describe extensions of this algorithm for learning DNF over certain nonuniform distributions and for learning a class of geometric concepts that generalizes DNF. Furthermore, we show that DNF is weakly learnable with respect to uniform from noisy examples. Our strong learning algorithm utilizes one of Freund's boosting techniques and relies on the fact that boosting does not require a completely distribution-independent weak learner. The boosted weak learner is a nonuniform extension of a parity-finding algorithm discovered by Goldreich and Levin.

📜 SIMILAR VOLUMES

An O(nlog log n) Learning Algorithm for

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

✍ Y. Mansour 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 571 KB

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 learnin