Human intuition behind SVD in case of recommendation system

Question

This does not answer my question. I struggled very hard to understand the SVD from a linear-algebra point of view. But in some cases I failed to connect the dots. So, I started to see all the application of SVD. Like movie recommendation system, Google page ranking system, etc.

Now in the case of movie recommendation system, what I had as a mental picture is...

The SVD is a technique that falls under collaborative filtering. And what the SVD does is factor a big data matrix into two smaller matrix. And as an input to the SVD we give an incomplete data matrix. And SVD gives us a probable complete data matrix. Here, in the case of a movie recommendation system we try to predict ratings of users. Incomplete input data matrix means some users didn't give ratings to certain movies. So the SVD will help to predict users' ratings. I still don't know how the SVD breaks down a large matrix to smaller pieces. I don't how the SVD determines the dimensions of the smaller matrices.

It would be helpful if anyone could judge my understanding. And I will very much appreciate any resources which can help me to understand the SVD from scratch to its application to Netflix recommendation systems. Also for the Google Page ranking system or for other applications.

I am looking forward to seeing an explanation more from human-intuition level and from a linear-algebra point of view. Because I am interested in using this algorithm in my research, I need to understand as soon as possible: how does the SVD work deep down from the core?

Answer 1

You're confusing the SVD with a matrix completion algorithm. The SVD takes an $(m \times n)$ data matrix $M$ and factors it into $M = U \Sigma V^\text{T}$, whereas a matrix completion algorithm takes a matrix with missing entries and fills them in according to some criterion. In particular, the SVD is not a collaborative filtering technique for recommendation systems like you're talking about, and it factors any matrix into three matrices, not two, and it cannot accept a matrix with missing entries as input.

If what you really want is some intuition about matrix completion algorithms, you need to understand that the key assumption behind them is that the given $(m \times n)$ matrix $M$ has a low rank, which means that $\text{rank}(M) < \min(m, n)$. In the case of the Netflix problem, we suppose that all Netflix customers fall into one of several groups that all rate movies approximately the same way. If we have only 5 movies that are being considered, and 6 customers, you might have a ratings matrix like this $$ \left[ \begin{matrix} 1 & 1 & 5 & 5 & 5 & 2\\ 2 & 2 & 1 & 1 & 1 & 1\\ 5 & 5 & 5 & 5 & 5 & 3\\ 5 & 5 & 4 & 4 & 4 & 4\\ 3 & 3 & 2 & 2 & 2 & 4 \end{matrix} \right] $$ where each row corresponds to a movie and each column corresponds to a customer. The customers fall into three different groups, with the customers 1 and 2 having identical ratings for all 5 movies, customers 3, 4, and 5 having identical ratings for all 5 movies, and customer 6 having a group with only themselves. This makes the matrix have $\text{rank}(M) = 3$, because there are only three linearly independent columns. If this is the true ratings that each customer would give if they saw and rated all 5 movies, then if we erased an entry to make a matrix $$ \left[ \begin{matrix} 1 & 1 & 5 & 5 & 5 & 2\\ 2 & 2 & 1 & 1 & 1 & 1\\ 5 & 5 & 5 & * & 5 & 3\\ 5 & 5 & 4 & 4 & 4 & 4\\ 3 & 3 & 2 & 2 & 2 & 4 \end{matrix} \right] $$ where $*$ denotes an unknown or erased entry, knowing that $\text{rank}(M) = 3$ is enough information to fill in the missing entry because if it was anything other than a 5 the rank of the matrix would then be 4 not 3.

To intuitively understand how the SVD relates to solving this problem, you also need to understand that the entries of the matrix $\Sigma$ (called the singular values of the matrix $M$) also tell you about the rank of $M$. To be specific, $\text{rank}(M) = \text{(the number of non-zero singular values)}$. Matrix completion algorithms are more complicated in reality, but the idea is essentially the same as in this simple example with one erased entry.

To learn what you need to understand matrix completion algorithms, you're going to have to learn a fair amount of linear algebra. A textbook might be the best place to start, but you could try learning about these topics in sequence:

1. The rank of a matrix
2. The eigenvalue decomposition of a matrix (precursor to the SVD)
3. The SVD
4. Matrix completion