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

[Zachary Pincus]

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
>