[
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 10/31/14 4:20 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. Quadratic minimization with positivity
3. Quadratic minimization with box : generalization of positivity
4. Quadratic minimization with elastic net :L1 is at 0.99, elastic net control
is not given to users
5. Quadratic minimization with affine constraints and bounds
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 Breeze will be used for iterative solve when ranks are
high...I need a different variant of CG for Formulation 5 so Breeze CG is not
sufficient for all the formulations this branch supports and needs to be
extended..
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. Derive rho from approximate min and max eigenvalues of gram matrix
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 topic modeling use-case, I expect to produce sparse coding results (L1 on
product factors, L2 on user factors)
Example runs:
NMF:
./bin/spark-submit --total-executor-cores 4 --master spark://localhost:7077
--jars ~/.m2/repository/com/github/scopt/scopt_2.10/3.2.0/scopt_2.10-3.2.0.jar
--class org.apache.spark.examples.mllib.MovieLensALS
./examples/target/spark-examples_2.10-1.1.0-SNAPSHOT.jar --rank 20
--numIterations 10 --userConstraint POSITIVE --lambdaUser 0.065
--productConstraint POSITIVE --lambdaProduct 0.065 --kryo
hdfs://localhost:8020/sandbox/movielens/
Sparse coding:
./bin/spark-submit --total-executor-cores 4 --master spark://localhost:7077
--jars ~/.m2/repository/com/github/scopt/scopt_2.10/3.2.0/scopt_2.10-3.2.0.jar
--class org.apache.spark.examples.mllib.MovieLensALS
./examples/target/spark-examples_2.10-1.1.0-SNAPSHOT.jar --delimiter " " --rank
20 --numIterations 10 --userConstraint SMOOTH --lambdaUser 0.065
--productConstraint SPARSE --lambdaProduct 0.065 --kryo
hdfs://localhost:8020/sandbox/movielens
Robust PLSA with least square loss:
./bin/spark-submit --total-executor-cores 4 --master spark://localhost:7077
--jars ~/.m2/repository/com/github/scopt/scopt_2.10/3.2.0/scopt_2.10-3.2.0.jar
--class org.apache.spark.examples.mllib.MovieLensALS
./examples/target/spark-examples_2.10-1.1.0-SNAPSHOT.jar --delimiter " " --rank
20 --numIterations 10 --userConstraint EQUALITY --lambdaUser 0.065
--productConstraint EQUALITY --lambdaProduct 0.065 --kryo
hdfs://localhost:8020/sandbox/movielens
With this change, users can select to apply user and product specific
constraint...basically positive factors for products (interpretability) and
smooth for users to get more RMSE improvements.
Thanks.
Deb
was (Author: debasish83):
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
> 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.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
