[Martin Taylor 960219 11:00]
Bill Powers (960217.0100 MST)
RE: E. coli with discrete steps
Results: The seeker found an equilibrium distance from the target,
that distance being very close to 0.6*(log2(D))^2 where log2(D) is
the log of the dimensionality to base 2. (For example, log2(64) =
6, and the equilibrium distance at 64 dimensions was near 0.6*36.This is a curious result. I wonder whether it could be due to the fact
that the unit step, in the equilibrium case, is actually causing the
seeker to overshoot the target.
That's not the reason. The reason has to do with the curvature of the
hypersphere of constant distance from the target. It's hard to illustrate
in ASCII on a 2-D screen, but I'll try. X= current position of "seeker",
x the seeker position after a 1-step move not toward the target, T the
target position.
1-D |----| = 1 unit
-----x----X-------------T---------------
The seeker has a 50-50 chance of moving away from the target, but if on
any step it moves toward the target, it will continue to do so until it
has an overshoot. The overshoot will be less than one unit, and thereafter
the seeker will oscillate around the target, moving toward and away
equally often, but always when it moves toward it will reach and overshoot
the target. In fact, we found that the RMS distance was about 1.5 units^2,
presumably something like a Gaussian distribution centred on the target.
2-D
--- x
/ \ x
> T X x
\ / x
--- x
In 2D, if the seeker is close to the target, there is more than a semicircle
of possible places to go, in which the result is worse than the current
position. In fact, if the distance to the target from the current position
is d, the expected distance to the target after the step is sqrt(d^2 + 1).
If d is large, then the 1 unit step away doesn't matter much because the
probability of going inward is near 0.5, but if d is relatively small, that
probability goes down.
I can't draw higher dimensional things. If the dimensionality is N,
the expected distance after one step is still sqrt(d^2 + 1), but for the
seeker to move closer on average, the probability of it going inward more
than one step times the size of the inward move has to counterbalance
this expected outward move every time it makes a random choice of direction.
The higher the dimensionality, for a given radius, the lower the probability
that a move will be inward, and the smaller the expected component of the
move toward the target if it really is inward. (I think--we'll probably
check this out when we continue this later in the week).
When the step is infinitesimal, the probability of going inward is 0.5
regardless of the dimensionality. Unit size steps mimic, very crudely,
the situation when the seeker cannot immediately tell whether it is
getting closer to or further from the target (there might, for example,
be external disturbances).
Did you distribute this unit step among
the dimensions so that the length of the step vector remained 1 unit
(meaning that the length of the step in any one dimension would be less
than 1 unit)?
Yes. No problems of that kind (barring the always finite possibility of
programming error. But since I'm not the programmer, I think that possibility
more remote than it might have been).
The meaning of a "1-unit" step changes with the size of the
region in which the variables can change -- with what you consider to be
a unit of length, and its relation to the range of the variables.
Yes. We chose the unit step as a unit of scale. The equilibrium distance
can be stated as so many "potential steps" from the target--how many steps
it would take if the seeker dived directly in toward the target. Any other
scale distance in the space comes from external considerations. When you
think about optimizing in an e-coli-like manner, you have to think about
how quickly and accurately the seeker can change direction if things are
getting worse, as compared to how far from optimum you are. What you
have to do is to scale your problem space in terms of the ability of the
seeker to make that discrimination, or to make small steps, whichever is
the limiting factor.
We started all the examples from a beginning distance of 10 units, thinking
that the equilibrium effect would be much smaller than it turned out to be.
The intention was to map out for the different dimensionalities how long it
took the seeker to go from 10 to 5, and from 20 to 10, from 40 to 20, and
so forth. But we found that the time from 10 to 5 became longer than we were
prepared to wait at 16-D on our fastest computer, which is why we started to
investigate what the seeker was actually doing. No matter what the
dimensionality, the seeker will eventually come within delta of the
target, but it takes an extraordinarily long time for even a relatively
low-dimensional space when delta is not a substantial factor larger
than the step size.
Anyway, I probably shouldn't say too much more about this, since we have
only preliminary results and by-eye curve fitting to get the curve
d(equilibrium) = 0.6*(log2(D))^2. We should know more about it by the
end of the week.
Martin