commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gilles <gil...@harfang.homelinux.org>
Subject Re: [math] Negative max in class Incrementor
Date Sun, 30 Aug 2015 21:13:55 GMT
On Sun, 30 Aug 2015 14:45:19 -0500, Ole Ersoy wrote:
> On 08/30/2015 08:18 AM, Gilles wrote:
>> Hi.
>>
>> On Sat, 29 Aug 2015 22:21:55 -0500, Ole Ersoy wrote:
>>> I'm deleting most of the discussion, because I think I may be
>>> throwing too many ingredients on the table.  For further context
>>> please see the previous thread.
>>>
>>>> I don't get that.  Here the main purpose is to set a hard limit
>>>> that will raise an exception (to avoid that some algo from running
>>>> forever).
>>> Well there are two concerns here.  One is the precise number of 
>>> steps
>>> that should be executed and the other is whether we need to raise 
>>> the
>>> exception.
>>>
>>> To stop the algorithm from running forever we let the `end` 
>>> callback
>>> notify the thing doing the incrementing that we are done.  Does 
>>> that
>>> make sense?
>>
>> Not sure. The current usage is
>> 1. Set the hard limit (and action when that limit is reached)
>> 2. Let the incrementor do its thing (count and call "trigger").
> IIUC there are three ways of using IntegerSequence as is:
> A)
> 1) Initialize the incrementor
> 2) check canIncrement()
> 3) get the increment
> 4) check canIncrement()
> 5) Increment if we can
> 6) Check again...
> 7 If we can't increment, were done, so we get the result of whatever
> and move on.
>
> B)
> We register a calllback and just keep incrementing until the callback
> is called.
>
> C) We catch the MaxCountExceededException
>
> We should only do B, because A is wasteful and C is not necessary.

A is not used in CM
B and C are. The former in order to signal failure (unexpectedly large
number of iterations), the latter in order to change the exception into
a more meaningful one (catch and rethrow instead of registering another
callback).

>>
>> IIUC, you propose that the increment tells its caller that the
>> limit has been reached.
> The CB tells the caller that the limit has been reached.  If the
> incrementer extends the callback interface, and registers with the
> caller, then yes.  But the CB could be completely separate from the
> Algorithm instance and the incrementer.
>
>> Then, I suppose, the caller will have to
>> act, rather than the incrementor.
> Case A)
> Continue until we converge on a solution that's good enough.  We
> register the 'increment' CB which notifies the algorithm that we are
> 'good enough', and if we don't converge then the `end` CB is called,
> and we take whatever action is necessary.

That's a completely different way of handling the evaluation of the
result.  Currently this is part of the algorithm logic (through
"tolerance" parameters).

>
> Case B)
> We want to exhaust all the steps so we register an 'end' CB.  We want
> to find the best possible solution in the allowed number of steps (We
> already now that we will not find the global optimal).

Return whatever was found after some number of steps is dangerous.
There was a discussion about it in the past, and IIRC the conclusion
was that it would not be "standard" behaviour.
In the optimizers, the "ConvergenceChecker" interface can be subverted
to count iterations/evaluations and accept a solution that does not
match the convergence criteria.

I still don't see why some algo should pass through the incrementor
"service" (dealing with 3 callbacks) in order to evaluate the current
state of its work..

>> Unless I'm missing something, I don't see the advantage (in the
>> examples from CM).
>
> The advantages are that we eliminate:
> - `canIncrement()`
> -  `hasIncrement()`
> - incrementNTimes()
> - MaxCountExceededException
> - MaxCountExceededException CB boilerplate
>
> We gain a simpler API.

?
In CM, the throwing of an exception is mandated by the failure to
stop before counter exhaustion.

The other methods are used within the Incrementor class, to provide
the "Iterator" and "range" functionality. [Those are not used within
CM, but I thought that they were interesting...]

>>> Secondly suppose we expect a sequence like 5, 10, 15, 20...but the
>>> max is 17.  Do we loop past 17 and let that be the final loop, thus
>>> passing in 20 to the increment listener / cb, or do we stop at 15?
>>
>> The proposed IntegerSequence.Incrementor would trigger the callback
>> if "increment()" is called again after 15 is returned.
> I think it's better if we just leave it up to the designer to figure
> out the max number of steps.
>
>> Note that the increment does not stop by itself. If a range is 
>> created
>> its last value will be 15 (and the callback will never be called, by
>> construction).
> That's another reason why I like just specifying only:
> - start
> - stepSize
> - maxNumberOfSteps.
>
> It's very easy to understand.  The callback is called when the
> `maxNumberOfSteps` is reached  Not that the other way is that
> complicated either :).

In the basic usage (where the step == 1), it's fairly identical.

Sometimes a "range" might be more natural.

> One thing I am saying though that is that if the `maxNumberOfSteps`
> is reached and no `end` callback is registered, then we can still 
> call
> increment.  It just results in a noop().  An exception is not thrown.
> If the caller wants to be notified when the counter is done, they 
> have
> to register a callback.

What would a use-case for CM?

>>> By
>>> letting the developer calculate the number of steps, avoiding the 
>>> use
>>> of a max, we gain simplicity and flexibility.
>>
>> In all CM usage, the number of steps is unknown; the Incrementor is
>> intended to avoid an infinite loop.
>
> IIUC the max number of steps are known?  The number of steps until we
> converge are unknown...and could reach the max number of steps.

As I said, it is mainly a fool-proof way to indicate failure rather 
than
run forever if e.g. the problem uncovered some implementation bug or
numerical problem (as it happened in a root solver).

>>> Lastly perhaps the `increment` callback wants to notify the
>>> `incrementer / algorithm` that it's done.  In this case we only
>>> specify the `start` and `stepSize` arguments and leave it up to the
>>> `increment` callback to realize the termination point and stop the
>>> algorithm.
>>
>> Cf. previous paragraph.
> I think we are saying the same thing there.
>>
>> Termination of the counter is not the same as termination of the
>> algorithm.
> I understand.  By using an incrementor and a max we are incrementing
> either until:
> - the algorithm concludes
> - We reach a max and use the result

Dangerous (cf. above).  It's better to relax the convergence criterion
and be sure that the solution matches the request.

> - We reach a max and indicate an error because we could not converge
> on a result
>
> All of these can be handled in a `increment` CB and a `end` CB.

Sure, but it requires a redesign.  IIRC there was a proposal quite some
time ago to rethink the class hierarchy in terms of an 
"IterativeAlgorithm".

>>   In CM usage, the latter must occur first, and the second
>> signals a failure.
>
> So when the `end` CB is called we either succeeded or had a failure.
> The end CB can evaluate the results and determine either one.  The
> algorithm could also signal to the `end` CB whether the result is a
> failure or success.

To further discuss, we'd have to see a bigger picture of how it would 
apply
to e.g. the "o.a.c.m.optim" package.

Regards,
Gilles

>> P.S. I'll commit the "IntegerSequence" class. You can try and patch 
>> it
>>      (or design an alternative) to show what you mean on some 
>> specific
>>      CM use of the old "Incrementor".
>
> OK I think it would be fun to play more with this.  I've been meaning
> to experiment with JDK 8 asynchronous callbacks as well. Hope to get
> some free time soon!
>
> Cheers,
> - Ole


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


Mime
View raw message