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?

up vote 25 down vote accepted

$\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.

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.

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

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.
  • 1. You want to choose a low k to avoid overfitting (much lower than whatever the dimensions of X are). This is basically for the same reason that linear regression is a better choice than a quintic for fitting a dataset of 6 points. 2. You don't know what the unknown entries are supposed to be, so you can't measure "the element-wise MSE" across them. My procedure fills up the missing values with numbers that were derived by minimizing error against the known values (and constraining that the matrix must be low-rank). – Stumpy Joe Pete Nov 19 '14 at 17:38

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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