Learning Entangled Single-Sample Gaussians

Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi

Abstract

We introduce a new model of Gaussian mixtures, motivated by the setting where the data points correspond to ratings on a set of items provided by users who have widely varying expertise, and each user can rate an item at most once. In this mixture model, each item i has a true quality μi, each user has a variance (lack of expertise) , and the rating of a user j on an item i consists of a single sample independently drawn from the Normal distribution . The aim is to learn the unknown item qualities μi's as precisely as possible. We study the single item case and obtain efficient algorithms for the problem, complemented by near-matching lower bounds; we also obtain preliminary results for the multiple items case. !TEX root = paper.tex
BibTeX
@inproceedings{chierichetti2014learning,
  author = {Flavio Chierichetti and Anirban Dasgupta and Ravi Kumar and Silvio Lattanzi},
  title = {{Learning Entangled Single-Sample Gaussians}},
  booktitle = {SODA},
  year = {2014},
  doi = {10.1137/1.9781611973402.38},
}

Loading related content...

Figure