Bayesian Sets

Zoubin Ghahramani, Katherine A. Heller

TL;DR

Bayesian Sets is a "clustering on demand" algorithm that takes a few query items and retrieves other items belonging to the same implicit concept. By framing set completion as a Bayesian inference problem, the authors created a method that is both mathematically principled and incredibly fast—reducing the search process to a single sparse matrix multiplication for binary data.

What Problem Does This Paper Address?

Traditional clustering is usually an unsupervised, "all-at-once" process: you feed an algorithm a dataset, and it partitions everything into groups. However, in many real-world scenarios, we already have a few examples of a concept (a query) and simply want to find "more like these."

The authors identify two main challenges in this "set completion" task:

  1. Feature Relevance: A single item can belong to many clusters. For example, a query for "Bush" and "Nixon" implies a cluster of "US Presidents," while "Bush" and "Blair" implies "World Leaders." The algorithm must dynamically determine which features matter based on the query.
  2. Scale: Information retrieval often involves millions of items. A retrieval algorithm needs to be nearly instantaneous, which usually rules out complex, iterative Bayesian models.

Methods

The core of the paper is the Bayesian Score. For a query set $\mathcal{D}_c$ and a candidate item $x$, the score is defined as:

$$\text{score}(x) = \frac{p(x|\mathcal{D}_c)}{p(x)}$$

This ratio compares the probability that $x$ was generated by the same model (with the same unknown parameters $\theta$) as the query set, versus the probability that $x$ was generated independently.

Graphical models illustrating the two hypotheses compared in the Bayesian Score.

The "Secret Sauce" for Speed: The authors focus on sparse binary data using a Bernoulli distribution with a conjugate Beta prior. They show that the log of this score is linear in $x$. This is a massive win for engineering:

  • The query is reduced to a weight vector $q$ and a scalar $c$.
  • The scores for the entire dataset can be computed via a single sparse matrix-vector multiplication: $s = c + \mathbf{X}q$.
  • This allows the algorithm to scale to massive datasets while maintaining a rigorous probabilistic foundation.

The paper also generalizes this to any distribution in the exponential family (like Gaussians), provided they have conjugate priors, which keeps the underlying integrals analytically tractable.

Datasets

The authors evaluated the algorithm on three distinct types of data:

  • Grolier Encyclopedia: 30,991 articles characterized by the presence of 15,276 words (binarized).
  • EachMovie: A collaborative filtering dataset of 1,813 people and their ratings for 1,532 movies (binarized to "liked" vs. "not liked").
  • NIPS Authors: A dataset of 2,037 authors and the vocabulary used in their papers (13,649 words).

Key Insights and Ideas

  • The Power of the Denominator: Dividing by the prior $p(x)$ is essential. Without it, the algorithm would simply return the most "common" items in the dataset (e.g., the word "the" or a blockbuster movie like Titanic) regardless of the query. The denominator acts as a natural "anti-popularity" filter.
  • Clustering on Demand: Unlike static clustering, this approach treats every query as a unique, temporary supervised learning task. It uses the query to "shrink" the prior toward the specific features shared by the query items.
  • Bayesian Efficiency: This paper serves as a counter-argument to the idea that Bayesian methods are inherently slow. By choosing conjugate priors, the authors achieve speeds comparable to (or faster than) ad-hoc heuristic retrieval methods.

Key Results

  • Speed: On the Grolier dataset (over 2 million non-zero entries), the algorithm computed queries in roughly 1.1 seconds on mid-2000s hardware.
  • Qualitative Superiority: The authors compared their results to the then-popular "Google Sets." While Google Sets excelled at items frequently co-occurring on web lists (like "Cambridge Colleges"), Bayesian Sets was much better at capturing abstract concepts.
Comparison of query results between Google Sets and Bayesian Sets for movie queries.
  • Human Evaluation: In a blind study of 30 subjects, users preferred Bayesian Sets results over Google Sets by a wide margin—ranging from 81.5% to 96.7% preference across various categories.

Limitations and Future Work

  • Thresholding: The algorithm provides a ranked list but doesn't inherently know where the "cluster" ends. The authors suggest that because the scores have a probabilistic interpretation, a principled threshold could be developed.
  • Model Selection: The performance relies on choosing the right probabilistic model for the data. While the Bernoulli model works well for sparse binary data, other data types (like continuous sensor data) would require different distributions.
  • Prior Sensitivity: While the authors used a simple empirical heuristic for the priors, the results could potentially be sensitive to these settings in more complex or noisy datasets.

Summary updated

Abstract

Inspired by “Google™ Sets”, we consider the problem of retrieving items from a concept or cluster, given a query consisting of a few items from that cluster. We formulate this as a Bayesian inference problem and de- scribe a very simple algorithm for solving it. Our algorithm uses a model- based concept of a cluster and ranks items using a score which evaluates the marginal probability that each item belongs to a cluster containing the query items. For exponential family models with conjugate priors this marginal probability is a simple function of sufficient statistics. We focus on sparse binary data and show that our score can be evaluated ex- actly using a single sparse matrix multiplication, making it possible to apply our algorithm to very large datasets. We evaluate our algorithm on three datasets: retrieving movies from EachMovie, finding completions of author sets from the NIPS dataset, and finding completions of sets of words appearing in the Grolier encyclopedia. We compare to Google™ Sets and show that Bayesian Sets gives very reasonable set completions.
BibTeX
@inproceedings{ghahramani2005bayesian,
  author = {Zoubin Ghahramani and Katherine A. Heller},
  title = {{Bayesian Sets}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2005},
}
Figure