How do I use the SVD in collaborative filtering?

Question

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?

Answer 1

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!}

Answer 2

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.