[Insight-users] Re: ITK SPSA optimizer: StateOfConvergence
question and SetScales bug.
Zachary Pincus
zpincus at stanford.edu
Tue Jun 28 14:35:29 EDT 2005
If you guys (and Luis? are you reading this) agree, I'll strike out the
StateOfConvergence code from the optimizer and add comments suggesting
that users add their own convergence detectors from a callback.
I'll also send a message to ITK-dev asking what they think about the
termination criteria situation in general and whether having a set of
prefab callbacks would be a good goal to add to the ITK roadmap or
whatever.
Zach
On Jun 28, 2005, at 10:21 AM, Stefan Klein wrote:
> Hi,
>
>
>> As for the termination criteria, I agree that it sounds like a great
>> idea to have a stable of callbacks that people could attach to any
>> optimizer to achieve their desired termination criteria. This would
>> be much better than the current situation.
>
> I like this idea as well.
>
>> Given that that's in the future, do we want to do anything about the
>> termination condition as it exists now in the SPSA code? (Even
>> something as minimal as providing a reference to where a scheme like
>> the StateOfConvergence stuff is described, so users could read
>> something for guidance would be valuable.)
>
> Maybe it would be better to just remove this whole convergence check
> and only terminate when the maximum number of iterations has been
> reached. It will save us from some parameters to choose. :)
>
> Stefan.
>
>
>
>> For my use, I'll probably just attach an observer and equip it with
>> whatever termination condition I need.
>>
>> Zach
>>
>> On Jun 27, 2005, at 7:34 AM, Mathieu De Craene wrote:
>>
>>> Le Monday 27 June 2005 à 13:32 +0200, Stefan Klein a écrit :
>>>> Hi Zach,
>>>>
>>>> Thanks for your careful review of this code :)
>>>>
>>>>
>>>>> (1) The convergence test is a bit unfamiliar to me. Since it's not
>>>>> what is described in Spall's papers on SPSA, reading them didn't
>>>>> help clarify matters.
>>>>>
>>>>> In general, I'm familiar with convergence tests that look at how
>>>>> much the value of the objective function has changed, or how much
>>>>> the parameters have changed, or how close the gradient magnitude
>>>>> is
>>>>> to zero. However, the "StateOfConvergence" test in the SPSA class
>>>>> is
>>>>> more unclear. Optimization terminates if StateOfConvergence is
>>>>> less
>>>>> than some threshold, where StateOfConvergence starts at zero and
>>>>> is
>>>>> updated as follows:
>>>>> StateOfConvergence <= DecayRate * (StateOfConvergence +
>>>>> LearningRate
>>>>> * GradientMagnitude)
>>>>>
>>>>> Could anyone give some guidance as to why this criteria was chosen
>>>>> over more simplistic tests such as mentioned above, and how to
>>>>> choose the threshold and decay rate parameter appropriately?
>>>>> (Naively, it seems that if the gradient starts large and then goes
>>>>> to zero, optimization could continue for some time as the "state
>>>>> of
>>>>> convergence" parameter decays, even though the optimum has already
>>>>> been found. Likewise, if the decay rate is too large, optimization
>>>>> could be terminated prematurely. Thus, choosing the right decay
>>>>> rate
>>>>> seems very important, but it is not clear how best to do so!)
>>>> Good question. I copied this part from Mathieu's code, so he may be
>>>> better able to answer this question. The problem of 'traditional'
>>>> convergence tests is that they stop if the test has been satisfied
>>>> once. In stochastic optimisation it is not unlikely that in one
>>>> iteration a zero gradient is measured, but in the next iteration
>>>> still
>>>> progress is being made. Moreover, the gradient magnitude does not
>>>> always cancel at the optimum (due to the stochasticity; that's why
>>>> the
>>>> decreasing gain sequence is needed). Mathieu's method tries to
>>>> attack
>>>> this problem, but I do agree now that the parameters are quite
>>>> hard to
>>>> choose properly.
>>>>
>>>> Would the following test be better maybe?:
>>>>
>>>> If ( (newPosition - currentPosition).magnitude() <
>>>> m_SomeUserEnteredThreshold )
>>>> {
>>>> m_NumberOfVerySmallSteps++;
>>>> if (m_NumberOfVerySmallSteps >=
>>>> m_UserEnteredMaximumNumberOfVerySmallSteps)
>>>> {
>>>> this->StopOptimization();
>>>> }
>>>> }
>>>> else
>>>> {
>>>> m_NumberOfVerySmallSteps = 0;
>>>> }
>>>>
>>>> The parameters to set are maybe more intuitive in this way.
>>>
>>> I have to confess that in my experiments, the convergence test
>>> always
>>> fails (for a registration application I mean) and the optimizer
>>> performs
>>> the maximum number of steps specified by the user. On synthetic cost
>>> functions however, it works well. My only conclusion is that this
>>> might
>>> not be the best test for noisy cost function such the ones we play
>>> with ;-) I like the scheme suggested by Stefan.
>>>
>>> In fact, this discussion is not specific to spsa... Maybe it would
>>> be
>>> better on a general point of view to use an observer on the
>>> optimizer so
>>> that the user can call the StopOptimization() method when his own
>>> convergence criterion is satisfied. This is more a question for ITK
>>> designers... Having a lot of various convergence tests embedded in
>>> different optimizers is not so modular.
>>>
>>>>
>>>>> (2) I think that there might be a bug in how the Scales parameter
>>>>> is
>>>>> used to scale the perturbations and the gradient value. I've read
>>>>> the email thread from a few months ago concerning this, but I
>>>>> think
>>>>> there's a bug in the implementation that breaks this slightly.
>>>>>
>>>>> The logic for dealing with the scaled delta (perturbation) values,
>>>>> as commented at the bottom of the ComputeGradient() method in
>>>>> itkSPSAOptimizer.cxx (lines 414-451), assumes that scaling is
>>>>> accomplished by dividing by sqrt(Scales). This sqrt(Scales) term
>>>>> eventually is transferred to a numerator, and thus to correct for
>>>>> that (i.e. put the scaling term back in the denominator where it
>>>>> belongs), the comment suggests an additional division by Scales.
>>>>> However in the actual code, the scaling is done (as it should be!)
>>>>> by dividing by Scales. However, in the code the correction remains
>>>>> an additional division by Scales, when it should be by Scales^2
>>>>> (as
>>>>> per the logic in the comment). Thus, the scaling factor winds up
>>>>> being canceled out entirely, instead of being transfered from a
>>>>> numerator to a denominator as a division by Scales^2 would
>>>>> properly
>>>>> do.
>>>> You are very right. If you use sqrt(Scales) you should divide by
>>>> Scales later; if you use Scales, you should use Scales^2 later. I
>>>> was
>>>> in a doubt whether to use the first or second option; i forgot why
>>>> I
>>>> chose for the first option, but the second option (that you propose
>>>> now) indeed gives the desired scaling, so is better!
>>>>
>>>> Kind regards,
>>>> Stefan.
>>>>
>>>
>>> I am a bit perplex about how we have to deal with scales... As far
>>> as I
>>> understand, we could always use Scales of 1 for each parameter and
>>> adapt
>>> the transformation for having parameters evolving in the same
>>> range...
>>> That's how I deal with Scales in my rigid registration code... But I
>>> know this is not the ITK way of seeing things. Sometime, a linear
>>> mapping of the parameters space is not the best thing to do : when
>>> optimizing the parameters of an affine transformation, it's good to
>>> have
>>> the x,y and z scaling factors evolving from -inf,+inf instead of
>>> 0,+inf.
>>> So a logarithmic mapping of these parameters is a good trick...
>>>
>>> Is there a gradient descent optimizer in ITK where the gradient is
>>> estimated using finite differences ? It could give us some
>>> inspiration
>>> no ?
>>>
>>> Math.
>>>
>>> --
>>> Mathieu De Craene <decraene at tele.ucl.ac.be>
>>> 010 47 93 53 - 0478 51 54 54 (cell) - 010 47 20 89 (fax)
>>> http://www.tele.ucl.ac.be/~decraene
>>>
>>> _______________________________________________
>>> Insight-users mailing list
>>> Insight-users at itk.org
>>> http://www.itk.org/mailman/listinfo/insight-users
>
> _______________________________________________
> Insight-users mailing list
> Insight-users at itk.org
> http://www.itk.org/mailman/listinfo/insight-users
More information about the Insight-users
mailing list