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

Zachary Pincus zpincus at stanford.edu
Wed Mar 16 22:38:28 EST 2005

```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

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?
>
>>
>>             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
>

```