### Abstract

We study the problem of learning a distribution from samples, when the underlying distribution is a mixture of product distributions over discrete domains. This problem is motivated by several practical applications such as crowdsourcing, recommendation systems, and learning Boolean functions. The existing solutions either heavily rely on the fact that the number of mixtures is finite or have sample/time complexity that is exponential in the number of mixtures. In this paper, we introduce a polynomial time/sample complexity method for learning a mixture of r discrete product distributions over {1,2,..., l}^{n}, for general l and r. We show that our approach is consistent and further provide finite sample guarantees. We use recently developed techniques from tensor decompositions for moment matching. A crucial step in these approaches is to construct certain tensors with low-rank spectral decompositions. These tensors are typically estimated from the sample moments. The main challenge in learning mixtures of discrete product distributions is that the corresponding low-rank tensors cannot be obtained directly from the sample moments. Instead, we need to estimate a low-rank matrix using only off-diagonal entries, and estimate a tensor using a few linear measurements. We give an alternating minimization based method to estimate the low-rank matrix, and formulate the tensor estimation problem as a least-squares problem.

Original language | English (US) |
---|---|

Pages (from-to) | 824-856 |

Number of pages | 33 |

Journal | Journal of Machine Learning Research |

Volume | 35 |

State | Published - Jan 1 2014 |

Event | 27th Conference on Learning Theory, COLT 2014 - Barcelona, Spain Duration: Jun 13 2014 → Jun 15 2014 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Control and Systems Engineering
- Statistics and Probability
- Artificial Intelligence

### Cite this

*Journal of Machine Learning Research*,

*35*, 824-856.

**Learning mixtures of discrete product distributions using spectral decompositions.** / Jain, Prateek; Oh, Sewoong.

Research output: Contribution to journal › Conference article

*Journal of Machine Learning Research*, vol. 35, pp. 824-856.

}

TY - JOUR

T1 - Learning mixtures of discrete product distributions using spectral decompositions

AU - Jain, Prateek

AU - Oh, Sewoong

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We study the problem of learning a distribution from samples, when the underlying distribution is a mixture of product distributions over discrete domains. This problem is motivated by several practical applications such as crowdsourcing, recommendation systems, and learning Boolean functions. The existing solutions either heavily rely on the fact that the number of mixtures is finite or have sample/time complexity that is exponential in the number of mixtures. In this paper, we introduce a polynomial time/sample complexity method for learning a mixture of r discrete product distributions over {1,2,..., l}n, for general l and r. We show that our approach is consistent and further provide finite sample guarantees. We use recently developed techniques from tensor decompositions for moment matching. A crucial step in these approaches is to construct certain tensors with low-rank spectral decompositions. These tensors are typically estimated from the sample moments. The main challenge in learning mixtures of discrete product distributions is that the corresponding low-rank tensors cannot be obtained directly from the sample moments. Instead, we need to estimate a low-rank matrix using only off-diagonal entries, and estimate a tensor using a few linear measurements. We give an alternating minimization based method to estimate the low-rank matrix, and formulate the tensor estimation problem as a least-squares problem.

AB - We study the problem of learning a distribution from samples, when the underlying distribution is a mixture of product distributions over discrete domains. This problem is motivated by several practical applications such as crowdsourcing, recommendation systems, and learning Boolean functions. The existing solutions either heavily rely on the fact that the number of mixtures is finite or have sample/time complexity that is exponential in the number of mixtures. In this paper, we introduce a polynomial time/sample complexity method for learning a mixture of r discrete product distributions over {1,2,..., l}n, for general l and r. We show that our approach is consistent and further provide finite sample guarantees. We use recently developed techniques from tensor decompositions for moment matching. A crucial step in these approaches is to construct certain tensors with low-rank spectral decompositions. These tensors are typically estimated from the sample moments. The main challenge in learning mixtures of discrete product distributions is that the corresponding low-rank tensors cannot be obtained directly from the sample moments. Instead, we need to estimate a low-rank matrix using only off-diagonal entries, and estimate a tensor using a few linear measurements. We give an alternating minimization based method to estimate the low-rank matrix, and formulate the tensor estimation problem as a least-squares problem.

UR - http://www.scopus.com/inward/record.url?scp=84939616999&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84939616999&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:84939616999

VL - 35

SP - 824

EP - 856

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

SN - 1532-4435

ER -