On learning mixture models for permutations

Show simple item record

dc.contributor.author Chierichetti, Flavio
dc.contributor.author Dasgupta, Anirban
dc.contributor.author Kumar, Ravi
dc.contributor.author Lattanzi, Silvio
dc.contributor.other 2015 Conference on Innovations in Theoretical Computer Science (ITCS 2015)
dc.coverage.spatial New York, US.
dc.date.accessioned 2015-01-21T11:01:52Z
dc.date.available 2015-01-21T11:01:52Z
dc.date.issued 2015-01-02
dc.identifier.citation Chierichetti, Flavio; Dasgupta, Anirban; Kumar, Ravi and Lattanzi, Silvio, "On learning mixture models for permutations", in the 2015 Conference on Innovations in Theoretical Computer Science (ITCS 2015), New York, US, Jan. 11-13, 2015. en_US
dc.identifier.uri http://dx.doi.org/10.1145/2688073.2688111
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/1587
dc.description.abstract In this paper we consider the problem of learning a mixture of permutations, where each component of the mixture is generated by a stochastic process. Learning permutation mixtures arises in practical settings when a set of items is ranked by different sub-populations and the rankings of users in a sub-population tend to agree with each other. While there is some applied work on learning such mixtures, they have been mostly heuristic in nature. We study the problem where the permutations in a mixture component are generated by the classical Mallows process in which each component is associated with a center and a scalar parameter. We show that even when the centers are arbitrarily separated, with exponentially many samples one can learn the mixture, provided the parameters are all the same and known; we also show that the latter two assumptions are information-theoretically inevitable. We then focus on polynomial-time learnability and show bounds on the performance of two simple algorithms for the case when the centers are well separated. Conceptually, our work suggests that while permutations may not enjoy as nice mathematical properties as Gaussians, certain structural aspects can still be exploited towards analyzing the corresponding mixture learning problem. en_US
dc.description.statementofresponsibility Anirban Dasgupta et al.
dc.language.iso en_US en_US
dc.publisher ACM Digital Library en_US
dc.subject Design and analysis of algorithms en_US
dc.subject Theory of computation en_US
dc.title On learning mixture models for permutations en_US
dc.type Article en_US


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account