loading...
Learning mixtures of product distributions over discrete domains
Pittsburgh, Pennsylvania, USA October 23-October 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.4646th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Jon Feldman, Columbia University
Ryan ODonnell, Microsoft Research
Rocco A. Servedio, Dept. of Computer Science, Columbia University

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).

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
Usage of this product signifies your acceptance of the Terms of Use.