What happens when you apply SVD to a collaborative filtering problem? What is the difference between the two?

Question

In Collaborative filtering, we have values that are not filled in. Suppose a user did not watch a movie then we have to put an 'na' in there.

If I am going to take an SVD of this matrix, then I have to put some number in there - say 0. Now if I factorize the matrix, I have a method to find similar users (by finding out which users are closer together in the reduced dimensional space). But the predicted preference itself - for a user to an item will be zero. (because thats what we entered on the unknown columns).

So I am stuck with the problem of collaborative filtering vs SVD. They seem to be almost the same, but not quite.

What is the difference between them and what happens when I apply an SVD to a collaborative filtering problem? I did, and the results seem acceptable in terms of finding nearby users, which is great, but how?

Answer 1

$\DeclareMathOperator*{\argmin}{arg\,min}$ Ok, when you say SVD, presumably you're talking about truncated SVD (where you only keep the $k$ biggest singular values). There are two different ways to look at the truncated SVD of a matrix. One is the standard definition:

First you do the SVD: $\underset{n\times m}{X} = \underset{n\times n}{U} \overset{n\times m}{\Sigma} \underset{m\times m}{V^T}$, where $U$ and $V$ are rotation matrices, and $\Sigma$ has the singular values along the diagonal. Then you pick the top $k$ singular values, zero out the rest, and hack off irrelevant rows and columns to make a $k$-rank approximation to the original: $X \approx \tilde{X} = \underset{n\times k}{\tilde{U}} \overset{k\times k}{\tilde{\Sigma}} \underset{k\times m}{\tilde{V}^T}$

This is all fine and dandy (and easy to implement in R or matlab), but it doesn't make sense when talking about matrices with missing values. However, there's an interesting property of the $k$-truncated SVD--It's the best $k$-rank approximation to the original! That is:

$ \tilde{X} = \argmin_{B : rank(B)=k} \displaystyle\sum\limits_{i,j} (X_{ij} - B_{ij})^2$

This property seems easy to generalize to the missing value case. Basically you're looking for a $k$-rank matrix that minimizes the element-wise mean squared error across the known entries of the original matrix. That is, when you're training the system, you ignore all of the missing values. (For tips on how you might actually go about finding a $k$-rank approximation, here are some places to look).

Then, once you've come up with a suitably "close" $k$-rank approximation to the original, you use it to fill in the missing values. That is, if $X_{ij}$ was missing, then you fill in $\tilde{X}_{ij}$. Tada! You are now done.

Answer 2

It seems like there are a lot of approaches on how to deal with missing values. The following paper with review in Section 1.3 may be a good starting point.

Answer 3

I need more reputation to comment on Stumpy Joe Pete's answer therefore I post this as an answer.

Stumpy thanks for the answer although I think it needs a bit of clarification. Particularly I mean this sentence:

Basically you're looking for a k-rank matrix that minimizes the element-wise mean squared error across the known entries of the original matrix.

First - wouldnt the highest rank always minimize this, or actually reconstruct the original X matrix? Secondly - Why would you only take the known entries. Intuitively it makes sense, but the procedure is actually also fitting the empty places which were replaced with some reasonable numbers.

My approach would be to carry out something like a cross validation:

1. Fill in the empty places with 0s or means or another reasonable number.
2. Replace one of the n known elements with 0 or a reasonable number
3. Carry out SVD reconstruction of rank k
4. Check the value of the known reconstructed element.
5. repeat for all possible known elements and calculate MSE
6. repeat for all possible k and choose the one with lowest MSE.