Learning sparse mixtures of rankings from noisy information
We study the problem of learning an unknown mixture of $k$ rankings over $n$ elements, given access to noisy samples drawn from the unknown mixture. We consider a range of different noise models, including natural variants of the "heat kernel" noise framework and the Mallows model. For each of these noise models we give an algorithm which, under mild assumptions, learns the unknown mixture to high accuracy and runs in $n^{O(\log k)}$ time. The best previous algorithms for closely related problems have running times which are exponential in $k$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sample Complexity of Learning Mixtures of Sparse Linear Regressions
In the problem of learning mixtures of linear regressions, the goal is to learn a collection of signal vectors from a sequence of (possibly noisy) linear measurements, where each measurement is evaluated on an unknown si…
compressed sensingOpen-Ended Question AnsweringSample Complexity of Learning Mixture of Sparse Linear Regressions
In the problem of learning mixtures of linear regressions, the goal is to learn a col-lection of signal vectors from a sequence of (possibly noisy) linear measurements,where each measurement is evaluated on an unknown si…
compressed sensingOpen-Ended Question AnsweringConcentric mixtures of Mallows models for top-$k$ rankings: sampling and identifiability
In this paper, we consider mixtures of two Mallows models for top-$k$ rankings, both with the same location parameter but with different scale parameters, i.e., a mixture of concentric Mallows models. This situation aris…
Learning when to rank: Estimation of partial rankings from sparse, noisy comparisons
A common task arising in various domains is that of ranking items based on the outcomes of pairwise comparisons, from ranking players and teams in sports to ranking products or brands in marketing studies and recommendat…
MarketingRecommendation SystemsSupport Recovery of Sparse Signals from a Mixture of Linear Measurements
Recovery of support of a sparse vector from simple measurements is a widely-studied problem, considered under the frameworks of compressed sensing, 1-bit compressed sensing, and more general single index models. We consi…
compressed sensing