You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@spark.apache.org by DB Tsai <db...@alpinenow.com> on 2014/02/22 13:28:24 UTC

MLLib - Thoughts about refactoring Updater for LBFGS?

Hi guys,

First of all, we would like to thank all the Spark community for
building such great platform for big data processing. We built the
multinomial logistic regression with LBFGS optimizer in Spark, and
LBFGS is a limited memory version of quasi-newton method which allows
us to train a very high-dimensional data without computing the Hessian
matrix as newton method required.

In Strata Conference, we did a great demo using Spark with our MLOR to
train mnist8m dataset. We're able to train the model in 5 mins with 50
iterations, and get 86% accuracy. The first iteration takes 19.8s, and
the remaining iterations take about 5~7s.

We did comparison between LBFGS and SGD, and often we saw 10x less
steps in LBFGS while the cost of per step is the same (just computing
the gradient).

The following is the paper by Prof. Ng at Stanford comparing different
optimizers including LBFGS and SGD. They use them in the context of
deep learning, but worth as reference.
http://cs.stanford.edu/~jngiam/papers/LeNgiamCoatesLahiriProchnowNg2011.pdf

We would like to break our MLOR with LBFGS into three patches to
contribute to the community.

1) LBFGS optimizer - which can be used in logistic regression, and
liner regression or replacing any algorithms using SGD.
The core underneath LBFGS Java implementation we used is from RISO
project, and the author, Robert is so kind to relicense it to GPL and
Apache2 dual license.

We're almost ready to submit a PR for LBFGS, see our github fork,
https://github.com/AlpineNow/incubator-spark/commits/dbtsai-LBFGS

However, we don't use Updater in LBFGS since it designs for GD, and
for LBFGS, we don't need stepSize, and adaptive learning rate, etc.
While it seems to be difficult to fit the LBFGS updater logic (well,
in lbfgs library, the new weights is returned given old weights, loss,
and gradient) into the current framework, I was thinking to abstract
out the code computing the gradient and loss terms of regularization
into different place so that different optimizer can also use it. Any
suggestion about this?

2) and 3), we will add the MLOR gradient to MLLib, and add a few
examples. Finally, we will have some tweak using mapPartition instead
of map to further improve the performance.

Thanks.

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
Hi Yinxusen,

I agree. I found a hack to use the current Updater.scala (it contains
not only the logic of regularization but also the adaptive learning
rate in SGD which will not be used in general for other optimizers),
but I think we still need to have a better design to deal with it.

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/


On Mon, Feb 24, 2014 at 6:46 PM, 尹绪森 <yi...@gmail.com> wrote:
> Hi DB and Xiangrui,
>
> L-BFGS is really useful. I think it will be cool if we can refactor the
> interface of runMiniBatchSGD, so as to plug in new optimizer more easily
> and compatible. What do you think of that ?
>
>
> 2014-02-23 3:49 GMT+08:00 Xiangrui Meng <me...@gmail.com>:
>
>> Hi DB,
>>
>> It is great to have the L-BFGS optimizer in MLlib and thank you for taking
>> care of the license issue. I looked through your PR briefly. It contains a
>> Java translation of the L-BFGS implementation, which is part of the RISO
>> package. Is it possible that we ask its author to make a release on maven
>> central and then we add it as a dependency instead of including the code
>> directly?
>>
>> Best,
>> Xiangrui
>>
>>
>> On Sat, Feb 22, 2014 at 4:28 AM, DB Tsai <db...@alpinenow.com> wrote:
>>
>> > Hi guys,
>> >
>> > First of all, we would like to thank all the Spark community for
>> > building such great platform for big data processing. We built the
>> > multinomial logistic regression with LBFGS optimizer in Spark, and
>> > LBFGS is a limited memory version of quasi-newton method which allows
>> > us to train a very high-dimensional data without computing the Hessian
>> > matrix as newton method required.
>> >
>> > In Strata Conference, we did a great demo using Spark with our MLOR to
>> > train mnist8m dataset. We're able to train the model in 5 mins with 50
>> > iterations, and get 86% accuracy. The first iteration takes 19.8s, and
>> > the remaining iterations take about 5~7s.
>> >
>> > We did comparison between LBFGS and SGD, and often we saw 10x less
>> > steps in LBFGS while the cost of per step is the same (just computing
>> > the gradient).
>> >
>> > The following is the paper by Prof. Ng at Stanford comparing different
>> > optimizers including LBFGS and SGD. They use them in the context of
>> > deep learning, but worth as reference.
>> >
>> http://cs.stanford.edu/~jngiam/papers/LeNgiamCoatesLahiriProchnowNg2011.pdf
>> >
>> > We would like to break our MLOR with LBFGS into three patches to
>> > contribute to the community.
>> >
>> > 1) LBFGS optimizer - which can be used in logistic regression, and
>> > liner regression or replacing any algorithms using SGD.
>> > The core underneath LBFGS Java implementation we used is from RISO
>> > project, and the author, Robert is so kind to relicense it to GPL and
>> > Apache2 dual license.
>> >
>> > We're almost ready to submit a PR for LBFGS, see our github fork,
>> > https://github.com/AlpineNow/incubator-spark/commits/dbtsai-LBFGS
>> >
>> > However, we don't use Updater in LBFGS since it designs for GD, and
>> > for LBFGS, we don't need stepSize, and adaptive learning rate, etc.
>> > While it seems to be difficult to fit the LBFGS updater logic (well,
>> > in lbfgs library, the new weights is returned given old weights, loss,
>> > and gradient) into the current framework, I was thinking to abstract
>> > out the code computing the gradient and loss terms of regularization
>> > into different place so that different optimizer can also use it. Any
>> > suggestion about this?
>> >
>> > 2) and 3), we will add the MLOR gradient to MLLib, and add a few
>> > examples. Finally, we will have some tweak using mapPartition instead
>> > of map to further improve the performance.
>> >
>> > Thanks.
>> >
>> > Sincerely,
>> >
>> > DB Tsai
>> > Machine Learning Engineer
>> > Alpine Data Labs
>> > --------------------------------------
>> > Web: http://alpinenow.com/
>> >
>>
>
>
>
> --
> Best Regards
> -----------------------------------
> Xusen Yin    尹绪森
> Beijing Key Laboratory of Intelligent Telecommunications Software and
> Multimedia
> Beijing University of Posts & Telecommunications
> Intel Labs China
> Homepage: *http://yinxusen.github.io/ <http://yinxusen.github.io/>*

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by 尹绪森 <yi...@gmail.com>.
Hi DB and Xiangrui,

L-BFGS is really useful. I think it will be cool if we can refactor the
interface of runMiniBatchSGD, so as to plug in new optimizer more easily
and compatible. What do you think of that ?


2014-02-23 3:49 GMT+08:00 Xiangrui Meng <me...@gmail.com>:

> Hi DB,
>
> It is great to have the L-BFGS optimizer in MLlib and thank you for taking
> care of the license issue. I looked through your PR briefly. It contains a
> Java translation of the L-BFGS implementation, which is part of the RISO
> package. Is it possible that we ask its author to make a release on maven
> central and then we add it as a dependency instead of including the code
> directly?
>
> Best,
> Xiangrui
>
>
> On Sat, Feb 22, 2014 at 4:28 AM, DB Tsai <db...@alpinenow.com> wrote:
>
> > Hi guys,
> >
> > First of all, we would like to thank all the Spark community for
> > building such great platform for big data processing. We built the
> > multinomial logistic regression with LBFGS optimizer in Spark, and
> > LBFGS is a limited memory version of quasi-newton method which allows
> > us to train a very high-dimensional data without computing the Hessian
> > matrix as newton method required.
> >
> > In Strata Conference, we did a great demo using Spark with our MLOR to
> > train mnist8m dataset. We're able to train the model in 5 mins with 50
> > iterations, and get 86% accuracy. The first iteration takes 19.8s, and
> > the remaining iterations take about 5~7s.
> >
> > We did comparison between LBFGS and SGD, and often we saw 10x less
> > steps in LBFGS while the cost of per step is the same (just computing
> > the gradient).
> >
> > The following is the paper by Prof. Ng at Stanford comparing different
> > optimizers including LBFGS and SGD. They use them in the context of
> > deep learning, but worth as reference.
> >
> http://cs.stanford.edu/~jngiam/papers/LeNgiamCoatesLahiriProchnowNg2011.pdf
> >
> > We would like to break our MLOR with LBFGS into three patches to
> > contribute to the community.
> >
> > 1) LBFGS optimizer - which can be used in logistic regression, and
> > liner regression or replacing any algorithms using SGD.
> > The core underneath LBFGS Java implementation we used is from RISO
> > project, and the author, Robert is so kind to relicense it to GPL and
> > Apache2 dual license.
> >
> > We're almost ready to submit a PR for LBFGS, see our github fork,
> > https://github.com/AlpineNow/incubator-spark/commits/dbtsai-LBFGS
> >
> > However, we don't use Updater in LBFGS since it designs for GD, and
> > for LBFGS, we don't need stepSize, and adaptive learning rate, etc.
> > While it seems to be difficult to fit the LBFGS updater logic (well,
> > in lbfgs library, the new weights is returned given old weights, loss,
> > and gradient) into the current framework, I was thinking to abstract
> > out the code computing the gradient and loss terms of regularization
> > into different place so that different optimizer can also use it. Any
> > suggestion about this?
> >
> > 2) and 3), we will add the MLOR gradient to MLLib, and add a few
> > examples. Finally, we will have some tweak using mapPartition instead
> > of map to further improve the performance.
> >
> > Thanks.
> >
> > Sincerely,
> >
> > DB Tsai
> > Machine Learning Engineer
> > Alpine Data Labs
> > --------------------------------------
> > Web: http://alpinenow.com/
> >
>



-- 
Best Regards
-----------------------------------
Xusen Yin    尹绪森
Beijing Key Laboratory of Intelligent Telecommunications Software and
Multimedia
Beijing University of Posts & Telecommunications
Intel Labs China
Homepage: *http://yinxusen.github.io/ <http://yinxusen.github.io/>*

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
Thanks for the pointers.

That's the plan...I am going to have default ALS, variable projection at
each ALS step, and then using the constrained first order solver that you
have...

I am hoping ECOS QP will beat all of them...I don't know...some of these
obvious assumptions does not work when the data is large...

About ECOS, we are trying to get it Apache licensed from Professor Boyd /
Alex Domahidi who is the primary author. Let's see how that goes...

I am not sure how easy it will be for projected gradient solver to handle
quadratic constraints...For simple bounds I feel it will work fine...On Mar
31, 2014 10:34 AM, "David Hall" <dl...@cs.berkeley.edu> wrote:

> On Mon, Mar 31, 2014 at 10:15 AM, Debasish Das <debasish.das83@gmail.com
> >wrote:
>
> > I added eclipse support in my qp branch:
> >
> > https://github.com/debasish83/breeze/tree/qp
>
>
> Ok, great. Totally fine for this to come in with the QP.
>
>
> >
> >
> > For the QP solver I will look into this solver
> http://www.joptimizer.com/
> >
> > Right now my plan is to use Professor Boyd's ECOS solver which is also
> > designed in the very similar lines but has been tested to solve even cone
> > programs...
> >
> > https://github.com/ifa-ethz/ecos
> >
> > Any idea whether I should add C native code using jniloader as the first
> > version or rewrite using breeze.optimize style and call netlib-java calls
> > for native support (ldl, cholesky etc)...
> >
>
> I personally don't care much. A year ago, I would have much preferred pure
> JVM, and a few months ago I would have just said get it working with
> natives, since presumably that's easier. *However*, ECOS is GPL, and
> jniloader is LGPL. So, you can't require these dependencies in an Apache
> product.
>
> IANAL, but if you want this in Spark, I would suggest you stop looking at
> ECOS immediately, at least until you have something that isn't encumbered
> that works well enough.
>
>
>
> >
> > I still have to think how much cone support we will need...In ALS for
> > example X^TX = I and Y^Y=I are interesting constraints for
> > orthogonality...and they are quadratic constraints...With BFGS and CG, it
> > is difficult to handle quadratic constraints...
> >
>
>
> I wonder how our general projected gradient solver would do? Clearly having
> dedicated QP support is better, but in terms of just getting it working, it
> might be enough.
>
> -- David
>
>
> >
> >
> >
> > On Sun, Mar 30, 2014 at 4:40 PM, David Hall <dl...@cs.berkeley.edu>
> wrote:
> >
> > > On Sun, Mar 30, 2014 at 2:01 PM, Debasish Das <
> debasish.das83@gmail.com
> > > >wrote:
> > >
> > > > Hi David,
> > > >
> > > > I have started to experiment with BFGS solvers for Spark GLM over
> large
> > > > scale data...
> > > >
> > > > I am also looking to add a good QP solver in breeze that can be used
> in
> > > > Spark ALS for constraint solves...More details on that soon...
> > > >
> > > > I could not load up breeze 0.7 code onto eclipse...There is a folder
> > > called
> > > > natives in the master but there is no code in that....all the code is
> > in
> > > > src/main/scala...
> > > >
> > > > I added the eclipse plugin:
> > > >
> > > > addSbtPlugin("com.github.mpeltonen" % "sbt-idea" % "1.6.0")
> > > >
> > > > addSbtPlugin("com.typesafe.sbteclipse" % "sbteclipse-plugin" %
> "2.2.0")
> > > >
> > > > But it seems the project is set to use idea...
> > > >
> > > > Could you please explain the dev methodology for breeze ? My idea is
> to
> > > do
> > > > solver work in breeze as that's the right place and get it into Spark
> > > > through Xiangrui's WIP on Sparse data and breeze support...
> > > >
> > >
> > > It would be great to have a QP Solver: I don't know if you know about
> > this
> > > library: http://www.joptimizer.com/
> > >
> > > I'm not quite sure what you mean by dev methodology. If you just mean
> how
> > > to get code into Breeze, just send a PR to scalanlp/breeze. Unit tests
> > are
> > > good for something nontrivial like this. Maybe some basic
> documentation.
> > >
> > >
> > > >
> > > > Thanks.
> > > > Deb
> > > >
> > > >
> > > >
> > > > On Fri, Mar 7, 2014 at 12:46 AM, DB Tsai <db...@alpinenow.com>
> wrote:
> > > >
> > > > > Hi Xiangrui,
> > > > >
> > > > > I think it doesn't matter whether we use Fortran/Breeze/RISO for
> > > > > optimizers since optimization only takes << 1% of time. Most of the
> > > > > time is in gradientSum and lossSum parallel computation.
> > > > >
> > > > > Sincerely,
> > > > >
> > > > > DB Tsai
> > > > > Machine Learning Engineer
> > > > > Alpine Data Labs
> > > > > --------------------------------------
> > > > > Web: http://alpinenow.com/
> > > > >
> > > > >
> > > > > On Thu, Mar 6, 2014 at 7:10 PM, Xiangrui Meng <me...@gmail.com>
> > > wrote:
> > > > > > Hi DB,
> > > > > >
> > > > > > Thanks for doing the comparison! What were the running times for
> > > > > > fortran/breeze/riso?
> > > > > >
> > > > > > Best,
> > > > > > Xiangrui
> > > > > >
> > > > > > On Thu, Mar 6, 2014 at 4:21 PM, DB Tsai <db...@alpinenow.com>
> > > wrote:
> > > > > >> Hi David,
> > > > > >>
> > > > > >> I can converge to the same result with your breeze LBFGS and
> > Fortran
> > > > > >> implementations now. Probably, I made some mistakes when I tried
> > > > > >> breeze before. I apologize that I claimed it's not stable.
> > > > > >>
> > > > > >> See the test case in BreezeLBFGSSuite.scala
> > > > > >> https://github.com/AlpineNow/spark/tree/dbtsai-breezeLBFGS
> > > > > >>
> > > > > >> This is training multinomial logistic regression against iris
> > > dataset,
> > > > > >> and both optimizers can train the models with 98% training
> > accuracy.
> > > > > >>
> > > > > >> There are two issues to use Breeze in Spark,
> > > > > >>
> > > > > >> 1) When the gradientSum and lossSum are computed distributively
> in
> > > > > >> custom defined DiffFunction which will be passed into your
> > > optimizer,
> > > > > >> Spark will complain LBFGS class is not serializable. In
> > > > > >> BreezeLBFGS.scala, I've to convert RDD to array to make it work
> > > > > >> locally. It should be easy to fix by just having LBFGS to
> > implement
> > > > > >> Serializable.
> > > > > >>
> > > > > >> 2) Breeze computes redundant gradient and loss. See the
> following
> > > log
> > > > > >> from both Fortran and Breeze implementations.
> > > > > >>
> > > > > >> Thanks.
> > > > > >>
> > > > > >> Fortran:
> > > > > >> Iteration -1: loss 1.3862943611198926, diff 1.0
> > > > > >> Iteration 0: loss 1.5846343143210866, diff 0.14307193024217352
> > > > > >> Iteration 1: loss 1.1242501524477688, diff 0.29053004039012126
> > > > > >> Iteration 2: loss 1.0930151243303563, diff 0.027782962952189336
> > > > > >> Iteration 3: loss 1.054036932835569, diff 0.03566113127440601
> > > > > >> Iteration 4: loss 0.9907956302751622, diff 0.05999907649459571
> > > > > >> Iteration 5: loss 0.9184205380342829, diff 0.07304737423337761
> > > > > >> Iteration 6: loss 0.8259870936519937, diff 0.10064381175132982
> > > > > >> Iteration 7: loss 0.6327447552109574, diff 0.23395293458364716
> > > > > >> Iteration 8: loss 0.5534101162436359, diff 0.1253815427665277
> > > > > >> Iteration 9: loss 0.4045020086612566, diff 0.26907321376758075
> > > > > >> Iteration 10: loss 0.3078824990823728, diff 0.23885980452569627
> > > > > >>
> > > > > >> Breeze:
> > > > > >> Iteration -1: loss 1.3862943611198926, diff 1.0
> > > > > >> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> > > > > >> WARNING: Failed to load implementation from:
> > > > > >> com.github.fommil.netlib.NativeSystemBLAS
> > > > > >> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> > > > > >> WARNING: Failed to load implementation from:
> > > > > >> com.github.fommil.netlib.NativeRefBLAS
> > > > > >> Iteration 0: loss 1.3862943611198926, diff 0.0
> > > > > >> Iteration 1: loss 1.5846343143210866, diff 0.14307193024217352
> > > > > >> Iteration 2: loss 1.1242501524477688, diff 0.29053004039012126
> > > > > >> Iteration 3: loss 1.1242501524477688, diff 0.0
> > > > > >> Iteration 4: loss 1.1242501524477688, diff 0.0
> > > > > >> Iteration 5: loss 1.0930151243303563, diff 0.027782962952189336
> > > > > >> Iteration 6: loss 1.0930151243303563, diff 0.0
> > > > > >> Iteration 7: loss 1.0930151243303563, diff 0.0
> > > > > >> Iteration 8: loss 1.054036932835569, diff 0.03566113127440601
> > > > > >> Iteration 9: loss 1.054036932835569, diff 0.0
> > > > > >> Iteration 10: loss 1.054036932835569, diff 0.0
> > > > > >> Iteration 11: loss 0.9907956302751622, diff 0.05999907649459571
> > > > > >> Iteration 12: loss 0.9907956302751622, diff 0.0
> > > > > >> Iteration 13: loss 0.9907956302751622, diff 0.0
> > > > > >> Iteration 14: loss 0.9184205380342829, diff 0.07304737423337761
> > > > > >> Iteration 15: loss 0.9184205380342829, diff 0.0
> > > > > >> Iteration 16: loss 0.9184205380342829, diff 0.0
> > > > > >> Iteration 17: loss 0.8259870936519939, diff 0.1006438117513297
> > > > > >> Iteration 18: loss 0.8259870936519939, diff 0.0
> > > > > >> Iteration 19: loss 0.8259870936519939, diff 0.0
> > > > > >> Iteration 20: loss 0.6327447552109576, diff 0.233952934583647
> > > > > >> Iteration 21: loss 0.6327447552109576, diff 0.0
> > > > > >> Iteration 22: loss 0.6327447552109576, diff 0.0
> > > > > >> Iteration 23: loss 0.5534101162436362, diff 0.12538154276652747
> > > > > >> Iteration 24: loss 0.5534101162436362, diff 0.0
> > > > > >> Iteration 25: loss 0.5534101162436362, diff 0.0
> > > > > >> Iteration 26: loss 0.40450200866125635, diff 0.2690732137675816
> > > > > >> Iteration 27: loss 0.40450200866125635, diff 0.0
> > > > > >> Iteration 28: loss 0.40450200866125635, diff 0.0
> > > > > >> Iteration 29: loss 0.30788249908237314, diff 0.23885980452569502
> > > > > >>
> > > > > >> Sincerely,
> > > > > >>
> > > > > >> DB Tsai
> > > > > >> Machine Learning Engineer
> > > > > >> Alpine Data Labs
> > > > > >> --------------------------------------
> > > > > >> Web: http://alpinenow.com/
> > > > > >>
> > > > > >>
> > > > > >> On Wed, Mar 5, 2014 at 2:00 PM, David Hall <
> dlwh@cs.berkeley.edu>
> > > > > wrote:
> > > > > >>> On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com>
> > > > wrote:
> > > > > >>>
> > > > > >>>> Hi David,
> > > > > >>>>
> > > > > >>>> On Tue, Mar 4, 2014 at 8:13 PM, dlwh <david.lw.hall@gmail.com
> >
> > > > wrote:
> > > > > >>>> > I'm happy to help fix any problems. I've verified at points
> > that
> > > > the
> > > > > >>>> > implementation gives the exact same sequence of iterates
> for a
> > > few
> > > > > >>>> different
> > > > > >>>> > functions (with a particular line search) as the c port of
> > > lbfgs.
> > > > > So I'm
> > > > > >>>> a
> > > > > >>>> > little surprised it fails where Fortran succeeds... but
> only a
> > > > > little.
> > > > > >>>> This
> > > > > >>>> > was fixed late last year.
> > > > > >>>> I'm working on a reproducible test case using breeze vs
> fortran
> > > > > >>>> implementation to show the problem I've run into. The test
> will
> > be
> > > > in
> > > > > >>>> one of the test cases in my Spark fork, is it okay for you to
> > > > > >>>> investigate the issue? Or do I need to make it as a standalone
> > > test?
> > > > > >>>>
> > > > > >>>
> > > > > >>>
> > > > > >>> Um, as long as it wouldn't be too hard to pull out.
> > > > > >>>
> > > > > >>>
> > > > > >>>>
> > > > > >>>> Will send you the test later today.
> > > > > >>>>
> > > > > >>>> Thanks.
> > > > > >>>>
> > > > > >>>> Sincerely,
> > > > > >>>>
> > > > > >>>> DB Tsai
> > > > > >>>> Machine Learning Engineer
> > > > > >>>> Alpine Data Labs
> > > > > >>>> --------------------------------------
> > > > > >>>> Web: http://alpinenow.com/
> > > > > >>>>
> > > > >
> > > >
> > >
> >
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by David Hall <dl...@cs.berkeley.edu>.
On Mon, Mar 31, 2014 at 10:15 AM, Debasish Das <de...@gmail.com>wrote:

> I added eclipse support in my qp branch:
>
> https://github.com/debasish83/breeze/tree/qp


Ok, great. Totally fine for this to come in with the QP.


>
>
> For the QP solver I will look into this solver http://www.joptimizer.com/
>
> Right now my plan is to use Professor Boyd's ECOS solver which is also
> designed in the very similar lines but has been tested to solve even cone
> programs...
>
> https://github.com/ifa-ethz/ecos
>
> Any idea whether I should add C native code using jniloader as the first
> version or rewrite using breeze.optimize style and call netlib-java calls
> for native support (ldl, cholesky etc)...
>

I personally don't care much. A year ago, I would have much preferred pure
JVM, and a few months ago I would have just said get it working with
natives, since presumably that's easier. *However*, ECOS is GPL, and
jniloader is LGPL. So, you can't require these dependencies in an Apache
product.

IANAL, but if you want this in Spark, I would suggest you stop looking at
ECOS immediately, at least until you have something that isn't encumbered
that works well enough.



>
> I still have to think how much cone support we will need...In ALS for
> example X^TX = I and Y^Y=I are interesting constraints for
> orthogonality...and they are quadratic constraints...With BFGS and CG, it
> is difficult to handle quadratic constraints...
>


I wonder how our general projected gradient solver would do? Clearly having
dedicated QP support is better, but in terms of just getting it working, it
might be enough.

-- David


>
>
>
> On Sun, Mar 30, 2014 at 4:40 PM, David Hall <dl...@cs.berkeley.edu> wrote:
>
> > On Sun, Mar 30, 2014 at 2:01 PM, Debasish Das <debasish.das83@gmail.com
> > >wrote:
> >
> > > Hi David,
> > >
> > > I have started to experiment with BFGS solvers for Spark GLM over large
> > > scale data...
> > >
> > > I am also looking to add a good QP solver in breeze that can be used in
> > > Spark ALS for constraint solves...More details on that soon...
> > >
> > > I could not load up breeze 0.7 code onto eclipse...There is a folder
> > called
> > > natives in the master but there is no code in that....all the code is
> in
> > > src/main/scala...
> > >
> > > I added the eclipse plugin:
> > >
> > > addSbtPlugin("com.github.mpeltonen" % "sbt-idea" % "1.6.0")
> > >
> > > addSbtPlugin("com.typesafe.sbteclipse" % "sbteclipse-plugin" % "2.2.0")
> > >
> > > But it seems the project is set to use idea...
> > >
> > > Could you please explain the dev methodology for breeze ? My idea is to
> > do
> > > solver work in breeze as that's the right place and get it into Spark
> > > through Xiangrui's WIP on Sparse data and breeze support...
> > >
> >
> > It would be great to have a QP Solver: I don't know if you know about
> this
> > library: http://www.joptimizer.com/
> >
> > I'm not quite sure what you mean by dev methodology. If you just mean how
> > to get code into Breeze, just send a PR to scalanlp/breeze. Unit tests
> are
> > good for something nontrivial like this. Maybe some basic documentation.
> >
> >
> > >
> > > Thanks.
> > > Deb
> > >
> > >
> > >
> > > On Fri, Mar 7, 2014 at 12:46 AM, DB Tsai <db...@alpinenow.com> wrote:
> > >
> > > > Hi Xiangrui,
> > > >
> > > > I think it doesn't matter whether we use Fortran/Breeze/RISO for
> > > > optimizers since optimization only takes << 1% of time. Most of the
> > > > time is in gradientSum and lossSum parallel computation.
> > > >
> > > > Sincerely,
> > > >
> > > > DB Tsai
> > > > Machine Learning Engineer
> > > > Alpine Data Labs
> > > > --------------------------------------
> > > > Web: http://alpinenow.com/
> > > >
> > > >
> > > > On Thu, Mar 6, 2014 at 7:10 PM, Xiangrui Meng <me...@gmail.com>
> > wrote:
> > > > > Hi DB,
> > > > >
> > > > > Thanks for doing the comparison! What were the running times for
> > > > > fortran/breeze/riso?
> > > > >
> > > > > Best,
> > > > > Xiangrui
> > > > >
> > > > > On Thu, Mar 6, 2014 at 4:21 PM, DB Tsai <db...@alpinenow.com>
> > wrote:
> > > > >> Hi David,
> > > > >>
> > > > >> I can converge to the same result with your breeze LBFGS and
> Fortran
> > > > >> implementations now. Probably, I made some mistakes when I tried
> > > > >> breeze before. I apologize that I claimed it's not stable.
> > > > >>
> > > > >> See the test case in BreezeLBFGSSuite.scala
> > > > >> https://github.com/AlpineNow/spark/tree/dbtsai-breezeLBFGS
> > > > >>
> > > > >> This is training multinomial logistic regression against iris
> > dataset,
> > > > >> and both optimizers can train the models with 98% training
> accuracy.
> > > > >>
> > > > >> There are two issues to use Breeze in Spark,
> > > > >>
> > > > >> 1) When the gradientSum and lossSum are computed distributively in
> > > > >> custom defined DiffFunction which will be passed into your
> > optimizer,
> > > > >> Spark will complain LBFGS class is not serializable. In
> > > > >> BreezeLBFGS.scala, I've to convert RDD to array to make it work
> > > > >> locally. It should be easy to fix by just having LBFGS to
> implement
> > > > >> Serializable.
> > > > >>
> > > > >> 2) Breeze computes redundant gradient and loss. See the following
> > log
> > > > >> from both Fortran and Breeze implementations.
> > > > >>
> > > > >> Thanks.
> > > > >>
> > > > >> Fortran:
> > > > >> Iteration -1: loss 1.3862943611198926, diff 1.0
> > > > >> Iteration 0: loss 1.5846343143210866, diff 0.14307193024217352
> > > > >> Iteration 1: loss 1.1242501524477688, diff 0.29053004039012126
> > > > >> Iteration 2: loss 1.0930151243303563, diff 0.027782962952189336
> > > > >> Iteration 3: loss 1.054036932835569, diff 0.03566113127440601
> > > > >> Iteration 4: loss 0.9907956302751622, diff 0.05999907649459571
> > > > >> Iteration 5: loss 0.9184205380342829, diff 0.07304737423337761
> > > > >> Iteration 6: loss 0.8259870936519937, diff 0.10064381175132982
> > > > >> Iteration 7: loss 0.6327447552109574, diff 0.23395293458364716
> > > > >> Iteration 8: loss 0.5534101162436359, diff 0.1253815427665277
> > > > >> Iteration 9: loss 0.4045020086612566, diff 0.26907321376758075
> > > > >> Iteration 10: loss 0.3078824990823728, diff 0.23885980452569627
> > > > >>
> > > > >> Breeze:
> > > > >> Iteration -1: loss 1.3862943611198926, diff 1.0
> > > > >> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> > > > >> WARNING: Failed to load implementation from:
> > > > >> com.github.fommil.netlib.NativeSystemBLAS
> > > > >> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> > > > >> WARNING: Failed to load implementation from:
> > > > >> com.github.fommil.netlib.NativeRefBLAS
> > > > >> Iteration 0: loss 1.3862943611198926, diff 0.0
> > > > >> Iteration 1: loss 1.5846343143210866, diff 0.14307193024217352
> > > > >> Iteration 2: loss 1.1242501524477688, diff 0.29053004039012126
> > > > >> Iteration 3: loss 1.1242501524477688, diff 0.0
> > > > >> Iteration 4: loss 1.1242501524477688, diff 0.0
> > > > >> Iteration 5: loss 1.0930151243303563, diff 0.027782962952189336
> > > > >> Iteration 6: loss 1.0930151243303563, diff 0.0
> > > > >> Iteration 7: loss 1.0930151243303563, diff 0.0
> > > > >> Iteration 8: loss 1.054036932835569, diff 0.03566113127440601
> > > > >> Iteration 9: loss 1.054036932835569, diff 0.0
> > > > >> Iteration 10: loss 1.054036932835569, diff 0.0
> > > > >> Iteration 11: loss 0.9907956302751622, diff 0.05999907649459571
> > > > >> Iteration 12: loss 0.9907956302751622, diff 0.0
> > > > >> Iteration 13: loss 0.9907956302751622, diff 0.0
> > > > >> Iteration 14: loss 0.9184205380342829, diff 0.07304737423337761
> > > > >> Iteration 15: loss 0.9184205380342829, diff 0.0
> > > > >> Iteration 16: loss 0.9184205380342829, diff 0.0
> > > > >> Iteration 17: loss 0.8259870936519939, diff 0.1006438117513297
> > > > >> Iteration 18: loss 0.8259870936519939, diff 0.0
> > > > >> Iteration 19: loss 0.8259870936519939, diff 0.0
> > > > >> Iteration 20: loss 0.6327447552109576, diff 0.233952934583647
> > > > >> Iteration 21: loss 0.6327447552109576, diff 0.0
> > > > >> Iteration 22: loss 0.6327447552109576, diff 0.0
> > > > >> Iteration 23: loss 0.5534101162436362, diff 0.12538154276652747
> > > > >> Iteration 24: loss 0.5534101162436362, diff 0.0
> > > > >> Iteration 25: loss 0.5534101162436362, diff 0.0
> > > > >> Iteration 26: loss 0.40450200866125635, diff 0.2690732137675816
> > > > >> Iteration 27: loss 0.40450200866125635, diff 0.0
> > > > >> Iteration 28: loss 0.40450200866125635, diff 0.0
> > > > >> Iteration 29: loss 0.30788249908237314, diff 0.23885980452569502
> > > > >>
> > > > >> Sincerely,
> > > > >>
> > > > >> DB Tsai
> > > > >> Machine Learning Engineer
> > > > >> Alpine Data Labs
> > > > >> --------------------------------------
> > > > >> Web: http://alpinenow.com/
> > > > >>
> > > > >>
> > > > >> On Wed, Mar 5, 2014 at 2:00 PM, David Hall <dl...@cs.berkeley.edu>
> > > > wrote:
> > > > >>> On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com>
> > > wrote:
> > > > >>>
> > > > >>>> Hi David,
> > > > >>>>
> > > > >>>> On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com>
> > > wrote:
> > > > >>>> > I'm happy to help fix any problems. I've verified at points
> that
> > > the
> > > > >>>> > implementation gives the exact same sequence of iterates for a
> > few
> > > > >>>> different
> > > > >>>> > functions (with a particular line search) as the c port of
> > lbfgs.
> > > > So I'm
> > > > >>>> a
> > > > >>>> > little surprised it fails where Fortran succeeds... but only a
> > > > little.
> > > > >>>> This
> > > > >>>> > was fixed late last year.
> > > > >>>> I'm working on a reproducible test case using breeze vs fortran
> > > > >>>> implementation to show the problem I've run into. The test will
> be
> > > in
> > > > >>>> one of the test cases in my Spark fork, is it okay for you to
> > > > >>>> investigate the issue? Or do I need to make it as a standalone
> > test?
> > > > >>>>
> > > > >>>
> > > > >>>
> > > > >>> Um, as long as it wouldn't be too hard to pull out.
> > > > >>>
> > > > >>>
> > > > >>>>
> > > > >>>> Will send you the test later today.
> > > > >>>>
> > > > >>>> Thanks.
> > > > >>>>
> > > > >>>> Sincerely,
> > > > >>>>
> > > > >>>> DB Tsai
> > > > >>>> Machine Learning Engineer
> > > > >>>> Alpine Data Labs
> > > > >>>> --------------------------------------
> > > > >>>> Web: http://alpinenow.com/
> > > > >>>>
> > > >
> > >
> >
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
I added eclipse support in my qp branch:

https://github.com/debasish83/breeze/tree/qp

For the QP solver I will look into this solver http://www.joptimizer.com/

Right now my plan is to use Professor Boyd's ECOS solver which is also
designed in the very similar lines but has been tested to solve even cone
programs...

https://github.com/ifa-ethz/ecos

Any idea whether I should add C native code using jniloader as the first
version or rewrite using breeze.optimize style and call netlib-java calls
for native support (ldl, cholesky etc)...

I still have to think how much cone support we will need...In ALS for
example X^TX = I and Y^Y=I are interesting constraints for
orthogonality...and they are quadratic constraints...With BFGS and CG, it
is difficult to handle quadratic constraints...



On Sun, Mar 30, 2014 at 4:40 PM, David Hall <dl...@cs.berkeley.edu> wrote:

> On Sun, Mar 30, 2014 at 2:01 PM, Debasish Das <debasish.das83@gmail.com
> >wrote:
>
> > Hi David,
> >
> > I have started to experiment with BFGS solvers for Spark GLM over large
> > scale data...
> >
> > I am also looking to add a good QP solver in breeze that can be used in
> > Spark ALS for constraint solves...More details on that soon...
> >
> > I could not load up breeze 0.7 code onto eclipse...There is a folder
> called
> > natives in the master but there is no code in that....all the code is in
> > src/main/scala...
> >
> > I added the eclipse plugin:
> >
> > addSbtPlugin("com.github.mpeltonen" % "sbt-idea" % "1.6.0")
> >
> > addSbtPlugin("com.typesafe.sbteclipse" % "sbteclipse-plugin" % "2.2.0")
> >
> > But it seems the project is set to use idea...
> >
> > Could you please explain the dev methodology for breeze ? My idea is to
> do
> > solver work in breeze as that's the right place and get it into Spark
> > through Xiangrui's WIP on Sparse data and breeze support...
> >
>
> It would be great to have a QP Solver: I don't know if you know about this
> library: http://www.joptimizer.com/
>
> I'm not quite sure what you mean by dev methodology. If you just mean how
> to get code into Breeze, just send a PR to scalanlp/breeze. Unit tests are
> good for something nontrivial like this. Maybe some basic documentation.
>
>
> >
> > Thanks.
> > Deb
> >
> >
> >
> > On Fri, Mar 7, 2014 at 12:46 AM, DB Tsai <db...@alpinenow.com> wrote:
> >
> > > Hi Xiangrui,
> > >
> > > I think it doesn't matter whether we use Fortran/Breeze/RISO for
> > > optimizers since optimization only takes << 1% of time. Most of the
> > > time is in gradientSum and lossSum parallel computation.
> > >
> > > Sincerely,
> > >
> > > DB Tsai
> > > Machine Learning Engineer
> > > Alpine Data Labs
> > > --------------------------------------
> > > Web: http://alpinenow.com/
> > >
> > >
> > > On Thu, Mar 6, 2014 at 7:10 PM, Xiangrui Meng <me...@gmail.com>
> wrote:
> > > > Hi DB,
> > > >
> > > > Thanks for doing the comparison! What were the running times for
> > > > fortran/breeze/riso?
> > > >
> > > > Best,
> > > > Xiangrui
> > > >
> > > > On Thu, Mar 6, 2014 at 4:21 PM, DB Tsai <db...@alpinenow.com>
> wrote:
> > > >> Hi David,
> > > >>
> > > >> I can converge to the same result with your breeze LBFGS and Fortran
> > > >> implementations now. Probably, I made some mistakes when I tried
> > > >> breeze before. I apologize that I claimed it's not stable.
> > > >>
> > > >> See the test case in BreezeLBFGSSuite.scala
> > > >> https://github.com/AlpineNow/spark/tree/dbtsai-breezeLBFGS
> > > >>
> > > >> This is training multinomial logistic regression against iris
> dataset,
> > > >> and both optimizers can train the models with 98% training accuracy.
> > > >>
> > > >> There are two issues to use Breeze in Spark,
> > > >>
> > > >> 1) When the gradientSum and lossSum are computed distributively in
> > > >> custom defined DiffFunction which will be passed into your
> optimizer,
> > > >> Spark will complain LBFGS class is not serializable. In
> > > >> BreezeLBFGS.scala, I've to convert RDD to array to make it work
> > > >> locally. It should be easy to fix by just having LBFGS to implement
> > > >> Serializable.
> > > >>
> > > >> 2) Breeze computes redundant gradient and loss. See the following
> log
> > > >> from both Fortran and Breeze implementations.
> > > >>
> > > >> Thanks.
> > > >>
> > > >> Fortran:
> > > >> Iteration -1: loss 1.3862943611198926, diff 1.0
> > > >> Iteration 0: loss 1.5846343143210866, diff 0.14307193024217352
> > > >> Iteration 1: loss 1.1242501524477688, diff 0.29053004039012126
> > > >> Iteration 2: loss 1.0930151243303563, diff 0.027782962952189336
> > > >> Iteration 3: loss 1.054036932835569, diff 0.03566113127440601
> > > >> Iteration 4: loss 0.9907956302751622, diff 0.05999907649459571
> > > >> Iteration 5: loss 0.9184205380342829, diff 0.07304737423337761
> > > >> Iteration 6: loss 0.8259870936519937, diff 0.10064381175132982
> > > >> Iteration 7: loss 0.6327447552109574, diff 0.23395293458364716
> > > >> Iteration 8: loss 0.5534101162436359, diff 0.1253815427665277
> > > >> Iteration 9: loss 0.4045020086612566, diff 0.26907321376758075
> > > >> Iteration 10: loss 0.3078824990823728, diff 0.23885980452569627
> > > >>
> > > >> Breeze:
> > > >> Iteration -1: loss 1.3862943611198926, diff 1.0
> > > >> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> > > >> WARNING: Failed to load implementation from:
> > > >> com.github.fommil.netlib.NativeSystemBLAS
> > > >> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> > > >> WARNING: Failed to load implementation from:
> > > >> com.github.fommil.netlib.NativeRefBLAS
> > > >> Iteration 0: loss 1.3862943611198926, diff 0.0
> > > >> Iteration 1: loss 1.5846343143210866, diff 0.14307193024217352
> > > >> Iteration 2: loss 1.1242501524477688, diff 0.29053004039012126
> > > >> Iteration 3: loss 1.1242501524477688, diff 0.0
> > > >> Iteration 4: loss 1.1242501524477688, diff 0.0
> > > >> Iteration 5: loss 1.0930151243303563, diff 0.027782962952189336
> > > >> Iteration 6: loss 1.0930151243303563, diff 0.0
> > > >> Iteration 7: loss 1.0930151243303563, diff 0.0
> > > >> Iteration 8: loss 1.054036932835569, diff 0.03566113127440601
> > > >> Iteration 9: loss 1.054036932835569, diff 0.0
> > > >> Iteration 10: loss 1.054036932835569, diff 0.0
> > > >> Iteration 11: loss 0.9907956302751622, diff 0.05999907649459571
> > > >> Iteration 12: loss 0.9907956302751622, diff 0.0
> > > >> Iteration 13: loss 0.9907956302751622, diff 0.0
> > > >> Iteration 14: loss 0.9184205380342829, diff 0.07304737423337761
> > > >> Iteration 15: loss 0.9184205380342829, diff 0.0
> > > >> Iteration 16: loss 0.9184205380342829, diff 0.0
> > > >> Iteration 17: loss 0.8259870936519939, diff 0.1006438117513297
> > > >> Iteration 18: loss 0.8259870936519939, diff 0.0
> > > >> Iteration 19: loss 0.8259870936519939, diff 0.0
> > > >> Iteration 20: loss 0.6327447552109576, diff 0.233952934583647
> > > >> Iteration 21: loss 0.6327447552109576, diff 0.0
> > > >> Iteration 22: loss 0.6327447552109576, diff 0.0
> > > >> Iteration 23: loss 0.5534101162436362, diff 0.12538154276652747
> > > >> Iteration 24: loss 0.5534101162436362, diff 0.0
> > > >> Iteration 25: loss 0.5534101162436362, diff 0.0
> > > >> Iteration 26: loss 0.40450200866125635, diff 0.2690732137675816
> > > >> Iteration 27: loss 0.40450200866125635, diff 0.0
> > > >> Iteration 28: loss 0.40450200866125635, diff 0.0
> > > >> Iteration 29: loss 0.30788249908237314, diff 0.23885980452569502
> > > >>
> > > >> Sincerely,
> > > >>
> > > >> DB Tsai
> > > >> Machine Learning Engineer
> > > >> Alpine Data Labs
> > > >> --------------------------------------
> > > >> Web: http://alpinenow.com/
> > > >>
> > > >>
> > > >> On Wed, Mar 5, 2014 at 2:00 PM, David Hall <dl...@cs.berkeley.edu>
> > > wrote:
> > > >>> On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com>
> > wrote:
> > > >>>
> > > >>>> Hi David,
> > > >>>>
> > > >>>> On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com>
> > wrote:
> > > >>>> > I'm happy to help fix any problems. I've verified at points that
> > the
> > > >>>> > implementation gives the exact same sequence of iterates for a
> few
> > > >>>> different
> > > >>>> > functions (with a particular line search) as the c port of
> lbfgs.
> > > So I'm
> > > >>>> a
> > > >>>> > little surprised it fails where Fortran succeeds... but only a
> > > little.
> > > >>>> This
> > > >>>> > was fixed late last year.
> > > >>>> I'm working on a reproducible test case using breeze vs fortran
> > > >>>> implementation to show the problem I've run into. The test will be
> > in
> > > >>>> one of the test cases in my Spark fork, is it okay for you to
> > > >>>> investigate the issue? Or do I need to make it as a standalone
> test?
> > > >>>>
> > > >>>
> > > >>>
> > > >>> Um, as long as it wouldn't be too hard to pull out.
> > > >>>
> > > >>>
> > > >>>>
> > > >>>> Will send you the test later today.
> > > >>>>
> > > >>>> Thanks.
> > > >>>>
> > > >>>> Sincerely,
> > > >>>>
> > > >>>> DB Tsai
> > > >>>> Machine Learning Engineer
> > > >>>> Alpine Data Labs
> > > >>>> --------------------------------------
> > > >>>> Web: http://alpinenow.com/
> > > >>>>
> > >
> >
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by David Hall <dl...@cs.berkeley.edu>.
On Sun, Mar 30, 2014 at 2:01 PM, Debasish Das <de...@gmail.com>wrote:

> Hi David,
>
> I have started to experiment with BFGS solvers for Spark GLM over large
> scale data...
>
> I am also looking to add a good QP solver in breeze that can be used in
> Spark ALS for constraint solves...More details on that soon...
>
> I could not load up breeze 0.7 code onto eclipse...There is a folder called
> natives in the master but there is no code in that....all the code is in
> src/main/scala...
>
> I added the eclipse plugin:
>
> addSbtPlugin("com.github.mpeltonen" % "sbt-idea" % "1.6.0")
>
> addSbtPlugin("com.typesafe.sbteclipse" % "sbteclipse-plugin" % "2.2.0")
>
> But it seems the project is set to use idea...
>
> Could you please explain the dev methodology for breeze ? My idea is to do
> solver work in breeze as that's the right place and get it into Spark
> through Xiangrui's WIP on Sparse data and breeze support...
>

It would be great to have a QP Solver: I don't know if you know about this
library: http://www.joptimizer.com/

I'm not quite sure what you mean by dev methodology. If you just mean how
to get code into Breeze, just send a PR to scalanlp/breeze. Unit tests are
good for something nontrivial like this. Maybe some basic documentation.


>
> Thanks.
> Deb
>
>
>
> On Fri, Mar 7, 2014 at 12:46 AM, DB Tsai <db...@alpinenow.com> wrote:
>
> > Hi Xiangrui,
> >
> > I think it doesn't matter whether we use Fortran/Breeze/RISO for
> > optimizers since optimization only takes << 1% of time. Most of the
> > time is in gradientSum and lossSum parallel computation.
> >
> > Sincerely,
> >
> > DB Tsai
> > Machine Learning Engineer
> > Alpine Data Labs
> > --------------------------------------
> > Web: http://alpinenow.com/
> >
> >
> > On Thu, Mar 6, 2014 at 7:10 PM, Xiangrui Meng <me...@gmail.com> wrote:
> > > Hi DB,
> > >
> > > Thanks for doing the comparison! What were the running times for
> > > fortran/breeze/riso?
> > >
> > > Best,
> > > Xiangrui
> > >
> > > On Thu, Mar 6, 2014 at 4:21 PM, DB Tsai <db...@alpinenow.com> wrote:
> > >> Hi David,
> > >>
> > >> I can converge to the same result with your breeze LBFGS and Fortran
> > >> implementations now. Probably, I made some mistakes when I tried
> > >> breeze before. I apologize that I claimed it's not stable.
> > >>
> > >> See the test case in BreezeLBFGSSuite.scala
> > >> https://github.com/AlpineNow/spark/tree/dbtsai-breezeLBFGS
> > >>
> > >> This is training multinomial logistic regression against iris dataset,
> > >> and both optimizers can train the models with 98% training accuracy.
> > >>
> > >> There are two issues to use Breeze in Spark,
> > >>
> > >> 1) When the gradientSum and lossSum are computed distributively in
> > >> custom defined DiffFunction which will be passed into your optimizer,
> > >> Spark will complain LBFGS class is not serializable. In
> > >> BreezeLBFGS.scala, I've to convert RDD to array to make it work
> > >> locally. It should be easy to fix by just having LBFGS to implement
> > >> Serializable.
> > >>
> > >> 2) Breeze computes redundant gradient and loss. See the following log
> > >> from both Fortran and Breeze implementations.
> > >>
> > >> Thanks.
> > >>
> > >> Fortran:
> > >> Iteration -1: loss 1.3862943611198926, diff 1.0
> > >> Iteration 0: loss 1.5846343143210866, diff 0.14307193024217352
> > >> Iteration 1: loss 1.1242501524477688, diff 0.29053004039012126
> > >> Iteration 2: loss 1.0930151243303563, diff 0.027782962952189336
> > >> Iteration 3: loss 1.054036932835569, diff 0.03566113127440601
> > >> Iteration 4: loss 0.9907956302751622, diff 0.05999907649459571
> > >> Iteration 5: loss 0.9184205380342829, diff 0.07304737423337761
> > >> Iteration 6: loss 0.8259870936519937, diff 0.10064381175132982
> > >> Iteration 7: loss 0.6327447552109574, diff 0.23395293458364716
> > >> Iteration 8: loss 0.5534101162436359, diff 0.1253815427665277
> > >> Iteration 9: loss 0.4045020086612566, diff 0.26907321376758075
> > >> Iteration 10: loss 0.3078824990823728, diff 0.23885980452569627
> > >>
> > >> Breeze:
> > >> Iteration -1: loss 1.3862943611198926, diff 1.0
> > >> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> > >> WARNING: Failed to load implementation from:
> > >> com.github.fommil.netlib.NativeSystemBLAS
> > >> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> > >> WARNING: Failed to load implementation from:
> > >> com.github.fommil.netlib.NativeRefBLAS
> > >> Iteration 0: loss 1.3862943611198926, diff 0.0
> > >> Iteration 1: loss 1.5846343143210866, diff 0.14307193024217352
> > >> Iteration 2: loss 1.1242501524477688, diff 0.29053004039012126
> > >> Iteration 3: loss 1.1242501524477688, diff 0.0
> > >> Iteration 4: loss 1.1242501524477688, diff 0.0
> > >> Iteration 5: loss 1.0930151243303563, diff 0.027782962952189336
> > >> Iteration 6: loss 1.0930151243303563, diff 0.0
> > >> Iteration 7: loss 1.0930151243303563, diff 0.0
> > >> Iteration 8: loss 1.054036932835569, diff 0.03566113127440601
> > >> Iteration 9: loss 1.054036932835569, diff 0.0
> > >> Iteration 10: loss 1.054036932835569, diff 0.0
> > >> Iteration 11: loss 0.9907956302751622, diff 0.05999907649459571
> > >> Iteration 12: loss 0.9907956302751622, diff 0.0
> > >> Iteration 13: loss 0.9907956302751622, diff 0.0
> > >> Iteration 14: loss 0.9184205380342829, diff 0.07304737423337761
> > >> Iteration 15: loss 0.9184205380342829, diff 0.0
> > >> Iteration 16: loss 0.9184205380342829, diff 0.0
> > >> Iteration 17: loss 0.8259870936519939, diff 0.1006438117513297
> > >> Iteration 18: loss 0.8259870936519939, diff 0.0
> > >> Iteration 19: loss 0.8259870936519939, diff 0.0
> > >> Iteration 20: loss 0.6327447552109576, diff 0.233952934583647
> > >> Iteration 21: loss 0.6327447552109576, diff 0.0
> > >> Iteration 22: loss 0.6327447552109576, diff 0.0
> > >> Iteration 23: loss 0.5534101162436362, diff 0.12538154276652747
> > >> Iteration 24: loss 0.5534101162436362, diff 0.0
> > >> Iteration 25: loss 0.5534101162436362, diff 0.0
> > >> Iteration 26: loss 0.40450200866125635, diff 0.2690732137675816
> > >> Iteration 27: loss 0.40450200866125635, diff 0.0
> > >> Iteration 28: loss 0.40450200866125635, diff 0.0
> > >> Iteration 29: loss 0.30788249908237314, diff 0.23885980452569502
> > >>
> > >> Sincerely,
> > >>
> > >> DB Tsai
> > >> Machine Learning Engineer
> > >> Alpine Data Labs
> > >> --------------------------------------
> > >> Web: http://alpinenow.com/
> > >>
> > >>
> > >> On Wed, Mar 5, 2014 at 2:00 PM, David Hall <dl...@cs.berkeley.edu>
> > wrote:
> > >>> On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com>
> wrote:
> > >>>
> > >>>> Hi David,
> > >>>>
> > >>>> On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com>
> wrote:
> > >>>> > I'm happy to help fix any problems. I've verified at points that
> the
> > >>>> > implementation gives the exact same sequence of iterates for a few
> > >>>> different
> > >>>> > functions (with a particular line search) as the c port of lbfgs.
> > So I'm
> > >>>> a
> > >>>> > little surprised it fails where Fortran succeeds... but only a
> > little.
> > >>>> This
> > >>>> > was fixed late last year.
> > >>>> I'm working on a reproducible test case using breeze vs fortran
> > >>>> implementation to show the problem I've run into. The test will be
> in
> > >>>> one of the test cases in my Spark fork, is it okay for you to
> > >>>> investigate the issue? Or do I need to make it as a standalone test?
> > >>>>
> > >>>
> > >>>
> > >>> Um, as long as it wouldn't be too hard to pull out.
> > >>>
> > >>>
> > >>>>
> > >>>> Will send you the test later today.
> > >>>>
> > >>>> Thanks.
> > >>>>
> > >>>> Sincerely,
> > >>>>
> > >>>> DB Tsai
> > >>>> Machine Learning Engineer
> > >>>> Alpine Data Labs
> > >>>> --------------------------------------
> > >>>> Web: http://alpinenow.com/
> > >>>>
> >
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
Hi David,

I have started to experiment with BFGS solvers for Spark GLM over large
scale data...

I am also looking to add a good QP solver in breeze that can be used in
Spark ALS for constraint solves...More details on that soon...

I could not load up breeze 0.7 code onto eclipse...There is a folder called
natives in the master but there is no code in that....all the code is in
src/main/scala...

I added the eclipse plugin:

addSbtPlugin("com.github.mpeltonen" % "sbt-idea" % "1.6.0")

addSbtPlugin("com.typesafe.sbteclipse" % "sbteclipse-plugin" % "2.2.0")

But it seems the project is set to use idea...

Could you please explain the dev methodology for breeze ? My idea is to do
solver work in breeze as that's the right place and get it into Spark
through Xiangrui's WIP on Sparse data and breeze support...

Thanks.
Deb



On Fri, Mar 7, 2014 at 12:46 AM, DB Tsai <db...@alpinenow.com> wrote:

> Hi Xiangrui,
>
> I think it doesn't matter whether we use Fortran/Breeze/RISO for
> optimizers since optimization only takes << 1% of time. Most of the
> time is in gradientSum and lossSum parallel computation.
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/
>
>
> On Thu, Mar 6, 2014 at 7:10 PM, Xiangrui Meng <me...@gmail.com> wrote:
> > Hi DB,
> >
> > Thanks for doing the comparison! What were the running times for
> > fortran/breeze/riso?
> >
> > Best,
> > Xiangrui
> >
> > On Thu, Mar 6, 2014 at 4:21 PM, DB Tsai <db...@alpinenow.com> wrote:
> >> Hi David,
> >>
> >> I can converge to the same result with your breeze LBFGS and Fortran
> >> implementations now. Probably, I made some mistakes when I tried
> >> breeze before. I apologize that I claimed it's not stable.
> >>
> >> See the test case in BreezeLBFGSSuite.scala
> >> https://github.com/AlpineNow/spark/tree/dbtsai-breezeLBFGS
> >>
> >> This is training multinomial logistic regression against iris dataset,
> >> and both optimizers can train the models with 98% training accuracy.
> >>
> >> There are two issues to use Breeze in Spark,
> >>
> >> 1) When the gradientSum and lossSum are computed distributively in
> >> custom defined DiffFunction which will be passed into your optimizer,
> >> Spark will complain LBFGS class is not serializable. In
> >> BreezeLBFGS.scala, I've to convert RDD to array to make it work
> >> locally. It should be easy to fix by just having LBFGS to implement
> >> Serializable.
> >>
> >> 2) Breeze computes redundant gradient and loss. See the following log
> >> from both Fortran and Breeze implementations.
> >>
> >> Thanks.
> >>
> >> Fortran:
> >> Iteration -1: loss 1.3862943611198926, diff 1.0
> >> Iteration 0: loss 1.5846343143210866, diff 0.14307193024217352
> >> Iteration 1: loss 1.1242501524477688, diff 0.29053004039012126
> >> Iteration 2: loss 1.0930151243303563, diff 0.027782962952189336
> >> Iteration 3: loss 1.054036932835569, diff 0.03566113127440601
> >> Iteration 4: loss 0.9907956302751622, diff 0.05999907649459571
> >> Iteration 5: loss 0.9184205380342829, diff 0.07304737423337761
> >> Iteration 6: loss 0.8259870936519937, diff 0.10064381175132982
> >> Iteration 7: loss 0.6327447552109574, diff 0.23395293458364716
> >> Iteration 8: loss 0.5534101162436359, diff 0.1253815427665277
> >> Iteration 9: loss 0.4045020086612566, diff 0.26907321376758075
> >> Iteration 10: loss 0.3078824990823728, diff 0.23885980452569627
> >>
> >> Breeze:
> >> Iteration -1: loss 1.3862943611198926, diff 1.0
> >> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> >> WARNING: Failed to load implementation from:
> >> com.github.fommil.netlib.NativeSystemBLAS
> >> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> >> WARNING: Failed to load implementation from:
> >> com.github.fommil.netlib.NativeRefBLAS
> >> Iteration 0: loss 1.3862943611198926, diff 0.0
> >> Iteration 1: loss 1.5846343143210866, diff 0.14307193024217352
> >> Iteration 2: loss 1.1242501524477688, diff 0.29053004039012126
> >> Iteration 3: loss 1.1242501524477688, diff 0.0
> >> Iteration 4: loss 1.1242501524477688, diff 0.0
> >> Iteration 5: loss 1.0930151243303563, diff 0.027782962952189336
> >> Iteration 6: loss 1.0930151243303563, diff 0.0
> >> Iteration 7: loss 1.0930151243303563, diff 0.0
> >> Iteration 8: loss 1.054036932835569, diff 0.03566113127440601
> >> Iteration 9: loss 1.054036932835569, diff 0.0
> >> Iteration 10: loss 1.054036932835569, diff 0.0
> >> Iteration 11: loss 0.9907956302751622, diff 0.05999907649459571
> >> Iteration 12: loss 0.9907956302751622, diff 0.0
> >> Iteration 13: loss 0.9907956302751622, diff 0.0
> >> Iteration 14: loss 0.9184205380342829, diff 0.07304737423337761
> >> Iteration 15: loss 0.9184205380342829, diff 0.0
> >> Iteration 16: loss 0.9184205380342829, diff 0.0
> >> Iteration 17: loss 0.8259870936519939, diff 0.1006438117513297
> >> Iteration 18: loss 0.8259870936519939, diff 0.0
> >> Iteration 19: loss 0.8259870936519939, diff 0.0
> >> Iteration 20: loss 0.6327447552109576, diff 0.233952934583647
> >> Iteration 21: loss 0.6327447552109576, diff 0.0
> >> Iteration 22: loss 0.6327447552109576, diff 0.0
> >> Iteration 23: loss 0.5534101162436362, diff 0.12538154276652747
> >> Iteration 24: loss 0.5534101162436362, diff 0.0
> >> Iteration 25: loss 0.5534101162436362, diff 0.0
> >> Iteration 26: loss 0.40450200866125635, diff 0.2690732137675816
> >> Iteration 27: loss 0.40450200866125635, diff 0.0
> >> Iteration 28: loss 0.40450200866125635, diff 0.0
> >> Iteration 29: loss 0.30788249908237314, diff 0.23885980452569502
> >>
> >> Sincerely,
> >>
> >> DB Tsai
> >> Machine Learning Engineer
> >> Alpine Data Labs
> >> --------------------------------------
> >> Web: http://alpinenow.com/
> >>
> >>
> >> On Wed, Mar 5, 2014 at 2:00 PM, David Hall <dl...@cs.berkeley.edu>
> wrote:
> >>> On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com> wrote:
> >>>
> >>>> Hi David,
> >>>>
> >>>> On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com> wrote:
> >>>> > I'm happy to help fix any problems. I've verified at points that the
> >>>> > implementation gives the exact same sequence of iterates for a few
> >>>> different
> >>>> > functions (with a particular line search) as the c port of lbfgs.
> So I'm
> >>>> a
> >>>> > little surprised it fails where Fortran succeeds... but only a
> little.
> >>>> This
> >>>> > was fixed late last year.
> >>>> I'm working on a reproducible test case using breeze vs fortran
> >>>> implementation to show the problem I've run into. The test will be in
> >>>> one of the test cases in my Spark fork, is it okay for you to
> >>>> investigate the issue? Or do I need to make it as a standalone test?
> >>>>
> >>>
> >>>
> >>> Um, as long as it wouldn't be too hard to pull out.
> >>>
> >>>
> >>>>
> >>>> Will send you the test later today.
> >>>>
> >>>> Thanks.
> >>>>
> >>>> Sincerely,
> >>>>
> >>>> DB Tsai
> >>>> Machine Learning Engineer
> >>>> Alpine Data Labs
> >>>> --------------------------------------
> >>>> Web: http://alpinenow.com/
> >>>>
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
Hi Xiangrui,

I think it doesn't matter whether we use Fortran/Breeze/RISO for
optimizers since optimization only takes << 1% of time. Most of the
time is in gradientSum and lossSum parallel computation.

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/


On Thu, Mar 6, 2014 at 7:10 PM, Xiangrui Meng <me...@gmail.com> wrote:
> Hi DB,
>
> Thanks for doing the comparison! What were the running times for
> fortran/breeze/riso?
>
> Best,
> Xiangrui
>
> On Thu, Mar 6, 2014 at 4:21 PM, DB Tsai <db...@alpinenow.com> wrote:
>> Hi David,
>>
>> I can converge to the same result with your breeze LBFGS and Fortran
>> implementations now. Probably, I made some mistakes when I tried
>> breeze before. I apologize that I claimed it's not stable.
>>
>> See the test case in BreezeLBFGSSuite.scala
>> https://github.com/AlpineNow/spark/tree/dbtsai-breezeLBFGS
>>
>> This is training multinomial logistic regression against iris dataset,
>> and both optimizers can train the models with 98% training accuracy.
>>
>> There are two issues to use Breeze in Spark,
>>
>> 1) When the gradientSum and lossSum are computed distributively in
>> custom defined DiffFunction which will be passed into your optimizer,
>> Spark will complain LBFGS class is not serializable. In
>> BreezeLBFGS.scala, I've to convert RDD to array to make it work
>> locally. It should be easy to fix by just having LBFGS to implement
>> Serializable.
>>
>> 2) Breeze computes redundant gradient and loss. See the following log
>> from both Fortran and Breeze implementations.
>>
>> Thanks.
>>
>> Fortran:
>> Iteration -1: loss 1.3862943611198926, diff 1.0
>> Iteration 0: loss 1.5846343143210866, diff 0.14307193024217352
>> Iteration 1: loss 1.1242501524477688, diff 0.29053004039012126
>> Iteration 2: loss 1.0930151243303563, diff 0.027782962952189336
>> Iteration 3: loss 1.054036932835569, diff 0.03566113127440601
>> Iteration 4: loss 0.9907956302751622, diff 0.05999907649459571
>> Iteration 5: loss 0.9184205380342829, diff 0.07304737423337761
>> Iteration 6: loss 0.8259870936519937, diff 0.10064381175132982
>> Iteration 7: loss 0.6327447552109574, diff 0.23395293458364716
>> Iteration 8: loss 0.5534101162436359, diff 0.1253815427665277
>> Iteration 9: loss 0.4045020086612566, diff 0.26907321376758075
>> Iteration 10: loss 0.3078824990823728, diff 0.23885980452569627
>>
>> Breeze:
>> Iteration -1: loss 1.3862943611198926, diff 1.0
>> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
>> WARNING: Failed to load implementation from:
>> com.github.fommil.netlib.NativeSystemBLAS
>> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
>> WARNING: Failed to load implementation from:
>> com.github.fommil.netlib.NativeRefBLAS
>> Iteration 0: loss 1.3862943611198926, diff 0.0
>> Iteration 1: loss 1.5846343143210866, diff 0.14307193024217352
>> Iteration 2: loss 1.1242501524477688, diff 0.29053004039012126
>> Iteration 3: loss 1.1242501524477688, diff 0.0
>> Iteration 4: loss 1.1242501524477688, diff 0.0
>> Iteration 5: loss 1.0930151243303563, diff 0.027782962952189336
>> Iteration 6: loss 1.0930151243303563, diff 0.0
>> Iteration 7: loss 1.0930151243303563, diff 0.0
>> Iteration 8: loss 1.054036932835569, diff 0.03566113127440601
>> Iteration 9: loss 1.054036932835569, diff 0.0
>> Iteration 10: loss 1.054036932835569, diff 0.0
>> Iteration 11: loss 0.9907956302751622, diff 0.05999907649459571
>> Iteration 12: loss 0.9907956302751622, diff 0.0
>> Iteration 13: loss 0.9907956302751622, diff 0.0
>> Iteration 14: loss 0.9184205380342829, diff 0.07304737423337761
>> Iteration 15: loss 0.9184205380342829, diff 0.0
>> Iteration 16: loss 0.9184205380342829, diff 0.0
>> Iteration 17: loss 0.8259870936519939, diff 0.1006438117513297
>> Iteration 18: loss 0.8259870936519939, diff 0.0
>> Iteration 19: loss 0.8259870936519939, diff 0.0
>> Iteration 20: loss 0.6327447552109576, diff 0.233952934583647
>> Iteration 21: loss 0.6327447552109576, diff 0.0
>> Iteration 22: loss 0.6327447552109576, diff 0.0
>> Iteration 23: loss 0.5534101162436362, diff 0.12538154276652747
>> Iteration 24: loss 0.5534101162436362, diff 0.0
>> Iteration 25: loss 0.5534101162436362, diff 0.0
>> Iteration 26: loss 0.40450200866125635, diff 0.2690732137675816
>> Iteration 27: loss 0.40450200866125635, diff 0.0
>> Iteration 28: loss 0.40450200866125635, diff 0.0
>> Iteration 29: loss 0.30788249908237314, diff 0.23885980452569502
>>
>> Sincerely,
>>
>> DB Tsai
>> Machine Learning Engineer
>> Alpine Data Labs
>> --------------------------------------
>> Web: http://alpinenow.com/
>>
>>
>> On Wed, Mar 5, 2014 at 2:00 PM, David Hall <dl...@cs.berkeley.edu> wrote:
>>> On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com> wrote:
>>>
>>>> Hi David,
>>>>
>>>> On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com> wrote:
>>>> > I'm happy to help fix any problems. I've verified at points that the
>>>> > implementation gives the exact same sequence of iterates for a few
>>>> different
>>>> > functions (with a particular line search) as the c port of lbfgs. So I'm
>>>> a
>>>> > little surprised it fails where Fortran succeeds... but only a little.
>>>> This
>>>> > was fixed late last year.
>>>> I'm working on a reproducible test case using breeze vs fortran
>>>> implementation to show the problem I've run into. The test will be in
>>>> one of the test cases in my Spark fork, is it okay for you to
>>>> investigate the issue? Or do I need to make it as a standalone test?
>>>>
>>>
>>>
>>> Um, as long as it wouldn't be too hard to pull out.
>>>
>>>
>>>>
>>>> Will send you the test later today.
>>>>
>>>> Thanks.
>>>>
>>>> Sincerely,
>>>>
>>>> DB Tsai
>>>> Machine Learning Engineer
>>>> Alpine Data Labs
>>>> --------------------------------------
>>>> Web: http://alpinenow.com/
>>>>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Xiangrui Meng <me...@gmail.com>.
Hi DB,

Thanks for doing the comparison! What were the running times for
fortran/breeze/riso?

Best,
Xiangrui

On Thu, Mar 6, 2014 at 4:21 PM, DB Tsai <db...@alpinenow.com> wrote:
> Hi David,
>
> I can converge to the same result with your breeze LBFGS and Fortran
> implementations now. Probably, I made some mistakes when I tried
> breeze before. I apologize that I claimed it's not stable.
>
> See the test case in BreezeLBFGSSuite.scala
> https://github.com/AlpineNow/spark/tree/dbtsai-breezeLBFGS
>
> This is training multinomial logistic regression against iris dataset,
> and both optimizers can train the models with 98% training accuracy.
>
> There are two issues to use Breeze in Spark,
>
> 1) When the gradientSum and lossSum are computed distributively in
> custom defined DiffFunction which will be passed into your optimizer,
> Spark will complain LBFGS class is not serializable. In
> BreezeLBFGS.scala, I've to convert RDD to array to make it work
> locally. It should be easy to fix by just having LBFGS to implement
> Serializable.
>
> 2) Breeze computes redundant gradient and loss. See the following log
> from both Fortran and Breeze implementations.
>
> Thanks.
>
> Fortran:
> Iteration -1: loss 1.3862943611198926, diff 1.0
> Iteration 0: loss 1.5846343143210866, diff 0.14307193024217352
> Iteration 1: loss 1.1242501524477688, diff 0.29053004039012126
> Iteration 2: loss 1.0930151243303563, diff 0.027782962952189336
> Iteration 3: loss 1.054036932835569, diff 0.03566113127440601
> Iteration 4: loss 0.9907956302751622, diff 0.05999907649459571
> Iteration 5: loss 0.9184205380342829, diff 0.07304737423337761
> Iteration 6: loss 0.8259870936519937, diff 0.10064381175132982
> Iteration 7: loss 0.6327447552109574, diff 0.23395293458364716
> Iteration 8: loss 0.5534101162436359, diff 0.1253815427665277
> Iteration 9: loss 0.4045020086612566, diff 0.26907321376758075
> Iteration 10: loss 0.3078824990823728, diff 0.23885980452569627
>
> Breeze:
> Iteration -1: loss 1.3862943611198926, diff 1.0
> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> WARNING: Failed to load implementation from:
> com.github.fommil.netlib.NativeSystemBLAS
> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> WARNING: Failed to load implementation from:
> com.github.fommil.netlib.NativeRefBLAS
> Iteration 0: loss 1.3862943611198926, diff 0.0
> Iteration 1: loss 1.5846343143210866, diff 0.14307193024217352
> Iteration 2: loss 1.1242501524477688, diff 0.29053004039012126
> Iteration 3: loss 1.1242501524477688, diff 0.0
> Iteration 4: loss 1.1242501524477688, diff 0.0
> Iteration 5: loss 1.0930151243303563, diff 0.027782962952189336
> Iteration 6: loss 1.0930151243303563, diff 0.0
> Iteration 7: loss 1.0930151243303563, diff 0.0
> Iteration 8: loss 1.054036932835569, diff 0.03566113127440601
> Iteration 9: loss 1.054036932835569, diff 0.0
> Iteration 10: loss 1.054036932835569, diff 0.0
> Iteration 11: loss 0.9907956302751622, diff 0.05999907649459571
> Iteration 12: loss 0.9907956302751622, diff 0.0
> Iteration 13: loss 0.9907956302751622, diff 0.0
> Iteration 14: loss 0.9184205380342829, diff 0.07304737423337761
> Iteration 15: loss 0.9184205380342829, diff 0.0
> Iteration 16: loss 0.9184205380342829, diff 0.0
> Iteration 17: loss 0.8259870936519939, diff 0.1006438117513297
> Iteration 18: loss 0.8259870936519939, diff 0.0
> Iteration 19: loss 0.8259870936519939, diff 0.0
> Iteration 20: loss 0.6327447552109576, diff 0.233952934583647
> Iteration 21: loss 0.6327447552109576, diff 0.0
> Iteration 22: loss 0.6327447552109576, diff 0.0
> Iteration 23: loss 0.5534101162436362, diff 0.12538154276652747
> Iteration 24: loss 0.5534101162436362, diff 0.0
> Iteration 25: loss 0.5534101162436362, diff 0.0
> Iteration 26: loss 0.40450200866125635, diff 0.2690732137675816
> Iteration 27: loss 0.40450200866125635, diff 0.0
> Iteration 28: loss 0.40450200866125635, diff 0.0
> Iteration 29: loss 0.30788249908237314, diff 0.23885980452569502
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/
>
>
> On Wed, Mar 5, 2014 at 2:00 PM, David Hall <dl...@cs.berkeley.edu> wrote:
>> On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com> wrote:
>>
>>> Hi David,
>>>
>>> On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com> wrote:
>>> > I'm happy to help fix any problems. I've verified at points that the
>>> > implementation gives the exact same sequence of iterates for a few
>>> different
>>> > functions (with a particular line search) as the c port of lbfgs. So I'm
>>> a
>>> > little surprised it fails where Fortran succeeds... but only a little.
>>> This
>>> > was fixed late last year.
>>> I'm working on a reproducible test case using breeze vs fortran
>>> implementation to show the problem I've run into. The test will be in
>>> one of the test cases in my Spark fork, is it okay for you to
>>> investigate the issue? Or do I need to make it as a standalone test?
>>>
>>
>>
>> Um, as long as it wouldn't be too hard to pull out.
>>
>>
>>>
>>> Will send you the test later today.
>>>
>>> Thanks.
>>>
>>> Sincerely,
>>>
>>> DB Tsai
>>> Machine Learning Engineer
>>> Alpine Data Labs
>>> --------------------------------------
>>> Web: http://alpinenow.com/
>>>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
On Thu, Mar 6, 2014 at 4:26 PM, David Hall <dl...@cs.berkeley.edu> wrote:
> I'm not sure why Spark should be serializing LBFGS? Shouldn't it live on
> the controller node? Or is this a per-node thing?
>
> But no problem to make it serializable.
It will live in the controller node. Only RDD operations are per-node
thing. I'm calling RDD operations inside the DiffFunction, so Spark
should not serialize anything. But it seems that Spark serialize evey
parent objects; can Spark anyone confirm this?

> Err, yeah. I should probably have LBFGS do this automatically, but there's
> a CachedDiffFunction that gets rid of the redundant calculations.
It will nice to have LBFHS do this automatically. Just try
CachedDiffFunction, and it works.

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by David Hall <dl...@cs.berkeley.edu>.
On Thu, Mar 6, 2014 at 4:21 PM, DB Tsai <db...@alpinenow.com> wrote:

> Hi David,
>
> I can converge to the same result with your breeze LBFGS and Fortran
> implementations now. Probably, I made some mistakes when I tried
> breeze before. I apologize that I claimed it's not stable.
>
> See the test case in BreezeLBFGSSuite.scala
> https://github.com/AlpineNow/spark/tree/dbtsai-breezeLBFGS
>
> This is training multinomial logistic regression against iris dataset,
> and both optimizers can train the models with 98% training accuracy.
>

great to hear! There were some bugs in LBFGS about 6 months ago, so
depending on the last time you tried it, it might indeed have been bugged.


>
> There are two issues to use Breeze in Spark,
>
> 1) When the gradientSum and lossSum are computed distributively in
> custom defined DiffFunction which will be passed into your optimizer,
> Spark will complain LBFGS class is not serializable. In
> BreezeLBFGS.scala, I've to convert RDD to array to make it work
> locally. It should be easy to fix by just having LBFGS to implement
> Serializable.
>

I'm not sure why Spark should be serializing LBFGS? Shouldn't it live on
the controller node? Or is this a per-node thing?

But no problem to make it serializable.


>
> 2) Breeze computes redundant gradient and loss. See the following log
> from both Fortran and Breeze implementations.
>

Err, yeah. I should probably have LBFGS do this automatically, but there's
a CachedDiffFunction that gets rid of the redundant calculations.

-- David


>
> Thanks.
>
> Fortran:
> Iteration -1: loss 1.3862943611198926, diff 1.0
> Iteration 0: loss 1.5846343143210866, diff 0.14307193024217352
> Iteration 1: loss 1.1242501524477688, diff 0.29053004039012126
> Iteration 2: loss 1.0930151243303563, diff 0.027782962952189336
> Iteration 3: loss 1.054036932835569, diff 0.03566113127440601
> Iteration 4: loss 0.9907956302751622, diff 0.05999907649459571
> Iteration 5: loss 0.9184205380342829, diff 0.07304737423337761
> Iteration 6: loss 0.8259870936519937, diff 0.10064381175132982
> Iteration 7: loss 0.6327447552109574, diff 0.23395293458364716
> Iteration 8: loss 0.5534101162436359, diff 0.1253815427665277
> Iteration 9: loss 0.4045020086612566, diff 0.26907321376758075
> Iteration 10: loss 0.3078824990823728, diff 0.23885980452569627
>
> Breeze:
> Iteration -1: loss 1.3862943611198926, diff 1.0
> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> WARNING: Failed to load implementation from:
> com.github.fommil.netlib.NativeSystemBLAS
> Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
> WARNING: Failed to load implementation from:
> com.github.fommil.netlib.NativeRefBLAS
> Iteration 0: loss 1.3862943611198926, diff 0.0
> Iteration 1: loss 1.5846343143210866, diff 0.14307193024217352
> Iteration 2: loss 1.1242501524477688, diff 0.29053004039012126
> Iteration 3: loss 1.1242501524477688, diff 0.0
> Iteration 4: loss 1.1242501524477688, diff 0.0
> Iteration 5: loss 1.0930151243303563, diff 0.027782962952189336
> Iteration 6: loss 1.0930151243303563, diff 0.0
> Iteration 7: loss 1.0930151243303563, diff 0.0
> Iteration 8: loss 1.054036932835569, diff 0.03566113127440601
> Iteration 9: loss 1.054036932835569, diff 0.0
> Iteration 10: loss 1.054036932835569, diff 0.0
> Iteration 11: loss 0.9907956302751622, diff 0.05999907649459571
> Iteration 12: loss 0.9907956302751622, diff 0.0
> Iteration 13: loss 0.9907956302751622, diff 0.0
> Iteration 14: loss 0.9184205380342829, diff 0.07304737423337761
> Iteration 15: loss 0.9184205380342829, diff 0.0
> Iteration 16: loss 0.9184205380342829, diff 0.0
> Iteration 17: loss 0.8259870936519939, diff 0.1006438117513297
> Iteration 18: loss 0.8259870936519939, diff 0.0
> Iteration 19: loss 0.8259870936519939, diff 0.0
> Iteration 20: loss 0.6327447552109576, diff 0.233952934583647
> Iteration 21: loss 0.6327447552109576, diff 0.0
> Iteration 22: loss 0.6327447552109576, diff 0.0
> Iteration 23: loss 0.5534101162436362, diff 0.12538154276652747
> Iteration 24: loss 0.5534101162436362, diff 0.0
> Iteration 25: loss 0.5534101162436362, diff 0.0
> Iteration 26: loss 0.40450200866125635, diff 0.2690732137675816
> Iteration 27: loss 0.40450200866125635, diff 0.0
> Iteration 28: loss 0.40450200866125635, diff 0.0
> Iteration 29: loss 0.30788249908237314, diff 0.23885980452569502
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/
>
>
> On Wed, Mar 5, 2014 at 2:00 PM, David Hall <dl...@cs.berkeley.edu> wrote:
> > On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com> wrote:
> >
> >> Hi David,
> >>
> >> On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com> wrote:
> >> > I'm happy to help fix any problems. I've verified at points that the
> >> > implementation gives the exact same sequence of iterates for a few
> >> different
> >> > functions (with a particular line search) as the c port of lbfgs. So
> I'm
> >> a
> >> > little surprised it fails where Fortran succeeds... but only a little.
> >> This
> >> > was fixed late last year.
> >> I'm working on a reproducible test case using breeze vs fortran
> >> implementation to show the problem I've run into. The test will be in
> >> one of the test cases in my Spark fork, is it okay for you to
> >> investigate the issue? Or do I need to make it as a standalone test?
> >>
> >
> >
> > Um, as long as it wouldn't be too hard to pull out.
> >
> >
> >>
> >> Will send you the test later today.
> >>
> >> Thanks.
> >>
> >> Sincerely,
> >>
> >> DB Tsai
> >> Machine Learning Engineer
> >> Alpine Data Labs
> >> --------------------------------------
> >> Web: http://alpinenow.com/
> >>
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
Hi David,

I can converge to the same result with your breeze LBFGS and Fortran
implementations now. Probably, I made some mistakes when I tried
breeze before. I apologize that I claimed it's not stable.

See the test case in BreezeLBFGSSuite.scala
https://github.com/AlpineNow/spark/tree/dbtsai-breezeLBFGS

This is training multinomial logistic regression against iris dataset,
and both optimizers can train the models with 98% training accuracy.

There are two issues to use Breeze in Spark,

1) When the gradientSum and lossSum are computed distributively in
custom defined DiffFunction which will be passed into your optimizer,
Spark will complain LBFGS class is not serializable. In
BreezeLBFGS.scala, I've to convert RDD to array to make it work
locally. It should be easy to fix by just having LBFGS to implement
Serializable.

2) Breeze computes redundant gradient and loss. See the following log
from both Fortran and Breeze implementations.

Thanks.

Fortran:
Iteration -1: loss 1.3862943611198926, diff 1.0
Iteration 0: loss 1.5846343143210866, diff 0.14307193024217352
Iteration 1: loss 1.1242501524477688, diff 0.29053004039012126
Iteration 2: loss 1.0930151243303563, diff 0.027782962952189336
Iteration 3: loss 1.054036932835569, diff 0.03566113127440601
Iteration 4: loss 0.9907956302751622, diff 0.05999907649459571
Iteration 5: loss 0.9184205380342829, diff 0.07304737423337761
Iteration 6: loss 0.8259870936519937, diff 0.10064381175132982
Iteration 7: loss 0.6327447552109574, diff 0.23395293458364716
Iteration 8: loss 0.5534101162436359, diff 0.1253815427665277
Iteration 9: loss 0.4045020086612566, diff 0.26907321376758075
Iteration 10: loss 0.3078824990823728, diff 0.23885980452569627

Breeze:
Iteration -1: loss 1.3862943611198926, diff 1.0
Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
WARNING: Failed to load implementation from:
com.github.fommil.netlib.NativeSystemBLAS
Mar 6, 2014 3:59:11 PM com.github.fommil.netlib.BLAS <clinit>
WARNING: Failed to load implementation from:
com.github.fommil.netlib.NativeRefBLAS
Iteration 0: loss 1.3862943611198926, diff 0.0
Iteration 1: loss 1.5846343143210866, diff 0.14307193024217352
Iteration 2: loss 1.1242501524477688, diff 0.29053004039012126
Iteration 3: loss 1.1242501524477688, diff 0.0
Iteration 4: loss 1.1242501524477688, diff 0.0
Iteration 5: loss 1.0930151243303563, diff 0.027782962952189336
Iteration 6: loss 1.0930151243303563, diff 0.0
Iteration 7: loss 1.0930151243303563, diff 0.0
Iteration 8: loss 1.054036932835569, diff 0.03566113127440601
Iteration 9: loss 1.054036932835569, diff 0.0
Iteration 10: loss 1.054036932835569, diff 0.0
Iteration 11: loss 0.9907956302751622, diff 0.05999907649459571
Iteration 12: loss 0.9907956302751622, diff 0.0
Iteration 13: loss 0.9907956302751622, diff 0.0
Iteration 14: loss 0.9184205380342829, diff 0.07304737423337761
Iteration 15: loss 0.9184205380342829, diff 0.0
Iteration 16: loss 0.9184205380342829, diff 0.0
Iteration 17: loss 0.8259870936519939, diff 0.1006438117513297
Iteration 18: loss 0.8259870936519939, diff 0.0
Iteration 19: loss 0.8259870936519939, diff 0.0
Iteration 20: loss 0.6327447552109576, diff 0.233952934583647
Iteration 21: loss 0.6327447552109576, diff 0.0
Iteration 22: loss 0.6327447552109576, diff 0.0
Iteration 23: loss 0.5534101162436362, diff 0.12538154276652747
Iteration 24: loss 0.5534101162436362, diff 0.0
Iteration 25: loss 0.5534101162436362, diff 0.0
Iteration 26: loss 0.40450200866125635, diff 0.2690732137675816
Iteration 27: loss 0.40450200866125635, diff 0.0
Iteration 28: loss 0.40450200866125635, diff 0.0
Iteration 29: loss 0.30788249908237314, diff 0.23885980452569502

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/


On Wed, Mar 5, 2014 at 2:00 PM, David Hall <dl...@cs.berkeley.edu> wrote:
> On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com> wrote:
>
>> Hi David,
>>
>> On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com> wrote:
>> > I'm happy to help fix any problems. I've verified at points that the
>> > implementation gives the exact same sequence of iterates for a few
>> different
>> > functions (with a particular line search) as the c port of lbfgs. So I'm
>> a
>> > little surprised it fails where Fortran succeeds... but only a little.
>> This
>> > was fixed late last year.
>> I'm working on a reproducible test case using breeze vs fortran
>> implementation to show the problem I've run into. The test will be in
>> one of the test cases in my Spark fork, is it okay for you to
>> investigate the issue? Or do I need to make it as a standalone test?
>>
>
>
> Um, as long as it wouldn't be too hard to pull out.
>
>
>>
>> Will send you the test later today.
>>
>> Thanks.
>>
>> Sincerely,
>>
>> DB Tsai
>> Machine Learning Engineer
>> Alpine Data Labs
>> --------------------------------------
>> Web: http://alpinenow.com/
>>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by David Hall <dl...@cs.berkeley.edu>.
I did not. They would be nice to have.


On Wed, Mar 5, 2014 at 5:21 PM, Debasish Das <de...@gmail.com>wrote:

> David,
>
> There used to be standard BFGS testcases in Professor Nocedal's
> package...did you stress test the solver with them ?
>
> If not I will shoot him an email for them.
>
> Thanks.
> Deb
>
>
>
> On Wed, Mar 5, 2014 at 2:00 PM, David Hall <dl...@cs.berkeley.edu> wrote:
>
> > On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com> wrote:
> >
> > > Hi David,
> > >
> > > On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com> wrote:
> > > > I'm happy to help fix any problems. I've verified at points that the
> > > > implementation gives the exact same sequence of iterates for a few
> > > different
> > > > functions (with a particular line search) as the c port of lbfgs. So
> > I'm
> > > a
> > > > little surprised it fails where Fortran succeeds... but only a
> little.
> > > This
> > > > was fixed late last year.
> > > I'm working on a reproducible test case using breeze vs fortran
> > > implementation to show the problem I've run into. The test will be in
> > > one of the test cases in my Spark fork, is it okay for you to
> > > investigate the issue? Or do I need to make it as a standalone test?
> > >
> >
> >
> > Um, as long as it wouldn't be too hard to pull out.
> >
> >
> > >
> > > Will send you the test later today.
> > >
> > > Thanks.
> > >
> > > Sincerely,
> > >
> > > DB Tsai
> > > Machine Learning Engineer
> > > Alpine Data Labs
> > > --------------------------------------
> > > Web: http://alpinenow.com/
> > >
> >
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
David,

There used to be standard BFGS testcases in Professor Nocedal's
package...did you stress test the solver with them ?

If not I will shoot him an email for them.

Thanks.
Deb



On Wed, Mar 5, 2014 at 2:00 PM, David Hall <dl...@cs.berkeley.edu> wrote:

> On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com> wrote:
>
> > Hi David,
> >
> > On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com> wrote:
> > > I'm happy to help fix any problems. I've verified at points that the
> > > implementation gives the exact same sequence of iterates for a few
> > different
> > > functions (with a particular line search) as the c port of lbfgs. So
> I'm
> > a
> > > little surprised it fails where Fortran succeeds... but only a little.
> > This
> > > was fixed late last year.
> > I'm working on a reproducible test case using breeze vs fortran
> > implementation to show the problem I've run into. The test will be in
> > one of the test cases in my Spark fork, is it okay for you to
> > investigate the issue? Or do I need to make it as a standalone test?
> >
>
>
> Um, as long as it wouldn't be too hard to pull out.
>
>
> >
> > Will send you the test later today.
> >
> > Thanks.
> >
> > Sincerely,
> >
> > DB Tsai
> > Machine Learning Engineer
> > Alpine Data Labs
> > --------------------------------------
> > Web: http://alpinenow.com/
> >
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by David Hall <dl...@cs.berkeley.edu>.
On Wed, Mar 5, 2014 at 1:57 PM, DB Tsai <db...@alpinenow.com> wrote:

> Hi David,
>
> On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com> wrote:
> > I'm happy to help fix any problems. I've verified at points that the
> > implementation gives the exact same sequence of iterates for a few
> different
> > functions (with a particular line search) as the c port of lbfgs. So I'm
> a
> > little surprised it fails where Fortran succeeds... but only a little.
> This
> > was fixed late last year.
> I'm working on a reproducible test case using breeze vs fortran
> implementation to show the problem I've run into. The test will be in
> one of the test cases in my Spark fork, is it okay for you to
> investigate the issue? Or do I need to make it as a standalone test?
>


Um, as long as it wouldn't be too hard to pull out.


>
> Will send you the test later today.
>
> Thanks.
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
Hi David,

On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com> wrote:
> I'm happy to help fix any problems. I've verified at points that the
> implementation gives the exact same sequence of iterates for a few different
> functions (with a particular line search) as the c port of lbfgs. So I'm a
> little surprised it fails where Fortran succeeds... but only a little. This
> was fixed late last year.
I'm working on a reproducible test case using breeze vs fortran
implementation to show the problem I've run into. The test will be in
one of the test cases in my Spark fork, is it okay for you to
investigate the issue? Or do I need to make it as a standalone test?

Will send you the test later today.

Thanks.

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by David Hall <dl...@cs.berkeley.edu>.
On Wed, Mar 5, 2014 at 8:50 AM, Debasish Das <de...@gmail.com>wrote:

> Hi David,
>
> Few questions on breeze solvers:
>
> 1. I feel the right place of adding useful things from RISO LBFGS (based on
> Professor Nocedal's fortran code) will be breeze. It will involve stress
> testing breeze LBFGS on large sparse datasets and contributing fixes to
> existing breeze LBFGS with the learning from RISO LBFGS.
>
> You agree on that right ?
>

That would be great.

>
> 2. Normally for doing experiments like 1, I fix the line search. What's
> your preferred line search in breeze BFGS ? I will also use that.
>
> More Thuente and Strong wolfe with backtracking helped me in the past.
>

The default is a Strong Wolfe search:
https://github.com/scalanlp/breeze/blob/master/src/main/scala/breeze/optimize/StrongWolfe.scala


>
> 3. The paper that you sent also says on L-BFGS-B is better on box
> constraints. I feel It's worthwhile to have both the solvers because many
> practical problems need box constraints or complex constraints can be
> reformulated in the realm of unconstrained and box constraints.


> Example use-cases for me are automatic feature extraction from photo/video
> frames using factorization.
>
> I will compare L-BFGS-B vs constrained QN method that you have in Breeze
> within an analysis similar to 1.
>

Great. Yeah I fully expect l-bfgs-b to be better on box constraints. It
turns out that this other method looked easier to implement and gave
reasonably good results even with box constraints.


>
> 4. Do you have a road-map on adding CG solvers in breeze ? Linear CG solver
> to compare with BLAS posv seems like a good usecase for me in mllib ALS.
> DB sent a paper by Professor Ng which shows the effectiveness of CG and
> BFGS over SGD in the email chain.
>

We have a linear CG solver (
https://github.com/scalanlp/breeze/blob/master/src/main/scala/breeze/optimize/linear/ConjugateGradient.scala)
which is used in the Truncated Newton solver. (
https://github.com/scalanlp/breeze/blob/master/src/main/scala/breeze/optimize/TruncatedNewtonMinimizer.scala)
But I've not implemented nonlinear CG, and honestly hadn't planned on it,
per below.


>
> I believe on non-convex problems like Matrix Factorization, CG family might
> converge to a better solution than BFGS. No way to know till we experiment
> on the datasets :-)
>

I've never had good experience with CG, and a vision colleague of mine
found that LBFGS was better on his (non-convex) stuff, but I could be
easily persuaded.

Thanks!

-- David


>
> Thanks.
> Deb
>
>
>
> On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com> wrote:
>
> > Just subscribing to this list, so apologies for quoting weirdly and any
> > other
> > etiquette offenses.
> >
> >
> > DB Tsai wrote
> > > Hi Deb,
> > >
> > > I had tried breeze L-BFGS algorithm, and when I tried it couple weeks
> > > ago, it's not as stable as the fortran implementation. I guessed the
> > > problem is in the line search related thing. Since we may bring breeze
> > > dependency for the sparse format support as you pointed out, we can
> > > just try to fix the L-BFGS in breeze, and we can get OWL-QN and
> > > L-BFGS-B.
> > >
> > > What do you think?
> >
> > I'm happy to help fix any problems. I've verified at points that the
> > implementation gives the exact same sequence of iterates for a few
> > different
> > functions (with a particular line search) as the c port of lbfgs. So I'm
> a
> > little surprised it fails where Fortran succeeds... but only a little.
> This
> > was fixed late last year.
> >
> > OWL-QN seems to mostly be stable, but probably deserves more testing.
> > Presumably it has whatever defects my LBFGS does. (It's really pretty
> > straightforward to implement given an L-BFGS)
> >
> > We don't provide an L-BFGS-B implementation. We do have a more general
> > constrained qn method based on
> > http://jmlr.org/proceedings/papers/v5/schmidt09a/schmidt09a.pdf (which
> > uses
> > a L-BFGS type update as part of the algorithm). From the experiments in
> > their paper, it's likely to not work as well for bound constraints, but
> can
> > do things that lbfgsb can't.
> >
> > Again, let me know what I can help with.
> >
> > -- David Hall
> >
> >
> > On Mon, Mar 3, 2014 at 3:52 PM, DB Tsai &lt;dbtsai@&gt; wrote:
> > > Hi Deb,
> > >
> > >> a.  OWL-QN for solving L1 natively in BFGS
> > > Based on what I saw from
> > >
> >
> https://github.com/tjhunter/scalanlp-core/blob/master/learn/src/main/scala/breeze/optimize/OWLQN.scala
> > > , it seems that it's not difficult to implement OWL-QN once LBFGS is
> > > done.
> > >
> > >>
> > >> b.  Bound constraints in BFGS : I saw you have converted the fortran
> > >> code.
> > >> Is there a license issue ? I can help in getting that up to speed as
> > >> well.
> > > I tried to convert the code from Fortran L-BFGS-B implementation to
> > > java using f2j; the translated code is just a messy, and it just
> > > doesn't work at all. There is no license issue here. Any idea about
> > > how to approach this?
> > >
> > >> c. Few variants of line searches : I will discuss on it.
> > >> For the dbtsai-lbfgs branch seems like it already got merged by
> Jenkins.
> > > I don't think it's merged into master. Still have couple things needed
> > > to be cleaned up. Just open the PR to have public feedback.
> > >
> > >> Is this getting merged to the master or there will be revisions on it
> ?
> > >>
> > >> https://github.com/apache/spark/pull/53
> > >>
> > >> Thanks.
> > >> Deb
> > >
> > > Sincerely,
> > >
> > > DB Tsai
> > > Machine Learning Engineer
> > > Alpine Data Labs
> > > --------------------------------------
> > > Web: http://alpinenow.com/
> >
> >
> >
> >
> > --
> > View this message in context:
> >
> http://apache-spark-developers-list.1001551.n3.nabble.com/MLLib-Thoughts-about-refactoring-Updater-for-LBFGS-tp2493p3935.html
> > Sent from the Apache Spark Developers List mailing list archive at
> > Nabble.com.
> >
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
Hi David,

Few questions on breeze solvers:

1. I feel the right place of adding useful things from RISO LBFGS (based on
Professor Nocedal's fortran code) will be breeze. It will involve stress
testing breeze LBFGS on large sparse datasets and contributing fixes to
existing breeze LBFGS with the learning from RISO LBFGS.

You agree on that right ?

2. Normally for doing experiments like 1, I fix the line search. What's
your preferred line search in breeze BFGS ? I will also use that.

More Thuente and Strong wolfe with backtracking helped me in the past.

3. The paper that you sent also says on L-BFGS-B is better on box
constraints. I feel It's worthwhile to have both the solvers because many
practical problems need box constraints or complex constraints can be
reformulated in the realm of unconstrained and box constraints.

Example use-cases for me are automatic feature extraction from photo/video
frames using factorization.

I will compare L-BFGS-B vs constrained QN method that you have in Breeze
within an analysis similar to 1.

4. Do you have a road-map on adding CG solvers in breeze ? Linear CG solver
to compare with BLAS posv seems like a good usecase for me in mllib ALS.
DB sent a paper by Professor Ng which shows the effectiveness of CG and
BFGS over SGD in the email chain.

I believe on non-convex problems like Matrix Factorization, CG family might
converge to a better solution than BFGS. No way to know till we experiment
on the datasets :-)

Thanks.
Deb



On Tue, Mar 4, 2014 at 8:13 PM, dlwh <da...@gmail.com> wrote:

> Just subscribing to this list, so apologies for quoting weirdly and any
> other
> etiquette offenses.
>
>
> DB Tsai wrote
> > Hi Deb,
> >
> > I had tried breeze L-BFGS algorithm, and when I tried it couple weeks
> > ago, it's not as stable as the fortran implementation. I guessed the
> > problem is in the line search related thing. Since we may bring breeze
> > dependency for the sparse format support as you pointed out, we can
> > just try to fix the L-BFGS in breeze, and we can get OWL-QN and
> > L-BFGS-B.
> >
> > What do you think?
>
> I'm happy to help fix any problems. I've verified at points that the
> implementation gives the exact same sequence of iterates for a few
> different
> functions (with a particular line search) as the c port of lbfgs. So I'm a
> little surprised it fails where Fortran succeeds... but only a little. This
> was fixed late last year.
>
> OWL-QN seems to mostly be stable, but probably deserves more testing.
> Presumably it has whatever defects my LBFGS does. (It's really pretty
> straightforward to implement given an L-BFGS)
>
> We don't provide an L-BFGS-B implementation. We do have a more general
> constrained qn method based on
> http://jmlr.org/proceedings/papers/v5/schmidt09a/schmidt09a.pdf (which
> uses
> a L-BFGS type update as part of the algorithm). From the experiments in
> their paper, it's likely to not work as well for bound constraints, but can
> do things that lbfgsb can't.
>
> Again, let me know what I can help with.
>
> -- David Hall
>
>
> On Mon, Mar 3, 2014 at 3:52 PM, DB Tsai &lt;dbtsai@&gt; wrote:
> > Hi Deb,
> >
> >> a.  OWL-QN for solving L1 natively in BFGS
> > Based on what I saw from
> >
> https://github.com/tjhunter/scalanlp-core/blob/master/learn/src/main/scala/breeze/optimize/OWLQN.scala
> > , it seems that it's not difficult to implement OWL-QN once LBFGS is
> > done.
> >
> >>
> >> b.  Bound constraints in BFGS : I saw you have converted the fortran
> >> code.
> >> Is there a license issue ? I can help in getting that up to speed as
> >> well.
> > I tried to convert the code from Fortran L-BFGS-B implementation to
> > java using f2j; the translated code is just a messy, and it just
> > doesn't work at all. There is no license issue here. Any idea about
> > how to approach this?
> >
> >> c. Few variants of line searches : I will discuss on it.
> >> For the dbtsai-lbfgs branch seems like it already got merged by Jenkins.
> > I don't think it's merged into master. Still have couple things needed
> > to be cleaned up. Just open the PR to have public feedback.
> >
> >> Is this getting merged to the master or there will be revisions on it ?
> >>
> >> https://github.com/apache/spark/pull/53
> >>
> >> Thanks.
> >> Deb
> >
> > Sincerely,
> >
> > DB Tsai
> > Machine Learning Engineer
> > Alpine Data Labs
> > --------------------------------------
> > Web: http://alpinenow.com/
>
>
>
>
> --
> View this message in context:
> http://apache-spark-developers-list.1001551.n3.nabble.com/MLLib-Thoughts-about-refactoring-Updater-for-LBFGS-tp2493p3935.html
> Sent from the Apache Spark Developers List mailing list archive at
> Nabble.com.
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by dlwh <da...@gmail.com>.
Just subscribing to this list, so apologies for quoting weirdly and any other
etiquette offenses.


DB Tsai wrote
> Hi Deb,
> 
> I had tried breeze L-BFGS algorithm, and when I tried it couple weeks
> ago, it's not as stable as the fortran implementation. I guessed the
> problem is in the line search related thing. Since we may bring breeze
> dependency for the sparse format support as you pointed out, we can
> just try to fix the L-BFGS in breeze, and we can get OWL-QN and
> L-BFGS-B.
> 
> What do you think?

I'm happy to help fix any problems. I've verified at points that the
implementation gives the exact same sequence of iterates for a few different
functions (with a particular line search) as the c port of lbfgs. So I'm a
little surprised it fails where Fortran succeeds... but only a little. This
was fixed late last year.

OWL-QN seems to mostly be stable, but probably deserves more testing.
Presumably it has whatever defects my LBFGS does. (It's really pretty
straightforward to implement given an L-BFGS)

We don't provide an L-BFGS-B implementation. We do have a more general
constrained qn method based on
http://jmlr.org/proceedings/papers/v5/schmidt09a/schmidt09a.pdf (which uses
a L-BFGS type update as part of the algorithm). From the experiments in
their paper, it's likely to not work as well for bound constraints, but can
do things that lbfgsb can't.

Again, let me know what I can help with.

-- David Hall


On Mon, Mar 3, 2014 at 3:52 PM, DB Tsai &lt;dbtsai@&gt; wrote:
> Hi Deb,
>
>> a.  OWL-QN for solving L1 natively in BFGS
> Based on what I saw from
> https://github.com/tjhunter/scalanlp-core/blob/master/learn/src/main/scala/breeze/optimize/OWLQN.scala
> , it seems that it's not difficult to implement OWL-QN once LBFGS is
> done.
>
>>
>> b.  Bound constraints in BFGS : I saw you have converted the fortran
>> code.
>> Is there a license issue ? I can help in getting that up to speed as
>> well.
> I tried to convert the code from Fortran L-BFGS-B implementation to
> java using f2j; the translated code is just a messy, and it just
> doesn't work at all. There is no license issue here. Any idea about
> how to approach this?
>
>> c. Few variants of line searches : I will discuss on it.
>> For the dbtsai-lbfgs branch seems like it already got merged by Jenkins.
> I don't think it's merged into master. Still have couple things needed
> to be cleaned up. Just open the PR to have public feedback.
>
>> Is this getting merged to the master or there will be revisions on it ?
>>
>> https://github.com/apache/spark/pull/53
>>
>> Thanks.
>> Deb
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/




--
View this message in context: http://apache-spark-developers-list.1001551.n3.nabble.com/MLLib-Thoughts-about-refactoring-Updater-for-LBFGS-tp2493p3935.html
Sent from the Apache Spark Developers List mailing list archive at Nabble.com.

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
Hi Xiangrui,

It seems that Robert is busy recently. I setup the org.riso in
maven central for him, and I was waiting for his response for
a while without any news. So, I decided to maintain myself.

I'm more favor of using breeze for both sparse and optimization
core math library. When I tried L-BFGS in breeze with iris dataset
using multinomial logistic regression, it converged to NaN for unknown
reasons, while the Fortran one converged to the solution similar to Newton
method. For some datasets, the L-BFGS in breeze can converge to
correct solution.

We may talk to David and understand the implementation difference
between them.

I agree that we need to rework on the updater to make it to generic;
however, it may take a very long time to design it right. How about
we open another story for this? Once we finish this PR (either use
fortran or breeze implementation), and get it merge, let's have a design
discussion around this. It may be more effective since we can design a
architecture that have to work for both cases in the codebase, and will
be easier to think about the edge case for it.

Thanks.

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/


On Tue, Mar 4, 2014 at 9:53 AM, Xiangrui Meng <me...@gmail.com> wrote:
> Hi DB,
>
> I saw you released the L-BFGS code under com.dbtsai.lbfgs on maven
> central, so I assume that Robert (the author of RISO) is not going to
> maintain it. Is it correct?
>
> For the breeze implementation, do you mind sharing more details about
> the issues you have?
>
> I saw the hack you did to get regGrad in the PR. Though well
> documented, it still increases the code complexity. I agree with Evan
> that we should make the current implementation more general for first
> order updates. Maybe we should spend some time on this direction.
>
> Best,
> Xiangrui
>
> On Tue, Mar 4, 2014 at 7:25 AM, Debasish Das <de...@gmail.com> wrote:
>> Yeah we should move f2j L-BFGS and L-BFGS-B to breeze..they already have 2
>> line searches..also the OWL-QN outline...
>>
>> Hi Xiangrui,
>>
>> What's the plan on the PR ?
>> https://github.com/apache/incubator-spark/pull/575
>>
>> Will you add breeze as a dependency for the sparse support ?
>>
>> I looked at your branch
>> https://github.com/mengxr/incubator-spark/tree/sparse and the code is using
>> mahout wrapper.
>>
>> I can add a branch which updates GLM with breeze sparse matrices in case
>> you are fine with breeze license and other issues that we discussed on the
>> PR.
>>
>> Thanks.
>> Deb
>>
>>
>>
>> On Mon, Mar 3, 2014 at 10:47 PM, DB Tsai <db...@alpinenow.com> wrote:
>>
>>> Hi Deb,
>>>
>>> I had tried breeze L-BFGS algorithm, and when I tried it couple weeks
>>> ago, it's not as stable as the fortran implementation. I guessed the
>>> problem is in the line search related thing. Since we may bring breeze
>>> dependency for the sparse format support as you pointed out, we can
>>> just try to fix the L-BFGS in breeze, and we can get OWL-QN and
>>> L-BFGS-B.
>>>
>>> What do you think?
>>>
>>> Thanks.
>>>
>>> Sincerely,
>>>
>>> DB Tsai
>>> Machine Learning Engineer
>>> Alpine Data Labs
>>> --------------------------------------
>>> Web: http://alpinenow.com/
>>>
>>>
>>> On Mon, Mar 3, 2014 at 3:52 PM, DB Tsai <db...@alpinenow.com> wrote:
>>> > Hi Deb,
>>> >
>>> >> a.  OWL-QN for solving L1 natively in BFGS
>>> > Based on what I saw from
>>> >
>>> https://github.com/tjhunter/scalanlp-core/blob/master/learn/src/main/scala/breeze/optimize/OWLQN.scala
>>> > , it seems that it's not difficult to implement OWL-QN once LBFGS is
>>> > done.
>>> >
>>> >>
>>> >> b.  Bound constraints in BFGS : I saw you have converted the fortran
>>> code.
>>> >> Is there a license issue ? I can help in getting that up to speed as
>>> well.
>>> > I tried to convert the code from Fortran L-BFGS-B implementation to
>>> > java using f2j; the translated code is just a messy, and it just
>>> > doesn't work at all. There is no license issue here. Any idea about
>>> > how to approach this?
>>> >
>>> >> c. Few variants of line searches : I will discuss on it.
>>> >> For the dbtsai-lbfgs branch seems like it already got merged by Jenkins.
>>> > I don't think it's merged into master. Still have couple things needed
>>> > to be cleaned up. Just open the PR to have public feedback.
>>> >
>>> >> Is this getting merged to the master or there will be revisions on it ?
>>> >>
>>> >> https://github.com/apache/spark/pull/53
>>> >>
>>> >> Thanks.
>>> >> Deb
>>> >
>>> > Sincerely,
>>> >
>>> > DB Tsai
>>> > Machine Learning Engineer
>>> > Alpine Data Labs
>>> > --------------------------------------
>>> > Web: http://alpinenow.com/
>>>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Xiangrui Meng <me...@gmail.com>.
Hi DB,

I saw you released the L-BFGS code under com.dbtsai.lbfgs on maven
central, so I assume that Robert (the author of RISO) is not going to
maintain it. Is it correct?

For the breeze implementation, do you mind sharing more details about
the issues you have?

I saw the hack you did to get regGrad in the PR. Though well
documented, it still increases the code complexity. I agree with Evan
that we should make the current implementation more general for first
order updates. Maybe we should spend some time on this direction.

Best,
Xiangrui

On Tue, Mar 4, 2014 at 7:25 AM, Debasish Das <de...@gmail.com> wrote:
> Yeah we should move f2j L-BFGS and L-BFGS-B to breeze..they already have 2
> line searches..also the OWL-QN outline...
>
> Hi Xiangrui,
>
> What's the plan on the PR ?
> https://github.com/apache/incubator-spark/pull/575
>
> Will you add breeze as a dependency for the sparse support ?
>
> I looked at your branch
> https://github.com/mengxr/incubator-spark/tree/sparse and the code is using
> mahout wrapper.
>
> I can add a branch which updates GLM with breeze sparse matrices in case
> you are fine with breeze license and other issues that we discussed on the
> PR.
>
> Thanks.
> Deb
>
>
>
> On Mon, Mar 3, 2014 at 10:47 PM, DB Tsai <db...@alpinenow.com> wrote:
>
>> Hi Deb,
>>
>> I had tried breeze L-BFGS algorithm, and when I tried it couple weeks
>> ago, it's not as stable as the fortran implementation. I guessed the
>> problem is in the line search related thing. Since we may bring breeze
>> dependency for the sparse format support as you pointed out, we can
>> just try to fix the L-BFGS in breeze, and we can get OWL-QN and
>> L-BFGS-B.
>>
>> What do you think?
>>
>> Thanks.
>>
>> Sincerely,
>>
>> DB Tsai
>> Machine Learning Engineer
>> Alpine Data Labs
>> --------------------------------------
>> Web: http://alpinenow.com/
>>
>>
>> On Mon, Mar 3, 2014 at 3:52 PM, DB Tsai <db...@alpinenow.com> wrote:
>> > Hi Deb,
>> >
>> >> a.  OWL-QN for solving L1 natively in BFGS
>> > Based on what I saw from
>> >
>> https://github.com/tjhunter/scalanlp-core/blob/master/learn/src/main/scala/breeze/optimize/OWLQN.scala
>> > , it seems that it's not difficult to implement OWL-QN once LBFGS is
>> > done.
>> >
>> >>
>> >> b.  Bound constraints in BFGS : I saw you have converted the fortran
>> code.
>> >> Is there a license issue ? I can help in getting that up to speed as
>> well.
>> > I tried to convert the code from Fortran L-BFGS-B implementation to
>> > java using f2j; the translated code is just a messy, and it just
>> > doesn't work at all. There is no license issue here. Any idea about
>> > how to approach this?
>> >
>> >> c. Few variants of line searches : I will discuss on it.
>> >> For the dbtsai-lbfgs branch seems like it already got merged by Jenkins.
>> > I don't think it's merged into master. Still have couple things needed
>> > to be cleaned up. Just open the PR to have public feedback.
>> >
>> >> Is this getting merged to the master or there will be revisions on it ?
>> >>
>> >> https://github.com/apache/spark/pull/53
>> >>
>> >> Thanks.
>> >> Deb
>> >
>> > Sincerely,
>> >
>> > DB Tsai
>> > Machine Learning Engineer
>> > Alpine Data Labs
>> > --------------------------------------
>> > Web: http://alpinenow.com/
>>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Xiangrui Meng <me...@gmail.com>.
Hi Deb,

I've been working with David to add or enhance some features to breeze
to make its performance comparable to bare-bone implementations. I'm
going to update that PR this week with sparse support to KMeans. You
are certainly welcome to update the GLM part. Make sure you are using
the master branch (0.7-SNAPSHOT) of breeze and comparing the
performance as you go. Let's make a separate thread if you want to
discuss more. Thanks!

Best,
Xiangrui

On Tue, Mar 4, 2014 at 7:25 AM, Debasish Das <de...@gmail.com> wrote:
> Yeah we should move f2j L-BFGS and L-BFGS-B to breeze..they already have 2
> line searches..also the OWL-QN outline...
>
> Hi Xiangrui,
>
> What's the plan on the PR ?
> https://github.com/apache/incubator-spark/pull/575
>
> Will you add breeze as a dependency for the sparse support ?
>
> I looked at your branch
> https://github.com/mengxr/incubator-spark/tree/sparse and the code is using
> mahout wrapper.
>
> I can add a branch which updates GLM with breeze sparse matrices in case
> you are fine with breeze license and other issues that we discussed on the
> PR.
>
> Thanks.
> Deb
>
>
>
> On Mon, Mar 3, 2014 at 10:47 PM, DB Tsai <db...@alpinenow.com> wrote:
>
>> Hi Deb,
>>
>> I had tried breeze L-BFGS algorithm, and when I tried it couple weeks
>> ago, it's not as stable as the fortran implementation. I guessed the
>> problem is in the line search related thing. Since we may bring breeze
>> dependency for the sparse format support as you pointed out, we can
>> just try to fix the L-BFGS in breeze, and we can get OWL-QN and
>> L-BFGS-B.
>>
>> What do you think?
>>
>> Thanks.
>>
>> Sincerely,
>>
>> DB Tsai
>> Machine Learning Engineer
>> Alpine Data Labs
>> --------------------------------------
>> Web: http://alpinenow.com/
>>
>>
>> On Mon, Mar 3, 2014 at 3:52 PM, DB Tsai <db...@alpinenow.com> wrote:
>> > Hi Deb,
>> >
>> >> a.  OWL-QN for solving L1 natively in BFGS
>> > Based on what I saw from
>> >
>> https://github.com/tjhunter/scalanlp-core/blob/master/learn/src/main/scala/breeze/optimize/OWLQN.scala
>> > , it seems that it's not difficult to implement OWL-QN once LBFGS is
>> > done.
>> >
>> >>
>> >> b.  Bound constraints in BFGS : I saw you have converted the fortran
>> code.
>> >> Is there a license issue ? I can help in getting that up to speed as
>> well.
>> > I tried to convert the code from Fortran L-BFGS-B implementation to
>> > java using f2j; the translated code is just a messy, and it just
>> > doesn't work at all. There is no license issue here. Any idea about
>> > how to approach this?
>> >
>> >> c. Few variants of line searches : I will discuss on it.
>> >> For the dbtsai-lbfgs branch seems like it already got merged by Jenkins.
>> > I don't think it's merged into master. Still have couple things needed
>> > to be cleaned up. Just open the PR to have public feedback.
>> >
>> >> Is this getting merged to the master or there will be revisions on it ?
>> >>
>> >> https://github.com/apache/spark/pull/53
>> >>
>> >> Thanks.
>> >> Deb
>> >
>> > Sincerely,
>> >
>> > DB Tsai
>> > Machine Learning Engineer
>> > Alpine Data Labs
>> > --------------------------------------
>> > Web: http://alpinenow.com/
>>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
Yeah we should move f2j L-BFGS and L-BFGS-B to breeze..they already have 2
line searches..also the OWL-QN outline...

Hi Xiangrui,

What's the plan on the PR ?
https://github.com/apache/incubator-spark/pull/575

Will you add breeze as a dependency for the sparse support ?

I looked at your branch
https://github.com/mengxr/incubator-spark/tree/sparse and the code is using
mahout wrapper.

I can add a branch which updates GLM with breeze sparse matrices in case
you are fine with breeze license and other issues that we discussed on the
PR.

Thanks.
Deb



On Mon, Mar 3, 2014 at 10:47 PM, DB Tsai <db...@alpinenow.com> wrote:

> Hi Deb,
>
> I had tried breeze L-BFGS algorithm, and when I tried it couple weeks
> ago, it's not as stable as the fortran implementation. I guessed the
> problem is in the line search related thing. Since we may bring breeze
> dependency for the sparse format support as you pointed out, we can
> just try to fix the L-BFGS in breeze, and we can get OWL-QN and
> L-BFGS-B.
>
> What do you think?
>
> Thanks.
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/
>
>
> On Mon, Mar 3, 2014 at 3:52 PM, DB Tsai <db...@alpinenow.com> wrote:
> > Hi Deb,
> >
> >> a.  OWL-QN for solving L1 natively in BFGS
> > Based on what I saw from
> >
> https://github.com/tjhunter/scalanlp-core/blob/master/learn/src/main/scala/breeze/optimize/OWLQN.scala
> > , it seems that it's not difficult to implement OWL-QN once LBFGS is
> > done.
> >
> >>
> >> b.  Bound constraints in BFGS : I saw you have converted the fortran
> code.
> >> Is there a license issue ? I can help in getting that up to speed as
> well.
> > I tried to convert the code from Fortran L-BFGS-B implementation to
> > java using f2j; the translated code is just a messy, and it just
> > doesn't work at all. There is no license issue here. Any idea about
> > how to approach this?
> >
> >> c. Few variants of line searches : I will discuss on it.
> >> For the dbtsai-lbfgs branch seems like it already got merged by Jenkins.
> > I don't think it's merged into master. Still have couple things needed
> > to be cleaned up. Just open the PR to have public feedback.
> >
> >> Is this getting merged to the master or there will be revisions on it ?
> >>
> >> https://github.com/apache/spark/pull/53
> >>
> >> Thanks.
> >> Deb
> >
> > Sincerely,
> >
> > DB Tsai
> > Machine Learning Engineer
> > Alpine Data Labs
> > --------------------------------------
> > Web: http://alpinenow.com/
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
Hi Deb,

I had tried breeze L-BFGS algorithm, and when I tried it couple weeks
ago, it's not as stable as the fortran implementation. I guessed the
problem is in the line search related thing. Since we may bring breeze
dependency for the sparse format support as you pointed out, we can
just try to fix the L-BFGS in breeze, and we can get OWL-QN and
L-BFGS-B.

What do you think?

Thanks.

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/


On Mon, Mar 3, 2014 at 3:52 PM, DB Tsai <db...@alpinenow.com> wrote:
> Hi Deb,
>
>> a.  OWL-QN for solving L1 natively in BFGS
> Based on what I saw from
> https://github.com/tjhunter/scalanlp-core/blob/master/learn/src/main/scala/breeze/optimize/OWLQN.scala
> , it seems that it's not difficult to implement OWL-QN once LBFGS is
> done.
>
>>
>> b.  Bound constraints in BFGS : I saw you have converted the fortran code.
>> Is there a license issue ? I can help in getting that up to speed as well.
> I tried to convert the code from Fortran L-BFGS-B implementation to
> java using f2j; the translated code is just a messy, and it just
> doesn't work at all. There is no license issue here. Any idea about
> how to approach this?
>
>> c. Few variants of line searches : I will discuss on it.
>> For the dbtsai-lbfgs branch seems like it already got merged by Jenkins.
> I don't think it's merged into master. Still have couple things needed
> to be cleaned up. Just open the PR to have public feedback.
>
>> Is this getting merged to the master or there will be revisions on it ?
>>
>> https://github.com/apache/spark/pull/53
>>
>> Thanks.
>> Deb
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
Hi Deb,

> a.  OWL-QN for solving L1 natively in BFGS
Based on what I saw from
https://github.com/tjhunter/scalanlp-core/blob/master/learn/src/main/scala/breeze/optimize/OWLQN.scala
, it seems that it's not difficult to implement OWL-QN once LBFGS is
done.

>
> b.  Bound constraints in BFGS : I saw you have converted the fortran code.
> Is there a license issue ? I can help in getting that up to speed as well.
I tried to convert the code from Fortran L-BFGS-B implementation to
java using f2j; the translated code is just a messy, and it just
doesn't work at all. There is no license issue here. Any idea about
how to approach this?

> c. Few variants of line searches : I will discuss on it.
> For the dbtsai-lbfgs branch seems like it already got merged by Jenkins.
I don't think it's merged into master. Still have couple things needed
to be cleaned up. Just open the PR to have public feedback.

> Is this getting merged to the master or there will be revisions on it ?
>
> https://github.com/apache/spark/pull/53
>
> Thanks.
> Deb

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
Hi DB,

I have forked the LBFGS repo. The features that I want in it are the
following:

a.  OWL-QN for solving L1 natively in BFGS

b.  Bound constraints in BFGS : I saw you have converted the fortran code.
Is there a license issue ? I can help in getting that up to speed as well.

c. Few variants of line searches : I will discuss on it.
For the dbtsai-lbfgs branch seems like it already got merged by Jenkins.

Is this getting merged to the master or there will be revisions on it ?

https://github.com/apache/spark/pull/53

Thanks.
Deb

On Mon, Mar 3, 2014 at 2:29 PM, DB Tsai <db...@alpinenow.com> wrote:

> Hi Deb,
>
> 1) The LBFGS code I published to maven central is here,
> https://github.com/dbtsai/lbfgs  You can fork it, and publish it
> locally so that mllib can use it. I also want to add orthant wise for
> L1, so we can work together to make it happen.
>
> I think ideally, we can rewrite it in scala, and move the optimizer to
> spark codebase. But I don't know how easy it is to write a very robust
> lbfgs.
>
> 2) I think the most easy way is just fork
> https://github.com/AlpineNow/spark/, and checkout dbtsai-lbfgs branch.
>
> We also need sparse support as well. Do we have good infrastructure
> around this?
>
> Thanks.
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/
>
>
> On Sun, Mar 2, 2014 at 10:23 AM, Debasish Das <de...@gmail.com>
> wrote:
> > Hi DB,
> >
> > 1. Could you point to the BFGS repositories used to publish artifacts to
> > maven central ? What's the best way to add changes to it ? I fork the
> repo
> > at my github ? Basically as I mentioned before I need to add lbfgs-b,
> > orthant wise for L1 handling and few variants of line search to lbfgs...
> >
> > 2. For the spark pull request, what's the best way to get your branch
> > dbtsai-lbfgs ?
> >
> > On my github spark mirror I can make a branch called debasish-lbfgs and
> > merge your code to it ?
> >
> > I need sparse support to the logistic regression classifier using lbfgs
> > solve and therefore I will need Xiangrui's branch as well...
> >
> > https://github.com/apache/incubator-spark/pull/575
> >
> > Thanks.
> > Deb
> >
> >
> >
> >
> >
> >
> >
> > On Sun, Mar 2, 2014 at 12:14 AM, DB Tsai <db...@alpinenow.com> wrote:
> >
> >> Hi Deb,
> >>
> >> The PR is here
> >> https://github.com/apache/spark/pull/53
> >>
> >> Hi Evan,
> >>
> >> I think we need to refactor the optimization methods and also the way
> >> we write algorithms. For example, if I want to use the new
> >> optimization method in  LogisticRegression.scala, I need to implement
> >> LogisticRegressionWithLBFGS class and object which are mostly
> >> identical to LogisticRegressionWithSGD. I'll open a JIRA for this.
> >>
> >> I just submit the LBFGS PR https://github.com/apache/spark/pull/53 ,
> >> and it depends on a bug fix in another PR
> >> https://github.com/apache/spark/pull/40
> >>
> >> Any comment and feedback is welcome.
> >>
> >> Thanks.
> >>
> >> Sincerely,
> >>
> >> DB Tsai
> >> Machine Learning Engineer
> >> Alpine Data Labs
> >> --------------------------------------
> >> Web: http://alpinenow.com/
> >>
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
Hi Deb,

1) The LBFGS code I published to maven central is here,
https://github.com/dbtsai/lbfgs  You can fork it, and publish it
locally so that mllib can use it. I also want to add orthant wise for
L1, so we can work together to make it happen.

I think ideally, we can rewrite it in scala, and move the optimizer to
spark codebase. But I don't know how easy it is to write a very robust
lbfgs.

2) I think the most easy way is just fork
https://github.com/AlpineNow/spark/, and checkout dbtsai-lbfgs branch.

We also need sparse support as well. Do we have good infrastructure
around this?

Thanks.

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/


On Sun, Mar 2, 2014 at 10:23 AM, Debasish Das <de...@gmail.com> wrote:
> Hi DB,
>
> 1. Could you point to the BFGS repositories used to publish artifacts to
> maven central ? What's the best way to add changes to it ? I fork the repo
> at my github ? Basically as I mentioned before I need to add lbfgs-b,
> orthant wise for L1 handling and few variants of line search to lbfgs...
>
> 2. For the spark pull request, what's the best way to get your branch
> dbtsai-lbfgs ?
>
> On my github spark mirror I can make a branch called debasish-lbfgs and
> merge your code to it ?
>
> I need sparse support to the logistic regression classifier using lbfgs
> solve and therefore I will need Xiangrui's branch as well...
>
> https://github.com/apache/incubator-spark/pull/575
>
> Thanks.
> Deb
>
>
>
>
>
>
>
> On Sun, Mar 2, 2014 at 12:14 AM, DB Tsai <db...@alpinenow.com> wrote:
>
>> Hi Deb,
>>
>> The PR is here
>> https://github.com/apache/spark/pull/53
>>
>> Hi Evan,
>>
>> I think we need to refactor the optimization methods and also the way
>> we write algorithms. For example, if I want to use the new
>> optimization method in  LogisticRegression.scala, I need to implement
>> LogisticRegressionWithLBFGS class and object which are mostly
>> identical to LogisticRegressionWithSGD. I'll open a JIRA for this.
>>
>> I just submit the LBFGS PR https://github.com/apache/spark/pull/53 ,
>> and it depends on a bug fix in another PR
>> https://github.com/apache/spark/pull/40
>>
>> Any comment and feedback is welcome.
>>
>> Thanks.
>>
>> Sincerely,
>>
>> DB Tsai
>> Machine Learning Engineer
>> Alpine Data Labs
>> --------------------------------------
>> Web: http://alpinenow.com/
>>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
Hi DB,

1. Could you point to the BFGS repositories used to publish artifacts to
maven central ? What's the best way to add changes to it ? I fork the repo
at my github ? Basically as I mentioned before I need to add lbfgs-b,
orthant wise for L1 handling and few variants of line search to lbfgs...

2. For the spark pull request, what's the best way to get your branch
dbtsai-lbfgs ?

On my github spark mirror I can make a branch called debasish-lbfgs and
merge your code to it ?

I need sparse support to the logistic regression classifier using lbfgs
solve and therefore I will need Xiangrui's branch as well...

https://github.com/apache/incubator-spark/pull/575

Thanks.
Deb







On Sun, Mar 2, 2014 at 12:14 AM, DB Tsai <db...@alpinenow.com> wrote:

> Hi Deb,
>
> The PR is here
> https://github.com/apache/spark/pull/53
>
> Hi Evan,
>
> I think we need to refactor the optimization methods and also the way
> we write algorithms. For example, if I want to use the new
> optimization method in  LogisticRegression.scala, I need to implement
> LogisticRegressionWithLBFGS class and object which are mostly
> identical to LogisticRegressionWithSGD. I'll open a JIRA for this.
>
> I just submit the LBFGS PR https://github.com/apache/spark/pull/53 ,
> and it depends on a bug fix in another PR
> https://github.com/apache/spark/pull/40
>
> Any comment and feedback is welcome.
>
> Thanks.
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
Hi Deb,

The PR is here
https://github.com/apache/spark/pull/53

Hi Evan,

I think we need to refactor the optimization methods and also the way
we write algorithms. For example, if I want to use the new
optimization method in  LogisticRegression.scala, I need to implement
LogisticRegressionWithLBFGS class and object which are mostly
identical to LogisticRegressionWithSGD. I'll open a JIRA for this.

I just submit the LBFGS PR https://github.com/apache/spark/pull/53 ,
and it depends on a bug fix in another PR
https://github.com/apache/spark/pull/40

Any comment and feedback is welcome.

Thanks.

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by "Evan R. Sparks" <ev...@gmail.com>.
Hi everyone,

Sorry I'm late to the thread here, but I want to point out a few things.
This is, of course, a most welcome contribution and it will be immediately
useful to everything currently using the stochastic gradient optimizers!

1) I'm all for refactoring the optimization methods to make them a little
more general - Perhaps there should be a "FirstOrderUpdater" that
subclasses updater which takes things like stepsize as paramters, but still
has an "compute" method. While the updater APIs are public, I'd be
surprised if anyone is using them directly, instead, I'd expect most people
to be using the APIs that rely on them (namely the SVM, Logistic, and
Linear regression classes). It should *definitely* be possible to keep the
loss function we're minimizing separate from the optimization method.

2) That said - LBFGS *does* rely on being able to take gradients of the
loss function, and is a gradient based method.

3) On that note, in your branch, the access pattern (and code pattern) for
L-BFGS is basically identical to the code for minibatchSGD - I may be
missing something, but we really should try to factor out the parts that
are the same and avoid duplicating this logic. I *think* coming up with an
LBFGSUpdater with an appropriate compute method is all we need
(particularly since we're keeping track of the loss history), but I might
be wrong here.

4) In general, I think we should think about incurring technical debt
through duplicated (in functionality) code in the codebase (e.g. yet
another Vector sum/multiply class) and code written in languages other than
Scala in MLlib - the fortran/C++ implementations of L-BFGS aren't doing
anything magical, and as long as we can get similar performance it will be
much easier to maintain if everything is in Scala (with some critical bits
in other languages - but I don't think this falls into that case).
Additionally, we should think about whether we really need these additional
dependencies. While I'm sure Mallet is great, I'm a little worried that
adding it as a dependency for one or two functions we could pretty easily
reimplement might be a little heavy and present problems in the future.

Anyway, you should submit a PR and we can work on it!

- Evan




On Tue, Feb 25, 2014 at 5:52 PM, Debasish Das <de...@gmail.com>wrote:

> Hi DB,
>
> Could you please point me to your spark PR ?
>
> Thanks.
> Deb
>
>
> On Tue, Feb 25, 2014 at 5:03 PM, DB Tsai <db...@alpinenow.com> wrote:
>
> > Hi Deb, Xiangrui
> >
> > I just moved the LBFGS code to maven central, and cleaned up the code
> > a little bit.
> >
> > https://github.com/AlpineNow/incubator-spark/commits/dbtsai-LBFGS
> >
> > After looking at Mallet, the api is pretty simple, and it's probably
> > can be easily tested
> > based on my PR.
> >
> > It will be tricky to just benchmark the time of optimizers by
> > excluding the parallel gradientSum
> > and lossSum computation, and I don't have good approach yet. Let's
> > compare the accuracy for the time being.
> >
> > Thanks.
> >
> > Sincerely,
> >
> > DB Tsai
> > Machine Learning Engineer
> > Alpine Data Labs
> > --------------------------------------
> > Web: http://alpinenow.com/
> >
> >
> > On Tue, Feb 25, 2014 at 12:07 PM, Debasish Das <debasish.das83@gmail.com
> >
> > wrote:
> > > Hi DB,
> > >
> > > I am considering building on your PR and add Mallet as the dependency
> so
> > > that we can run some basic comparisons test on large scale sparse
> > datasets
> > > that I have.
> > >
> > > In the meantime, let's discuss if there are other optimization packages
> > > that we should try.
> > >
> > > My wishlist has bounded bfgs as well and I will add it to the PR.
> > >
> > > About the PR getting merged to mllib, we can plan that later.
> > >
> > > Thanks.
> > > Deb
> > >
> > >
> > >
> > > On Tue, Feb 25, 2014 at 11:36 AM, DB Tsai <db...@alpinenow.com>
> wrote:
> > >
> > >> I find some comparison between Mallet vs Fortran version. The result
> > >> is closed but not the same.
> > >>
> > >>
> >
> http://t3827.ai-mallet-development.aitalk.info/help-with-l-bfgs-t3827.html
> > >>
> > >> Here is LBFGS-B
> > >> Cost: 0.6902411220175793
> > >> Gradient: -5.453609E-007, -2.858372E-008, -1.369706E-007
> > >> Theta: -0.014186210102171406, -0.303521206706629,
> -0.018132348904129902
> > >>
> > >> And Mallet LBFGS (Tollerance .000000000000001)
> > >> Cost: 0.6902412268833071
> > >> Gradient: 0.000117, -4.615523E-005, 0.000114
> > >> Theta: -0.013914961040040107, -0.30419883021414335,
> > -0.016838481937958744
> > >>
> > >> So this shows me, that Mallet is close, but Plain ol Gradient Descent
> > >> and LBFGS-B are really close.
> > >> I see that Mallet also has a "LineOptimizer" and "Evaluator" that I
> > >> have yet to explore...
> > >>
> > >> Sincerely,
> > >>
> > >> DB Tsai
> > >> Machine Learning Engineer
> > >> Alpine Data Labs
> > >> --------------------------------------
> > >> Web: http://alpinenow.com/
> > >>
> > >>
> > >> On Tue, Feb 25, 2014 at 11:16 AM, DB Tsai <db...@alpinenow.com>
> wrote:
> > >> > Hi Deb,
> > >> >
> > >> > On Tue, Feb 25, 2014 at 7:07 AM, Debasish Das <
> > debasish.das83@gmail.com>
> > >> wrote:
> > >> >> Continuation on last email sent by mistake:
> > >> >>
> > >> >> Is cpl license is compatible with apache ?
> > >> >>
> > >> >> http://opensource.org/licenses/cpl1.0.php
> > >> >
> > >> > Based on what I read here, there is no problem to include CPL code
> in
> > >> > apache project
> > >> > as long as the code isn't modified, and we include the maven binary.
> > >> > https://www.apache.org/legal/3party.html
> > >> >
> > >> >> Mallet jars are available on maven. They have hessian based solvers
> > >> which
> > >> >> looked interesting along with bfgs and cg.
> > >> >
> > >> > We found that hessian based solvers don't scale as the # of features
> > >> grow, and
> > >> > we have lots of customers trying to train sparse input. That's our
> > >> motivation to
> > >> > work on L-BFGS which approximate hessian using just a few vectors.
> > >> >
> > >> > Just take a look at MALLET, and it does have L-BFGS and its variant
> > >> OWL-QN
> > >> > which can tackle L1 problem. Since implementing L-BFGS is very
> > subtle, I
> > >> don't
> > >> > know the quality of the mallet implementation. Personally, I
> > >> > implemented one based
> > >> > on textbook, and not very stable. If MALLET is robust, I'll go for
> it
> > >> > since it has more
> > >> > features, and already in maven.
> > >> >
> > >> >> Note that right now the version is not blas optimized. With jblas
> or
> > >> >> netlib-java discussions that's going on it can be improved. Also it
> > >> runs on
> > >> >> a single thread which can be improved...so there is scope for
> further
> > >> >> improvements in the code.
> > >> >
> > >> > I think it will not impact performance even it's not blas optimized
> > >> > nor multi-threaded,
> > >> > since most of the parallelization is in computing gradientSum and
> > >> > lossSum in Spark,
> > >> > and the optimizer just takes gradientSum, lossSum, and weights to
> get
> > >> > the newWeights.
> > >> >
> > >> > As a result, 99.9% of time is in computing gradientSum and lossSum.
> > >> > Only small amount
> > >> > of time is in optimization.
> > >> >
> > >> >>
> > >> >> Basically Xiangrui, is there a push back on making optimizers part
> of
> > >> spark
> > >> >> mllib ? I am exploring cg and qp solvers for spark mllib as well
> and
> > I
> > >> am
> > >> >> developing these as part of mllib optimization. I was hoping we
> > should
> > >> be
> > >> >> able to publish mllib as a maven artifact later.
> > >> >>
> > >> >> Thanks.
> > >> >> Deb
> > >> >
> > >> > Thanks.
> > >> >
> > >> > Sincerely,
> > >> >
> > >> > DB Tsai
> > >> > Machine Learning Engineer
> > >> > Alpine Data Labs
> > >> > --------------------------------------
> > >> > Web: http://alpinenow.com/
> > >>
> >
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
Hi DB,

Could you please point me to your spark PR ?

Thanks.
Deb


On Tue, Feb 25, 2014 at 5:03 PM, DB Tsai <db...@alpinenow.com> wrote:

> Hi Deb, Xiangrui
>
> I just moved the LBFGS code to maven central, and cleaned up the code
> a little bit.
>
> https://github.com/AlpineNow/incubator-spark/commits/dbtsai-LBFGS
>
> After looking at Mallet, the api is pretty simple, and it's probably
> can be easily tested
> based on my PR.
>
> It will be tricky to just benchmark the time of optimizers by
> excluding the parallel gradientSum
> and lossSum computation, and I don't have good approach yet. Let's
> compare the accuracy for the time being.
>
> Thanks.
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/
>
>
> On Tue, Feb 25, 2014 at 12:07 PM, Debasish Das <de...@gmail.com>
> wrote:
> > Hi DB,
> >
> > I am considering building on your PR and add Mallet as the dependency so
> > that we can run some basic comparisons test on large scale sparse
> datasets
> > that I have.
> >
> > In the meantime, let's discuss if there are other optimization packages
> > that we should try.
> >
> > My wishlist has bounded bfgs as well and I will add it to the PR.
> >
> > About the PR getting merged to mllib, we can plan that later.
> >
> > Thanks.
> > Deb
> >
> >
> >
> > On Tue, Feb 25, 2014 at 11:36 AM, DB Tsai <db...@alpinenow.com> wrote:
> >
> >> I find some comparison between Mallet vs Fortran version. The result
> >> is closed but not the same.
> >>
> >>
> http://t3827.ai-mallet-development.aitalk.info/help-with-l-bfgs-t3827.html
> >>
> >> Here is LBFGS-B
> >> Cost: 0.6902411220175793
> >> Gradient: -5.453609E-007, -2.858372E-008, -1.369706E-007
> >> Theta: -0.014186210102171406, -0.303521206706629, -0.018132348904129902
> >>
> >> And Mallet LBFGS (Tollerance .000000000000001)
> >> Cost: 0.6902412268833071
> >> Gradient: 0.000117, -4.615523E-005, 0.000114
> >> Theta: -0.013914961040040107, -0.30419883021414335,
> -0.016838481937958744
> >>
> >> So this shows me, that Mallet is close, but Plain ol Gradient Descent
> >> and LBFGS-B are really close.
> >> I see that Mallet also has a "LineOptimizer" and "Evaluator" that I
> >> have yet to explore...
> >>
> >> Sincerely,
> >>
> >> DB Tsai
> >> Machine Learning Engineer
> >> Alpine Data Labs
> >> --------------------------------------
> >> Web: http://alpinenow.com/
> >>
> >>
> >> On Tue, Feb 25, 2014 at 11:16 AM, DB Tsai <db...@alpinenow.com> wrote:
> >> > Hi Deb,
> >> >
> >> > On Tue, Feb 25, 2014 at 7:07 AM, Debasish Das <
> debasish.das83@gmail.com>
> >> wrote:
> >> >> Continuation on last email sent by mistake:
> >> >>
> >> >> Is cpl license is compatible with apache ?
> >> >>
> >> >> http://opensource.org/licenses/cpl1.0.php
> >> >
> >> > Based on what I read here, there is no problem to include CPL code in
> >> > apache project
> >> > as long as the code isn't modified, and we include the maven binary.
> >> > https://www.apache.org/legal/3party.html
> >> >
> >> >> Mallet jars are available on maven. They have hessian based solvers
> >> which
> >> >> looked interesting along with bfgs and cg.
> >> >
> >> > We found that hessian based solvers don't scale as the # of features
> >> grow, and
> >> > we have lots of customers trying to train sparse input. That's our
> >> motivation to
> >> > work on L-BFGS which approximate hessian using just a few vectors.
> >> >
> >> > Just take a look at MALLET, and it does have L-BFGS and its variant
> >> OWL-QN
> >> > which can tackle L1 problem. Since implementing L-BFGS is very
> subtle, I
> >> don't
> >> > know the quality of the mallet implementation. Personally, I
> >> > implemented one based
> >> > on textbook, and not very stable. If MALLET is robust, I'll go for it
> >> > since it has more
> >> > features, and already in maven.
> >> >
> >> >> Note that right now the version is not blas optimized. With jblas or
> >> >> netlib-java discussions that's going on it can be improved. Also it
> >> runs on
> >> >> a single thread which can be improved...so there is scope for further
> >> >> improvements in the code.
> >> >
> >> > I think it will not impact performance even it's not blas optimized
> >> > nor multi-threaded,
> >> > since most of the parallelization is in computing gradientSum and
> >> > lossSum in Spark,
> >> > and the optimizer just takes gradientSum, lossSum, and weights to get
> >> > the newWeights.
> >> >
> >> > As a result, 99.9% of time is in computing gradientSum and lossSum.
> >> > Only small amount
> >> > of time is in optimization.
> >> >
> >> >>
> >> >> Basically Xiangrui, is there a push back on making optimizers part of
> >> spark
> >> >> mllib ? I am exploring cg and qp solvers for spark mllib as well and
> I
> >> am
> >> >> developing these as part of mllib optimization. I was hoping we
> should
> >> be
> >> >> able to publish mllib as a maven artifact later.
> >> >>
> >> >> Thanks.
> >> >> Deb
> >> >
> >> > Thanks.
> >> >
> >> > Sincerely,
> >> >
> >> > DB Tsai
> >> > Machine Learning Engineer
> >> > Alpine Data Labs
> >> > --------------------------------------
> >> > Web: http://alpinenow.com/
> >>
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
Hi Deb, Xiangrui

I just moved the LBFGS code to maven central, and cleaned up the code
a little bit.

https://github.com/AlpineNow/incubator-spark/commits/dbtsai-LBFGS

After looking at Mallet, the api is pretty simple, and it's probably
can be easily tested
based on my PR.

It will be tricky to just benchmark the time of optimizers by
excluding the parallel gradientSum
and lossSum computation, and I don't have good approach yet. Let's
compare the accuracy for the time being.

Thanks.

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/


On Tue, Feb 25, 2014 at 12:07 PM, Debasish Das <de...@gmail.com> wrote:
> Hi DB,
>
> I am considering building on your PR and add Mallet as the dependency so
> that we can run some basic comparisons test on large scale sparse datasets
> that I have.
>
> In the meantime, let's discuss if there are other optimization packages
> that we should try.
>
> My wishlist has bounded bfgs as well and I will add it to the PR.
>
> About the PR getting merged to mllib, we can plan that later.
>
> Thanks.
> Deb
>
>
>
> On Tue, Feb 25, 2014 at 11:36 AM, DB Tsai <db...@alpinenow.com> wrote:
>
>> I find some comparison between Mallet vs Fortran version. The result
>> is closed but not the same.
>>
>> http://t3827.ai-mallet-development.aitalk.info/help-with-l-bfgs-t3827.html
>>
>> Here is LBFGS-B
>> Cost: 0.6902411220175793
>> Gradient: -5.453609E-007, -2.858372E-008, -1.369706E-007
>> Theta: -0.014186210102171406, -0.303521206706629, -0.018132348904129902
>>
>> And Mallet LBFGS (Tollerance .000000000000001)
>> Cost: 0.6902412268833071
>> Gradient: 0.000117, -4.615523E-005, 0.000114
>> Theta: -0.013914961040040107, -0.30419883021414335, -0.016838481937958744
>>
>> So this shows me, that Mallet is close, but Plain ol Gradient Descent
>> and LBFGS-B are really close.
>> I see that Mallet also has a "LineOptimizer" and "Evaluator" that I
>> have yet to explore...
>>
>> Sincerely,
>>
>> DB Tsai
>> Machine Learning Engineer
>> Alpine Data Labs
>> --------------------------------------
>> Web: http://alpinenow.com/
>>
>>
>> On Tue, Feb 25, 2014 at 11:16 AM, DB Tsai <db...@alpinenow.com> wrote:
>> > Hi Deb,
>> >
>> > On Tue, Feb 25, 2014 at 7:07 AM, Debasish Das <de...@gmail.com>
>> wrote:
>> >> Continuation on last email sent by mistake:
>> >>
>> >> Is cpl license is compatible with apache ?
>> >>
>> >> http://opensource.org/licenses/cpl1.0.php
>> >
>> > Based on what I read here, there is no problem to include CPL code in
>> > apache project
>> > as long as the code isn't modified, and we include the maven binary.
>> > https://www.apache.org/legal/3party.html
>> >
>> >> Mallet jars are available on maven. They have hessian based solvers
>> which
>> >> looked interesting along with bfgs and cg.
>> >
>> > We found that hessian based solvers don't scale as the # of features
>> grow, and
>> > we have lots of customers trying to train sparse input. That's our
>> motivation to
>> > work on L-BFGS which approximate hessian using just a few vectors.
>> >
>> > Just take a look at MALLET, and it does have L-BFGS and its variant
>> OWL-QN
>> > which can tackle L1 problem. Since implementing L-BFGS is very subtle, I
>> don't
>> > know the quality of the mallet implementation. Personally, I
>> > implemented one based
>> > on textbook, and not very stable. If MALLET is robust, I'll go for it
>> > since it has more
>> > features, and already in maven.
>> >
>> >> Note that right now the version is not blas optimized. With jblas or
>> >> netlib-java discussions that's going on it can be improved. Also it
>> runs on
>> >> a single thread which can be improved...so there is scope for further
>> >> improvements in the code.
>> >
>> > I think it will not impact performance even it's not blas optimized
>> > nor multi-threaded,
>> > since most of the parallelization is in computing gradientSum and
>> > lossSum in Spark,
>> > and the optimizer just takes gradientSum, lossSum, and weights to get
>> > the newWeights.
>> >
>> > As a result, 99.9% of time is in computing gradientSum and lossSum.
>> > Only small amount
>> > of time is in optimization.
>> >
>> >>
>> >> Basically Xiangrui, is there a push back on making optimizers part of
>> spark
>> >> mllib ? I am exploring cg and qp solvers for spark mllib as well and I
>> am
>> >> developing these as part of mllib optimization. I was hoping we should
>> be
>> >> able to publish mllib as a maven artifact later.
>> >>
>> >> Thanks.
>> >> Deb
>> >
>> > Thanks.
>> >
>> > Sincerely,
>> >
>> > DB Tsai
>> > Machine Learning Engineer
>> > Alpine Data Labs
>> > --------------------------------------
>> > Web: http://alpinenow.com/
>>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
Hi DB,

I am considering building on your PR and add Mallet as the dependency so
that we can run some basic comparisons test on large scale sparse datasets
that I have.

In the meantime, let's discuss if there are other optimization packages
that we should try.

My wishlist has bounded bfgs as well and I will add it to the PR.

About the PR getting merged to mllib, we can plan that later.

Thanks.
Deb



On Tue, Feb 25, 2014 at 11:36 AM, DB Tsai <db...@alpinenow.com> wrote:

> I find some comparison between Mallet vs Fortran version. The result
> is closed but not the same.
>
> http://t3827.ai-mallet-development.aitalk.info/help-with-l-bfgs-t3827.html
>
> Here is LBFGS-B
> Cost: 0.6902411220175793
> Gradient: -5.453609E-007, -2.858372E-008, -1.369706E-007
> Theta: -0.014186210102171406, -0.303521206706629, -0.018132348904129902
>
> And Mallet LBFGS (Tollerance .000000000000001)
> Cost: 0.6902412268833071
> Gradient: 0.000117, -4.615523E-005, 0.000114
> Theta: -0.013914961040040107, -0.30419883021414335, -0.016838481937958744
>
> So this shows me, that Mallet is close, but Plain ol Gradient Descent
> and LBFGS-B are really close.
> I see that Mallet also has a "LineOptimizer" and "Evaluator" that I
> have yet to explore...
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/
>
>
> On Tue, Feb 25, 2014 at 11:16 AM, DB Tsai <db...@alpinenow.com> wrote:
> > Hi Deb,
> >
> > On Tue, Feb 25, 2014 at 7:07 AM, Debasish Das <de...@gmail.com>
> wrote:
> >> Continuation on last email sent by mistake:
> >>
> >> Is cpl license is compatible with apache ?
> >>
> >> http://opensource.org/licenses/cpl1.0.php
> >
> > Based on what I read here, there is no problem to include CPL code in
> > apache project
> > as long as the code isn't modified, and we include the maven binary.
> > https://www.apache.org/legal/3party.html
> >
> >> Mallet jars are available on maven. They have hessian based solvers
> which
> >> looked interesting along with bfgs and cg.
> >
> > We found that hessian based solvers don't scale as the # of features
> grow, and
> > we have lots of customers trying to train sparse input. That's our
> motivation to
> > work on L-BFGS which approximate hessian using just a few vectors.
> >
> > Just take a look at MALLET, and it does have L-BFGS and its variant
> OWL-QN
> > which can tackle L1 problem. Since implementing L-BFGS is very subtle, I
> don't
> > know the quality of the mallet implementation. Personally, I
> > implemented one based
> > on textbook, and not very stable. If MALLET is robust, I'll go for it
> > since it has more
> > features, and already in maven.
> >
> >> Note that right now the version is not blas optimized. With jblas or
> >> netlib-java discussions that's going on it can be improved. Also it
> runs on
> >> a single thread which can be improved...so there is scope for further
> >> improvements in the code.
> >
> > I think it will not impact performance even it's not blas optimized
> > nor multi-threaded,
> > since most of the parallelization is in computing gradientSum and
> > lossSum in Spark,
> > and the optimizer just takes gradientSum, lossSum, and weights to get
> > the newWeights.
> >
> > As a result, 99.9% of time is in computing gradientSum and lossSum.
> > Only small amount
> > of time is in optimization.
> >
> >>
> >> Basically Xiangrui, is there a push back on making optimizers part of
> spark
> >> mllib ? I am exploring cg and qp solvers for spark mllib as well and I
> am
> >> developing these as part of mllib optimization. I was hoping we should
> be
> >> able to publish mllib as a maven artifact later.
> >>
> >> Thanks.
> >> Deb
> >
> > Thanks.
> >
> > Sincerely,
> >
> > DB Tsai
> > Machine Learning Engineer
> > Alpine Data Labs
> > --------------------------------------
> > Web: http://alpinenow.com/
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
I find some comparison between Mallet vs Fortran version. The result
is closed but not the same.

http://t3827.ai-mallet-development.aitalk.info/help-with-l-bfgs-t3827.html

Here is LBFGS-B
Cost: 0.6902411220175793
Gradient: -5.453609E-007, -2.858372E-008, -1.369706E-007
Theta: -0.014186210102171406, -0.303521206706629, -0.018132348904129902

And Mallet LBFGS (Tollerance .000000000000001)
Cost: 0.6902412268833071
Gradient: 0.000117, -4.615523E-005, 0.000114
Theta: -0.013914961040040107, -0.30419883021414335, -0.016838481937958744

So this shows me, that Mallet is close, but Plain ol Gradient Descent
and LBFGS-B are really close.
I see that Mallet also has a "LineOptimizer" and "Evaluator" that I
have yet to explore...

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/


On Tue, Feb 25, 2014 at 11:16 AM, DB Tsai <db...@alpinenow.com> wrote:
> Hi Deb,
>
> On Tue, Feb 25, 2014 at 7:07 AM, Debasish Das <de...@gmail.com> wrote:
>> Continuation on last email sent by mistake:
>>
>> Is cpl license is compatible with apache ?
>>
>> http://opensource.org/licenses/cpl1.0.php
>
> Based on what I read here, there is no problem to include CPL code in
> apache project
> as long as the code isn't modified, and we include the maven binary.
> https://www.apache.org/legal/3party.html
>
>> Mallet jars are available on maven. They have hessian based solvers which
>> looked interesting along with bfgs and cg.
>
> We found that hessian based solvers don't scale as the # of features grow, and
> we have lots of customers trying to train sparse input. That's our motivation to
> work on L-BFGS which approximate hessian using just a few vectors.
>
> Just take a look at MALLET, and it does have L-BFGS and its variant OWL-QN
> which can tackle L1 problem. Since implementing L-BFGS is very subtle, I don't
> know the quality of the mallet implementation. Personally, I
> implemented one based
> on textbook, and not very stable. If MALLET is robust, I'll go for it
> since it has more
> features, and already in maven.
>
>> Note that right now the version is not blas optimized. With jblas or
>> netlib-java discussions that's going on it can be improved. Also it runs on
>> a single thread which can be improved...so there is scope for further
>> improvements in the code.
>
> I think it will not impact performance even it's not blas optimized
> nor multi-threaded,
> since most of the parallelization is in computing gradientSum and
> lossSum in Spark,
> and the optimizer just takes gradientSum, lossSum, and weights to get
> the newWeights.
>
> As a result, 99.9% of time is in computing gradientSum and lossSum.
> Only small amount
> of time is in optimization.
>
>>
>> Basically Xiangrui, is there a push back on making optimizers part of spark
>> mllib ? I am exploring cg and qp solvers for spark mllib as well and I am
>> developing these as part of mllib optimization. I was hoping we should be
>> able to publish mllib as a maven artifact later.
>>
>> Thanks.
>> Deb
>
> Thanks.
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by DB Tsai <db...@alpinenow.com>.
Hi Deb,

On Tue, Feb 25, 2014 at 7:07 AM, Debasish Das <de...@gmail.com> wrote:
> Continuation on last email sent by mistake:
>
> Is cpl license is compatible with apache ?
>
> http://opensource.org/licenses/cpl1.0.php

Based on what I read here, there is no problem to include CPL code in
apache project
as long as the code isn't modified, and we include the maven binary.
https://www.apache.org/legal/3party.html

> Mallet jars are available on maven. They have hessian based solvers which
> looked interesting along with bfgs and cg.

We found that hessian based solvers don't scale as the # of features grow, and
we have lots of customers trying to train sparse input. That's our motivation to
work on L-BFGS which approximate hessian using just a few vectors.

Just take a look at MALLET, and it does have L-BFGS and its variant OWL-QN
which can tackle L1 problem. Since implementing L-BFGS is very subtle, I don't
know the quality of the mallet implementation. Personally, I
implemented one based
on textbook, and not very stable. If MALLET is robust, I'll go for it
since it has more
features, and already in maven.

> Note that right now the version is not blas optimized. With jblas or
> netlib-java discussions that's going on it can be improved. Also it runs on
> a single thread which can be improved...so there is scope for further
> improvements in the code.

I think it will not impact performance even it's not blas optimized
nor multi-threaded,
since most of the parallelization is in computing gradientSum and
lossSum in Spark,
and the optimizer just takes gradientSum, lossSum, and weights to get
the newWeights.

As a result, 99.9% of time is in computing gradientSum and lossSum.
Only small amount
of time is in optimization.

>
> Basically Xiangrui, is there a push back on making optimizers part of spark
> mllib ? I am exploring cg and qp solvers for spark mllib as well and I am
> developing these as part of mllib optimization. I was hoping we should be
> able to publish mllib as a maven artifact later.
>
> Thanks.
> Deb

Thanks.

Sincerely,

DB Tsai
Machine Learning Engineer
Alpine Data Labs
--------------------------------------
Web: http://alpinenow.com/

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Xiangrui Meng <me...@gmail.com>.
Hi Deb,

CPL 1.0 is compatible if the inclusion is appropriately labeled
(https://www.apache.org/legal/3party.html). I think it is great to
have an L-BFGS optimizer in mllib, but we need to investigate some
time to figure out which one to use. I'm not sure whether jblas or
netlib-java will make a big difference here, because L-BFGS doesn't
have dense level-2 BLAS operations. But it would be great if someone
can do the comparison and show some numbers. FYI, spark-mllib is
published in maven central.

Best,
Xiangrui

On Tue, Feb 25, 2014 at 7:07 AM, Debasish Das <de...@gmail.com> wrote:
> Continuation on last email sent by mistake:
>
> Is cpl license is compatible with apache ?
>
> http://opensource.org/licenses/cpl1.0.php
>
> Mallet jars are available on maven. They have hessian based solvers which
> looked interesting along with bfgs and cg.
>
> Definitely the lbfgs f2j looks promising as the base fortran code is
> perhaps the best bfgs code I have used. Also the bounded bfgs is useful for
> many cases to enforce constraints on say pca....
>
> Note that right now the version is not blas optimized. With jblas or
> netlib-java discussions that's going on it can be improved. Also it runs on
> a single thread which can be improved...so there is scope for further
> improvements in the code.
>
> Basically Xiangrui, is there a push back on making optimizers part of spark
> mllib ? I am exploring cg and qp solvers for spark mllib as well and I am
> developing these as part of mllib optimization. I was hoping we should be
> able to publish mllib as a maven artifact later.
>
> Thanks.
> Deb
> On Feb 25, 2014 6:53 AM, "Debasish Das" <de...@gmail.com> wrote:
>
>> Hi DB, Xiangrui,
>>
>> Mallet from cmu also has bfgs cg and a good optimization package.  Do you
>> know if cpl license si
>> On Feb 22, 2014 11:50 AM, "Xiangrui Meng" <me...@gmail.com> wrote:
>>
>>> Hi DB,
>>>
>>> It is great to have the L-BFGS optimizer in MLlib and thank you for taking
>>> care of the license issue. I looked through your PR briefly. It contains a
>>> Java translation of the L-BFGS implementation, which is part of the RISO
>>> package. Is it possible that we ask its author to make a release on maven
>>> central and then we add it as a dependency instead of including the code
>>> directly?
>>>
>>> Best,
>>> Xiangrui
>>>
>>>
>>> On Sat, Feb 22, 2014 at 4:28 AM, DB Tsai <db...@alpinenow.com> wrote:
>>>
>>> > Hi guys,
>>> >
>>> > First of all, we would like to thank all the Spark community for
>>> > building such great platform for big data processing. We built the
>>> > multinomial logistic regression with LBFGS optimizer in Spark, and
>>> > LBFGS is a limited memory version of quasi-newton method which allows
>>> > us to train a very high-dimensional data without computing the Hessian
>>> > matrix as newton method required.
>>> >
>>> > In Strata Conference, we did a great demo using Spark with our MLOR to
>>> > train mnist8m dataset. We're able to train the model in 5 mins with 50
>>> > iterations, and get 86% accuracy. The first iteration takes 19.8s, and
>>> > the remaining iterations take about 5~7s.
>>> >
>>> > We did comparison between LBFGS and SGD, and often we saw 10x less
>>> > steps in LBFGS while the cost of per step is the same (just computing
>>> > the gradient).
>>> >
>>> > The following is the paper by Prof. Ng at Stanford comparing different
>>> > optimizers including LBFGS and SGD. They use them in the context of
>>> > deep learning, but worth as reference.
>>> >
>>> http://cs.stanford.edu/~jngiam/papers/LeNgiamCoatesLahiriProchnowNg2011.pdf
>>> >
>>> > We would like to break our MLOR with LBFGS into three patches to
>>> > contribute to the community.
>>> >
>>> > 1) LBFGS optimizer - which can be used in logistic regression, and
>>> > liner regression or replacing any algorithms using SGD.
>>> > The core underneath LBFGS Java implementation we used is from RISO
>>> > project, and the author, Robert is so kind to relicense it to GPL and
>>> > Apache2 dual license.
>>> >
>>> > We're almost ready to submit a PR for LBFGS, see our github fork,
>>> > https://github.com/AlpineNow/incubator-spark/commits/dbtsai-LBFGS
>>> >
>>> > However, we don't use Updater in LBFGS since it designs for GD, and
>>> > for LBFGS, we don't need stepSize, and adaptive learning rate, etc.
>>> > While it seems to be difficult to fit the LBFGS updater logic (well,
>>> > in lbfgs library, the new weights is returned given old weights, loss,
>>> > and gradient) into the current framework, I was thinking to abstract
>>> > out the code computing the gradient and loss terms of regularization
>>> > into different place so that different optimizer can also use it. Any
>>> > suggestion about this?
>>> >
>>> > 2) and 3), we will add the MLOR gradient to MLLib, and add a few
>>> > examples. Finally, we will have some tweak using mapPartition instead
>>> > of map to further improve the performance.
>>> >
>>> > Thanks.
>>> >
>>> > Sincerely,
>>> >
>>> > DB Tsai
>>> > Machine Learning Engineer
>>> > Alpine Data Labs
>>> > --------------------------------------
>>> > Web: http://alpinenow.com/
>>> >
>>>
>>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
Continuation on last email sent by mistake:

Is cpl license is compatible with apache ?

http://opensource.org/licenses/cpl1.0.php

Mallet jars are available on maven. They have hessian based solvers which
looked interesting along with bfgs and cg.

Definitely the lbfgs f2j looks promising as the base fortran code is
perhaps the best bfgs code I have used. Also the bounded bfgs is useful for
many cases to enforce constraints on say pca....

Note that right now the version is not blas optimized. With jblas or
netlib-java discussions that's going on it can be improved. Also it runs on
a single thread which can be improved...so there is scope for further
improvements in the code.

Basically Xiangrui, is there a push back on making optimizers part of spark
mllib ? I am exploring cg and qp solvers for spark mllib as well and I am
developing these as part of mllib optimization. I was hoping we should be
able to publish mllib as a maven artifact later.

Thanks.
Deb
On Feb 25, 2014 6:53 AM, "Debasish Das" <de...@gmail.com> wrote:

> Hi DB, Xiangrui,
>
> Mallet from cmu also has bfgs cg and a good optimization package.  Do you
> know if cpl license si
> On Feb 22, 2014 11:50 AM, "Xiangrui Meng" <me...@gmail.com> wrote:
>
>> Hi DB,
>>
>> It is great to have the L-BFGS optimizer in MLlib and thank you for taking
>> care of the license issue. I looked through your PR briefly. It contains a
>> Java translation of the L-BFGS implementation, which is part of the RISO
>> package. Is it possible that we ask its author to make a release on maven
>> central and then we add it as a dependency instead of including the code
>> directly?
>>
>> Best,
>> Xiangrui
>>
>>
>> On Sat, Feb 22, 2014 at 4:28 AM, DB Tsai <db...@alpinenow.com> wrote:
>>
>> > Hi guys,
>> >
>> > First of all, we would like to thank all the Spark community for
>> > building such great platform for big data processing. We built the
>> > multinomial logistic regression with LBFGS optimizer in Spark, and
>> > LBFGS is a limited memory version of quasi-newton method which allows
>> > us to train a very high-dimensional data without computing the Hessian
>> > matrix as newton method required.
>> >
>> > In Strata Conference, we did a great demo using Spark with our MLOR to
>> > train mnist8m dataset. We're able to train the model in 5 mins with 50
>> > iterations, and get 86% accuracy. The first iteration takes 19.8s, and
>> > the remaining iterations take about 5~7s.
>> >
>> > We did comparison between LBFGS and SGD, and often we saw 10x less
>> > steps in LBFGS while the cost of per step is the same (just computing
>> > the gradient).
>> >
>> > The following is the paper by Prof. Ng at Stanford comparing different
>> > optimizers including LBFGS and SGD. They use them in the context of
>> > deep learning, but worth as reference.
>> >
>> http://cs.stanford.edu/~jngiam/papers/LeNgiamCoatesLahiriProchnowNg2011.pdf
>> >
>> > We would like to break our MLOR with LBFGS into three patches to
>> > contribute to the community.
>> >
>> > 1) LBFGS optimizer - which can be used in logistic regression, and
>> > liner regression or replacing any algorithms using SGD.
>> > The core underneath LBFGS Java implementation we used is from RISO
>> > project, and the author, Robert is so kind to relicense it to GPL and
>> > Apache2 dual license.
>> >
>> > We're almost ready to submit a PR for LBFGS, see our github fork,
>> > https://github.com/AlpineNow/incubator-spark/commits/dbtsai-LBFGS
>> >
>> > However, we don't use Updater in LBFGS since it designs for GD, and
>> > for LBFGS, we don't need stepSize, and adaptive learning rate, etc.
>> > While it seems to be difficult to fit the LBFGS updater logic (well,
>> > in lbfgs library, the new weights is returned given old weights, loss,
>> > and gradient) into the current framework, I was thinking to abstract
>> > out the code computing the gradient and loss terms of regularization
>> > into different place so that different optimizer can also use it. Any
>> > suggestion about this?
>> >
>> > 2) and 3), we will add the MLOR gradient to MLLib, and add a few
>> > examples. Finally, we will have some tweak using mapPartition instead
>> > of map to further improve the performance.
>> >
>> > Thanks.
>> >
>> > Sincerely,
>> >
>> > DB Tsai
>> > Machine Learning Engineer
>> > Alpine Data Labs
>> > --------------------------------------
>> > Web: http://alpinenow.com/
>> >
>>
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Debasish Das <de...@gmail.com>.
Hi DB, Xiangrui,

Mallet from cmu also has bfgs cg and a good optimization package.  Do you
know if cpl license si
On Feb 22, 2014 11:50 AM, "Xiangrui Meng" <me...@gmail.com> wrote:

> Hi DB,
>
> It is great to have the L-BFGS optimizer in MLlib and thank you for taking
> care of the license issue. I looked through your PR briefly. It contains a
> Java translation of the L-BFGS implementation, which is part of the RISO
> package. Is it possible that we ask its author to make a release on maven
> central and then we add it as a dependency instead of including the code
> directly?
>
> Best,
> Xiangrui
>
>
> On Sat, Feb 22, 2014 at 4:28 AM, DB Tsai <db...@alpinenow.com> wrote:
>
> > Hi guys,
> >
> > First of all, we would like to thank all the Spark community for
> > building such great platform for big data processing. We built the
> > multinomial logistic regression with LBFGS optimizer in Spark, and
> > LBFGS is a limited memory version of quasi-newton method which allows
> > us to train a very high-dimensional data without computing the Hessian
> > matrix as newton method required.
> >
> > In Strata Conference, we did a great demo using Spark with our MLOR to
> > train mnist8m dataset. We're able to train the model in 5 mins with 50
> > iterations, and get 86% accuracy. The first iteration takes 19.8s, and
> > the remaining iterations take about 5~7s.
> >
> > We did comparison between LBFGS and SGD, and often we saw 10x less
> > steps in LBFGS while the cost of per step is the same (just computing
> > the gradient).
> >
> > The following is the paper by Prof. Ng at Stanford comparing different
> > optimizers including LBFGS and SGD. They use them in the context of
> > deep learning, but worth as reference.
> >
> http://cs.stanford.edu/~jngiam/papers/LeNgiamCoatesLahiriProchnowNg2011.pdf
> >
> > We would like to break our MLOR with LBFGS into three patches to
> > contribute to the community.
> >
> > 1) LBFGS optimizer - which can be used in logistic regression, and
> > liner regression or replacing any algorithms using SGD.
> > The core underneath LBFGS Java implementation we used is from RISO
> > project, and the author, Robert is so kind to relicense it to GPL and
> > Apache2 dual license.
> >
> > We're almost ready to submit a PR for LBFGS, see our github fork,
> > https://github.com/AlpineNow/incubator-spark/commits/dbtsai-LBFGS
> >
> > However, we don't use Updater in LBFGS since it designs for GD, and
> > for LBFGS, we don't need stepSize, and adaptive learning rate, etc.
> > While it seems to be difficult to fit the LBFGS updater logic (well,
> > in lbfgs library, the new weights is returned given old weights, loss,
> > and gradient) into the current framework, I was thinking to abstract
> > out the code computing the gradient and loss terms of regularization
> > into different place so that different optimizer can also use it. Any
> > suggestion about this?
> >
> > 2) and 3), we will add the MLOR gradient to MLLib, and add a few
> > examples. Finally, we will have some tweak using mapPartition instead
> > of map to further improve the performance.
> >
> > Thanks.
> >
> > Sincerely,
> >
> > DB Tsai
> > Machine Learning Engineer
> > Alpine Data Labs
> > --------------------------------------
> > Web: http://alpinenow.com/
> >
>

Re: MLLib - Thoughts about refactoring Updater for LBFGS?

Posted by Xiangrui Meng <me...@gmail.com>.
Hi DB,

It is great to have the L-BFGS optimizer in MLlib and thank you for taking
care of the license issue. I looked through your PR briefly. It contains a
Java translation of the L-BFGS implementation, which is part of the RISO
package. Is it possible that we ask its author to make a release on maven
central and then we add it as a dependency instead of including the code
directly?

Best,
Xiangrui


On Sat, Feb 22, 2014 at 4:28 AM, DB Tsai <db...@alpinenow.com> wrote:

> Hi guys,
>
> First of all, we would like to thank all the Spark community for
> building such great platform for big data processing. We built the
> multinomial logistic regression with LBFGS optimizer in Spark, and
> LBFGS is a limited memory version of quasi-newton method which allows
> us to train a very high-dimensional data without computing the Hessian
> matrix as newton method required.
>
> In Strata Conference, we did a great demo using Spark with our MLOR to
> train mnist8m dataset. We're able to train the model in 5 mins with 50
> iterations, and get 86% accuracy. The first iteration takes 19.8s, and
> the remaining iterations take about 5~7s.
>
> We did comparison between LBFGS and SGD, and often we saw 10x less
> steps in LBFGS while the cost of per step is the same (just computing
> the gradient).
>
> The following is the paper by Prof. Ng at Stanford comparing different
> optimizers including LBFGS and SGD. They use them in the context of
> deep learning, but worth as reference.
> http://cs.stanford.edu/~jngiam/papers/LeNgiamCoatesLahiriProchnowNg2011.pdf
>
> We would like to break our MLOR with LBFGS into three patches to
> contribute to the community.
>
> 1) LBFGS optimizer - which can be used in logistic regression, and
> liner regression or replacing any algorithms using SGD.
> The core underneath LBFGS Java implementation we used is from RISO
> project, and the author, Robert is so kind to relicense it to GPL and
> Apache2 dual license.
>
> We're almost ready to submit a PR for LBFGS, see our github fork,
> https://github.com/AlpineNow/incubator-spark/commits/dbtsai-LBFGS
>
> However, we don't use Updater in LBFGS since it designs for GD, and
> for LBFGS, we don't need stepSize, and adaptive learning rate, etc.
> While it seems to be difficult to fit the LBFGS updater logic (well,
> in lbfgs library, the new weights is returned given old weights, loss,
> and gradient) into the current framework, I was thinking to abstract
> out the code computing the gradient and loss terms of regularization
> into different place so that different optimizer can also use it. Any
> suggestion about this?
>
> 2) and 3), we will add the MLOR gradient to MLLib, and add a few
> examples. Finally, we will have some tweak using mapPartition instead
> of map to further improve the performance.
>
> Thanks.
>
> Sincerely,
>
> DB Tsai
> Machine Learning Engineer
> Alpine Data Labs
> --------------------------------------
> Web: http://alpinenow.com/
>