[Insight-developers] Re: SPSA Optimizer

Mathieu De Craene decraene at tele.ucl.ac.be
Thu Mar 24 05:47:35 EST 2005


Hi Stefan, 

Thanks a lot for such a nice work. I just would like to make sure I
understand the way to deal with scales in optimization.

If we refer to the classical gradient descent optimizer,
http://www.itk.org/cgi-bin/viewcvs.cgi/Code/Numerics/itkGradientDescentOptimizer.cxx?root=Insight&view=markup
it seems there is to phases. In the first one, the gradient is computed
without taking into account the scales
	m_CostFunction->GetValueAndDerivative( 
	this->GetCurrentPosition(), m_Value, m_Gradient );
In the second phase, the scales are applied to the gradient before
updating the parameters
	transformedGradient[j] = m_Gradient[j] / scales[j];

In your implementation, you take into account the scales in the first
phase (gradient computation) when applying the perturbation 
	m_Delta[j] /= sqrt(scales[j]);

I understand than applying too big perturbations can bring the optimizer
in a region where the metric is not nicely behaving... But aren't we
biasing the gradient computation using this trick ? 

Dank voor de moeite,


Math.


Le jeudi 24 mars 2005 à 11:08 +0100, Stefan Klein a écrit :
> Hi Mathieu, Daniel and others,
> 
> I put together a new SPSA optimizer, based on the three version that
> we had. I also added a Test.
> 
> You may download the zip from:
> http://www.isi.uu.nl/People/Stefan/
> 
> 
> > - what should be the default values for a, A, C?
> >     - I used a=A=c=0.1  (Don't trust my implementation...)
> >     - Mathieu uses a=01.6, A = 60(!), C=0.01
> >     - Stefan uses a=A=c=1.0
> > - Are we OK with Alpha = 0.602, Gamma = 0.101?
> 
> alpha = 0.602 and gamma = 0.101, as J. Spall suggests.
> 
> c depends on the amount of noise in your problem and the range of your
> parameters, so could by anything. So, 1.0 seemed the most appropriate
> to me as a default.
> 
> a depends on your specific problem as well, so is set to 1.0 by
> default.
> 
> A is set to 10.0, which is 10% of the default
> MaximumNumberOfIterations.
> 
> The Scales thing gave me quite a headache but I think I did it correct
> now. In the .cxx I tried to explain why I did it like i did...
> 
> Please let me know what you think about it!
> 
> Regards,
> Stefan.
> 
> 
> At 10:04 18/03/05, Mathieu De Craene wrote:
> > Le jeudi 17 mars 2005 à 09:10 -0500, Blezek, Daniel J (Research) a
> > écrit :
> > > Stefan, Marius, Mathieu,
> > >  
> > >   Excellent.  I liked the try / catch blocks, and the stopping
> > > criteria in Mathieu's implementation.  Essentially, the code is
> > the
> > > same across all 3 implementations...  As you would expect from the
> > > nicely written paper.
> > >  
> > > - what should be the default values for a, A, C?
> > >     - I used a=A=c=0.1  (Don't trust my implementation...)
> > >     - Mathieu uses a=01.6, A = 60(!), C=0.01
> > 
> > 
> > In fact, this value should be changed to 0.5 or 1. I used a Set()
> > method
> > in the main code to change the default value. For rigid registration
> > for
> > instance, I doubt you will measure anything by changing the
> > translations
> > coefficients by 0.01 mm ;-)
> > 
> > If the A coefficient is big, it means that the optimizer will make
> > big
> > steps at the initial iterations.
> > An idea of the successive trials made by the spsa optimizer in rigid
> > registration can be seen on this animation :
> > http://www.tele.ucl.ac.be/~decraene/anims/RIGID.mpeg
> > 
> > I think it is good to keep this parameter big enough if we want to
> > keep
> > the robust behavior of this optimizer.
> > 
> > >     - Stefan uses a=A=c=1.0
> > > - Are we OK with Alpha = 0.602, Gamma = 0.101?
> > >  
> > 
> > I have never experimented other set of values but these work fine
> > for
> > me ! 
> > 
> > >  
> > > -dan
> > >         -----Original Message-----
> > >         From: Stefan Klein [mailto:stefan at isi.uu.nl]
> > >         Sent: Thursday, March 17, 2005 8:55 AM
> > >         To: Blezek, Daniel J (Research); Mathieu De Craene
> > >         Cc: Insight-users at itk.org; insight-developers at itk.org
> > >         Subject: RE: [Insight-users] some contributions
> > >         
> > >         
> > >         Eh, but then we'll have 2 SPSA-optimizers....
> > >         Wouldn't it be the best to have one that combines the good
> > of
> > >         all 3 versions?
> > >         
> > >         plan:
> > >         - we include the scales thing and the test and some
> > elements
> > >         from Mathieu's implementation
> > >         - we'll mail it to the list.
> > >         - you check it (if we combined all features correctly) and
> > >         correct it
> > >         - Daniel commits it to the itk.
> > >         
> > >         Marius&Stefan.
> > >         
> > >         
> > >         
> > >         At 08:39 17/03/05, Blezek, Daniel J (Research) wrote:
> > >         > Oddly enough, I also have an implementation of the SPSA
> > >         > algorithm!  I offered to put Stefan's implementation in,
> > >         > provided he account for m_Scale and write a test.  I'll
> > make
> > >         > the same offer for you, Mathieu.  I've put my code on
> > the
> > >         > itk Wiki @ http://itk.org/Wiki/SPSAOptimizer however, I
> > >         > haven't tested my code very well, as it's new.
> > >         > 
> > >         > -dan
> > >         > 
> > >         > -----Original Message-----
> > >         > From: insight-users-bounces at itk.org
> > >         > [mailto:insight-users-bounces at itk.org]On Behalf Of
> > Mathieu
> > >         > De Craene
> > >         > Sent: Thursday, March 17, 2005 8:20 AM
> > >         > To: Stefan Klein
> > >         > Cc: Insight-users at itk.org; insight-developers at itk.org
> > >         > Subject: Re: [Insight-users] some contributions
> > >         > 
> > >         > 
> > >         > Le mercredi 16 mars 2005 à 21:34 +0100, Stefan Klein a
> > >         > écrit :
> > >         > > Hi all,
> > >         > > 
> > >         > > We have created some classes that are useful for us.
> > We
> > >         > hope also for other 
> > >         > > people, so we would like to contribute them. The code
> > can
> > >         > be found for 
> > >         > > download on:
> > >         > >       http://www.isi.uu.nl/People/Stefan/
> > >         > > 
> > >         > > - itkEulerTransform.h: This class is a wrap around the
> > >         > Euler2DTransform and 
> > >         > > the Euler3DTransform. In this way it is templated over
> > the
> > >         > dimension, like 
> > >         > > other Transform-classes.
> > >         > > 
> > >         > > - SimultaneousPerturbation.zip: This class implements
> > the
> > >         > so-called 
> > >         > > Simultaneous Perturbation method as an ITK optimizer.
> > For
> > >         > more info on this 
> > >         > > optimization method, go to:
> > >         > >       http://www.jhuapl.edu/SPSA
> > >         > > 
> > >         > 
> > >         > I have also have some code for SPSA optimization. I
> > found it
> > >         > quite
> > >         > useful for rigid registration (it seems to be pretty
> > >         > robust). The source
> > >         > code for a rigid registration application based on ITK
> > is
> > >         > available on 
> > >         > 
> > >         > http://euterpe.tele.ucl.ac.be/Waleo2/vesale/
> > >         > 
> > >         > I would like to compare our implementations of this
> > >         > optimizer.
> > >         > 
> > >         > Regards,
> > >         > 
> > >         > Mathieu.
> > >         > 
> > >         > > - FullSearch.zip: This class implements a (semi-)Full
> > >         > Search optimization 
> > >         > > routine. This can be useful for research, to scan the
> > >         > optimization surface, 
> > >         > > or to evaluate the result of other optimizers. It
> > allows
> > >         > the user to
> > >         > > specify which parameters should be evaluated, in which
> > >         > range.
> > >         > > 
> > >         > > Since we have contributed 3 things now, we also have a
> > >         > feature request; as 
> > >         > > a reward :-)
> > >         > > 
> > >         > > Would it be possible to add a public function to the 
> > >         > > MattesMutualInformationImageToImageMetric that forces
> > the
> > >         > metric to select 
> > >         > > new spatial samples? This would be useful if you would
> > >         > want new spatial 
> > >         > > samples every iteration for example.
> > >         > > 
> > >         > > We hope that the contributions are useful. Any
> > comments
> > >         > are welcome!!
> > >         > > 
> > >         > > Marius and Stefan.
> > >         > > 
> > >         > > 
> > >         > > Marius Staring, Stefan Klein
> > >         > > Image Sciences Institute
> > >         > > University Medical Centre Utrecht
> > >         > > Heidelberglaan 100, 3584 CX Utrecht, The Netherlands
> > >         > > phone: +31 (0)30 250 3186, fax: +31 (0)30 251 3399
> > >         > > {marius,stefan}@isi.uu.nl,
> > >         > > http://www.isi.uu.nl/People/Marius
> > >         > > http://www.isi.uu.nl/People/?stefan
> > >         > > 
> > >         >
> 



More information about the Insight-developers mailing list