[Martin Taylor 960216 17:50]

Today my retired mathematician friend came in and we started a little

simulation of an e-coli approach to a central target in N-dimensions,

with the new twist that the seeker could move only in steps of exactly

one unit, and if it moved in the wrong direction it would choose a new

direction from the place it reached (i.e. it didn't know how to get back

where it just came from). The rules are as follows.

1. Choose a start point.

2. Choose a direction at random and move one unit in that direction.

3. See if the new place is closer to target than the old. If yes, make

another unit move in same direction, and repeat step 3. If no, go to step 2.

4 (at least today). Stop after several thousand steps, when the

experimenter gets bored with watching the results on the screen.

As we ran it today, it was just a test run, so we looked at a representation

of the mean distance from target and the standard deviation of that distance

averaged over the previous 10,000 executions of step 2 above. We originally

intended to see how quickly the seeker halved the distance to the target,

starting at various start distances, but it turned out that the seeker

actually oscillated around an equilibrium value rather than going to the

target. If the dimensionality was small enough, the fluctuations around

the equilibrium might bring it below threshold, but then it would be likely

to move away again, so we thought this was not a very useful datum.

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 holds from

about D=4 to D=256, to judge from by-eye averaging of the 10,000 point

averages.

The standard deviation of the seeker's position was equal to 1+epsilon times

the mean, where epsilon ranged from (by memory) 0.06 at D=4 to .006 at D=64

(the only two conditions except the uninteresting D=1 that we tried before

the mathematician went home). I find this a most intriguing result, but at

the moment I don't know what to make of it.

Conclusion. If e-coli cannot "go home" to where things were better, but

must go from wherever he arrived, and if it takes a finite distance before

he can determine whether things have improved, then he will not reach an

optimum but will reach some reasonably stable equilibrium distance from

the optimum. This clearly applies to reorganization by flipping the sign

of a connecting link. It probably does not apply to smooth alteration of

connection weights.

Probably we'll look some more at the problem next week.

Martin