apache/spark — pull request #2705 by debasish83 (2014-10-08 03:49:55+00:00)
Title: [MLLIB] [WIP] SPARK-2426: Quadratic Minimization for MLlib 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:

1. SMOOTH : default ALS with L2 regularization
2. POSITIVE: ALS with positive factors
3. BOUNDS: ALS with factors bounded within upper and lower bound (default within 0 and 1)
4. SPARSE: ALS with L1 regularization
5. 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:
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 the first version based on our experimentation with ECOS IP solver and MOSEK comparisons. I will document the comparisons.

Details of the algorithm are in the following reference:
http://web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf

Right now the default parameters of alpha, rho are set as 1.0 but the following issues show up in experiments with MovieLens dataset:
1. ~3X higher iterations as compared to NNLS
2. For SPARSE we are hitting the max iterations (400) around 10% of the time
3. For EQUALITY rho is set at 50 based on a reference from Professor Boyd on optimal control

We choose ADMM as the baseline solver but this PR will explore the following solver enhancements to decrease the iteration count:
1. Accelerated ADMM using Nesterov acceleration
2. FISTA style forward backward splitting

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

1. Sparse matrix factorization to improve recommendation
On Movielens data right now the RMSE with SPARSE is 10% (1.04) lower than the Mahout/Spark baseline (0.9) but have not looked into map, prec@k and ndcg@k measures. Using the PR from @coderxiang to look into IR measures.
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
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. Improve the convergence rate of forward-backward splitting on quadratic problems
2. Move the test-cases to QuadraticMinimizerSuite.scala
3. Generate results for each of the use-cases and add tests related to each use-case

Related future PRs:
1. Scale the factorization rank and remove the need to construct H matrix
2. Replace the quadratic loss xtHx + ctx with a Convex loss