[
https://issues.apache.org/jira/browse/SPARK-2426?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14095232#comment-14095232
]
Debasish Das edited comment on SPARK-2426 at 8/13/14 3:31 PM:
--------------------------------------------------------------
Hi Xiangrui,
The branch is ready for an initial review. I will do lot of clean-up this week.
I need some advice on whether we should bring the additional ALS features first
or integrate NNLS with QuadraticMinimizer so that we can handle large ranks as
well.
https://github.com/debasish83/spark/commits/qp-als
optimization/QuadraticMinimizer.scala is the placeholder for all
QuadraticMinimization.
Right now we support 5 features:
1. Least square
2. Least square with positivity
3. Least square with bounds : generalization of positivity
4. Least square with equality and positivity/bounds for LDA/PLSA
5. Least square + L1 constraint for sparse NMF
There are lot many regularization in Proximal.scala which can be re-used in
mllib updater...L1Updater in mllib is an example of Proximal algorithm...
QuadraticMinimizer is optimized for direct solve right now (cholesky / lu based
on problem we are solving)
The CG core from NNLS should be used for iterative solve when ranks are
high...I need a different variant of CG for Formulation 4 so NNLS CG is not
sufficient for all the formulations this branch supports...
Right now I am experimenting with ADMM rho and lambda values so that the NNLS
iterations are at par with Least square with positivity. The idea for rho and
lambda tuning are the following:
1. Derive an optimal value of lambda for quadratic problems, similar to idea of
Nesterov's acceleration being used in algorithms like FISTA and accelerated
ADMM from UCLA
2. Equilibrate/Scale the gram matrix such that rho can always be set at 1.0
For Matlab based experiments within PDCO, ECOS(IPM), MOSEK and ADMM variants,
ADMM is faster with producing result quality within 1e-4 of MOSEK. I will
publish the numbers and the matlab script through the ECOS jnilib open source
(GPL licensed). I did not add any of ECOS code here so that everything stays
Apache.
For recommendation use-case, I expect to produce Jellylish L1 ball projection
results on netflix/movielens dataset using Formulation 5.
Example runs:
Least square with equality and positivity for topic modeling, all topics sum to
1.0:
bin/spark-submit --class org.apache.spark.examples.mllib.MovieLensALS \
| examples/target/scala-*/spark-examples-*.jar \
| --rank 25 --numIterations 10 --lambda 1.0 --kryo --qpProblem 4\
| data/mllib/sample_movielens_data.txt
Least square with L1 regularization:
bin/spark-submit --class org.apache.spark.examples.mllib.MovieLensALS \
| examples/target/scala-*/spark-examples-*.jar \
| --rank 25 --numIterations 10 --lambda 1.0 --lambdaL1 1e-2 --kryo
--qpProblem 5\
| data/mllib/sample_movielens_data.txt
Thanks.
Deb
was (Author: debasish83):
Hi Xiangrui,
The branch is ready for an initial review. I will do lot of clean-up this week.
https://github.com/debasish83/spark/commits/qp-als
optimization/QuadraticMinimizer.scala is the placeholder for all
QuadraticMinimization.
Right now we support 5 features:
1. Least square
2. Least square with positivity
3. Least square with bounds : generalization of positivity
4. Least square with equality and positivity/bounds for LDA/PLSA
5. Least square + L1 constraint for sparse NMF
There are lot many regularization in Proximal.scala which can be re-used in
mllib updater...L1Updater is an example of Proximal algorithm.
I feel we should move NNLS into QuadraticMinimizer as well and clean ALS.scala
as you have suggested before...
QuadraticMinimizer is optimized for direct solve right now (cholesky / lu based
on problem we are solving)
The CG core from NNLS should be used for iterative solve when ranks are
high...I need a different variant of CG for Formulation 4 so NNLS CG is not
sufficient for all the formulations.
Right now I am experimenting with ADMM rho and lambda values so that the NNLS
iterations are at par with Least square with positivity.
I will publish results from the comparisons.
I will also publish comparisons with PDCO, ECOS (IPM) and MOSEK with ADMM
variants used in this branch...
For recommendation use-case, I expect to produce Jellylish L1 ball projection
results on netflix/movielens dataset using Formulation 5.
Thanks.
Deb
> Quadratic Minimization for MLlib ALS
> ------------------------------------
>
> Key: SPARK-2426
> URL: https://issues.apache.org/jira/browse/SPARK-2426
> Project: Spark
> Issue Type: New Feature
> Components: MLlib
> Affects Versions: 1.0.0
> Reporter: Debasish Das
> Assignee: Debasish Das
> Original Estimate: 504h
> Remaining Estimate: 504h
>
> Current ALS supports least squares and nonnegative least squares.
> I presented ADMM and IPM based Quadratic Minimization solvers to be used for
> the following ALS problems:
> 1. ALS with bounds
> 2. ALS with L1 regularization
> 3. ALS with Equality constraint and bounds
> Initial runtime comparisons are presented at Spark Summit.
> http://spark-summit.org/2014/talk/quadratic-programing-solver-for-non-negative-matrix-factorization-with-spark
> Based on Xiangrui's feedback I am currently comparing the ADMM based
> Quadratic Minimization solvers with IPM based QpSolvers and the default
> ALS/NNLS. I will keep updating the runtime comparison results.
> For integration the detailed plan is as follows:
> 1. Add QuadraticMinimizer and Proximal algorithms in mllib.optimization
> 2. Integrate QuadraticMinimizer in mllib ALS
--
This message was sent by Atlassian JIRA
(v6.2#6252)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
