[From Bill Powers (950210.1900 MST)]
Martin Taylor (970209 13:40)--
What this means is that the e-coli technique will work, even in
high dimensional spaces, provided that the current position is not
too close to the optimum. For an example, in a space of 2048
dimensions, there is a probability of at least 0.2 that a step of 1
unit will result in an improvement if the current position is
further than 22 units from the optimum (and the space is uniform in
respect of penalty for distance from the optimum).
You are reporting a result that is of very great interest for PCT -- as
you know. Previously it has been thought that in very high-dimensional
spaces (i.e., many independent control parameters needing to be adjusted
at the same time) the e. coli type of reorganization would be far too
slow to accomplish anything. So we had been thinking that we need a way
to make reorganization more specific, perhaps by localizing it in every
control system. While localized reorganization is still a reasonable
concept, thanks to you and your colleague we now know that it's not the
only choice. I think this discovery ranks with the initial demonstration
via the e. coli effect that random reorganization could lead to far more
efficient operation of one or two parameters than I had thought possible
when writing B:CP. We now know that the number of parameters that can be
adjusted simultaneously on the basis of a _single_ intrinsic error can
be in the thousands without making the process unreasonably slow.
The way you report your results is somewhat hard to figure out. Let's
see if I understand the following:
Dim Minimum distance
for p>0.05 p>.20 p>.30
1024 10.0 14.5 23
I take it that this means that if the steps are of size M, with 1024
dimensions, there is better than a 1 in 20 chance of an improvement per
step if the distance to the goal value is 10M, better than 1 in 5 if the
distance is 14.5M, and better than 1 in 3.3 if the distance is 23M.
OR: if we are at a distance of R from the optimum position, then to get
a 1 in 3 chance of a favorable move per iteration, we should make the
step size R/23. Is that also a correct way of putting it?
And another way to say it is that if we are making random steps in a
1024-dimensional world, and find that we get an improvement only about
one time in 3, the goal must be about 23 steps away (in some direction).
OK?
The e. coli principle is just a little different, but I think critically
so, from the way you've set up the problem. In the e. coli method there
is an underlying constant velocity vector. In the 2-D case, a favorable
direction leads (in the simplest case) to suspending random tumbles. The
swimming continues, iteration after iteration, until finally the
projection of the velocity vector onto the current radius from the
target goes negative. Then there is a random change in direction, or a
series of random changes until a favorable direction is found again. If
there is a series of random changes, they occur at intervals just long
enough to detect that the direction is still unfavorable. So there are
bursts of tumbles interspersed with periods of movement in a constant
direction.
If you just do random changes in _position_ in hyperspace, lengthening
or shortening the period between tumbles will have no influence on the
outcome. You will perform exactly the same random walk as you would if
you just did the jumps as fast as possible, except that sometimes there
would be longer pauses between jumps and sometimes shorter pauses. The
pattern of positions would be the same in either case, and would be
unbiased.
When you change the intervals between altering the direction of a
constant velocity vector in hyperspace, now you can bias the random walk
by leaving the direction the same as long as the error keeps shrinking,
and introducing a random change in direction only when the rate of
change of error goes positive. This guarantees that the total distance
travelled in a favorable direction will be greater than the total
distance travelled in an unfavorable direction. That's the e. coli
principle.
The result you have so far (and the upcoming one with a constant step
size) takes us part of the way by showing that there is a useful
probability that a direction selected at random will be favorable. But
to finish the analysis, we need to know what will happen if a velocity
is established in that direction, and the line in that direction is
extended until finally further progress would start to take us away from
the center again. If you do the e. coli simulation you will see that
this is how it works; if the spot is headed reasonably "toward" the
target, you just let it travel until it gets as close to the target as
it is going to get, and _then_ you start hitting the space bar until you
get a direction that promises a still-closer approach. This also works
when all you can see is the absolute magnitude of the radius to the
target; you refrain from hitting the space bar as long as the radius is
decreasing. Eventually it will increase again, of course, because of the
underlying two-dimensional geometry, but you don't need to know _why_ it
does this.
A full analysis of the problem requires taking the reference signal into
account. When e. coli has a positive nonzero reference signal for the
rate of increase of the nutrient, this is equivalent to defining an
angle to left and right of the optimum direction that is less than 90
degrees each way, or in 3 dimensions, a cone. Tumbles will occur when
the result is a direction lying outside the angle or cone, even if the
resulting rate is still somewhat positive. This makes for more tumbling,
but more progress toward the goal when a favorable result does occur.
Again there is probably an optimum setting of the reference signal,
because the more positive the reference signal is, the lower the chances
are of finding a direction that does not immediately result in another
tumble, but the closer to zero the reference signal is, the more
progress will be made at a large angle to the right direction.
When this analysis is combined with the analysis you and your colleague
are working on, we will have a complete picture of how the e. coli
method will work as a way of correcting multidimensional errors on the
basis of a single sum of squared errors. I think such a result, aside
from being very important to PCT, could stand on its own as a
mathematical achievement of great usefulness, in the category of methods
of steep descent.
Thanks, Martin, for keeping this line of enquiry going forward.
···
----------------------------------------------------------------------
Bill Leach (950209.21:37 EDT)--
When they finally pulled the cork out of your email system, the pressure
must have been incredible. How much more of that is still bottled up in
there?
I found all your posts very pleasing to read, perhaps most especially
the one where you were talking about the difficult realization that PCT
was not going to support (or deny) your favorite ideas. This, to me, is
the critical realization, the one that turns a person from a passenger
on the PCT bandwagon into a driver. Most people who come into PCT come
with an agenda that they've been developing for years. They see a few
concepts that seem to support them, and accept PCT for that reason
alone. It takes a couple of years of sincere study to realize that PCT
doesn't give a damn about your pet social program, your religion, your
politics, your generalizations, or your delusions. PCT is just an
attempt to understand how human behavior works, no matter what behavior
it happens to be. And to the extent that it succeeds in that attempt, it
takes us to a completely different plane of understanding, and puts all
older pet ideas into a new light. You expressed that very beautifully.
It's interesting to me how the old agendas hang around for a long time,
yet in those who have grasped the basic nature of PCT, they come under
conscious scrutiny in a way that never happened before, and PCT becomes
the viewpoint from which they are seen. We can always drop back to the
old-agenda points of view and have interesting arguments, but I think we
are all pretty sure that the real solutions of the world's woes are not
going to be found at that level of understanding.
-----------------------------------------------------------------------
Rick Marken (950208.1945)--
Very nicely put, all the way through. Reading your posts is sometimes
extremely boring; I agree with everything.
-----------------------------------------------------------------------
Best to all,
Bill P.