teideal glic deisbhéalach

During a lunchtime conversation the other day, a coworker mentioned that he was hacking in his spare time on an entry for the Netflix Prize. This got me to thinking about collaborative filtering: why had I never seen a good description of how to do it? I suspect that people who might ordinarily have a casual interest in the subject hear that there are some statistics involved, whereupon they immediately freeze in the mathematical headlights, and turn the conversation to something else, anything else. In early 2005, a researcher named Daniel Lemire published, with Anna Maclachlan, a paper with the jazzy title of “Slope One Predictors for Online Rating-Based Collaborative Filtering“. This is an important paper, because it presents a family of really simple collaborative filtering schemes. I mean really simple: there are no statistics involved, just a little bit of linear algebra. Unfortunately, because the Lemire/Maclachlan paper is aimed at an academic audience, it’s not trivial to tell by merely reading it how simple the technique it presents is, so what follows is my attempt to translate its ideas into my native language of Attention Deficit Programmerese. To make things more concrete, I’m going to present an implementation in less than 40 lines of Python (and I’ll try to explain any obscure bits of Python as I go). Cool, huh? Regardless of the underlying implementation, collaborative filters tend to try to solve the same broad problem using much the same data.

1. You have your crowd of users.
2. You have your big pile of items.
3. Some of your users have been generous enough to tell you what they think of some of your items.
4. You want to hawk more items to a user, and you’d prefer to make your suggestions relevant to their likely interests.

Items 1 through 3 suggest that you could use the opinions that people have recorded about shiny doodads they have seen, to give a good guess as to which doodads they haven’t seen, but might like. I am not going to explain the mathematics behind the Slope One predictor, because Lemire and Maclachlan’s paper pretty much pulls the numerical justification out of a hat. I’m not immersed in the literature of the field, so I’ll be lazy and take them at their word when they say their approach works; and hey, that’s easy code to write, so let’s get hacking! (The scheme I’m going to talk about is referred to as “Weighted Slope One” in the Lemire and Maclachlan paper.) My Slope One implementation stores its data in two 2D matrices. The X and Y axes are identical in each matrix. If the items to be rated are “cuttlefish”, “octopus”, and “squid”, we end up with two 3×3 matrices, each with the following rows and columns: The coloured cells above indicate which elements of the matrix contain useful information. I’ll describe why most of the matrix is empty later. To keep things simple, let’s represent our matrices as two levels of Python dict objects (a dict is simply a hash table, if you’re not familiar with Python). The key of each dict is an item ID, so to get the matrix entry for “squid vs cuttlefish”, we look in the first-level dict for squid, then the second-level dict for cuttlefish.

class SlopeOne(object):

    def __init__(self):

        self.diffs = {}

        self.freqs = {}

The self.diffs matrix will hold differential ratings (I’ll describe what these are soon), and the self.freqs matrix will contain the number of times we’ve computed a differential rating for each pair of items. We’ll fill in the first and second levels of the dicts once we know what our data looks like, so let’s talk about the shape of the data. We need to be able to express ratings such as “Alice rated a squid as 1, and a cuttlefish as 4″. This is easy to express with two levels of dicts; the first maps from a user to all of that user’s ratings, and the second maps items to their ratings. In other words, our user data looks like this in Python:

userdata = dict(alice=dict(squid=1, cuttlefish=4)),

                bob=dict(squid=3, octopus=2))

The time has come to load the data into our matrices; let’s call the method update.

    def update(self, data):

To fill in the matrices, we must look at each rating from every user.

        for user, ratings in data.iteritems():

For each user and rating they have submitted, we will be iterating over every rating they have submitted a second time. The first thing we do is make sure that the necessary second-level dicts in each matrix exist.

            for item, rating in ratings.iteritems():

                self.freqs.setdefault(item, {})

                self.diffs.setdefault(item, {})

The setdefault call is an unfortunately ugly Pythonic idiom that means “if there’s no value for the given key (the first parameter) in the dict, assign it the given value (the second parameter)”. Inside this loop, we iterate over the user’s ratings again, to compare each rating against every other.

                for item2, rating2 in ratings.iteritems():

                    self.freqs[item].setdefault(item2, 0)

                    self.diffs[item].setdefault(item2, 0.0)

Here, we ensure that there are zeroes present in the matrix for every pair of ratings. (Notice that we’re using an integer zero to count frequencies, and a floating point zero for ratings.) For every pair of ratings, we modify the appropriate cell in self.freqs by adding one to the number of times we’ve seen that pair of ratings.

                    self.freqs[item][item2] += 1

And to update the self.diffs matrix, we compute the difference between the ratings for the two items.

                    self.diffs[item][item2] += rating - rating2

This is why I called self.diffs the “differential rating” matrix. Every time a user rates an item, we update the appropriate cells in this matrix to reflect the accumulated difference between that rating and every other rating the user has made. Once we’re done, we scale each differential rating based on the number of times we’ve seen that pair of items.

        for item, ratings in self.diffs.iteritems():

            for item2, rating in ratings.iteritems():

            ratings[item2] /= self.freqs[item][item2]

Now let’s pull the whole thing together, so you can see how simple this update method is.

    def update(self, data):

        for user, prefs in data.iteritems():

            for item, rating in prefs.iteritems():

                self.freqs.setdefault(item, {})

                self.diffs.setdefault(item, {})

                for item2, rating2 in prefs.iteritems():

                    self.freqs[item].setdefault(item2, 0)

                    self.diffs[item].setdefault(item2, 0.0)

                    self.freqs[item][item2] += 1

                    self.diffs[item][item2] += item - item2

        for item, ratings in self.diffs.iteritems():

            for item2, rating in ratings.iteritems():

                ratings[item2] /= self.freqs[item][item2]

That’s a measly 13 lines of code, 4 of which are due to us using dict objects to represent matrices. Nice! (By the way, notice that the update method made no use of the user IDs we passed in. This technique doesn’t care who rated what, just how an item has been rated. Collaborative filtering techniques that don’t use user information directly are called “item-based”, while those that do are called “user-based”.) It’s easy to fill out our matrices:

s = SlopeOne()

s.update(dict(alice=dict(squid=1.0, cuttlefish=4.0)),

              bob=dict(squid=1.0, octupus=3.0)))

With a little data in place, we’d like to make a prediction. To do this, we’ll pass the ratings a user has made to the predict method; it will return predictions of ratings for items the user hasn’t rated.

    def predict(self, userprefs):

We begin with two empty dicts; preds will accumulate prediction data, and freqs will accumulate counts.

        preds, freqs = {}, {}

We iterate over every item the user has rated, for items that have been rated by anyone (the try/except clause below lets us skip over unrated item pairs).

        for item, rating in userprefs.iteritems():

            for diffitem, diffratings in self.diffs.iteritems():

                try:

                    freq = self.freqs[diffitem][item]

                except KeyError:

                    continue

We make sure there are zeroes present in our dicts before we accumulate anything into them.

                preds.setdefault(diffitem, 0.0)

                freqs.setdefault(diffitem, 0)

The accumulation step is simple.

                preds[diffitem] += freq * (diffratings[item] + rating)

                freqs[diffitem] += freq

We must filter the result a little before we return it. We return a new dict, containing weighted predictions for every item, but omitting items that the user has rated (no point in predicting those), and omitting items for which we have a cumulative frequency of zero.

        return dict([(item, value / freqs[item])

                     for item, value in preds.iteritems()

                     if item not in userprefs and freqs[item] > 0])

And now let’s see the predict method without all of those intrusive comments, again to see how simple it is.

    def predict(self, userprefs):

        preds, freqs = {}, {}

        for item, rating in userprefs.iteritems():

            for diffitem, diffratings in self.diffs.iteritems():

                try:

                    freq = self.freqs[diffitem][item]

                except KeyError:

                    continue

                preds.setdefault(diffitem, 0.0)

                freqs.setdefault(diffitem, 0)

                preds[diffitem] += freq * (diffratings[item] + rating)

                freqs[diffitem] += freq

        return dict([(item, value / freqs[item])

                     for item, value in preds.iteritems()

                     if item not in userprefs and freqs[item] > 0])

Our proof-of-concept Weighted Slope One predictor clocks in at 33 lines of Python. If we had a sparse 2D matrix class handy, we could trim six of those lines. That’s not bad! It wouldn’t be difficult to go from this trivial implementation to something truly efficient. From the way we construct the matrices in the update method, we can make a few potentially space saving observations.

• Some portions of each matrix are entirely empty. They don’t contain zeroes; they contain nothing, because nobody has rated those pairs of items. If Alice rates squid and cuttlefish, while Bob rates squid and octopus, there will be no entries for cuttlefish vs octopus in either matrix.
• The diagonal of the self.diffs matrix will always be either empty or zero, so there’s no need to store values on the diagonal of the self.freqs matrix.
• Each entry in the upper right of the self.diffs matrix is the negative of the symmetric entry in the bottom left. The upper right of the self.freqs matrix is symmetric to the bottom left (corresponding entries have identical values).

We could thus represent each matrix as a strictly lower triangular matrix. Because much of a matrix is going to be empty for real databases of items and ratings, we would save a lot by storing it in sparse form. If you want to build a web site that uses collaborative filtering, and you’re not a specialist, the Slope One scheme has a lot going for it. It is simple to implement, and the arithmetic is easy to understand (in stark contrast to techniques that use singular value decomposition, cosine correlation or Pearson’s correlation coefficient, or other gymnastic statistical approaches). It’s also easy to see that updates and predictions can both be performed in data parallel style (predictions are easy to express in mapreduce form). Better yet, it’s easy and cheap to update the Slope One data structures on the fly, instead of taking everything offline and performing a heavyweight nightly thrashing of a database. You can download a copy of my sample Weighted Slope One implementation as slope_one.py. Have fun!