9
$\begingroup$

Matrix factorization is widely applied in collaborative filtering, and briefly speaking, it tries to learn the following parameters: $$\min_{q_u,p_i}\sum_{\{u,i\}}(r_{ui} - q_u^Tp_i)^2$$

And we could apply SGD and ALS as the learning algorithm, however, as I read here, they said,

SGD is not practical if the dataset size is huge, instead ALS is better.

I wonder why SGD is not good if the dataset is huge? I thought even if it's huge, we could use mini-batch SGD, which is the widely adopted way to train large nerual nets, isn't it?

FOLLOWUP

By SGD, each time we only use one data point $r_{ui}$, and only optimize one part of the entire loss, i.e. optimize $(r_{ui} - q_u^Tp_i)^2$, so we update $q_u$ using the gradient of this part, resulting $\tilde{q_u}$.

Absolutely $\tilde{q_u}$ will optimize $(r_{ui} - q_u^Tp_i)^2$, but it might worsen other parts of the entire loss, say $(r_{uj} - q_u^Tp_j)^2$, I mean both $r_{ui}$ and $r_{un}$ involves $q_u$.

Considering the above case, how could we guarantee that SGD will converge?

$\endgroup$
2
  • $\begingroup$ SGD and ALS aren't the only approaches to matrix factorization. SVD is a third that may have computational advantages over the others, particularly for large datasets. $\endgroup$
    – user78229
    Mar 25, 2016 at 17:52
  • $\begingroup$ @DJohnson, yes you'er right, but here I just want to figure out more about SGD vs ALS :-) $\endgroup$
    – avocado
    Mar 26, 2016 at 2:25

2 Answers 2

10
+100
$\begingroup$

Both SGD and ALS are very practical for matrix factorization,

Yehuda Koren, a winner of the Netflix prize (see here) and a pioneer in Matrix factorization techniques for CF, worked at Yahoo labs at the time, and was a part of the development of a CF model for Yahoo.

Reading through Yahoo labs' publications (for example here and here), it is easy to see that they are using SGD heavily, and we can only assume that the same holds for production systems.

Matrix factorization is often done on a matrix of user_featurexmovie_features (instead of matrices of usersxmovies) because of the cold-start issue, making the argument mentioned in the link less relevant.

SGD also has the upper hand regarding dealing with missing data, which is a fairly common scenario.

To sum up, SGD is a very common method for CF, and I see no reason why it cannot be applied on large data sets.

$\endgroup$
3
  • $\begingroup$ Great hints, but I have a followup question about SGD's convergence when applied to MF, please see my post. $\endgroup$
    – avocado
    Mar 24, 2016 at 3:35
  • $\begingroup$ The S in the SGD stands for stochastic, You might have a few iterations in which you are stepping away from the local maximum, but on average, you are walking in the right direction. $\endgroup$
    – Uri Goren
    Mar 24, 2016 at 8:27
  • $\begingroup$ Having said that, there are quite a lot of variation on GD that work better than SGD in some circumstances, for example, In the paper that Alex cited, Biased SGD had the best convergence rate among the algorithms they tested (ALS and SGD are listed there as well). $\endgroup$
    – Uri Goren
    Mar 24, 2016 at 8:30
8
$\begingroup$

Check out the comparison here:

Recommender: An Analysis of Collaborative Filtering Techniques -Aberger

The conclusion seems to be that biased stochastic gradient descent is generally faster and more accurate than ALS except in situations of sparse data in which ALS performs better.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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