Learning Hierarchical Riffle Independent Groupings from Rankings

Jonathan Huang, Carlos GuestrinICML 2010 · OpenReview

Modeling how people rank things—whether it’s political candidates, movies, or search results—is notoriously difficult. With $n$ items, there are $n!$ possible orderings, a number that explodes as $n$ grows. In their paper, "Learning Hierarchical Riffle Independent Groupings from Rankings," Jonathan Huang and Carlos Guestrin present a clever way to break this complexity down by discovering "riffle independent" hierarchies.

TL;DR

The authors provide the first automated method to discover hierarchical structures in ranked data using "riffled independence"—a concept where groups of items are ranked independently and then "shuffled" together. By identifying these latent coalitions, they can build statistical models that are both computationally efficient and highly interpretable.

What Problem Does This Paper Address?

Standard probabilistic independence is tricky for rankings. If you know "Apples" are ranked #1, you immediately know "Oranges" cannot be #1. This "mutual exclusivity" means items are always technically dependent.

Previous work introduced riffled independence to solve this. Imagine ranking a set of vegetables and a set of fruits separately, then interleaving (riffling) those two lists together like a deck of cards to get a final ranking. While this concept is powerful, there was no way to automatically figure out which items should be grouped together (e.g., should "Green Foods" be independent of "Red Foods"?). This paper fills that gap by providing an algorithm to learn these groupings directly from data.

Methods: Hierarchical Riffle Independent Decompositions

The authors propose a framework for Hierarchical Riffle Independent Decompositions. Instead of one big ranking, they model the data as a tree where each node represents a "riffle" of its children.

Examples of hierarchical riffled independence structures

The Objective Function

To find the best groupings, they needed a way to measure how "riffle independent" two sets are. While the gold standard (KL-divergence) is computationally impossible to search through, the authors developed a proxy based on Mutual Information. They look at "triplets" of items to see if the relative ranking of two items tells you anything about the absolute rank of a third. If it doesn't, you've likely found a point of riffled independence.

The "Anchors" Algorithm

Searching every possible way to split a set of items is an exponential nightmare. The authors introduced the Anchors method, a greedy heuristic. It picks two "anchor" items that are likely in different groups and then uses them to sort the remaining items into the most probable partitions. This reduces the search space from exponential to a manageable $O(n^3 m)$ time complexity.

Datasets

The paper evaluates the approach on three main fronts:

  1. Synthetic Data: Rankings generated from known hierarchical structures to test if the algorithm could recover the "ground truth."
  2. APA Election Data: Rankings of five candidates for the American Psychological Association presidency.
  3. Irish Election Data: A much larger dataset of 2,500 ballots from the 2002 Irish General Election (Meath constituency) involving 14 candidates.

Key Insights and Ideas

  • Relative vs. Absolute: The "aha moment" is that while absolute ranks are constrained by mutual exclusivity, relative ranks (is A better than B?) are not. By focusing on relative rankings, the authors bypass the mathematical headaches of traditional ranking models.
  • Latent Coalitions: The hierarchical structure isn't just a math trick; it reveals real-world "coalitions." In the election data, the algorithm automatically grouped candidates by their political parties without being told which party they belonged to.
  • The Power of Triplets: You don't need to look at the whole ranking at once. Looking at how items behave in groups of three (triplets) is often enough to detect the underlying independence structure of the entire set.
Internal and cross triplets used to measure independence

Key Results

  • Structure Recovery: On synthetic data, the algorithm perfectly recovered the true hierarchy as the number of samples increased, proving the "Anchors" heuristic is highly effective.
  • Political Insights: On the Irish election data, the model successfully clustered candidates from the major parties (Fianna Fáil and Fine Gael) into their own branches of the tree.
  • Better Generalization: The hierarchical riffle models achieved higher log-likelihoods on "unseen" test data compared to simpler "chain" models, meaning they capture the true distribution of voter preferences more accurately without overfitting.

Limitations and Future Work

While the Anchors algorithm is fast, it is still a heuristic and might miss the absolute optimal grouping in very noisy or complex datasets. The authors also note that they focused on "thin" hierarchies (where groups are small).

Future work could involve extending this to more general graphical models for rankings or exploring how these hierarchical structures change over time (e.g., how political coalitions shift during an election cycle). This paper lays the groundwork for treating rankings not as one-dimensional lists, but as rich, nested structures.

Summary updated

Abstract

Riffled independence is a generalized notion of probabilistic independence that has been shown to be naturally applicable to ranked data. In the riffled independence model, one assigns rankings to two disjoint sets of items independently, then in a second stage, interleaves (or riffles) the two rankings together to form a full ranking, as if by shuffling a deck of cards. Because of this interleaving stage, it is much more difficult to detect riffled independence than ordinary independence. In this paper, we provide the first 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.
BibTeX
@inproceedings{huang2010learning,
  author = {Jonathan Huang and Carlos Guestrin},
  title = {{Learning Hierarchical Riffle Independent Groupings from Rankings}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=r1WtMoWOZH},
}
Figure