𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Pass-Efficient Algorithms for Learning Mixtures of Uniform Distributions

✍ Scribed by Chang, Kevin L.; Kannan, Ravi

Book ID
118180794
Publisher
Society for Industrial and Applied Mathematics
Year
2009
Tongue
English
Weight
393 KB
Volume
39
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An Efficient Membership-Query Algorithm
An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution
✍ Jeffrey C Jackson πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 566 KB

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 alg

Learning mixtures of point distribution
Learning mixtures of point distribution models with the EM algorithm
✍ Abdullah A. Al-Shaher; Edwin R. Hancock πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 409 KB

This paper demonstrates how the EM algorithm can be used for learning and matching mixtures of point distribution models. We make two contributions. First, we show how shape-classes can be learned in an unsupervised manner. We present a fast procedure for training point distribution models using the

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