Uncovering the Riffled Independence Structure of Rankings

Details Uncovering the Riffled Independence Structure of Rankings Uncovering the Riffled Independence Structure of Rankings

2010-06-07

arxiv.org/abs/1006.1328v1

Computer Science

Learning

65 pages

Scientific paper

Representing distributions over permutations can be a daunting task due to the fact that the number of permutations of $n$ objects scales factorially in $n$. One recent way that has been used to reduce storage complexity has been to exploit probabilistic independence, but as we argue, full independence assumptions impose strong sparsity constraints on distributions and are unsuitable for modeling rankings. We identify a novel class of independence structures, called \emph{riffled independence}, encompassing a more expressive family of distributions while retaining many of the properties necessary for performing efficient inference and reducing sample complexity. In riffled independence, one draws two permutations independently, then performs the \emph{riffle shuffle}, common in card games, to combine the two permutations to form a single permutation. Within the context of ranking, riffled independence corresponds to ranking disjoint sets of objects independently, then interleaving those rankings. In this paper, we provide a formal introduction to riffled independence and present algorithms for using riffled independence within Fourier-theoretic frameworks which have been explored by a number of recent papers. Additionally, we propose an automated method for discovering sets of items which are riffle independent from a training set of rankings. We show that our clustering-like algorithms can be used to discover meaningful latent coalitions from real preference ranking datasets and to learn the structure of hierarchically decomposable models based on riffled independence.

Affiliated with

Also associated with

No associations

Rating

Uncovering the Riffled Independence Structure of Rankings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Uncovering the Riffled Independence Structure of Rankings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uncovering the Riffled Independence Structure of Rankings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-367833