commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Phil Steitz <phil.ste...@gmail.com>
Subject Re: [math] Testing for convergence in iterative algorithms
Date Tue, 09 Aug 2011 08:18:47 GMT
On 8/8/11 10:41 PM, S├ębastien Brisard wrote:
> 2011/8/8 Phil Steitz <phil.steitz@gmail.com>:
>> Sounds reasonable.  Have a look at the StoppingCondition interface
>> and its implementations in the genetics package.  Something like
>> that would probably work.
>>
>> Phil
>>
> I wasn't aware of o.a.c.m.genetics.StoppingCondition. It's exactly
> what I would need, only slightly more general. Instead of a
> Population, the StoppingCriterion should be passed the "state" (for
> what that means) of the iterative solvers.

Right.  Just need to decide how to encapsulate that state. 
Interestingly, the Population abstraction in the genetics package
provides another good example to consider following here.  It is
very similar in its context to the state of an iterative numerical
algorithm.
>
> So at the moment, stopping criteria are implemented in at least two
> different places in Commons Math
>   - o.a.c.m.optimization.ConvergenceChecker.converged(int iteration,
> PAIR previous, PAIR current)
>   - o.a.c.m.genetic.StoppingCondition.isSatisfied(Population population)
>
> Do we want to reconcile these two different implementations of the
> same concept? I think it would be interesting to give a thought about
> iterative algorithms at large, and design some general classes that
> support the implementation of such an iterative algorithm.

Interesting idea.  Lets see where it goes.
>
> Here are a few (obvious) thoughts on what makes an iterative
> algorithm. Maybe that could help.
>   - Iterative algorithms obviously iterate, so they probably keep an
> eye on the current iteration number. Besides, an upper bound on the
> total number of iterations must be set. As was suggested, this hints
> at the use of o.a.c.m.util.Incrementor.

Another thing to keep in mind is that in some cases the stopping
criteria is the number of function evaluations.  But yes, IIUC the
intent, all of these kinds of counts can be represented using the
Incrementor.
>   - Iterative algorithms update their *state*, whether this is a
> Population, a RealVector, or anything. So from one iteration to the
> next, the state changes.

Yes, at least that is how we think about them.  In some cases,
obviously state ends up in some kind of attractor or divergent
condition that makes it not change any more; but the point of the
iteration is to evolve the state.

>   - The iterative scheme itself can be quite long, and it might be
> interesting to have a way to *listen* to the algorithm while the
> iterations take place (for example, to back-up the whole thing). This
> relates to the thread on "Monitors".

Yes, I think we all agree we need to have a way to do this.
>   - The last two points bring up a new question (I think). Let us
> imagine that at the end of each iteration, the Iterative Algorithm
> calls monitor.update(state). Then the monitor can access the updated
> state of the Iterative Algorithm, and possibly *alter* it, which might
> ruin the whole thing. This would call for monitor.update() being
> passed a *copy* of the updated state, which might be unefficient, no
> (if the computation works on large data sets)?

This gets problem and implementation-dependent quickly, but I think
in principle it would be a good idea to ensure that only immutable
objects bearing information about state could be carried on events
propagated via the monitoring framework.  At the same time, in some
cases, it might be good to allow monitors to halt or change
execution via established interfaces.  JMX provides some good
examples to think about here.  You can start and stop web
applications in Tomcat, for example, via JMX and you can see how
many active sessions there are, etc; but you can't get a reference
to a user session to play with (at least I hope not :)
>   - The iterations should stop at some point. If the maximum iteration
> count has been reached, an exception should generally (but not
> necessarily) be thrown, this is taken care of by the Incrementor.
> Otherwise, it means that the algorithm has reached a *satisfactory*
> state. What satisfactory means depends on the actual problem at hand.
> For optimization purposes, it really means "stable": the current
> solution is not much different from the previous solution (the
> previous state must be kept in some place). For linear solvers, it
> means: the residual is small enough (only the current state is used).
> Both approaches might be reconciled by the same method hasConverged()
> which would take anything as a parameter (a pair of RealPointValuePair
> --previous and next--, a residual,...).

Here we have the StoppingCondition again.
>
> So a few concepts emerge: Iterative Algorithm, State, Incrementor,
> Observer (or monitor, or listener...), Convergence Criterion.
>
> Maybe that takes us too much on the philosophical side, in which case
> the discussion should be closed soon. As for me, I'm very much
> interested...

The tricky bit here is a) how to encapsulate state in a generic way
that has enough substance to it to be actually useful and b)
similarly how to do the same for convergence.  I am probably too
influenced by the topological connotation of the latter term which
makes it seem basically different to me from what we have in the GA,
where we are not really trying to engineer convergence of a sequence
in any topological space.  But it could be they can rightly be seen
as the same and Population in the GA should be a sublcass of
whatever we end up calling iterative algorithm state.

Another tricky bit is that in some of the examples you gave, history
as well as current state must be available to the StoppingCondition
- so just passing it current state is not enough.   It might
actually be better for the StoppingCondition to be what you are
calling a monitor - an event listener that can subscribe to the
events carrying the information that it needs.

As I said on the other thread, I think in any case a generic event
framework to support the "monitoring" requirement would be a good
thing to develop.

Phil
>
> Sebastien
>
> ---------------------------------------------------------------------
> 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