Bayesian Sets

Zoubin Ghahramani∗ and Katherine A. Heller
Gatsby Computational Neuroscience Unit
University College London
London WC1N 3AR, U.K.
{zoubin,heller}@gatsby.ucl.ac.uk

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 fromthat cluster. We formulate this as a Bayesian inference problem and describe a very simple algorithm for solving it. Our algorithm uses a modelbased 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 exactly using a single sparse matrix multiplication, making it possible toapply our algorithm to very large datasets. We evaluate our algorithm onthree datasets: retrieving movies from EachMovie, finding completionsof author sets from the NIPS dataset, and finding completions of sets ofwords appearing in the Grolier encyclopedia. We compare to Google™
Sets and show that Bayesian Sets gives very reasonable set completions.

1

Introduction

What do Jesus and Darwin have in common? Other than being associated with two
different views on the origin of man, they also have colleges at Cambridge University named after them. If these two names are entered as a query into Google™ Sets
(http://labs.google.com/sets) it returns a list of other colleges at Cambridge.
Google™ Sets is a remarkably useful tool which encapsulates a very practical and interesting problem in machine learning and information retrieval.1 Consider a universe of items
D. Depending on the application, the set D may consist of web pages, movies, people,
words, proteins, images, or any other object we may wish to form queries on. The user
provides a query in the form of a very small subset of items Dc ⊂ D. The assumption
is that the elements in Dc are examples of some concept / class / cluster in the data. The
algorithm then has to provide a completion to the set Dc —that is, some set Dc0 ⊂ D which
presumably includes all the elements in Dc and other elements in D which are also in thisconcept / class / cluster2 .
∗ZG is also at CALD, Carnegie Mellon University, Pittsburgh PA 15213.
Google™ Sets is a large-scale clustering algorithm that uses many millions of data instances
extracted from web data (Simon Tong, personal communication). We are unable to describe any
details of how the algorithm works due its proprietary nature.
2
From here on, we will use the term “cluster” to refer to the target concept.
1

We can view this problem from several perspectives. First, the query can be interpreted
as elements of some unknown cluster, and the output of the algorithm is the completionof that cluster. Whereas most clustering algorithms are completely unsupervised, here thequery provides supervised hints or constraints as to the membership of a particular cluster.
We call this view clustering on demand, since it involves forming a cluster once someelements of that cluster have been revealed. An important advantage of this approach overtraditional clustering is that the few elements in the query can give useful information as
to the features which are relevant for forming the cluster. For example, the query “Bush”,“Nixon”, “Reagan” suggests that the features republican and US President are relevant tothe cluster, while the query “Bush”, “Putin”, “Blair” suggests that current and world leader
are relevant. Given the huge number of features in many real world data sets, such hints as
to feature relevance can produce much more sensible clusters.
Second, we can think of the goal of the algorithm to be to solve a particular information retrieval problem [2, 3, 4]. As in other retrieval problems, the output should be relevant to thequery, and it makes sense to limit the output to the top few items ranked by relevance to thequery. In our experiments, we take this approach and report items ranked by relevance. Our
relevance criterion is closely related to a Bayesian framework for understanding patterns ofgeneralization in human cognition [5].

2Bayesian Sets

Let D be a data set of items, and x ∈ D be an item from this set. Assume the user provides
a query set Dc which is a small subset of D. Our goal is to rank the elements of D by how
well they would “fit into” a set which includes Dc . Intuitively, the task is clear: if the set
D is the set of all movies, and the query set consists of two animated Disney movies, we
expect other animated Disney movies to be ranked highly.
We use a model-based probabilistic criterion to measure how well items fit into Dc . Having
observed Dc as belonging to some concept, we want to know how probable it is that x also
belongs with Dc . This is measured by p(x|Dc ). Ranking items simply by this probability
is not sensible since some items may be more probable than others, regardless of Dc . For
example, under most sensible models, the probability of a string decreases with the numberof characters, the probability of an image decreases with the number of pixels, and theprobability of any continuous variable decreases with the precision to which it is measured.
We want to remove these effects, so we compute the ratio:score(x) =p(x|Dc )p(x)(1)

where the denominator is the prior probability of x and under most sensible models will
scale exactly correctly with number of pixels, characters, discretization level, etc. Using
Bayes rule, this score can be re-written as:score(x) =p(x, Dc )p(x) p(Dc )(2)which can be interpreted as the ratio of the joint probability of observing x and Dc , to theprobability of independently observing x and Dc . Intuitively, this ratio compares the probability that x and Dc were generated by the same model with the same, though unknown,
parameters θ, to the probability that x and Dc came from models with different parametersθ and θ0 (see figure 1). Finally, up to a multiplicative constant independent of x, the scorecan be written as: score(x) = p(Dc |x), which is the probability of observing the query set
given x (i.e. the likelihood of x).
From the above discussion, it is still not clear how one would compute quantities suchas p(x|Dc ) and p(x). A natural model-based way of defining a cluster is to assume that

Figure 1: Our Bayesian score compares the hypotheses that the data was generated by each of theabove graphical models.

the data points in the cluster all come independently and identically distributed from some
simple parameterized statistical model. Assume that the parameterized model is p(x|θ)
where θ are the parameters. If the data points in Dc all belong to one cluster, then under
this definition they were generated from the same setting of the parameters; however, thatsetting is unknown, so we need to average over possible parameter values weighted bysome prior density on parameter values, p(θ). Using these considerations and the basic
rules of probability we arrive at:Zp(x) =
p(x|θ) p(θ) dθ(3)
Z Yp(Dc ) =p(xi |θ) p(θ) dθ(4)xi ∈DcZp(x|Dc )=p(θ|Dc )=p(x|θ) p(θ|Dc ) dθp(Dc |θ) p(θ)
p(Dc )(5)(6)

We are now fully equipped to describe the “Bayesian Sets” algorithm:
Bayesian Sets Algorithm
background: a set of items D, a probabilistic model p(x|θ) wherex ∈ D, a prior on the model parameters p(θ)
input: a query Dc = {xi } ⊂ D
for all x ∈ D dop(x|Dc )computescore(x) =p(x)end foroutput: return elements of D sorted by decreasing score
We mention two properties of this algorithm to assuage two common worries with Bayesian
methods—tractability and sensitivity to priors:
1. For the simple models we will consider, the integrals (3)-(5) are analytical. In fact,
for the model we consider in section 3 computing all the scores can be reduced toa single sparse matrix multiplication.

2. Although it clearly makes sense to put some thought into choosing sensible models p(x|θ) and priors p(θ), we will show in 5 that even with very simple models
and almost no tuning of the prior one can get very competitive retrieval results. In
practice, we use a simple empirical heuristic which sets the prior to be vague but
centered on the mean of the data in D.

3Sparse Binary Data

We now derive in more detail the application of the Bayesian Sets algorithm to sparsebinary data. This type of data is a very natural representation for the large datasets we usedin our evaluations (section 5). Applications of Bayesian Sets to other forms of data (realvalued, discrete, ordinal, strings) are also possible, and especially practical if the statisticalmodel is a member of the exponential family (section 4).
Assume each item xi ∈ Dc is a binary vector xi = (xi1 , . . . , xiJ ) where xij ∈ {0, 1}, andthat each element of xi has an independent Bernoulli distribution:p(xi |θ) =JYxθj ij (1 − θj )1−xij

(7)

j=1

The conjugate prior for the parameters of a Bernoulli distribution is the Beta distribution:p(θ|α, β) =JY
Γ(αj + βj )α −1

Γ(αj )Γ(βj )
j=1

θj j

(1 − θj )βj −1(8)where α and β are hyperparameters, and the Gamma function is a generalization of thefactorial function. For a query Dc = {xi } consisting of N vectors it is easy to show that:p(Dc |α, β) =Y Γ(αj + βj ) Γ(α̃j )Γ(β̃j )jΓ(αj )Γ(βj ) Γ(α̃j + β̃j )

(9)

PN
PN
where α̃ = α + i=1 xij and β̃ = β + N − i=1 xij . For an item x = (x·1 . . . x·J ) thescore, written with the hyperparameters explicit, can be computed as follows:Γ(αj +βj +N )Γ(α̃j +x·j )Γ(β̃j +1−x·j )p(x|Dc , α, β) Y Γ(αj +βj +N +1)Γ(α̃j )Γ(β̃j )=score(x) =Γ(αj +βj ) Γ(αj +x·j )Γ(βj +1−x·j )p(x|α, β)jΓ(αj +βj +1)(10)

Γ(αj )Γ(βj )This daunting expression can be dramatically simplified. We use the fact that Γ(x) =(x − 1) Γ(x − 1) for x > 1. For each j we can consider the two cases x·j = 0 and x·j = 1
αj +βj α̃jand separately. For x·j = 1 we have a contribution αj +β. For x·j = 0 we have aj +N αj
β̃

α +β

j
j
j
contribution αj +β. Putting these together we get:j +N βjscore(x) =Yjαj + βj
αj + βj + N

α̃j
αj

x·j

X

qj x·jβ̃jβj!1−x·j(11)

The log of the score is linear in x:
log score(x) = c +

(12)

j

where

c=

X
j

log(αj + βj ) − log(αj + βj + N ) + log β̃j − log βj

(13)

and

qj = log α̃j − log αj − log β̃j + log βj(14)
If we put the entire data set D into one large matrix X with J columns, we can computethe vector s of log scores for all points using a single matrix vector multiplications = c + Xq

(15)

For sparse data sets this linear operation can be implemented very efficiently. Each query
Dc corresponds to computing the vector q and scalar c. This can also be done efficiently if
the query is also sparse, since most elements of q will equal log βj − log(βj + N ) whichis independent of the query.

4

Exponential Families

We generalize the above result to models in the exponential family. The distribution forsuch models can be written in the form p(x|θ) = f (x)g(θ) exp{θ> u(x)}, where u(x) is a
K-dimensional vector of sufficient statistics, θ are the natural parameters, and f and g are
non-negative functions. The conjugate prior is p(θ|η, ν) = h(η, ν)g(θ)η exp{θ> ν}, where
η and ν are hyperparameters, and h normalizes the distribution.
Given a query Dc = {xi } with N items, and a candidate x, it is not hard to show that thescore for the candidate is:Ph(η + 1, ν + u(x)) h(η + N, ν + i u(xi ))Pscore(x) =(16)h(η, ν) h(η + N + 1, ν + u(x) + i u(xi ))This expression helps us understand when the score can be computed efficiently. First ofall, the score only depends on the size of the query (N ), the sufficient statistics computedfrom each candidate, and from the whole query. It therefore makes sense to precompute U,
a matrix of sufficient statistics corresponding to X. Second, whether the score is a linear
operation on U depends on whether log h is linear in the second argument. This is the casefor the Bernoulli distribution, but not for all exponential family distributions. However,for many distributions, such as diagonal covariance Gaussians, even though the score isnonlinear in U, it can be computed by applying the nonlinearity elementwise to U. For
sparse matrices, the score can therefore still be computed in time linear in the number of
non-zero elements of U.

5

Results

We ran our Bayesian Sets algorithm on three different datasets: the Groliers Encyclopedia dataset, consisting of the text of the articles in the Encyclopedia, the EachMovie
dataset, consisting of movie ratings by users of the EachMovie service, and the NIPS authors dataset, consisting of the text of articles published in NIPS volumes 0-12 (spanning
the 1987-1999 conferences). The Groliers dataset is 30991 articles by 15276 words, where
the entries are the number of times each word appears in each document. We preprocess(binarize) the data by column normalizing each word, and then thresholding so that a (article,word) entry is 1 if that word has a frequency of more than twice the article mean.
We do essentially no tuning of the hyperparameters. We use broad empirical priors, where
α = c×m, β = c × (1−m) where m is a mean vector over all articles, and c = 2. The
analogous priors are used for both other datasets.
The EachMovie dataset was preprocessed, first by removing movies rated by less than 15
people, and people who rated less than 200 movies. Then the dataset was binarized so that a(person, movie) entry had value 1 if the person gave the movie a rating above 3 stars (froma possible 0-5 stars). The data was then column normalized to account for overall movie
popularity. The size of the dataset after preprocessing was 1813 people by 1532 movies.

Finally the NIPS author dataset (13649 words by 2037 authors), was preprocessed very
similarly to the Grolier dataset. It was binarized by column normalizing each author, andthen thresholding so that a (word,author) entry is 1 if the author uses that word more frequently than twice the word mean across all authors.
The results of our experiments, and comparisons with Google Sets for word and movie
queries are given in tables 2 and 3. Unfortunately, NIPS authors have not yet achieved thekind of popularity on the web necessary for Google Sets to work effectively. Instead welist the top words associated with the cluster of authors given by our algorithm (table 4).
The running times of our algorithm on all three datasets are given in table 1. All experiments were run in Matlab on a 2GHz Pentium 4, Toshiba laptop. Our algorithm is very fast
both at pre-processing the data, and answering queries (about 1 sec per query).
S IZE
N ON -Z ERO E LEMENTS
P REPROCESS T IMEQ UERY T IMEG ROLIERS

E ACH M OVIE

NIPS

30991 × 15276
2,363,514
6.1 S
1.1 S

1813 × 1532
517,709
0.56 S
0.34 S

13649 × 2037
933,295
3.22 S
0.47 S

Table 1: For each dataset we give the size of that dataset along with the time taken to do the (onetime) preprocessing and the time taken to make a query (both in seconds).

Q UERY: WARRIOR , S OLDIERQ UERY: A NIMALQ UERY: F ISH , WATER , C ORALG OOGLE S ETSBAYES S ETSG OOGLE S ETSBAYES S ETSG OOGLE S ETSBAYES S ETSWARRIORSOLDIERSPY
ENGINEER
MEDIC
SNIPER
DEMOMANPYROSCOUTPYROMANIACHWGUYSOLDIERWARRIORMERCENARYCAVALRY
BRIGADECOMMANDING
SAMURAIBRIGADIERINFANTRY
COLONELSHOGUNATE

ANIMAL
PLANT
FREE
LEGAL
FUNGALHUMAN
HYSTERIA
VEGETABLE
MINERAL
INDETERMINATE
FOZZIE BEAR

ANIMALANIMALS
PLANT
HUMANS
FOOD
SPECIESMAMMALSAGO
ORGANISMS
VEGETATIONPLANTS

FISH
WATER
CORAL
AGRICULTURE
FORESTRICE
SILK ROAD
RELIGIONHISTORY POLITICS
DESERT
ARTS

WATER
FISH
SURFACE
SPECIES
WATERSMARINEFOOD
TEMPERATURE
OCEANSHALLOWFT

Table 2: Clusters of words found by Google Sets and Bayesian Sets based on the given queries.
The top few are shown for each query and each algorithm. Bayesian Sets was run using Grolier
Encyclopedia data.

It is very difficult to objectively evaluate our results since there is no ground truth for thistask. One person’s idea of a good query cluster may differ drastically from another person’s.
We chose to compare our algorithm to Google Sets since it was our main inspiration and it
is currently the most public and commonly used algorithm for performing this task.
Since we do not have access to the Google Sets algorithm it was impossible for us to run
their method on our datasets. Moreover, Google Sets relies on vast amounts of web data,
which we do not have. Despite those two important caveats, Google Sets clearly “knows”
a lot about movies3 and words, and the comparison to Bayesian Sets is informative.
We found that Google Sets performed very well when the query consisted of items which
can be found listed on the web (e.g. Cambridge colleges). On the other hand, for more
abstract concepts (e.g. “soldier” and “warrior”, see Table 2) our algorithm returned moresensible completions.
While we believe that most of our results are self-explanatory, there are a few details that wewould like to elaborate on. The top query in table 3 consists of two classic romantic movies,
3

In fact, one of the example queries on the Google Sets website is a query of movie titles.

Q UERY: G ONE WITH THE WIND , CASABLANCAG OOGLE S ETSCASABLANCA (1942)
GONE WITH THE WIND (1939)
ERNEST SAVES CHRISTMAS (1988)
CITIZEN KANE (1941)
PET DETECTIVE (1994)
VACATION (1983)
WIZARD OF OZ (1939)
THE GODFATHER (1972)
LAWRENCE OF ARABIA (1962)
ON THE WATERFRONT (1954)

BAYES S ETSGONE WITH THE WIND (1939)
CASABLANCA (1942)
THE AFRICAN QUEEN (1951)
THE PHILADELPHIA STORY (1940)
MY FAIR LADY (1964)
THE ADVENTURES OF ROBIN HOOD (1938)
THE MALTESE FALCON (1941)
REBECCA (1940)SINGING IN THE RAIN (1952)
IT HAPPENED ONE NIGHT (1934)

Q UERY: M ARY P OPPINS , T OY S TORYQ UERY: C UTTHROAT I SLAND , L AST ACTION H EROG OOGLE S ETSBAYES S ETSG OOGLE S ETSBAYES S ETSTOY STORYMARY POPPINSTOY STORY 2
MOULIN ROUGE
THE FAST AND THE FURIOUS
PRESQUE RIENSPACED
BUT I ’ M A CHEERLEADER
MULAN
WHO FRAMED ROGER RABBITMARY POPPINSTOY STORYWINNIE THE POOH
CINDERELLA
THE LOVE BUG
BEDKNOBS AND BROOMSTICKSDAVY CROCKETTTHE PARENT TRAPDUMBO
THE SOUND OF MUSICLAST ACTION HEROCUTTHROAT ISLANDGIRL
END OF DAYSHOOKTHE COLOR OF NIGHT
CONEHEADSADDAMS FAMILY I
ADDAMS FAMILY IISINGLESCUTTHROAT ISLANDLAST ACTION HEROKULL THE CONQUEROR
VAMPIRE IN BROOKLYNSPRUNGJUDGE DREDD
WILD BILLHIGHLANDER III
VILLAGE OF THE DAMNEDFAIR GAME

Table 3: Clusters of movies found by Google Sets and Bayesian Sets based on the given queries. The
top 10 are shown for each query and each algorithm. Bayesian Sets was run using the EachMovie
dataset.

and while most of the movies returned by Bayesian Sets are also classic romances, hardly
any of the movies returned by Google Sets are romances, and it would be difficult to call
“Ernest Saves Christmas” either a romance or a classic. Both “Cutthroat Island” and “Last
Action Hero” are action movie flops, as are many of the movies given by our algorithm
for that query. All the Bayes Sets movies associated with the query “Mary Poppins” and“Toy Story” are children’s movies, while 5 of Google Sets’ movies are not. “But I’ma Cheerleader”, while appearing to be a children’s movie, is actually an R rated movie
involving lesbian and gay teens.
Q UERY: A.S MOLA , B.S CHOLKOPF
T OP M EMBERS
A.S MOLA
B.S CHOLKOPF
S.M IKA
G.R ATSCH
R.W ILLIAMSON
K.M ULLER
J.W ESTONJ.S HAWE -TAYLOR
V.VAPNIK
T.O NODA

T OP W ORDSVECTORSUPPORT
KERNELPAGES
MACHINESQUADRATICSOLVEREGULARIZATIONMINIMIZINGMINQ UERY: L.S AUL , T.JAAKKOLA
T OP M EMBERS
L.S AUL
T.JAAKKOLA
M.R AHIM
M.J ORDAN
N.L AWRENCE
T.J EBARA
W.W IEGERINCK
M.M EILA
S.I KEDA
D.H AUSSLER

T OP W ORDS
LOG
LIKELIHOODMODELSMIXTURE
CONDITIONALPROBABILISTICEXPECTATIONPARAMETERS
DISTRIBUTION
ESTIMATIONQ UERY: A.N G , R.S UTTONT OP M EMBERS
R.S UTTON
A.N G
Y.M ANSOUR
B.R AVINDRAN
D.KOLLER
D.P RECUP
C.WATKINS
R.M OLL
T.P ERKINS
D.M C A LLESTER

T OP W ORDSDECISION
REINFORCEMENTACTIONSREWARDSREWARD
START
RETURNRECEIVEDMDP
SELECTS

Table 4: NIPS authors found by Bayesian Sets based on the given queries. The top 10 are shown foreach query along with the top 10 words associated with that cluster of authors. Bayesian Sets was
run using NIPS data from vol 0-12 (1987-1999 conferences).

The NIPS author dataset is rather small, and co-authors of NIPS papers appear very similar
to each other. Therefore, many of the authors found by our algorithm are co-authors of a
NIPS paper with one or more of the query authors. An example where this is not the case is
Wim Wiegerinck, who we do not believe ever published a NIPS paper with Lawrence Saulor Tommi Jaakkola, though he did have a NIPS paper on variational learning and graphicalmodels.

As part of the evaluation of our algorithm, we showed 30 naı̈ve subjects the unlabeledresults of Bayesian Sets and Google Sets for the queries shown from the EachMovie andGroliers Encyclopedia datasets, and asked them to choose which they preferred. The resultsof this study are given in table 5.
Q UERY% BAYES S ETSP- VALUEWARRIORA NIMAL
F ISH

96.7
93.3
90.0
86.7
96.7
81.5

< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001
0.0008G ONE WITH THE W IND
M ARY P OPPINSC UTTHROAT I SLAND

Table 5: For each evaluated query (listed byfirst query item), we give the percentage of respondents who preferred the results given by
Bayesian Sets and the p-value rejecting the null
hypothesis that Google Sets is preferable toBayesian Sets on that particular query.

Since, in the case of binary data, our method reduces to a matrix-vector multiplication, we
also came up with ten heuristic matrix-vector methods which we ran on the same queries,
using the same datasets. Descriptions and results can be found in supplemental material on
the authors websites.

6

Conclusions

We have described an algorithm which takes a query consisting of a small set of items,
and returns additional items which belong in this set. Our algorithm computes a scorefor each item by comparing the posterior probability of that item given the set, to the priorprobability of that item. These probabilities are computed with respect to a statistical modelfor the data, and since the parameters of this model are unknown they are marginalized out.
For exponential family models with conjugate priors, our score can be computed exactly
and efficiently. In fact, we show that for sparse binary data, scoring all items in a large
data set can be accomplished using a single sparse matrix-vector multiplication. Thus, we
get a very fast and practical Bayesian algorithm without needing to resort to approximate
inference. For example, a sparse data set with over 2 million nonzero entries (Grolier) canbe queried in just over 1 second.
Our method does well when compared to Google Sets in terms of set completions, demonstrating that this Bayesian criterion can be useful in realistic problem domains. One of the
problems we have not yet addressed is deciding on the size of the response set. Since thescores have a probabilistic interpretation, it should be possible to find a suitable thresholdto these probabilities. In the future, we will incorporate such a threshold into our algorithm.
The problem of retrieving sets of items is clearly relevant to many application domains.
Our algorithm is very flexible in that it can be combined with a wide variety of types ofdata (e.g. sequences, images, etc.) and probabilistic models. We plan to explore efficient
implementations of some of these extensions. We believe that with even larger datasets theBayesian Sets algorithm will be a very useful tool for many application areas.
Acknowledgements: Thanks to Avrim Blum and Simon Tong for useful discussions, and to Sam
Roweis for some of the data. ZG was partially supported at CMU by the DARPA CALO project.

References[1] Google ™Sets. http://labs.google.com/sets[2] Lafferty, J. and Zhai, C. (2002) Probabilistic relevance models based on document and query generation. In Language
modeling and information retrieval.
[3] Ponte, J. and Croft, W. (1998) A language modeling approach to information retrieval. SIGIR.
[4] Robertson, S. and Sparck Jones, K. (1976). Relevance weighting of search terms. J Am Soc Info Sci.
[5] Tenenbaum, J. B. and Griffiths, T. L. (2001). Generalization, similarity, and Bayesian inference. Behavioral and Brain
Sciences, 24:629–641.
[6] Tong, S. (2005). Personal communication.