Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.

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 sorta the same, but not quiet.

What is the difference, 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?).

Any pointers much appreciated.

share|improve this question

2 Answers

up vote 3 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.

share|improve this answer

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.

share|improve this answer
Thanks for the pointer, I am going thru it. – Jason Jul 27 '12 at 17:14

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer: please explain why you're recommending it as a solution. Answers that don't explain anything will be deleted. See Good Subjective, Bad Subjective for more information.

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.