commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ole Ersoy <ole.er...@gmail.com>
Subject Re: [Math] LeastSquaresOptimizer Design
Date Tue, 22 Sep 2015 14:52:16 GMT
On 09/22/2015 06:46 AM, Gilles wrote:
> Hi.
>
> On Mon, 21 Sep 2015 19:55:15 -0500, Ole Ersoy wrote:
>> Hola,
>>
>> On 09/21/2015 04:15 PM, Gilles wrote:
>>> Hi.
>>>
>>> On Sun, 20 Sep 2015 15:04:08 -0500, Ole Ersoy wrote:
>>>> On 09/20/2015 05:51 AM, Gilles wrote:
>>>>> On Sun, 20 Sep 2015 01:12:49 -0500, Ole Ersoy wrote:
>>>>>> Wanted to float some ideas for the LeastSquaresOptimizer (Possibly
>>>>>> General Optimizer) design.  For example with the
>>>>>> LevenbergMarquardtOptimizer we would do:
>>>>>> `LevenbergMarquardtOptimizer.optimize(OptimizationContext c);`
>>>>>>
>>>>>> Rough optimize() outline:
>>>>>> public static void optimise() {
>>>>>> //perform the optimization
>>>>>> //If successful
>>>>>>     c.notify(LevenberMarquardtResultsEnum.SUCCESS, solution);
>>>>>> //If not successful
>>>>>>
>>>>>>
>>>>>>
>>>>>> c.notify(LevenberMarquardtResultsEnum.TOO_SMALL_COST_RELATIVE_TOLERANCE,
>>>>>> diagnostic);
>>>>>> //or
>>>>>>
>>>>>>
>>>>>>
>>>>>> c.notify(LevenberMarquardtResultsEnum.TOO_SMALL_PARAMETERS_RELATIVE_TOLERANCE,
>>>>>> diagnostic)
>>>>>> //etc
>>>>>> }
>>>>>>
>>>>>> The diagnostic, when turned on, will contain a trace of the last
N
>>>>>> iterations leading up to the failure.  When turned off, the Diagnostic
>>>>>> instance only contains the parameters used to detect failure. The
>>>>>> diagnostic could be viewed as an indirect way to log optimizer
>>>>>> iterations.
>>>>>>
>>>>>> WDYT?
>>>>>
>>>>> I'm wary of having several different ways to convey information to the
>>>>> caller.
>>>> It would just be one way.
>>>
>>> One way for optimizer, one way for solvers, one way for ...
>>
>> Yes I see what you mean, but I think on a whole it will be worth it
>> to add additional sugar code that removes the need for exceptions.
>
> Isn't always possible to wrap exception-generating code so that upper
> layers do not see them?
The layer that calls the commons math function will see errors through the callback interface.
 They are not exceptions though. The error is encoded as an Enum and is specific to the calling
code...not generic across multiple classes.

>
> The interface would have to know how to handle them and propagate the
> information in some other form (callback).
Yes I think now we are saying the same thing.

>
>>>
>>>> But the caller may not be the receiver
>>>> (It could be).  The receiver would be an observer attached to the
>>>> OptimizationContext that implements an interface allowing it to observe
>>>> the optimization.
>>>
>>> I'm afraid that it will add to the questions of what to put in the
>>> code and how.  [We already had sometimes heated discussions just for
>>> the IMHO obvious (e.g. code formatting, documentation, exception...).]
>>
>> Hehe.  Yes I remember some of these discussions.  I wonder how much
>> time was spent debating the exceptions alone?  Surely everyone must
>> have had this feeling in pit of their stomach that there's got to be a
>> better way.  On the exception topic, these are some of the issues:
>>
>> I18N
>> ===================
>> If you are new to commons math and thinking about designing a commons
>> math compatible exception you should probably understand the I18N
>> stuff that's bound to exception (and wonder why it's bound the the
>> exception).  Grab a coffee and spend a few hours, unless you are
>> obviously fairly new to Java like some ofthe people posting for help.
>> In this case when the exception occurs, there is going to be a lot of
>> tutoring going on on the users list.
>
> I already said all I had to say about this; it's in the archive.
> Summary: I agree that it shouldn't be here.
>
>> Number of Exceptions
>> ===================
>> Before you do actually design a new exception, you should probably
>> see if there is an exception that already fits the category of what
>> you are doing.  So you start reading.  Exception1...nop
>> Exception2...nop...Exception3...Exception999..But I think I'm getting
>> warmer.  OK - Did not find it ... but I'm fairly certain that there is
>> a elegant place for it somewhere in the exception hierarchy...
>
> On this, I also explained at length my views (assuming that exceptions
> are part of the design).
> Summary: an exception indicates that something went wrong, and the caller
> should not hope to get anything good out of the call that raised the
> exception (i.e. he _must_ craft another call that meets the requirements
> of the code).

And further down it is noted that if the caller wants to deal with the exceptions directly
based on the call then the caller can create a wrapper for each commons math function throwing
the exception.  So the most elegant way of doing this is probably one wrapper per class. 
And the interface for the wrapper is left up to the designer.

Or we could get rid of the exceptions, design a callback interface for each solver / optimizer
/ etc.  They should be pretty similar across commons math.  In general they have two methods:

success(solution);
error(Enum.CODE, [Diagnostics])

Enum.CODE would be used for I18N.

The Diagnostics are optional, but I would say at a minimum at propagate the same information
that exceptions are propagating now.

>> Handling of Exceptions
>> ===================
>> If our app uses several of the commons math classes (That throw
>> exceptions of the same type), and one of those classes throws an
>> exception,what is the app supposed to do?
>
> Cf. previous paragraph.
Diddo.

>
>> I think most developers would find that question somewhat
>> challenging.  There are numerous strategies.  Catch all exceptions and
>> log what happened, etc.  But what if the requirement is that if an
>> exception is thrown, the organization that receives it has 0 seconds
>> to get to the root cause of it and understand the dynamics. Is this
>> doable?  (Yes obviously, but how hard is it...?).
>
> Cf. previous paragraph.
> In effect, you describe an upper layer's requirement (handling an expected
> "unexpected(!) failure"). IMHO, it's out CM's realm (CM raises the exception,
> end of story).

Or CM detects that it cannot provide a solution and sends the message via coded as an Enum
via the callback interface.

>
>>>>> It seems that the reporting interfaces could quickly overwhelm
>>>>> the "actual" code (one type of context per algorithm).
>>>> There would one type of Observer interface per algorithm. It would
>>>> act on the solution and what are currently exceptions, although these
>>>> would be translated into enums.
>>>
>>> Unless I'm mistaken, the most common use-case for codes implemented
>>> in a library such as CM is to provide a correct answer or bail out
>>> in a non-equivocal way.
>> Most java developers are used to synchronous coding...call the method
>> get the response...catch the exception if needed.  This is changing
>> with JDK8, and as we evolve and start using lambdas, we become more
>> accustomed to the functional callback style of programming.
>> Personally I want to be able to use an API that gives me what I need
>> when everything works as expected, allows me to resolve unexpected
>> issues with minimal effort, and is as simple, fluid, and lightweight
>> as possible.
>
> I've not yet used Java 8; I would have if we were allowed to use it in
> CM...

I think it's pretty sweet :).  Spring recommends that everyone upgrade.

>
>
> However, I'm not convinced that asynchronicity should be dealt with
> at the CM level, beyond making its algorithms multi-thread friendly.
> IMO, this is the important change (that can make a big difference,
> performance-wise, on machines with multiple cores).
> Then developers can use the standard tools in "java.util.concurrent"
> to select a runtime policy (single/multi-thread and/or (a)synchronous).
That sounds good.  For the asynchronous option the user is probably going to want be notified
via a callback...unless there's another option?

>
>
>>> It would make the code more involved to handle a minority of
>>> (undefined) cases. [Actual examples would be welcome in order to
>>> focus the discussion.]
>>
>> Rough Outline (I've evolved the concept and moved away from the
>> OptimizationContext in the process of writing):
>>
>> interface LevenbergMarquardtObserver {
>>
>>     public void hola(Solution s);
>>     public void sugarHoneyIceTea(ResultType rt, Dianostics d);
>> }
>>
>> public class LMObserver implements LevenbergMarquardtObserver {
>>
>>    private Application application;
>>
>>    public LMObserver(Application application) {
>>        this.application = application;
>>    }
>>
>>    public void hola(ResultType rt, Solution s) {
>>                 application.next(solution);
>>    }
>>
>>    public void sugarHoneyIceTea(ResultType rt, Diagnostic s)
>>        if (rt == ResultType.I_GOT_THIS_ONE) {
>>             //I looked at the commons unit tests for this algorithm
>> evaluating
>>             //the diagnostics that shows how this failure can occur
>>             //I'm totally fixing this!  Steps aside!
>>        }
>>        else if (rt == ResultType.REALLY_COMPLICATED_STUFF)
>>        {
>>            //We need our best engineers...call India.
>>        }
>>   )
>>
>>
>> public class Application {
>>     //Note nothing is returned.
>>     LevenberMarquardtOptimizer.setOberver(new
>> LMObserver(this)).setLeastSquaresProblem(new
>> ClassThatImplementsTheProblem())).start();
>>
>>     public void next(Solution solution) {
>>
>>         //Do cool stuff.
>>
>>     }
>> }
>>
>> Or an asynchronous variation:
>>
>> public class Application {
>> //This call will not block because async is true
>>     LevenberMarquardtOptimizer.setAsync(true).setOberver(new
>> LMObserver()).setLeastSquaresProblem(new
>> ClassThatImplementsTheProblem())).start();
>>
>>     //Do more stuff right away.
>>
>>     public void next(Solution solution) {
>>         //When the thread running the optimization is done, this
>> method is called back.
>>         //Do whatever comes next
>>     }
>> }
>>
>> The above would start the optimization in a separate thread that does
>> not / SHOULD NOT share data with the main thread.
>
> Cf. previous paragraph: I think that can be done in a layer above CM.
But CM will be better if it dumps the exceptions and takes a more direct approach.

>
>>>>> The current reporting is based on exceptions, and assumes that if no
>>>>> exception was thrown, then the user's request completed successfully.
>>>> Sure - personally I'd much rather deal with something similar to an
>>>> HTTP status code in a callback, than an exception .  I think the code
>>>> is cleaner and the calback makes it more elegant to apply an adaptive
>>>> approach to handling the response, like slightly relaxing constraints,
>>>> convergence parameters, etc.  Also by getting rid of the exceptions,
>>>> we no longer depend on the I18N layer that they are tied to and now
>>>> the messages can be more informative, since they target the root
>>>> cause.  The observer can also run in the 'main' thread' while the
>>>> optimization can run asynchronously.  Also WRT JDK9 and modules,
>>>> loosing the exceptions would mean one less dependency when the library
>>>> is up into JDK9 modules...which would be more in line with this
>>>> philosophy:
>>>> https://github.com/substack/browserify-handbook#module-philosophy
>>>
>>> I'm not sure I fully understood the philosophy from the text in this
>>> short paragraph.
>>> But I do not agree with the idea that the possibility to quickly find
>>> some code is more important than standards and best practices.
>>
>> If you go to npmjs.org and type in Neural Network you will get 56
>> results all linked to github repositories.
>>
>> In addition there's meta data indicating number of downloads in the
>> last day, last month, etc.  Try typing in cosine.  Odds are you will
>> find a package that does just want you want and nothing else. This is
>> very underwhelming and refreshing in terms of cloning off of github
>> and getting familar with tests etc.  Also eye opening.  How many of us
>> knew that we could do that much stuff with cosine! :).
>
> I really don't mean to question the quality of any of those implementations,
> but the issue is there: How to choose?
For math ATM it's more obscure.  For other libraries like superagent:
https://www.npmjs.com/package/superagent

With 30K downloads in the last day, it's much easier to be assured that it's the way to go.
 It's also a fantastic way to learn REST.

>
> That there are so many of them sort of defeats the purpose of "quickly
> find what you need".
Yes - NodeJS is relatively new, so some of the packages have not had much time to 'simmer'.

>
> It seems (?) that the consequence of this modularity (?) is to encourage
> the creation of many independent/competing/duplicate projects of small
> teams (I'd guess, a 1-person-team, in most cases).
Well if you look at Superagent for example, the team size is significant.  But it's not so
much the team size.  It's what superagent does.  It does one thing, and does it really well.

>
>>>>> I totally agree that in some circumstances, more information on the
>>>>> inner working of an algorithm would be quite useful.
>>>> ... Algorithm iterations become unit testable.
>>>>>
>>>>> But I don't see the point in devoting resources to reinvent the wheel:
>>>> You mean pimping the wheel?  Big pimpin.
>>>
>>> I think that logging statements are easy to add, not disruptive at all,
>>> and come in handy to understand a code's unexpected behaviour.
>>> Assuming that a "logging" feature is useful, it can be added *now* using
>>> a dependency towards a weight-less (!) framework such as "slf4j".
>>> IMO, it would be a waste of time to implement a new communication layer
>>> that can do that, and more, if it would be used for logging only in 99%
>>> of the cases.
>> SLF4J is used by almost every other framework, so why not use it?
>
> Good question: I also asked it quite some time ago.
> Didn't get a satisfying answer. Boiled down to "no dependency" policy.
I think it would be worth examining breaking up CM into JDK9 modules and then utilizing SLF4J
when it adds value.

>
>> Logging and the diagnostic could be used together.  The primary
>> purpose of the diagnostic though is to collect data that will be
>> useful in `sugarHoneyIceTea`.
>
> I'm not sure I understand correctly the purpose: if the "Solution" is
> found, do you ever need more "context" (i.e. "Result", "Diagnostics")?

If the solution is found, then the method calls cb.notify(solution).  The diagnostic is never
created.
If the solution is not found, then the method calls cb.error(ErrorCodeEnum.THE_CODE_WITH_REALLY_GOOD_JAVADOC_DESCRIBING_THE_ERROR,
Diagnostic);

interface Callback {
    notify(Solution solution);
    error(ErrorCodeEnum enum)
}

The big difference here between exceptions and an ErrorCodeEnum is that the ErrorCodeEnum
is tied to the root of what happened.  For example if on line 335 the code detects that it
will not converge, then an Enum code is created for this specific case, unit tested for this
specific case, and documented for this specific case.

Suppose that the something similar occurs at three different points in the code.  The code
could throw the same exception three times, for three different reasons, but it's still the
same exception.  So if you are the API user - which would you rather have?  Codes that tell
you precisely what happened, or dig through the exceptions so that you can derive what happened
in your wrapper code?

>
> If it is only necessary in case of failure, CM's exception can already
> carry context information.  As I wrote above, such an exception could
> be caught by a wrapper (not necessarily part of the CM "core") and
> translated into whatever the upper layer expect (e.g. "Diagnostics").

I think CM needs to examine the amount of overhead that exceptions cause with respect to developers
and API users.

>
>>>
>>>>>
>>>>> I longed several times for the use of a logging library.
>>>>> The only show-stopper has been the informal "no-dependency" policy...
>>>> JDK9 Jigsaw should solve dependency hell, so the less coupling
>>>> between commons math classes the better.
>>>
>>> I wouldn't call "coupling" the dependency towards exception classes:
>>> they are little utilities that can make sense in various parts of the
>>> library.
>>
>> If for example the Simplex solver is broken off into it's own module,
>> then it has to be coupled to the exceptions, unless it is exception
>> free.
>
> Why is it a problem to be coupled with a few tiny exception classes?
If it's necessary then it's necessary.  If put put an exception free design next to the one
with exceptions and look at both through the lens of:
- Which is best for developer productivity?
- Which is best in terms of API user productivity?

> Then if it is really a problem, we can indeed define "local" exceptions
> for each package.
Or not.

>
>>>
>>> [Unless one wants to embark on yet another discussion about exceptions;
>>> whether there should be one class for each of the "messages" that exist
>>> in "LocalizedFormats"; whether localization should be done in CM;
>>> etc.]
>>
>> I think it would be best to just eliminate the exceptions.
>
> I'd think that most users of CM should deem that dangerous.
Or refreshing once they see the alternative.

> An exception is relatively difficult to ignore unknowingly (and was
> rightfully a better alternative the old "check the return value").

This is another issue.  Runtime exception can be ignored.

>
>>>
>>>> Anyways I'm obviously
>>>> interested in playing with this stuff, so when I get something up into
>>>> a repository I'll to do a callback :).
>>>
>>> If you are interested in big overhauls, there is one that gathered
>>> relative consensus: rewrite the algorithms in a "multithread-friendly"
>>> way.
>> I think that's a tall order that will take us into JDK88 :).
>
> That would be a real pity.
> I recall a nit-picking discussion about how to initialize the "FastMath"
> class in order to gain a few _milliseconds_. :-/
>
>> But
>> using callbacks and making potentially long running computations
>> asynchronous could be a middle ground that would allow simple multi
>> threaded use without fiddling around under the hood...
>
> Cf. above (this does not need ad-hoc CM code, beyond the relevant classes
> implementing "Runnable" and/or "Callable").
That's what I like about it.  It's simple.  So if CM algorithms get an `async` option, combined
with a callback interface, then the implementation is pretty straightforward.

>
>>> Some ideas were floated (cf. ML archive) but no implementation or
>>> experiment...  Perhaps with a well-defined goal such as performance
>>> improvement, your design suggestions will become clearer to more people.
>>>
>>> AFAIK, only the classes in the "o.a.c.m.neuralnet" package are currently
>>> ready to be used with the "java.util.concurrent" framework.
>> FWIU Neural Nets are a great fit for concurrency.
>
> Quite true.
>
> But even the optimizers could benefit from just being able to use
> more threads: It is often (always?) necessary to evaluate the objective
> function "N" times per iteration. So, the computation could be about
>   min(N, numCores)
> times faster.

JDK8 streams make this really simple.  The part that is not so simple is specifying the number
of threads or perhaps a percentage of the number of cores.  If we could do:

Solve.optimize(problem, config.numberOfThreads);
Solve.optimize(problem, targetCoreUtilitzation);

I think more of us would find JDK8 and streams attractive.


>
>> I think for the
>> others we will end up having discussions around how users would
>> control the number of threads, etc. again that makes some of us
>> nervous.
>
> One additional parameters: numCores.
>
>> An asynchronous operation that runs in one separate thread
>> is easier to reason about.
>
> Sure.
>
> But then we should stop talking about performance on this list. ;-}
Well - code that is single threaded is easier to reason about. There are two different ways
to utilize the cores.  Create 10 solvers solving 10 problems using asynchronous invocations,
or run the 10 problems synchronously using a concurrent algorithm.

If there's only one problem to solve, then obviously we need the concurrency, but the asynchronous
option is the low hanging fruit.

>
>> If we want to test 10 neural net
>> configurations, and we have 10 cores, then we can start each by itself
>> by doing something like:
>>
>>
>> Nework.setAsync(true).addNeurons().connectNeurons().addObserver(observer).start().
>> //Now do 10 more
>> //If the observer is shared then notifications should be thread safe.
>
> I had a similar argument for not making "FastMath" initialization faster
> (at the cost of a lot of additional code):  It was rejected...
Perhaps if FastMath was more modular, the pill would have been easier to swallow?

Cheers,
- Ole

>
> Regards,
> Gilles
>
>
> P.S. I think that several issues evoked in this thread could warrant opening
>      their own thread, to gather more opinions on actual actions to be taken.
I think that would be good.  Some of these topics could definitely use a different subject
heading.
- Exception removal / Enum coding of errors
- I18N messages corresponding to Enums
- Callbacks
- Asynchronous option
- JDK9 Modularity
- JDK8 Stream API (At least if streams are used, then CM is one steps closer to simple concurrency).

There were a few more cans that I did not open yet.  One is wrapping method arguments in a
self validating context, eliminating the need for CM method calls to check and throw exceptions
for things like nulls, etc.

Instead the client would construct the context with all parameters. The code would call:

context.valid(CB);

If the context is invalid, then the CB.notify(ErrorEnum code) is called.  This removes exceptions
due to invalid arguments.

>
>
>> Cheers,
>> - Ole
>>
>> P.S. Dang that was a long email.  If I write one more of these, ban me :)
>
> My fault: I should not keep answering! ;-)
I'm banning myself :)

>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message