apache/spark — pull request #3221 by debasish83 (2014-11-12 08:20:15+00:00)
Title: [MLLIB] [WIP] SPARK-2426: Quadratic Minimization for ALS

ALS is a generic algorithm for matrix factorization which is equally applicable for both feature space and similarity space. Current ALS support L2 regularization and positivity constraint. This PR introduces userConstraint and productConstraint to ALS and let's the user select different constraints for user and product solves. The supported constraints are the following:

SMOOTH : default ALS with L2 regularization
ELASTIC NET: ALS with Elastic Net regularization
POSITIVE: ALS with positive factors
BOUNDS: ALS with factors bounded within upper and lower bound (default within 0 and 1)
EQUALITY: ALS with equality constraint (default the factors sum up to 1 and positive)

First let's focus on the problem formulation. Both implicit and explicit feedback ALS formulation can be written as a quadratic minimization problem. The quadratic objective can be written as xtHx + ctx. Each of the respective constraints take the following form (for example sparsity constraint)

minimize xtHx + ctx
s.t ||x||1 <= c (SPARSE constraint)

We rewrite the objective as f(x) = xtHx + ctx and the constraint as an indicator function g(x)
Now minimization of f(x) + g(x) can be carried out using various forward backward splitting algorithms. We choose ADMM for this PR.

For use-cases the PR is focused on the following:

1. Sparse matrix factorization
Example run:
MASTER=spark://localhost:7077 ./bin/run-example mllib.MovieLensALS --rank 20 --numIterations 10 --userConstraint SMOOTH --lambdaUser 0.065 --productConstraint SPARSE --lambdaProduct 0.1 --kryo hdfs://localhost:8020/sandbox/movielens/

2. Topic modeling using LSA
References:
2007 Sparse coding: papers.nips.cc/paper/2979-efficient-sparse-coding-algorithms.pdf
2011 Sparse Latent Semantic Analysis LSA(some of it is implemented in Graphlab):
https://www.cs.cmu.edu/~xichen/images/SLSA-sdm11-final.pdf
2012 Sparse Coding + MR/MPI Microsoft: http://web.stanford.edu/group/mmds/slides2012/s-hli.pdf
Implementing the 20NG flow to validate the sparse coding result improvement over LDA based topic modeling.

3. Topic modeling using PLSA
Reference:
Tutorial on Probabilistic Topic Modeling: Additive Regularization for Stochastic Matrix Factorization
The EQUALITY formulation with a Quadratic loss is an approximation to the KL divergence loss being used in PLSA. We are interested to see if it improves the result further as compared to the Sparse coding.

Next steps:
1. Move QuadraticMinimizerSuite.scala to breeze
2. Scale the factorization rank and remove the need to construct H matrix
3. Replace the quadratic loss xtHx + ctx with a Convex loss

Detailed experiments are on the JIRA https://issues.apache.org/jira/browse/SPARK-2426