|
Published Articles >> Table of Contents >> Abstract
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
pp. 501-510
Learning mixtures of product distributions over discrete domains
Jon Feldman, Columbia University
Ryan ODonnell, Microsoft Research
Rocco A. Servedio, Dept. of Computer Science, Columbia University
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.46
Send link to a friend
| Abstract |
|
We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. [19]. We give a poly (n/ \in ) time algorithm for learning a mixture of k arbitrary product distributions over the n-dimensional Boolean cube {0,1}^n to accuracy , for any constant k. Previous poly(n)-time algorithms could only achieve this for k = 2 product distributions; our result answers an open question stated independently in [8] and [15]. We further give evidence that no polynomial time algorithm can succeed when k is superconstant, by reduction from a notorious open problem in PAC learning. Finally, we generalize our poly(n/ \in) time algorithm to learn any mixture of k = O(1) product distributions over {0, 1, . . . , b}^n, for any b = O(1).
|
 Additional Information
|
Citation:
Jon Feldman, Ryan ODonnell, Rocco A. Servedio,
"Learning mixtures of product distributions over discrete domains,"
focs,
pp. 501-510,
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05),
2005
|
|
