Riffled Independence for Ranked Data

Jonathan Huang, Carlos GuestrinNeurIPS 2009 · OpenReview

Introduction

Modeling how people rank items is notoriously difficult because the number of possible orderings grows factorially. Representing a probability distribution over permutations of $n$ objects is a daunting task—for just 10 items, there are over 3.6 million states; for 20, the number explodes to quintillions. This paper introduces riffled independence, a clever middle ground that allows researchers to model groups of items as independent while still allowing them to interleave in a final list, much like shuffling two halves of a deck of cards.

The Restrictiveness of Standard Independence

To make ranking models tractable, researchers often assume probabilistic independence. However, in the context of permutations, standard independence is incredibly restrictive. It imposes a strict "first-order condition" where if two sets of items are independent, one set must occupy a fixed block of ranks. For example, if a user's preferences for fruits and vegetables are independent, traditional models require fruits to always occupy ranks 1–5, and vegetables to occupy 6–10.

In reality, this is rarely true. You might have strong, independent preferences for different types of sushi and different types of dessert, but in a "top 10 favorite foods" list, you would likely interleave them. Traditional models cannot handle this interleaving without sacrificing the computational efficiency that independence provides.

Methods: The Riffled Independence Model

The authors propose Riffled Independence, inspired by the Gilbert-Varshamov-Reeds (or Bayer-Diaconis) model of card shuffling.

First-order marginal probability matrices under various riffled independence assumptions.
  1. The Concept: You independently draw two permutations (one for subset $X$, one for subset $Y$) and then apply a "riffle shuffle" to combine them. This preserves the internal relative ordering of each set but allows them to interleave naturally.
  2. Biased Riffle Shuffles: The model introduces a bias parameter, $\alpha$. If $\alpha=0.5$, the interleaving is uniform. If $\alpha$ approaches 0 or 1, the model reverts toward traditional independence, where one set is strictly preferred over the other.
  3. Fourier-Theoretic Framework: Instead of computing in the massive $n!$ space, the authors operate in the Fourier domain, representing distributions as collections of matrices (Fourier coefficients).
  4. Algorithms: They introduce RiffleJoin to merge two independent factors into a joint distribution using a riffle shuffle, and RiffleSplit to tease apart a joint distribution into its riffle-independent components.

Key Insights and Results

The core insight of this work is that independence in rankings should be defined by the relative order within subsets, not the absolute positions they occupy. Riffled independence acts as a strict generalization of probabilistic independence; by setting the shuffling distribution to a delta function, the traditional, restrictive model is recovered.

The authors validated their approach on two real-world datasets:

  • APA Dataset: Analyzing 5,738 ballots from the 1980 American Psychological Association presidential election, the model confirmed a long-standing conjecture by statistician Persi Diaconis. It revealed that voters ranked "academicians" and "clinicians" independently and then interleaved them, with one specific candidate acting as a riffle-independent bridge between the two groups.
  • Sushi Dataset: Using 5,000 full rankings of 10 sushi types, the riffle-independent model achieved a higher log-likelihood on held-out test data compared to the full model, particularly when the training set was small. This highlights a major advantage: by assuming riffled independence, accurate models can be learned from far fewer examples due to reduced parameter counts.

Computationally, the RiffleJoin algorithm scales polynomially ($O(n^2 d^3)$, where $d$ is the dimension of the Fourier matrix). This makes it feasible to evaluate rankings of up to 40 items—far beyond the reach of exhaustive methods.

Limitations and Future Work

While powerful, the current algorithms generally assume the independent subsets are known in advance. Exhaustive search for these subsets is possible for small datasets (like the APA data) but becomes intractable as $n$ grows. Future work may explore riffled independence in non-Fourier frameworks, such as graphical models for permutations, and develop formal statistical tests to determine if a dataset truly exhibits riffled independence before applying the model.

Summary updated

Abstract

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 riffled independence, which encompasses 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 riffle shuffle, common in card games, to combine the two permutations to form a single permutation. In ranking, riffled independence corresponds to ranking disjoint sets of objects independently, then interleaving those rankings. We provide a formal introduction and present algorithms for using riffled independence within Fourier-theoretic frameworks which have been explored by a number of recent papers.
BibTeX
@inproceedings{huang2009riffled,
  author = {Jonathan Huang and Carlos Guestrin},
  title = {{Riffled Independence for Ranked Data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=HyWf9ub_ZH},
}
Figure