FunkSVD Algorithm
A FunkSVD Algorithm is an SVD algorithm for large sparse matrices.
- See: SVD++.
References
2017
2006
- http://sifter.org/~simon/journal/20061211.html
- QUOTE: So, in other words, if we take the rank-40 [[singular value decomposition of the 8.5B matrix, we have the best (least error) approximation we can within the limits of our user-movie-rating model. I.e., the SVD has found our "best" generalizations for us. Pretty neat, eh?
Only problem is, we don't have 8.5B entries, we have 100M entries and 8.4B empty cells. Ok, there's another problem too, which is that computing the SVD of ginormous matrices is... well, no fun. Unless you're into that sort of thing.
But, just because there are five hundred really complicated ways of computing singular value decompositions in the literature doesn't mean there isn't a really simple way too: Just take the derivative of the approximation error and follow it. This has the added bonus that we can choose to simply ignore the unknown error on the 8.4B empty slots.
So, yeah, you mathy guys are rolling your eyes right now as it dawns on you how short the path was.
If you write out the equations for the error between the SVD-like model and the original data -- just the given values, not the empties -- and then take the derivative with respect to the parameters we're trying to infer, you get a rather simple result which I'll give here in C code to save myself the trouble of formatting the math:
- QUOTE: So, in other words, if we take the rank-40 [[singular value decomposition of the 8.5B matrix, we have the best (least error) approximation we can within the limits of our user-movie-rating model. I.e., the SVD has found our "best" generalizations for us. Pretty neat, eh?
userValue[user] += lrate * err * movieValue[movie]; movieValue[movie] += lrate * err * userValue[user];