[Insight-users] Criterion to stop 1+1_evolutionary optimizer?

[Zachary Pincus]

The "current criteria" I was referring to is the frobenius norm of the 
"A" matrix. The units of this norm are the units of the dimensions 
being optimized over. So if all the dimensions are measured in the same 
units, or are properly scaled (if that's even possible), then the 
fro-norm criteria has meaningful units.

For example, if you're only optimizing over x any y translation in mm, 
then setting the initial search radius to 3 means that the gaussian 
will be sampled with a 3 mm variance. Setting the convergence criteria 
to "0.1" means that the optimizer will declare convergence when the 
search radius has shrunk to approximately 0.1mm variance.

That's how the optimizer was supposed to behave since it was first 
added to ITK. Note, however, that there were a few errors in the 
optimizer, which I noticed and fixed *AFTER* the 2.0.0 release. If you 
want this optimizer to work properly for you, I strongly suggest 
grabbing a CVS copy of ITK -- or at least the optimizer.

Zach


On Mar 17, 2005, at 6:29 AM, Li, George (NIH/NCI) wrote:

> Thanks, Zach:
>
> Your explanation is quite clear and informative. One
> Question on your comment of "The good thing about
> The current criteria is that it has semi-meaningful
> Units", is the "current criteria" available already
> In itk2.0.0? I may have missed something. Are you
> referring it as what you would do or have done? Would
> it be available in ITK eventually or sometime soon?
>
> Regards,
>
> George
>
>
> -----Original Message-----
> From: Zachary Pincus [mailto:zpincus at stanford.edu]
> Sent: Wednesday, March 16, 2005 10:38 PM
> To: Li, George (NIH/NCI)
> Cc: 'Insight-users at itk.org'
> Subject: Re: [Insight-users] Criterion to stop 1+1_evolutionary 
> optimizer?
>
>
> Hi George,
>
> Luis and I had recently been discussing the 1+1 optimizer's stopping
> criterion, actually. While Stephen's comments seem right on in terms of
> the big picture, I figure I'll give what insight I have specifically
> about the evolutionary optimizer.
>
> Here's how the evolutionary optimizer works: it takes random steps
> drawn from a n-dimensional gaussian. If a step is good, then the
> covariance matrix of the gaussian is stretched such that there is more
> density in the "good" direction; conversely if a bad step is taken then
> the matrix is shrunk to put less density in the bad directions. In this
> way, the optimizer becomes biased toward searching in "profitable"
> directions.
>
> The "growth factor" controls how much the covariance grows with good
> steps, and the "shrink factor" controls how it shrinks with bad steps.
> Now, when the optimizer finds a optimal point, every step it takes
> subsequently will be a "bad" step, so the covariance matrix will shrink
> with each step. The stopping criteria is defined as the "size" of the
> covariance matrix. (Actually, it is the frobenius norm of the "A"
> matrix, where the covariance is A'A.)
>
> The frobenius norm of A decreases approximately by the shrink factor
> with each bad move. A is initialized as the identity matrix times the
> initial search radius. If scales are set, then the entries of A are
> divided by the scale for the corresponding dimension. So what I do to
> choose the stopping criterion is to calculate the initial frobenius
> norm of A, and decide how many bad steps I'm willing to tolerate before
> declaring convergence. I then set the shrink factor and stopping
> criteria accordingly.
>
> One could also modify the optimizer to either (a) take the number of
> "bad" steps in a row as the stopping criteria, or (b) use the ratio of
> the initial frobenius norm of A to the current norm as the stopping
> criteria. These might be easier for users to set. The good thing about
> the current criteria is that it has semi-meaningful units. (If it is
> optimizing three dimensions of translation in mm, then the units of the
> initial search radius and stopping criteria will also be mm.)
>
> Zach Pincus
>
> Department of Biochemistry and Program in Biomedical Informatics 
> Stanford
> University School of Medicine
>
>
> On Mar 16, 2005, at 1:06 PM, Li, George (NIH/NCI) wrote:
>
>> Hi, Luis and all itk users:
>>
>> I have found the multi-resolution samples. So, I am
>> Now upgrading my registration program for a better and
>> More attractive performance.
>>
>> For OnePlusOneOptimizer, The growth factor seems to be
>> A suitable variable to control the fitting speed for
>> Each pyramid. However, how to set a stopping criterion
>> Seems unclear to me.
>>
>> Anyone has experience or idea on this matter?
>>
>> Thanks,
>>
>> George
>>
>>
>>
>> -----Original Message-----
>> From: Li, George (NIH/NCI)
>> Sent: Tuesday, March 15, 2005 12:28 PM
>> To: Li, George (NIH/NCI); 'Luis Ibanez'
>> Cc: Insight-users at itk.org
>> Subject: Registration performance
>>
>>
>> Hi, Luis:
>>
>> Sometime ago, you commented on improving performance
>> As the following. I now understand what you meant by Multi-resolution.
>> However, is there any sample code For its implementation?
>>
>>> Trivial answer to your question about performance:
>>>
>>>             The way to improve performance
>>>              is to use multi-resolution.
>>>
>>> You can register volumes of size 200x200x200 pixels
>>> in about 20 seconds when using 3 levels of a multi- resolution
>>> pyramid, by subsampling by 2 at each level, in a typical Pentium 4
>>> machine at 2Ghz, and 512Mb of memory.
>>
>> Now, it seems that the registration performance has
>> Become a big issue to me, and some 20 seconds for a Registration is
>> much attractive, comparing with a few minutes.
>>
>> So, could you further provide some guidance on it?
>>
>> Thanks,
>>
>> George
>> _______________________________________________
>> 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
>