8
$\begingroup$

This might be a very stupid question, but I have read the great comments regarding how to deal with missing values before applying SVD, but I would like to know how it works with a simple example:

        Movie1 Movie2 Movie3
User1     5             4
User2     2      5      5
User3            3      4
User4     1             5
User5     5      1      5

Given the matrix above, if I remove the NA values, I will end up having only User2 and User5. This means that my U will be 2 × k. But if I predict the missing values, U should be 5 × k, which I can multiply with singular values and V.

Would anyone of you fill in the missing values in the matrix above by first removing users with missing values and then applying SVD? Please provide a very simple explanation of the procedure you applied and make your answer practical (i.e. number multiplied with another number gives an answer) rather than using too much math symbols.

I apologize for a very stupid question, but I just want to really grasp the content. I've read the following links:

stats.stackexchange.com/q/33142

stats.stackexchange.com/q/31096

stats.stackexchange.com/q/33103

$\endgroup$
  • $\begingroup$ Everyone did not watch at least one movie, right? So removing all users who have missing data will result in zero users, and zero rows in your utility (rating) matrix. So you cannot remove any rows that are missing some data, right? SVD is not helpful for datasets with missing values. There are other matrix factorization techniques however which can impute them. Look, SVD would need you to impute missing data in advance, some other way. You can do imputation the silly way by just using any old constant but then what is the point of using such garbage data? Do you want garbage to be output? $\endgroup$ – Geoffrey Anderson Apr 27 '18 at 13:44
5
$\begingroup$

SVD is only defined for complete matrices. So if you stick to plain SVD you need to fill in these missing values before (SVD is not a imputing-algorithm per se). The errors you introduce will hopefully be cancelled out by your matrix-factorization approach (general assumption: data is generated by a low-rank model).

Removing complete rows like you want to do is just bad. Even setting the missing values to zero would be better.

There are many imputation strategies, but in this case, i would impute with the column-mean (or maybe row-mean). This is basically the strategy recommend in your 2nd link.

        Movie1 Movie2 Movie3
User1   5             4
User2   2      5      5
User3          3      4
User4   1             5
User5   5      1      5

becomes (column-mean; average score of movie)

        Movie1 Movie2 Movie3
User1   5      3      4
User2   2      5      5
User3   3      3      4
User4   1      3      5
User5   5      1      5

And one more remark: you should preprocess the data. At least subtract the mean from all values!

Have a look at this introduction. It mensions the impute+SVD approach and also talks about a more direct modelling of missing values. But in this case, other algorithms are used.

$\endgroup$
  • $\begingroup$ Thank you for your reply. Please look at this bloglink. It seems that Simon only used non-missing ratings i.e. he ignored the missing ratings. Is this not the same as I am proposing. Please advise. $\endgroup$ – Boro Dega May 27 '16 at 22:27
  • 2
    $\begingroup$ Take your time and read my link. It covers exactly the strategy your bloglink describes. He is not imputing anything and he is not using SVD. He just uses some Stochastic gradient descent formulation of the SVD-motivated approach (which offers the possibility to ignore all missing entries)! For more information just google for matrix factorization + stochastic gradient. There is a lot of work! $\endgroup$ – sascha May 28 '16 at 0:16
2
$\begingroup$

There are lots of ways to predict missing values but classic SVD is not one of them. The nice thing is that machine learning now offers many ways to do this, some of which are based on matrix factorization, others completely different than matrix factorization. You can choose and make a completely custom model, and this is commonly done now because the tools are powerful enough today. Matrix factorization is still certainly a good way to predict missing values in sparse data, but SVD itself is not.

The accepted answer here, apparently advised the questioner to just pick any constant value such as 0 or 99 or -3 or whatever, to assign to the missing values in advance, and then run SVD on that. This is a bad answer if the goal is to predict on sparse datasets. But if instead the OP's goal is simply to run SVD, then pre-assigning any constant value will work fine, so pick any value and then run SVD if the results do not matter for the OP. I said SVD is a bad solution for prediction of missing values because assuming a constant value in all the sparse locations could end up being that you introducing literally more noise points than known good data points.

What's the point of learning noise? And why would you even suggest that the missing values are actually the same constant value, when the point of the exercise is to predict what they are? You don't expect the missing values to really be all the same, right? That's going to underestimate the number of principal components that result if there's constant data so pervasive in your dataset, for one thing. Also that's a very easy prediction problem then. You don't need a learning algorithm or even a factorization algorithm. You just said the missing values are a known constant. No need to impute! You did that already, manually, by just guessing the old fashioned way.

You can get fancier with SVD and pre-impute the missing values using a random distribution that's empirically derived using the mean and standard deviation from the known (non-missing) data. But then there's randomness instead of patterns in the data and you presumably expected matrix factorization and dimensionality reduction inherent in that technique to find the patterns that you expect are there. You won't discover many patterns of any use in random noise, though, so it's not helping to use this way either.

The bottom line is that the output of SVD -- or any other algorithm -- will be largely garbage whenever there is an overwhelming amount of investigator-provided junk data fed in. No algorithm can learn a good model from majority junk data. Just say no to that whole "approach."

It seems likely that the OP's goal is to predict, and to use a matrix factorization design as part of the learning algorithm. In this case, the nice thing is you can feasibly write your own cost function which crucially omits from the cost, any predictions made against the missing values. No junk data whatsoever is fed to the learning algorithm this way. Use a good gradient-descent based optimizer, such as Adam (there are others). You can get a solution that's measurably accurate to whatever degree on training, dev, and test dataset, provided you follow a good machine learning project methodology. Feel free to add terms and complexity to your model like user bias, item bias, global bias, regularization, or whatever else you need to control bias error and variance error to your project's requirements and available datasets.

A modern machine learning development package make this a practical approach now. TensorFlow for example (or Microsoft CNTK et al) can help you do exactly what I described on a sparse dataset using a matrix factorization model.

$\endgroup$
  • $\begingroup$ Great reflection. I really like your answer and it is spot on. Would you be able to expand your answer with a script which shows your solutions. Then that will be the answer to the question. Thanks $\endgroup$ – Boro Dega May 5 '18 at 9:05
2
$\begingroup$

This paper covers what you are looking for in very elegant detail (using soft threshold SVD). Like Geoffrey pointed out, they do this by writing their own cost function which excludes from the cost, any predictions made against the missing values.

Summary : Mazumdar et al use convex relaxation techniques to provide a sequence of regularized low-rank solutions for large-scale matrix completion problems. Algorithm SOFT-IMPUTE iteratively replaces the missing elements with those obtained from a soft-thresholded SVD. Exploiting the problem structure, they show that the task can be performed with a complexity of order linear in the matrix dimensions. The algorithm is readily scalable to large matrices; for e.g it fits a rank-95 approximation to the full Netflix training set in 3.3 hours. The methods achieve good training and test errors and have superior timings when compared to other competitive state-of-the-art techniques.

@article{mazumder2010spectral, title={Spectral regularization algorithms for learning large incomplete matrices}, author={Mazumder, Rahul and Hastie, Trevor and Tibshirani, Robert}, journal={Journal of machine learning research}, volume={11}, number={Aug}, pages={2287--2322}, year={2010} }

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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