Matches, Recommendations and the Netflix Challenge

What is collaborative filtering (CF)?

• From a user's point of view:
        → "I'd like to know what users like me rate highly"

• From a seller's point of view:
        → I'd like to predict what a user would like based on ratings or purchases from similar users.

• Origin of the term:
  • Email system add-on called Tapestry devised by Goldberg et al [Gold1992] in 1992.
  • Users rate email content or record actions "e.g., replied".
  • Users filter email based on others' ratings or actions
          → e.g., "Include all emails that Alice replied to".

• The current use is more technical:
  • Users rate some items.
  • Goal: predict a user's rating of some item they have not rated.
  • This approach was developed by the pioneering GroupLens project on movie ratings in 1994 [Resn1994].

• Define ratings matrix A_ij as follows
        A_ij = user i's rating of item j.

• Example with 5 users, 8 items:
  • Consider the following ratings matrix:

    
                      1   2   3   4   5   6   7   8
             Alice  |     1       5   5       3     |
             Bob    | 4       2           1       2 |
             Chen   |     1                         |
             Dave   |     2       4           3     |
             Ella   |     5       1   1           5 |
             

  • Alice and Bob have no overlap.
  • Alice and Dave have similar ratings.
          → Can predict Dave's rating of item 5 as "high".
  • Alice and Ella rate many items in common, but differently.
  • Chen offers very little data.
          → Hard to find a similar user.

• The Netflix Challenge:
  • Started in October 2006.
  • Ratings from 480,189 users on 17,770 movies.
  • Total of 100,480,507 ratings.
  • Test test of about 1 million missing ratings.
  • Goal: predict missing ratings.
  • Challenge: beat Netflix's own algorithm by 10%.
  • Won by a combination of teams in 2009.

Approaches to CF:

• Data-driven approach:
  • Use the data to compute similarities between users or items.
  • Generate a prediction based on the data from similar users/items.
  • Also called the memory-based approach.

• Model-driven approach:
  • Use the data to build a statistical model.
          → And estimate that model's parameters.
  • Use model for prediction.

• Hybrid approaches: these combine the above two.

• Henceforth, we'll assume the following version of the CF problem:
  • We are given the user-item ratings matrix A.
  • The goal: predict missing entry A_uv.
          → User u's rating of item v.

The data-driven approach:

• This approach was pioneered by the GroupLens project [Resn1994].

• Since then it has been refined and modified by several others.

• Two kinds:
  • User-similarity: find similar users to user u who have rated v and use their ratings.
  • Item-similarity: find similar items to item v, and use the ratings of these items.

• Let's first focus on the user-similarity approach.

  
  Algorithm: userSimilarity (A, u, v)
  Input: ratings matrix A, and desired missing entry A[u,v]
       // Compute distances to other users.
  1.   for each user i
  2.      s[i] = similarity (i, u)
  3.   endfor
  
       // Find a set of "close" or similar users.
  4.   similar-user-set S = φ
  5.   for each user i that has rated item j
  6.       if similarEnough (i, u)
  7.           add i to S
  8.       endif
  9.   endfor
  
       // Use the ratings of these users to predict user u's rating v.
  10.  r = combineRatings (S, v)
  11.  return r
       

• The details of similarity() similarEnough() and combineRatings() differentiate various algorithms in this category.
        → We will only look at a few ideas - see the references for more details.

• First, observe that rows of A are user-vectors:
  • For example, consider this matrix:

    
                      1   2   3   4   5   6   7   8
             Alice  |     1       5   5       3     |
             Bob    | 4       2           1       2 |
             Chen   |     1                         |
             Dave   |     2       4           3     |
             Ella   |     5       1   1           5 |
             

  • The vector for user Bob is: (4, 0, 2, 0, 0, 1, 0, 2) (assuming 0 is not a rating).

  Exercise: What is the cosine of the angle between the "Alice" and "Dave" vectors? What is the cosine of the angle between the "Alice" and "Chen" vectors?

• Similarly, columns are item-vectors:
  • For example:

    
                      1   2   3   4   5   6   7   8
             Alice  |     1       5   5       3     |
             Bob    | 4       2           1       2 |
             Chen   |     1                         |
             Dave   |     2       4           3     |
             Ella   |     5       1   1           5 |
             

• Computing similarity: several ways
  • Inverse Mean-square difference between the vectors for two rows.

    

  • Cosine of angle between vectors.

    

  • Pearson-correlation between the vectors.

    

• Many ways of identifying the "close-enough" ones:
  • Keep the K closest ones (where K is an algorithm parameter).
  • Maintain a threshold δ and keep those users within this distance.

• Combining ratings from close users on item v:
  • Average their ratings.

    

  • Take a weighted average, weighted by similarity

    

  • Offset weighted average by the mean.
          → Because some users tend to have high averages or low averages.

    

  • Note: κ is a normalizing factor.
  • More complex statistical techniques such as multiple-regression have been tried [Hill1995].

• The item-similarity approach: [Sarw2001]
  • Recall: our goal is to estimate A_uv.
  • In this approach: find a set of similar items I.
  • Use the ratings of users for the items in I.

• How to find similar items?
  • Use the same types of vector-similarity measures as in comparing users.
          → Only this time, we use the columns of A.
  • Thus, items are similar if many users tend to rate them similarly.

• How to combine ratings?
  • Again, using the same ideas as in user-similarity.
  • Find those items in I that have ratings for user u.
  • Combine those ratings as above.

Model-based approaches:

• Model-based approaches try to uncover some underlying "structure" if such a structure exists or can be approximated.

• For example: we "know" intuitively that users can be divided into "sci-fi movies", "romance movies" and the like.

• If we can identify the user as one of these types, our prediction success might go up.

• We'll next look at a few model-based approaches.

Simple clustering:

• Create user categories.
        → These could be done by hand (e.g., "sci-fi", "romance" etc).

• For each user, identify their category.

• To compute A_uv:
  • Identify u's category c.
  • Find users in c who have rated v.
  • Combine their ratings using some kind of averaging.

• How do we classify users into categories?
  • Create "fake" user vectors, one for each category.
          → These serve as prototypes for the categories (ideal users).
  • Each such vector will have high ratings for the movies in that category, low for the others.
          → This means we need to "know" these categories.
  • Then, one can use vector-similarity with these category prototypes.
  • Example:

    
                      1   2   3   4   5   6   7   8
             Alice  |     1       5   5       3     |
             Bob    | 4       2           1       2 |
             Chen   |     1                         |
             Dave   |     2       4           3     |
             Ella   |     5       1   1           5 |
    
             Sci-fi | 0   5   0   5   0   0   0   0 |      // Movies 3 and 5 are sci-fi movies. Rest of the ratings are 0. 
             

  • How to do this without pre-defined categories:
    • Initially, we'll create K empty clusters.
    • Initially, assign each user to a random cluster.
    • Treat each user-vector as a point in n space.
    • Compute the average "point" (the cluster mean) in each cluster.
    • Now, for each user, identify closest mean and re-classify the user accordingly.
    • Repeat.

    This is called K-means clustering.

    
    Algorithm: K-means (A, u, v)
    Input: ratings matrix A, and desired missing entry A[u,v]
    1.   for each user i
            // Initially assign each user to a random cluster.
    2.      cluster[i] = random (1, K)
    3.   endfor
    
    4.   while not converged
            // Find the mean of each cluster and assign users to the cluster whose mean they are closest to.
    5.      Mk = computeMean (Ck)
    6.      for each user i
    7.         find closest cluster mean k
    8.         cluster[i] = k
    9.      endfor
    10.  endwhile
    
    11.  k = cluster for user u
    12.  S = users in Ck that have rated v
    13.  r = combineRatings (S, v)
    14.  return r
             

A probabilistic approach: the Naive-Bayes method

• Let user u's vector of ratings be (u₁,...,u_n).

• We want to predict u_v, one of the missing ones.

• Suppose we treat this as the random variable U_v.

• Then, in a 5-point rating system, such a random variable can take values 1,2, ... ,or 5.

• We ask the question: what is
        Pr[U_v=r | u₁,...,u_n].

• That is, given the known ratings (u₁,...,u_n). what is the probability that the unknown one is r?
        (Where r is either 1,2, ..., or 5.)

• If we had these probabilities, how do we actually pick the rating?
        → The simplest way: pick the rating r whose probability Pr[U_v=r | u₁,...,u_n]. is highest.

• One way to do this:
  • Find other users who have rated both (u₁,...,u_n). and u_v.
  • Estimate Pr[U_v=r | u₁,...,u_n]. from this data by simple averaging.
  • For this to be possible, the matrix A needs to be dense
          → The data has to be rich enough to find many such "high-overlap" users.
  • Unfortunately, this is not the case in practice (at least for movie data).
  • Some applications explicitly ask the user to rate 10-15 items so that all users have rated the same items.

• So, let's examine a way around this problem: the Naive Bayes approach.

• Using Bayes' rule
        Pr[U_v=r | u₁,...,u_n]
        = Pr[u₁,...,u_n | U_v=r] Pr[U_v=r] / Pr[u₁,...,u_n]
  • Note that Pr[u₁,...,u_n] is the simply the user-independent probability of observing the known ratings.
  • This is a "constant" for the system.
          → We will absorb it in a normalizing constant.
  • Thus, Pr[U_v=r | u₁,...,u_n]   ∝   Pr[u₁,...,u_n | U_v=r] Pr[U_v=r]

• Next, we will assume independence between items and write
        Pr[u₁,...,u_n | U_v=r]   =   Π_i Pr[u_i | U_v=r]

• Each of these can be estimated because there's hope that we can find users who've rated both item v and item i.

• Similarly, Pr[U_v=r] can be estimated from the column vector for item v.

• Thus, we can estimate
        Pr[U_v=r | u₁,...,u_n]   =   κ Pr[u₁,...,u_n | U_v=r] Pr[U_v=r]   =   κ Pr[U_v=r] Π_i Pr[u_i | U_v=r]
  where κ is a normalizing constant.

• In fact, we don't need to worry about the normalizing constant at all:
  • We are interested in picking that rating r for which Pr[U_v=r | u₁,...,u_n] is largest.
  • This is the same as picking the rating for which
          Pr[U_v=r] Π_i Pr[u_i | U_v=r]
    is highest (without the normalizing constant).

• Let's outline this approach with some pseudocode:

  
  Algorithm: naiveBayes (A, u, v)
  Input: ratings matrix A, and desired missing entry A[u,v]
        // Estimate Pr[Uv=r].
  1.    for each rating value r
  2.        num_v_r = # users that rated v as r
  3.        num_v = # users that rated v
  4.        RatingEstimate[r] = num_v_r / num_v
  5.    endfor
  
        // Estimate Pr[ui | Uv=r] for each possible i and r.
  6.    for each r
  7.        for each item j ≠ v
  8.            num_u_j_r = # users that rate j as uj and v as r
  9.            num_v_r = # users that rated v as r
  10.           conditionalRating[j] = num_u_j_r / num_v_r
  11.       endfor
  12.   endfor
  
        // Estimate Pr[Uv=r |  u1,...,un] using the product and identify the largest.
  13.   rmax = 0
  14.   for each r
  15.       product[r] = ratingEstimate[r]
  16.       for each item j ≠ v
  17.           product[r] = product[r] * conditionalRating[j]
  18.       endfor
  19.       if product[r] > rmax
  20.           rmax = product[r]
  21.       endif
  22.   endfor
  
  23.   return rmax
           

• The Bayes approach has been used in book recommendation engines [Moon1999].

Machine learning:

• The field of machine-learning has grown tremendously in the past 10-20 years.
        → Several sophisticated mc-learning algorithms have been developed.

• There are many types of mc-learning problems.
        → The one most applicable to CF is classification.

• The classification or supervised learning problem:
  • There are m so-called classes
          C₁, ... ,C_m
  • We are given a d-dimensional input or query vector
          x = (x₁, ... ,x_d)
  • The objective: classify x into the "best" class.
  • To train a classifer, we are also give training data, a number of previously classified vectors:
          x₁, y₁    - training vector 1 and its known class y₁
          x₂, y₂    - training vector 2 and its known class y₂
          ...
          x_k, y_k    - training vector k and its known class y_k

• A machine learning algorithm:
  • Uses the training data to "train" a d-dimensional function F such that
          y = F(x) = F(x₁, ..., x_d).
  • Thus, F computes the class for an input vector
          x = (x₁, ... ,x_d)

• How can machine-learning be applied to CF? Here are two simple ways:

• First, for simplicity, let's re-order the matrix A's rows and columns so that the missing entry is at the bottom right.

  
                    1   2   3   4   5   6   7   8
           Alice  |     1       5   5       3   3 |
           Bob    | 4       2           1       2 |
           Chen   |     1                         |
           Ella   |     5       1   1           5 |
           Dave   |     2       4   2       3   ? |    // Desired missing entry is for last user and last item.
           

• Then, one way to create a mc-learning problem is user-based:
  • The classes are the possible ratings 1, 2, ..., 5.
  • Treat the rows up to column d = n-1 as training vectors with the known classes in the last column.

    
                        TRAINING VECTORS             CLASS
             Alice  |     1       5   5       3  |     3 |
             Bob    | 4       2           1      |     2 |
             Ella   |     5       1   1          |     5 |
    
    		    QUERY VECTOR
             Dave   |     2       4   2       3  |     ? |    
             

• The same thing could be item-based, using columns:
  • Treat the columns as vectors.

    
    	              TRAINING             QUERY
                          2     4   5     7      8
             Alice  |     1     5   5     3  |   3 |
             Bob    |                        |   2 |
             Chen   |     1                  |     |
             Ella   |     5     1   1        |   5 |
    
             Dave   |     2     4   2     3  |   ? |    <-  class (y) values
             

• Two problems with this approach:
  • A zero rating is treated the same as a low rating.
  • The matrix is often too large (vectors too wide).

• More sophisticated approaches:
  • Use matrix compression via factoring
          → Methods like SVD.
  • Specialized factoring or preprocessing.

References and further reading