2
$\begingroup$

I work on a recommender system framework which is implemented with a variant on Funk SVD (See his explanation of his algorithm here).

However the framework that we are trying to integrate doesn't support Funk SVD, only SGD (Stochastic Gradient Descent).

Since shouldn't these be compatible? In other words, I should be able to create the U and V matrices with SGD and then treat them like they were made via the Funk SVD process?

Are there any disadvantages of using this versus the algorithm detailed by Funk?

$\endgroup$
  • $\begingroup$ fyi TCS tends to frown on implementation questions even for very advanced algorithms. can you give any more details on your recommender system framework ie which one? $\endgroup$ – vzn Sep 30 '12 at 3:26
  • $\begingroup$ Im part of working with lenskit $\endgroup$ – Daniel Gratzer Sep 30 '12 at 3:48
  • $\begingroup$ ok, are you talking also about some other framework that is using SGD? $\endgroup$ – vzn Sep 30 '12 at 6:24
  • $\begingroup$ fyi it looks like crossvalidated.se has some SVD related question related to collaborative filtering. also I see that funks algorithm was referred to as stochastic gradient descent here, dont know if this is correct. his algorithm was never written up in a paper as far as I know. $\endgroup$ – vzn Sep 30 '12 at 15:35
  • $\begingroup$ This question is certainly better off here than on Theoretical Computer Science. Please add some information about what those shorthands mean. $\endgroup$ – Raphael Sep 30 '12 at 16:38
2
$\begingroup$

simon funk is the apparent inventor of a simple & ingenious SVD (singular value decomposition) algorithm during the netflix contest although the algorithm may have predated his discovery (would like to know a ref if anyone knows). SGD = stochastic gradient descent (?) which can be applied to all kinds of optimization problems, incl SVD.

so it depends on your recommender system framework and if its trying to use SVD for recommendations, which is common, but not universal. if it is using SGD to compute the SVD, then that is very similar to the Funk algorithm except the Funk algorithm is probably more prone to get stuck in local minima.

in other words the SGD may find a superior solution but it may take longer. so basically both SGD/Funk are two approaches to computing the U,V matrices & you can do experimental testing to see which gives you the best results or desirable performance.

Funks algorithm is basically just straight gradient descent and SGD is stochastic gradient descent that adds a simulated annealing-like approach to the optimization where earlier in the convergence/search, weights are randomly perturbed to avoid local minima, and then as the search progresses & hopefully converges, the perturbation factor decreases.

fyi for SVD it can be possible to find the optimal solution using matrix based methods even for large matrices (esp if large distributed resources are available) and one could possibly compare either the Funk algorithm or SGD to the actual global optimum.

$\endgroup$
  • $\begingroup$ addendum heres a good slideshow, intro to matrix methods wrt filtering by alex lin that hopefully clarifies the issues $\endgroup$ – vzn Sep 30 '12 at 15:36
  • $\begingroup$ note Funk had several variations of his algorithm iirc. see also netflix forum, basic overview of Funk algorithm $\endgroup$ – vzn Sep 30 '12 at 15:50
  • $\begingroup$ vzn, can you explain why do you think Funk used ordinary gradient descent and not SGD? I looked at the pseudo code he included in his article and it looks like SGD to me. Also, could you explain why Funk's SVD is "more prone to get stuck in local minima"? $\endgroup$ – dpelisek Apr 17 '18 at 16:37

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.