Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

I'm a bit confused with how the SVD is used in collaborative filtering. Suppose I have a social graph, and I build an adjacency matrix from the edges, then take an SVD (let's forget about regularization, learning rates, sparsity optimizations, etc), how do I use this SVD to improve my recommendations?

Suppose my social graph corresponded to instagram, and I was tasked with the responsibility of recommending users in the service, based only on the social graph. I would first build an adjacency matrix A (mxm), take the SVD, A = U s V, choose the first k eigenvalues, then what?

I would presumably create a new set of matrices:

U_new ~ mxk

s_new ~ kxk

V_new ~ kxm

then what does one do?

I've looked on the web, and most links focus on calculating the SVD, but no one tells you what to do with it. So what should I do?

share|improve this question

3 Answers 3

up vote 8 down vote accepted

I would like to offer a dissenting opinion:

Missing Edges as Missing Values

In a collaborative filtering problem, the connections that do not exist (user $i$ has not rated item $j$, person $x$ has not friended person $y$) are generally treated as missing values to be predicted, rather than as zeros. That is, if user $i$ hasn't rated item $j$, we want to guess what he might rate it if he had rated it. If person $x$ hasn't friended $y$, we want to guess how likely it is that he'd want to friend him. The recommendations are based on the reconstructed values.

When you take the SVD of the social graph (e.g., plug it through svd()), you are basically imputing zeros in all those missing spots. That this is problematic is more obvious in the user-item-rating setup for collaborative filtering. If I had a way to reliably fill in the missing entries, I wouldn't need to use SVD at all. I'd just give recommendations based on the filled in entries. If I don't have a way to do that, then I shouldn't fill them before I do the SVD.*

SVD with Missing Values

Of course, the svd() function doesn't know how to cope with missing values. So, what exactly are you supposed to do? Well, there's a way to reframe the problem as

"Find the matrix of rank $k$ which is closest to the original matrix"

That's really the problem you're trying to solve, and you're not going to use svd() to solve it. A way that worked for me (on the Netflix prize data) was this:

  • Try to fit the entries with a simple model, e.g., $\hat{X}_{i,j} = \mu + \alpha_i + \beta_j$. This actually does a good job.

  • Assign each user $i$ a $k$-vector $u_i$ and each item $j$ a $k$-vector $v_j$. (In your case, each person gets a right and left $k$-vector). You'll ultimately be predicting the residuals as dot products: $\sum u_{im}v_{jm}$

  • Use some algorithm to find the vectors which minimize the distance to the original matrix. For instance, use this paper

Best of luck!

* : What Tenali is recommending is basically nearest neighbors. You try to find users who are similar and make recommendations on that. Unfortunately, the sparsity problem (~99% of the matrix is missing values) makes it hard to find nearest neighbors using cosine distance or jaccard similarity or whatever. So, he's recommending doing an SVD of the matrix (with zeros imputed at the missing values) to first compress users into a smaller feature space and then do comparisons there. Doing SVD-nearest-neighbors is fine, but I would still recommend doing the SVD the right way (I mean... my way). No need to do nonsensical value imputation!

share|improve this answer
    
This was actually the response I was looking for, and wanted to hear :) Thank you very much! –  Vishal Sep 1 '12 at 2:14
    
Oddly the question asked "I've looked on the web, and most links focus on calculating the SVD, but no one tells you what to do with it. So what should I do?" or for that matter the title says, " How do I use the SVD in collaborative filtering?" –  TenaliRaman Sep 1 '12 at 3:15
    
Yep, and my answer summarized how I use it in collaborative filtering. –  Stumpy Joe Pete Sep 1 '12 at 3:45
    
And my +1 to your answer. My comment was for the OP. I understood the problem to be - I have done SVD but I don't know what to do next. –  TenaliRaman Sep 1 '12 at 4:02
1  
Thanks, not trying to argue ^_^ Take it easy. –  Stumpy Joe Pete Sep 1 '12 at 4:04

The reason no one tells you what to do with it is because if you know what SVD does, then it is a bit obvious what to do with it :-).

Since your rows and columns are the same set, I will explain this through a different matrix A. Let the matrix A be such that rows are the users and the columns are the items that the user likes. Note that this matrix need not be symmetric, but in your case, I guess it turns out to be symmetric. One way to think of SVD is as follows : SVD finds a hidden feature space where the users and items they like have feature vectors that are closely aligned.

So, when we compute $A = U \times s \times V$, the $U$ matrix represents the feature vectors corresponding to the users in the hidden feature space and the $V$ matrix represents the feature vectors corresponding to the items in the hidden feature space.

Now, if I give you two vectors from the same feature space and ask you to find if they are similar, what is the simplest thing that you can think of for accomplishing that? Dot product.

So, if I want to see user $i$ likes item $j$, all I need to do is take the dot product of the $i$th entry in $U$ and $j$th entry in V. Of course, dot product is by no means the only thing you can apply, any similarity measure that you can think of is applicable.

share|improve this answer
    
Two questions: 1) Do you fill missing values with zero (item j not reviewed by user i) before running SVD? 2) How do you compute if a new user will like item j? –  B_Miner Oct 26 '13 at 3:25
    
@B_Miner Hi, sorry for the delayed response. The answers: 1) Well, yes, we usually fill the missing values with zero before running SVD. However, I usually recommend to fill it with non-zero rating - for example, you can fill the missing values by the average rating that the user has given so far. 2) SVD-based approach is for only known users and known items. It cannot handle new users or new items. And how can it, if a new user comes in, we don't know anything about him in this framework to predict. –  TenaliRaman Nov 4 '13 at 10:08
    
@B_Miner If you want to work with new users/items, we have to assume that we have access to some user features and item features. Then, you can use a more sophisticated model like PDLF (Predictive Discrete Latent Factor model). This will allow you to handle new users/items because it works with a known feature space. –  TenaliRaman Nov 4 '13 at 10:10

However: With pure vanilla SVD you might have problems recreating the original matrix, let alone predicting values for missing items. The useful rule-of-thumb in this area is calculating average rating per movie, and subtracting this average for each user / movie combination, that is, subtracting movie bias from each user. Then it is recommended you run SVD, and of course, you would have to record these bias values somewhere, in order to recreate ratings, or predict for unknown values. I'd read Simon Funk's post on SVD for recommendations - he invented an incremental SVD approach during Netflix competition.

http://sifter.org/~simon/journal/20061211.html

I guess demeaning matrix A before SVD makes sense, since SVD's close cousin PCA also works in a similar way. In terms of incremental computation, Funk told me that if you do not demean, first gradient direction dominates the rest of the computation. I've seen this firsthand, basically without demeaning things do not work.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.