Home

Learning mixtures of product distributions over discrete domains

Jon Feldman; Ryan O'Donnell; Rocco Anthony Servedio

Title:
Learning mixtures of product distributions over discrete domains
Author(s):
Feldman, Jon
O'Donnell, Ryan
Servedio, Rocco Anthony
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-029-05
Abstract:
We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. We give a $\poly(n/\eps)$ time algorithm for learning a mixture of $k$ arbitrary product distributions over the $n$-dimensional Boolean cube $\{0,1\}^n$ to accuracy $\eps$, for any constant $k$. Previous polynomial time algorithms could only achieve this for $k = 2$ product distributions; our result answers an open question stated independently by Cryan and by Freund and Mansour. 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/\eps)$ time algorithm to learn any mixture of $k = O(1)$ product distributions over $\{0,1, \dots, b\}^n$, for any $b = O(1)$.
Subject(s):
Computer science
Item views:
156
Metadata:
text | xml
Suggested Citation:
Jon Feldman, Ryan O'Donnell, Rocco Anthony Servedio, 2005, Learning mixtures of product distributions over discrete domains, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:29411.

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use