Stochastic Gradient descent (SGD) vs Alternating least squares (ALS) for Matrix Factorization

@袁全V在微博上推荐了推荐系统的一些开源工具. 后来我选择了LibFM和GraphLab的代码进行精读.

在阅读了Alternating Least Squares、Stochastic Gradient descent做矩阵分解时遇到了相同的问题:

What is the different in ALS, SGD and biased SGD

Danny Bickson 在GraphLab Google Users做了回答(原文地址):

The papers ALS, SGD and bias-SGD are described in the following papers:

• Alternating Least Squares (ALS)

  Yunhong Zhou, Dennis Wilkinson, Robert Schreiber and Rong Pan. Large-Scale Parallel Collaborative Filtering for the Netflix Prize. Proceedings of the 4th international conference on Algorithmic Aspects in Information and Management. Shanghai, China pp. 337-348, 2008.

• Stochastic gradient descent (SGD)

  1. Matrix Factorization Techniques for Recommender Systems Yehuda Koren, Robert Bell, Chris Volinsky In IEEE Computer, Vol. 42, No. 8. (07 August 2009), pp. 30-37
  2. Takács, G, Pilászy, I., Németh, B. and Tikk, D. (2009). Scalable Collaborative Filtering Approaches for Large Recommender Systems. Journal of Machine Learning Research, 10, 623-656.

• Bias stochastic gradient descent (Bias-SGD)

  Y. Koren. Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model. ACM SIGKDD 2008. Equation (5).

Both ALS and SGD solve a similar quadratic cost function.
ALS operates by starting with a random guess for the users (or movies) and then computes a least square step to compute the movies (or users) alternating between the two.
SGD works by starting with a random guess and computing the gradient of the cost function and making a step in the direction of the gradient.

Typically, SGD iteration is faster, since ALS involves a least squares solution which is heavier.
However, fewer ALS iterations are typically needed for solving to the same level of accuracy.
Also ALS is more parallel since all movies or users can be computed independently in parallel, while SGD may have slower parallel performance in case two different users have seen the same movie, this results in concurrent updates to the gradient of the same movies which slows down the operation.

ALS significantly exploits linear algebra packages and specifically Intel MKL which can give a speedup of x5 - x10.

Bias-SGD is a slightly improved version of SGD, which also computes a bias for each movie and user, thus slightly improving accuracy at the cost of additional computation.

Regarding parameter tuning, SGD has more parameters to tune since you need to carefully select the gradient step size. Both SGD and ALS have regularization parameters to tune, number of iterations, and feature vector width.

Anyway it is hard to estimate which method will work better on which dataset. That is why it is very convenient to use graphlab/graphchi - once you prepare your data to the right format you can immediately test multiple methods.

推荐阅读:

1. Stochastic Gradient descent (SGD) vs Alternating least squares (ALS) for Matrix Factorization
2. Baum J, Cook C, Curtis M, et al. Parallelization of matrix factorization for recommender systems[R]. Technical Report HPCF–2010–22, UMBC High Performance Computing Facility, University of Maryland, Baltimore County, 2010.(Ggraduate assistant).