SVD of a matrix with missing values

Question

Suppose I have a Netflix-style recommendation matrix, and I want to build a model that predicts potential future movie ratings for a given user. Using Simon Funk's approach, one would use stochastic gradient descent to minimize the Frobenius norm between the full matrix and the item-by-item * user-by-user matrix combined with an L2 regularization term.

In practice, what do people do with the missing values from the recommendation matrix, which is the whole point of doing the calculation? My guess from reading Simon's blog post is that he ONLY uses the non-missing terms (which consist of (say) ~1% of the recommendation matrix) to build a model (with some judicious choice of hyper-parameters and regularization) to predict the other 99% of the matrix?

In practice, do you really skip all those values? Or do you infer as much as possible BEFORE doing stochastic gradient descent? What are some of the standard best practices for dealing with the missing values?

Answer 1

Yes, in practice those values are skipped. In your description in terms of a Frobenius norm, this corresponds to minimising the components of the norm which can be measured, i.e. those which have known ratings. The regularisation term can be seen as a Bayesian prior on the components of the feature vectors, with the SVD calculating the maximum likelihood estimator, subject to this prior and the known values.

It's probably best to think of the SVD as a method for inferring the missing values. If you've already got a better way of doing this, why do you need the SVD? If you don't, then the SVD will happily fill in the gaps for you.

Answer 2

In practice, what do people do with the missing values from the recommendation matrix, which is the whole point of doing the calculation? My guess from reading Simon's blog post is that he ONLY uses the non-missing terms to build a model.

That's right -- that's the point of his and your model, to predict the missing terms, right? It's a crucial point that many actually forget. They think they can just "assume" to pre-assign a constant to missing data without a care in the world, and things will magically work out well enough from an SVD. Garbage in, garbage out: It's real, and you had better watch it. You'd better not feed junk data to a model if you want something useful to result.

It is certainly NOT "best to infer any missing values" on majority sparse dataset and then run SVD on that with some hope to impute values for you (which you already imputed before you ran SVD, right?). What do you think, a model is magic? THere is no magic nor technology to overcome majority garbage data. You cannot lie to a model that data is real data when it's not real at all, but really just some junk you just plain made up from thin air.

SVD does other useful things so I'm certainly not saying SVD is worthless in the least. Go ahead and use SVD only on complete datasets, perhaps which you've intelligently imputed missing values on already using a machine learning model with all due attention to bias error and variance error during its development.

Machine learning is the way. So if you still want to know how to impute values using a matrix factorization design, there are certainly good ways to do exactly this using machine learning, and importantly they don't feed any junk data to a model to pointlessly attempt to learn from.

Exactly such a machine learning matrix factorization model is presented quite well by the instructors of the Stanford online course Mining Massive Data Sets, in module 5. They show you the math and explain the model. They don't code it up for you though.

It's OK because you can code it up yourself, if you understand basic machine learning. Do you know what a loss function and a cost function are? Regularization? Gradient descent? ARe you OK with matrix multiplication and addition? Bias error and variance error? If so then you are good. If not then you should consider to take Andrew Ng's online course Machine Learning at Coursera, which is one of the many good starting places. Then also go take the online course Mining Massive Data Sets which talks exactly about matrix factorization and machine learning for making recommender models.

Suffice it to say, you can completely design as well as code up your own factorization model which handles missing data very well, just like Simon Funk did, and you can do it from scratch but it's not hard at all any more like it was back in his day, because now you can use a tool like TensorFlow or Microsoft CNTK which does a lot for you. Define a loss function and a cost function, choose an optimizer, partition your dataset into training, dev, test from the data that's actually available (labeled data) and let it run. Seriously, it works. It's not easy debugging TF and its graph building errors, but it can work great in the end and takes less than one page of code.

Specifically, one way to not feed fake data to a matrix factorization machine learning model, is to skip over the missing data's matrix elements in your loss and cost functions.

Answer 3

There is a thesis which reviews many recommendation systems and compares them, but does not talk about long term tracking of the missing items, for example, to test the predictions. That's part of your question? Using the time component in that way? Among the many papers and methods the thesis reviews are time aware/sensitive systems, such as the research in the Rendle papers. If your question is also about handling sparsity of data, that is also discussed in detail throughout the thesis and there are many methods. sparse matrices and imputation with zeroes or matrix factorization that adds a linking matrix of clustering of users (users who rate items similarly) or a linking matrix of clustering of items.

The thesis title is "Low Rank Models for Recommender Systems with Limited Preference Information" by Evgeny Frolov https://www.skoltech.ru/app/data/uploads/2018/09/Frolov_Dissertation_Final1.pdf