Technical reports:
Learning mixtures of product distributions over discrete domains
Jon Feldman; Ryan O'Donnell; Rocco Anthony Servedio
Downloads:
- Title:
- Learning mixtures of product distributions over discrete domains
- Author(s):
-
Feldman, Jon
O'Donnell, Ryan
Servedio, Rocco Anthony - Date:
- 2005
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:29411
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-029-05
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- 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:
- 119