Chapter II: Part 2

Coupling between isolated excitable (iron) sites is greatly affected by the fine structure and effective bulk resistivity of the glass and fluid medium which supports and fills the space between such sites. In general (see Section 3, following) it is necessary, to promote strong coupling between small structures, to impede the “short-circuit” return flow of current from an active or excited surface, through the electrolyte and back through the dendritic structure attached to the same excitable site. This calls for control (increase) of the bulk resistivity, preferably by means specifically independent of electrolyte composition, which relates to and affects surface phenomena such as recovery (_i.e._, the “refractory” period). Figure 2 illustrates the way in which this is being done, _i.e._, by appropriate choice of particle size distributions. The case illustrated shows the approximate proper volume ratios for maximum resistivity in a two-size-phase random mixture of spheres.

2. Regenerative Loops

Figure 3 shows an iron loop (about 2-inch diameter) wrapped with a silver wire helix which is quite stable in 53-55% acid and which will easily support a circulating pattern of three impulses. For demonstration, unilateral waves can be generated by first touching the iron with a piece of zinc (which produces two oppositely travelling waves) and then blocking one of them with a piece of platinum or a small platinum screen attached to the end of a stick or wand. Carbon blocks may also be used for this purpose.

The smallest regenerative or reverberatory loop which we are at present able to devise is about 1 mm in diameter. Multiple waves, as expected, produce stable patterns in which all impulses are equally spaced. This phenomenon can be related to the slightly slower speed characteristic of the relative refractory period as compared with a more fully recovered zone.

3. Strong Coupling

If two touching pieces of iron are placed in a bath of nitric acid, a wave generated on one will ordinarily spread to the other. As is to be expected, a similar result is obtained if the two pieces are connected through an external conducting wire. However, if they are isolated, strong coupling does not ordinarily occur, especially if the elements are small in comparison with a “critical size,” σ/ρ where σ is the surface resistivity of passive iron surface (in Ω-cm²) and ρ is the volume resistivity of the acid (in Ω-cm). A simple and informative structure which demonstrates the essential conditions for strong electrical coupling between isolated elements of very small size may be constructed as shown in Figure 4. The dielectric barrier insures that charge transfer through one dipole must be accompanied by an equal and opposite transfer through the surfaces of the other dipole. If the “inexcitable” silver tails have sufficiently high conductance (_i.e._, sufficiently large surface area, hence preferably, dendrites), strong coupling will occur, just as though the cores of the two pieces of iron were connected with a solid conducting wire.

4. Inhibitory Coupling

If a third “dipole” is inserted through the dielectric membrane in the opposite direction, then excitation of this isolated element tends to inhibit the response which would otherwise be elicited by excitation of one of the parallel dipoles. Figure 5 shows the first such “logically-complete” interaction cell successfully constructed and demonstrated. It may be said to behave as an elementary McCulloch-Pitts neuron (15). Further analysis shows that similar structures incorporating many dipoles (both excitatory and inhibitory) can be made to behave as general “linear decision functions” in which all input weights are approximately proportional to the total size or length of their corresponding attached dendritic structures.

5. Dendrite Growth

Figure 6 shows a sample gold dendrite grown by electrodeposition (actual size, about 1 mm) from a 54% nitric acid solution to which gold chloride was added. When such a dendrite is attached to a piece of iron (both submerged), activation of the excitable element produces a field in such a direction as to promote further growth of the dendritic structure. Thus, if gold chloride is added to the solution used in the elementary interaction cells described above, all input influence “weights” tend to increase with use and, hence, produce a plasticity of function.

6. Field Effects in Locally-Refractory Regions

Our measurements indicate that, during the refractory period following excitation, the surface resistance of iron in nitric acid drops to substantially less than 1% of its resting value in a manner reminiscent of nerve membranes (4). Thus, if a distributed or gross field exists at any time throughout a complex cellular aggregate, concomitant current densities in locally-refractive regions will be substantially higher than elsewhere and, if conditions appropriate to dendrite growth exist (as described above) growth rates in such regions will also be substantially higher than elsewhere. It would appear that, as a result, recently active functional couplings (in contrast to those not associated with recent neural activity) should be significantly altered by widely distributed fields or massive peripheral shocks. This mechanism might thus explain the apparent ability of the brain to form specific temporal associations in response to spatially-diffuse effects such as are generated, for example, by the pain receptors.

Figure 6—Dendritic structures, living and non-living. (a) Cat dendrite trees (from Bok, “Histonomy of the Cerebral Cortex,” Elsevier, 1959); (b) Electrodeposited gold dendrite tree.]

SUMMARY

An attempt is being made to develop meaningful electrochemical model techniques which may contribute toward a clearer understanding of cortical function. Two basic phenomena are simultaneously employed which are variants of (1) the Lillie iron-wire nerve model, and (2) growth of metallic dendrites by electrodeposition. These phenomena are being induced particularly within dense cellular aggregates of various materials whose interstitial spaces are flooded with liquid electrolyte.

REFERENCES

1. Bok, S. T.,
“Histonomy of the Cerebral Cortex,”
Amsterdam, London:Elsevier Publishing Co., New York:Princeton,
1959

2. Bonhoeffer, K. F.,
“Activation of Passive Iron as a Model for the Excitation of
Nerve,”
_J. Gen. Physiol._ =32=:69-91 (1948).
This paper summarizes work carried out during 1941-1946
at the University of Leipzig, and published during the
war years in German periodicals.

3. Boycott, B. B., and Young, J. Z.,
“The Comparative Study of Learning,”
S. E. B. Symposia, No. IV
“Physiological Mechanisms in Animal Behavior,”
Cambridge: University Press, USA:Academic Press, Inc., 1950

4. Cole, K. S., and Curtis, H. J.,
“Electric Impedance of the Squid Giant Axon During Activity,”
_J. Gen. Physiol._ =22=:649-670 (1939)

5. Eccles, J. C.,
“The Effects of Use and Disuse of Synaptic Function,”
“Brain Mechanisms and Learning—A Symposium,”
organized by the Council for International Organizations of
Medical Science, Oxford:Blackwell Scientific Publications, 1961

6. Franck, U. F.,
“Models for Biological Excitation Processes,”
“Progress in Biophysics and Biophysical Chemistry,”
J. A. V. Butler, ed., London and New York:Pergamon Press,
pp. 171-206, 1956

7. Gerard, R. W.,
“Biological Roots of Psychiatry,”
_Science_ =122 (No. 3162)=:225-230 (1955)

8. Gesell, R.,
“A Neurophysiological Interpretation of the Respiratory Act,”
_Ergedn. Physiol._ =43:=477-639 (1940)

9. Hebb, D. O.,
“The Organization of Behavior, A Neuropsychological Theory,”
New York:John Wiley and Sons, 1949

10. Hebb, D. O.,
“Distinctive Features of Learning in the Higher Animal,”
“Brain Mechanisms and Learning—A Symposium,”
organized by the Council for International Organizations of
Medical Science, Oxford:Blackwell Scientific Publications, 1961

11. Konorski, J.,
“Conditioned Reflexes and Neuron Organization,”
Cambridge:Cambridge University Press, 1948

12. Lillie, R. S.,
“Factors Affecting the Transmission and Recovery in the Passive
Iron Nerve Model,”
_J. Gen. Physiol._ =4=:473 (1925)

13. Lillie, R. S., _Biol. Rev._ =16=:216 (1936)

14. Matumoto, M., and Goto, K.,
“A New Type of Nerve Conduction Model,”
_The Gurma Journal of Medical Sciences_ =4(No. 1)= (1955)

15. McCulloch, W. S., and Pitts, W.,
“A Logical Calculus of the Ideas Immanent in Nervous Activity,”
_Bulletin of Mathematical Biophysics_ =5=:115-133 (1943)

16. Morrell, F.,
“Electrophysiological Contributions to the Neural
Basis of Learning,”
_Physiological Reviews_ =41(No. 3)= (1961)

17. Pask, G.,
“The Growth Process Inside the Cybernetic Machine,”
_Proc. 2nd Congress International Association Cybernetics_,
Gauthier-Villars, Paris:Namur, 1958

18. Retzlaff, E.,
“Neurohistological Basis for the Functioning of Paired
Half-Centers,”
_J. Comp. Neurology_ =101=:407-443 (1954)

19. Sperry, R. W.,
“Neurology and the Mind-Brain Problem,”
_Amer. Scientist_ =40(No. 2)=: 291-312 (1952)

20. Tasaki, I., and Bak, A. F.,
_J. Gen. Physiol._ =42=:899 (1959)

21. Thorpe, W. H.,
“The Concepts of Learning and Their Relation to Those of
Instinct,”
S. E. B. Symposia, No. IV,
“Physiological Mechanisms in Animal Behavior,”
Cambridge:University Press, USA:Academic Press, Inc., 1950

22. Yamagiwa, K.,
“The Interaction in Various Manifestations
(Observations on Lillie’s Nerve Model),”
_Jap. J. Physiol._ =1=:40-54 (1950)

23. Young, J. Z.,
“The Evolution of the Nervous System and of the
Relationship of Organism and Environment,”
G. R. de Beer, ed.,
“Evolution,”
Oxford:Clarendon Press, pp. 179-204, 1938

24. Young, J. Z.,
“Doubt and Certainty in Science, A Biologist’s Reflections
on the Brain,”
New York:Oxford Press, 1951

Multi-Layer Learning Networks

R. A. STAFFORD

_Philco Corp., Aeronutronic Division
Newport Beach, California_

INTRODUCTION

This paper is concerned with the problem of designing a network of linear threshold elements capable of efficiently adapting its various sets of weights so as to produce a prescribed input-output relation. It is to accomplish this adaptation by being repetitively presented with the various inputs along with the corresponding desired outputs. We will not be concerned here with the further requirement of various kinds of ability to “generalize”—_i.e._, to tend to give correct outputs for inputs that have not previously occurred when they are similar in some transformed sense to other inputs that have occurred.

In putting forth a model for such an adapting or “learning” network, a requirement is laid down that the complexity of the adaption process in terms of interconnections among elements needed for producing appropriate weight changes, should not greatly exceed that already required to produce outputs from inputs with a static set of weights. In fact, it has been found possible to use the output-from-input computing capacity of the network to help choose proper weight changes by observing the effect on the output of a variety of possible weight changes.

No attempt is made here to defend the proposed network model on theoretical grounds since no effective theory is known at present. Instead, the plausibility of the various aspects of the network model, combined with empirical results must suffice.

SINGLE ELEMENTS

To simplify the problem it is assumed that the network receives a set of two-valued inputs, x₁, x₂, ..., xₙ, and is required to produce only a single two-valued output, y. It is convenient to assign the numerical quantities +1 and -1 to the two values of each variable.

The simplest network would consist of a single linear threshold element with a set of weights, c₀, c₁, c₂, ..., cₙ. These determine the output-input relation or function so that y is +1 or -1 according as the quantity, c₀ + c₁x₁ + c₂x₂ + ... + cₙxₙ, is positive or not, respectively. It is possible for such a single element to exhibit an adaptive behavior as follows. If, for a given set, x₁, x₂, ..., xₙ, the output, y, is correct, then make no changes to the weights. Otherwise change the weights according to the equations

Δc₀ = y* Δcᵢ = y*xᵢ, i = 1,2, ...,n

where y* is the desired output.

It has been shown by a number of people that the weights of such an element are assured of arriving at a set of values which produce the correct output-input relation after a sufficient number of errors, provided that such a set exists. An upper bound on the number of possible errors can be given which depends only on the initial weight values and the logical function to be learned. This does not, however, solve our network problem for two reasons.

First, as the number, n, of inputs gets large, the number of errors to be expected for most functions which can be learned increases to unreasonable values. For example, for n = 6, most such functions result in 500 to 1000 errors compared to an average of 32 errors to be expected in a perfect learning device.

Second, and more important, the fraction of those logical functions which can be generated in a single element becomes vanishingly small as n increases. For example, at n = 6 less than one in each three trillion logical functions is so obtainable.

NETWORKS OF ELEMENTS

It can be demonstrated that if a sufficiently large number of linear threshold elements is used, with the outputs of some being the inputs of others, then a final output can be produced which is any desired logical function of the inputs. The difficulty in such a network lies in the fact that we are no longer provided with a knowledge of the correct output for each element, but only for the final output. If the final output is incorrect there is no obvious way to determine which sets of weights should be altered.

As a result of considerable study and experimentation at Aeronutronic, a network model has been evolved which, it is felt, will get around these difficulties. It consists of four basic features which will now be described.

Positive Interconnecting Weights

It is proposed that all weights in elements attached to inputs which come from other elements in the network be restricted to positive values. (Weights attached to the original inputs to the network, of course, must be allowed to be of either sign.) The reason for such a restriction is this. If element 1 is an input to element 2 with weight c₁₂, element 2 to element 3 with weight c₂₃, _etc._, then the sign of the product, c₁₂c₂₃ ..., gives the sense of the effect of a change in the output of element 1 on the final element in the chain (assuming this is the only such chain between the two elements). If these various weights were of either possible sign, then a decision as to whether or not to change the output in element 1 to help correct an error in the final element would involve all weights in the chain. Moreover, since there would in general be a multiplicity of such chains, the decision is rendered impossibly difficult.

The above restriction removes this difficulty. If the output of any element in the network is changed, say, from -1 to +1, the effect on the final element, if it is affected at all, is in the same direction.

It should be noted that this restriction does not seriously affect the logical capabilities of a network. In fact, if a certain logical function can be achieved in a network with the use of weights of unrestricted sign, then the same function can be generated in another network with only positive interconnecting weights and, at worst, twice the number of elements. In the worst case this is done by generating in the restricted network both the output and its complement for each element of the unrestricted network. (It is assumed that there are no loops in the network.)

A Variable Bias

The central problem in network learning is that of determining, for a given input, the set of elements whose outputs can be altered so as to correct the final element, and which will do the least amount of damage to previous adaptations to other inputs. Once this set has been determined, the incrementing rule given for a single element will apply in this case as well (subject to the restriction of leaving interconnecting weights positive), since the desired final output coincides with that desired for each of the elements to be changed (because of positive interconnecting weights).

In the process of arriving at such a decision three factors need to be considered. Elements selected for change should tend to be those whose output would thereby be affected for a minimum number of other possible inputs. At the same time it should be ascertained that a change in each of the elements in question does indeed contribute significantly towards correcting the final output. Finally, a minimum number of such elements should be used.

It would appear at first that this kind of decision is impossible to achieve if the complexity of the decision apparatus is kept comparable to that of the basic input-output network as mentioned earlier. However, in the method to be described it is felt that a reasonable approximation to these requirements will be achieved without an undue increase in complexity.

It is assumed that in addition to its normal inputs, each element receives a variable input bias which we can call b. The output of every element should then be determined by the sign of the usual weighted sum of its inputs plus this bias quantity. This bias is to be the same for each element of the network. If b = 0 the network will behave as before. However, if b is increased gradually, various elements throughout the network will commence changing from -1 to +1, with one or a few changing at any one time as a rule. If b is decreased, the opposite will occur.

Now suppose that for a given input the final output ought to be +1 but actually is -1. Assume that b is then raised so high that this final output is corrected. Then commence a gradual decline in b. Various elements may revert to -1, but until the final output does, no weights are changed. When the final output does revert to -1, it is due to an element’s having a sum (weighted sum plus bias) which just passed down through zero. This then caused a chain effect of changing elements up to the final element, but presumably this element is the only one possessing a zero sum. This can then be the signal for the weights on an element to change—a change of final output from right to wrong accompanied simultaneously by a zero sum in the element itself.

After such a weight change, the final output will be correct once more and the bias can again proceed to fall. Before it reaches zero, this process may occur a number of times throughout the network. When the bias finally stands at zero with the final output correct, the network is ready for the next input. Of course if -1 is desired, the bias will change in the opposite direction.

It is possible that extending the weight change process a little past the zero bias level may have beneficial results. This might increase the life expectancy of each learned input-output combination and thereby reduce the total number of errors. This is because the method used above can stop the weight correction process so that even though the final output is correct, some elements whose output are essential to the final output have sums close to zero, which are easily changed by subsequent weight changes.

It will be noted that this method conforms to all three considerations mentioned previously. First, by furnishing each element the same bias, and by not changing weights until the final output becomes incorrect with dropping bias, there is a strong tendency to select elements which, with b = 0, would have sums close to zero. But the size of the sum in an element is a good measure of the amount of damage done to an element for other inputs if its current output is to be changed. Second, it is obvious that each element changed has had a demonstrable effect on the final output. Finally, there will be a clear tendency to change only a minimum of elements because changes never occur until the output clearly requires a change.

On the other hand this method requires little more added complexity to the network than it already has. Each element requires a bias, an error signal, and the desired final output, these things being uniform for all elements in a network. Some external device must manipulate the bias properly, but this is a simple behavior depending only on an error signal and the desired final output—not on the state of individual elements in the network. What one has, then, is a network consisting of elements which are nearly autonomous as regards their decisions to change weights. Such a scheme appears to be the only way to avoid constructing a central weight-change decision apparatus of great complexity. This rather sophisticated decision is made possible by utilizing the computational capabilities the network already possesses in producing outputs from inputs.

It should be noted here that this varying bias method requires that the variable bias be furnished to just those elements which have variable weights and to no others. Any fixed portion of the network, such as preliminary layers or final majority function for example, must operate independently of the variable bias. Otherwise, the final output may go from right to wrong as the bias moves towards zero and no variable-weight element be to blame. In such a case the network would be hung up.

Logical Redundancy in the Network

A third aspect of the network model is that for all the care taken in the previous steps, they will not suffice in settling quickly to a set of weights that will generate the required logical function unless there is a great multiplicity of ways in which this can be done. This is to say that a learning network needs to have an excess margin of weights and elements beyond the minimum required to generate the functions which are to be learned.

This is analogous to the situation that prevails for a single element as regards the allowed range of values on its weights. It can be shown for example, that any function for n=6 that can be generated by a single element can be obtained with each weight restricted to the range of integer values -9,-8, ..., +9. Yet no modification of the stated weight change rule is known which restricts weight values to these and yet has any chance of ever being learned for most functions.

Fatigued Elements

It would appear from some of the preliminary results of network simulations that it may be useful to have elements become “fatigued” after undergoing an excessive number of weight changes. Experiments have been performed on simplifications of the model described so far which had the occasional result that a small number of elements came to a state where they received most of the weight increments, much to the detriment of the learning process. In such cases the network behaves as if it were composed of many fewer adjustable elements. In a sense this is asking each element to maintain a record of the data it is being asked to store so that it does not attempt to exceed its own information capacity.

It is not certain just how this fatigue factor should enter in the element’s actions, but if it is to be compatible with the variable bias method, this fatigue factor must enter into the element’s response to a changing bias. Once an element changes state with zero sum at the same time that the final output becomes wrong, incrementing must occur if the method is to work. Hence a “fatigued” element must respond less energetically to a change of bias, perhaps with a kind of variable factor to be multiplied by the bias term.

NETWORK STRUCTURE

It is felt that the problem of selecting the structure of interconnections for a network is intimately connected to the previously mentioned problem of generalization. Presumably a given type of generalization can be obtained by providing appropriate fixed portions of the network and an appropriate interconnection structure for the variable portion. However, for very large networks, it is undoubtedly necessary to restrict the complexity so that it can be specified by relatively simple rules. Since very little is known about this quite important problem, no further discussion will be attempted here.

COMPUTER SIMULATION RESULTS

A computer simulation of some of the network features previously described has been made on an IBM 7090. Networks with an excess of elements and with only positive interconnecting weights were used. However, in place of the variable bias method, a simple choice of the element of sum closest to, and on the wrong side of, zero was made without regard to the effectiveness of the element in correcting the final output. No fatigue factors were used.

The results of these simulations are very encouraging, but at the same time indicate the need for the more sophisticated methods. No attempt will be made here to describe the results completely.

In one series of learning experiments, a 22-element network was used which had three layers, 10 elements on the first, 11 on the second, and 1 on the third. The single element on the third was the final output, and was a fixed majority function of the 11 elements in the second layer. These in turn each received inputs from each of the 10 on the first layer and from each of the 6 basic inputs. The 10 on the first layer each received only the 6 basic inputs. A set of four logical functions, A, B, C, and D, was used. Function A was actually a linear threshold function which could be generated by the weights 8, 7, 6, 5, 4, 3, 2, functions B and C were chosen by randomly filling in a truth table, while D was the parity function.

TABLE I
-------+--------+---------+-------
A | B | C | D
r e | r e | r e | r e
-------+--------+---------+-------
5 54 | 8 100 | 11 101 | 4 52
4 37 | 9 85 | 4 60 | 5 62
4 44 | 6 72 | 9 85 | 6 56
-------+--------+---------+-------

Table I gives the results of one series of runs with these functions and this network, starting with various random initial weights. The quantity, r, is the number of complete passes through the 64-entry truth table before the function was completely learned, while e is the total number of errors made. In evaluating the results it should be noted that an ideal learning device would make an average of 32 errors altogether on each run. The totals recorded in these runs are agreeably close to this ideal. As expected, the linear threshold function is the easiest to learn, but it is surprising that the parity function was substantially easier than the two randomly chosen functions. Table II gives a chastening result of the same experiment with all interconnecting weights removed except that the final element is a fixed majority function of the other 21 elements. Thus there was adaptation on one layer only. As can be seen Table I is hardly better than Table II so that the value of variable interconnecting weights was not being fully realized. In a later experiment the number of elements was reduced to 12 elements and the same functions used. In this case the presence of extra interconnecting weights actually proved to be a hindrance! However a close examination of the incrementing process brought out the fact that the troublesome behavior was due to the greater chance of having only a few (often only one) elements do nearly all the incrementing. It is expected that the use of the additional refinements discussed herein will produce a considerable improvement in bringing out the full power of adaptation in multiple layers of a network.

TABLE II
-------+--------+---------+-------
A | B | C | D
r e | r e | r e | r e
-------+--------+---------+-------
7 47 | 18 192 | 8 110 | 4 48
3 40 | 7 69 | 10 98 | 6 68
4 43 | 7 82 | 4 47 | 6 46
-------+--------+---------+-------

FUTURE PROBLEMS

Aside from the previous question of deciding on network structure, there are several other questions that remain to be studied in learning networks.

There is the question of requiring more than a single output from a network. If, say, two outputs are required for a given input, one +1 and the other -1, this runs into conflict with the incrementing process. Changes that aid one output may act against the other. Apparently the searching process depicted before with a varying bias must be considerably refined to find weight changes which act on all the outputs in the required way. This is far from an academic question because there will undoubtedly be numerous cases in which the greatest part of the input-output computation will have shared features for all output variables. Only at later levels do they need to be differentiated. Hence it is necessary to envision a single network producing multiple outputs rather than a separate network for each output variable if full efficiency is to be achieved.

Another related question is that of using input variables that are either many-, or continuous-, valued rather than two-valued. No fundamental difficulties are discernible in this case, but the matter deserves some considerable study and experimentation.

Another important question involves the use of a succession of inputs for producing an output. That is, it may be useful to allow time to enter into the network’s logical action, thus giving it a “dynamic” as well as “static” capability.

Adaptive Detection of Unknown Binary Waveforms

J. J. SPILKER, JR.

_Philco Western Development Laboratories
Palo Alto, California_

This work was supported by the Philco WDL
Independent Development Program. This paper,
submitted after the Symposium, represents a
more detailed presentation of some of the
issues raised in the discussion sessions at the
Symposium and hence, constitutes a worthwhile
addition to the Proceedings.

INTRODUCTION

One of the most important objectives in processing a stream of data is to determine and detect the presence of any invariant or quasi-invariant “features” in that data stream. These features are often initially unknown and must be “learned” from the observations. One of the simplest features of this form is a finite length signal which occurs repetitively, but not necessarily periodically with time, and has a waveshape that remains invariant or varies only slowly with time.

In this discussion, we assume that the data stream has been pre-processed, perhaps by a detector or discriminator, so as to exhibit this type of repetitive (but unknown) waveshape or signal structure. The observed signal, however, is perturbed by additive noise or other disturbances. It is desired to separate the quasi-invariance of the data from the truly random environment. The repetitive waveform may represent, for example, the transmission of an unknown sonar or radar, a pulse-position modulated noise-like waveform, or a repeated code word.

The problem of concern is to estimate the signal waveshape and to determine the time of each signal occurrence. We limit this discussion to the situation where only a single repetitive waveform is present and the signal sample values are binary. The observed waveform is assumed to be received at low signal-to-noise ratio so that a single observation of the signal (even if one knew precisely the arrival time) is not sufficient to provide a good estimate of the signal waveshape. The occurrence time of each signal is assumed to be random.

THE ADAPTIVE DETECTION MACHINE

The purpose of this note is to describe very briefly a machine[2] which has been implemented to recover the noise-perturbed binary waveform. A simplified block diagram of the machine is shown in Figure 1. The experimental machine has been designed to operate on signals of 10³ samples duration.

[2] The operation of this machine is described in substantially greater detail in J. J. Spilker, Jr., D. D. Luby, R. D. Lawhorn, “Adaptive Binary Waveform Detection,” Philco Western Development Laboratories, Communication Sciences Department, TR #75, December 1963.

Each analog input sample enters the machine at left and may either contain a signal sample plus noise or noise alone. In order to permit digital operation in the machine, the samples are quantized in a symmetrical three-level quantizer. The samples are then converted to vector form, _e.g._, the previous 10³ samples form the vector components. A new input vector, ⮕Y⁽ⁱ⁾, is formed at each sample instant.

Define the signal sample values as s₁, s₂, ..., sₙ. The observed vector Y⁽ⁱ⁾ is then either (a) perfectly centered signal plus noise, (b) shifted signal plus noise, or (c) noise alone.

{ (s₁, s₂, ..., sₙ) + (n₁, n₂, ..., nₙ) (a)
(Y⁽ⁱ⁾)ᵗ = { (0, ..., s₁, s₂, ..., sₙ₋ⱼ) + (n₁, n₂, ..., nₙ) (b)
{ (0 ... 0) + (n₁, n₂, ..., nₙ) (c)

At each sample instant, two measurements are made on the input vector, an energy measurement ‖Y⁽ⁱ⁾‖² and a polarity coincidence cross-correlation with the present estimate of the signal vector stored in memory. If the weighted sum of the energy and cross-correlation measurements exceeds the present threshold value Γᵢ, the input vector is accepted as containing the signal (properly shifted in time), and the input vector is added to the memory. The adaptive memory has 2^{Q} levels, 2^{Q-1} positive levels, 1 zero level and 2^{Q-1}-1 negative levels. New contributions are made to the memory by normal vector addition except that saturation occurs when a component value is at the maximum or minimum level.

The acceptance or rejection of a given input vector is based on a hypersphere decision boundary. The input vector is accepted if the weighted sum γᵢ exceeds the threshold Γᵢ

γᵢ = Y⁽ⁱ⁾∙M⁽ⁱ⁾ + α‖Y⁽ⁱ⁾‖² ⩾ Γᵢ.

Geometrically, we see that the input vector is accepted if it falls on or outside of a hypersphere centered at ⮕C⁽ⁱ⁾ = -⮕M⁽ⁱ⁾/2α having radius squared

Γ⁽ⁱ⁾ ‖M⁽ⁱ⁾‖²
[r⁽ⁱ⁾]² = ——— + —————— .
α (2α)²

Both the center and radius of this hypersphere change as the machine adapts. The performance and optimality of hypersphere-type decision boundaries have been _discussed in related work_ by Glaser[3] and Cooper.[4]

[3] F. M. Glaser, “Signal Detection by Adaptive Filters,” _IRE Trans. Information Theory_, pp. 87-90; April 1961.

[4] P. W. Cooper, “The Hypersphere in Pattern Recognition,” _Information and Control_, pp. 324-346; December 1962.

The threshold value, Γᵢ, is adapted so that it increases if the memory becomes a better replica of the signal with the result that γᵢ increases. On the other hand, if the memory is a poor replica of the signal (for example, if it contains noise alone), it is necessary that the threshold decay with time to the point where additional acceptances can modify the memory structure.

The experimental machine is entirely digital in operation and, as stated above, is capable of recovering waveforms of up to 10³ samples in duration. In a typical experiment, one might attempt to recover an unknown noise-perturbed, pseudo-random waveform of up to 10³ bits duration which occurs at random intervals. If no information is available as to the signal waveshape, the adaptive memory is blank at the start of the experiment.

In order to illustrate the operation of the machine most clearly, let us consider a repetitive binary waveform which is composed of 10³ bits of alternate “zeros” and “ones.” A portion of this waveform is shown in Figure 2a. The waveform actually observed is a noise-perturbed version of this waveform shown in Figure 2b at-6 db signal-to-noise ratio. The exact sign of each of the signal bits obviously could not be accurately determined by direct observation of Figure 2b.

Figure 2—Binary signal with additive noise at-6 db SNR]

Figure 3—Adaption of the memory at-6 db SNR: (a) Blank initial memory; (b) Memory after first dump; (c) Memory after 12 dumps; (d) Memory after 40 dumps; (e) Perfect “checkerboard” memory for comparison]

As the machine memory adapts to this noisy input signal, it progresses as shown in Figure 3. The sign of 10^{3} memory components are displayed in a raster pattern in this figure. Figure 3a shows the memory in its blank initial state at the start of the adaption process. Figure 3b shows the memory after the first adaption of the memory. This first “dump” occurred after the threshold had decayed to the point where an energy measurement produced an acceptance decision. Figure 3c and 3d show the memory after 12 and 40 adaptions, respectively. These dumps, of course, are based on both energy and cross-correlation measurements. As can be seen, the adapted memory after 40 dumps is already quite close to the perfect memory shown by the “checkerboard” pattern of Figure 3c.

The detailed analysis of the performance of this type of machine vs. signal-to-noise ratio, average signal repetition rate, signal duration, and machine parameters is extremely complex. Therefore, it is not appropriate here to detail the results of the analytical and experimental work on the performance of this machine. However, several conclusions of a general nature can be stated.

(a) Because the machine memory is always adapting, there
is a relatively high penalty for “false alarms.”
False alarms can destroy a perfect memory. Hence,
the threshold level needs to be set appropriately
high for the memory adaption. If one wishes to
detect signal occurrences with more tolerance to
false alarms, a separate comparator and threshold
level should be used.

(b) The present machine structure, which allows for
slowly varying changes in the signal waveshape,
exhibits a marked threshold effect in steady-state
performance at an input signal-to-noise ratio
(peak signal power-to-average noise power ratio)
of about -12 db. Below this signal level, the time
required for convergence increases very rapidly with
decreasing signal level. At higher SNR, convergence
to noise-like signals, having good auto-correlation
properties, occurs at a satisfactory rate.

A more detailed discussion of performance has been published in the report cited in footnote reference 1.

Conceptual Design of Self-Organizing Machines

P. A. KLEYN

_Northrop Nortronics_
_Systems Support Department_
_Anaheim, California_

Self-organization is defined and several examples
which motivate this definition are presented. The
significance of this definition is explored by
comparison with the metrization problem discussed
in the companion paper (1) and it is seen that
self-organization requires decomposing the space
representing the environment. In the absence
of a priori knowledge of the environment, the
self-organizing machine must resort to a sequence
of projections on unit spheres to effect this
decomposition. Such a sequence of projections
can be provided by repeated use of a nilpotent
projection operator (NPO). An analog computer
mechanization of one such NPO is discussed
and the signal processing behavior of the NPO
is presented in detail using the Euclidean
geometrical representation of the metrizable
topology provided in the companion paper.
Self-organizing systems using multiple NPO’s
are discussed and current areas of research are
identified.

INTRODUCTION

Unlike the companion paper which considers certain questions in depth, this paper presents a survey of the scope of our work in self-organizing systems and is not intended to be profound.

The approach we have followed may be called phenomenological (Figure 1). That is, the desired behavior (self-organization) was defined, represented mathematically, and a mechanism(s) required to yield the postulated behavior was synthesized using mathematical techniques. One advantage of this approach is that it avoids assumptions of uniqueness of the mechanism. Another advantage is that the desired behavior, which is after all the principal objective, is taken as invariant. An obvious disadvantage is the requirement for the aforementioned synthesis technique; fortunately in our case a sufficiently general technique had been developed by the author of the companion paper.

From the foregoing and from the definition of self-organization we employ (see conceptual model), it would appear that our research does not fit comfortably within any of the well publicized approaches to self-organization (2). Philosophically, we lean toward viewpoints expressed by Ashby (3), (4), Hawkins (5), and Mesarovic (6) but with certain reservations. We have avoided the neural net approach partly because it is receiving considerable attention and also because the brain mechanism need not be the unique way to produce the desired behavior.

Nor have we followed the probability computer or statistical decision theory approach exemplified by Braverman (7) because these usually require some sort of preassigned coordinate system (8). Neither will the reader find much indication of formal logic (9) or heuristic (10) programming. Instead, we view a self-organizing system more as a mirror whose appearance reflects the environment rather than its own intrinsic nature. With this viewpoint, a self-organizing system appears very flexible because it possesses few internal constraints which would tend to distort the reflection of the environment and hinder its ability to adapt.

CONCEPTUAL MODEL

Definition

A system is said to be self-organizing if, after observing the input and output of an unknown phenomenon (transfer relation), the system organizes itself into a simulation of the unknown phenomenon.

Implicit in this definition is the requirement that the self-organizing machine (SOM) not possess a preassigned coordinate system. In fact it is just this ability to acquire that coordinate system implicit in the input-output spaces which define the phenomenon that we designate as self-organization. Thus any a priori information programmed into the SOM by means of, for example, stored or wired programs, constrains the SOM and limits its ability to adapt. We do not mean to suggest that such preprogramming is not useful or desirable; merely that it is inconsistent with the requirement for self-organization. As shown in Figure 2, it is the given portion of the environment which the SOM is to simulate, which via the defining end spaces, furnishes the SOM with all the data it needs to construct the coordinate system intrinsic to those spaces.

The motivation for requiring the ability to simulate as a feature of self-organization stems from the following examples.

Consider the operation of driving an automobile. Figure 3 depicts the relation characterized by a set of inputs; steering, throttle, brakes, transmission, and a set of outputs; the trajectory. Operation of the automobile requires a device (SOM) which for a desired trajectory can furnish those inputs which realize the desired trajectory. In order to provide the proper inputs to the automobile, the SOM must contain a simulation of ⨍⁻¹(x).

Since ⨍(x) is completely defined in terms of the inputs and the resulting trajectories, exposure to them provide the SOM with all the information necessary to simulate ⨍⁻¹(x). And if the SOM possesses internal processes which cause rearrangement of the input-output relation of the SOM to correspond to ⨍⁻¹(x) in accordance with the observed data, the SOM can operate an automobile. It is this internal change which is implied by the term “self-organizing,” but note that the instructions which specify the desired organization have their source in the environment.

As a second example consider adaptation to the environment. Adapt (from Webster) means: “to change (oneself) so that one’s behavior, attitudes, _etc._, will conform to new or changed circumstances. Adaptation in biology means a change in structure, function or form that produces better adjustment to the environment.” These statements suggest a simulation because adjustment to the environment implies survival by exposing the organism to the beneficial rather than the inimical effects of the environment. If we represent the environment (or portion thereof) as a relation as shown in Figure 2, we note that the ability to predict what effect a given disturbance will have is due to a simulation of the cause-effect relation which characterizes the environment.

It would be a mistake to infer from these examples that simulation preserves the appearance of the causes and effects which characterize a relation. We clarify this situation by examining a relation and its simulation.

Consider the relation between two mothers and their sons as pictured in Figure 4. Observe that if symbols (points) are substituted for the actual physical objects (mothers and sons), the relation is not altered in any way. This is what we mean by simulation and this is how a SOM simulates. It is not even necessary that the objects, used to display the relation, be defined; _i.e._, these objects may be primitive. (If this were not so, no mathematical or physical theory could model the environment.) The main prerequisite is sufficient resolution to distinguish the objects from each other.

MATHEMATICAL MODEL

The mathematical model must represent both the environment and the SOM and for reasons given in the companion paper each is represented as a metrizable topology. For uniqueness we factor each space into equal parts and represent the environment as the channel

W ⟶ X. (Ref. 10a)

Consider now the SOM to be represented by the cascaded channels

X ⟶ Y ⟶ Z

where X ⟶ Y is a variable which represents the reorganization of the SOM existing input-output relation represented by Y ⟶ Z.

The solution of the three channels-in-cascade problem

W ⟶ X ⟶ Y ⟶ Z,

where p(W) (11), p(X), p(X|W), p(Y), p(Z), p(Z|Y) are fixed, yields that middle channel p₀(Y|X), from a set of permissible middle channels {p(Y|X)}, which maximizes R(Z,W).

Then the resulting middle channel describes that reorganization of the SOM which yields the optimum simulation of W ⟶ X by the SOM, within the constraints upon Ch(Z,Y).

The solution (the middle channel) depends of course on the particular end channels. Obviously the algorithm which is used to find the solution does not. It follows that if some physical process were constrained to carrying out the steps specified by the algorithm, said process would be capable of simulation and would exhibit self-organization.

Although the formal solution to the three-channels-in-cascade problem is not complete, the solution is sufficiently well characterized to permit proceeding with a mechanization of the algorithm. A considerable portion of the solution is concerned with the decomposition and metrization of channels and it is upon this feature that we now focus attention.

As suggested in the companion paper, if the dimensionality of the spaces is greater than one, the SOM has only one method available (12). Consider the decomposition of a space without, for the moment, making the distinction between input and output.

Figure 5 depicts objects represented by a (perhaps multidimensional) “cloud” of points. In the absence of a preassigned coordinate system, the SOM computes the center of gravity of the cloud (which can be done in any coordinate system) and describes the points in terms of the distance from this center of gravity; or, which is the same, as concentric spheres with origin at the center of gravity.

The direction of particular point cannot be specified for there is no reference radius vector. Since the SOM wants to end up with a cartesian coordinate system, it must transform the sphere (a two-dimensional surface) into a plane (a two-dimensional surface). Unfortunately, a sphere is not homeomorphic to a plane; thus the SOM has to decompose the sphere into a cartesian product of a hemisphere (12a) and a denumerable group. The SOM then can transform the hemisphere into a plane. The points projected onto the plane constitute a space of the same character as the one with which the SOM started. Thus, it can repeat all operations on the plane (a space of one less dimension) by finding the center of gravity and the circle upon which the desired point is situated. The circle is similarly decomposed into a line times a denumerable group. By repeating this operation as many times as the space has dimensions, the SOM eventually arrives at a single point and has obtained in the process a description of the space. Since this procedure can be carried on by the repeated use of one operator, this operator is nilpotent and to reflect this fact as well as the use of a projection, we have named this a nilpotent projection operator or NPO for short.

MECHANIZATION OF THE NPO

Analog computer elements were used to simulate one NPO which was tested in the experimental configuration shown in Figure 6. The NPO operates upon a channel which is artificially generated from the two noise generators i₁ and i₂ and the signal generator i₀ (i₀ may also be a noise generator). The NPO accepts the inputs labelled X₁ and X₂ and provides the three outputs Ξ₁, Ξ₂, and γ. X₁ is the linear combination of the outputs of generators i₁ and i₀, similarly X₂ is obtained from i₂ and i₀.

Obviously, i₀ is an important parameter since it represents the memory relating the spaces X₁ and X₂. Ξ₁ has the property that the magnitude of its projection on i₀ is a maximum while Ξ₂ to the opposite has a zero projection on i₀. γ is the detected version of the eigenvalue of Ch(X₂,X₁).

In the companion paper it was shown how one can provide a Euclidean geometrical representation of the NPO. This representation is shown in Figure 7 which shows the vectors i₀, i₁, i₂, X₁, X₂, Ξ₁, Ξ₂, and the angles Θ₁, Θ₂, and γ. The length of a vector is given by

|X| = κₓ(2πε)⁻¹ᐟ² ∈ H(X)

and the angle between two vectors by

|Θ(X₁,X₂)|-sin⁻¹ ∈ -R(X₁,X₂).

The three vectors i₀, i₁, i₂ provide an orthogonal coordinate system because the corresponding signals are random, _i.e._,

κ
R(i₀,i₁,i₂) ≡ 0.

As external observers we have a prior knowledge of this coordinate system; however, the NPO is given only the vectors X₁ and X₂ in the i₀ ⨉ i₁ and i₀ ⨉ i₂ planes. The NPO can reconstruct the entire geometry but the actual output Ξ obviously is constrained to lie in the plane of the input vector X. The following formulas are typical of the relations present.

|Ξ₁|
tan β = ————
|Ξ₂|

cos Θ = cos 2β csc 2γ

cos 2β
cos 2Θ₁ = -1 + 2 ———————
1-cos 2γ

cos Θ = cos Θ₁ cos Θ₂.

We have obtained a complete description of the NPO which involves 74 formulas. These treat the noise in the various outputs, invariances of the NPO and other interesting features. A presentation of these would be outside of the scope of this paper and would tend to obscure the main features of the NPO. Thus, we show here only a typical sample of the computer simulation, Figure 8 and Figure 9. Conditions for these runs are shown in Table I. Run No. 6 duplicates run No. 5 except for the fact that i₁ and i₂ were disabled in run No. 6.

Observe that all our descriptions of the NPO and the space it is to decompose have been time invariant while the signals shown in the simulation are presented as functions of time. The conversion may be effected as follows: Given a measurable (single-valued) function

x = x(t)t ∊ T
where
μ(T) > 0
we define the space
X = {x = x(t) ∍ t ∊ T}

and a probability distribution

μ(x⁻¹(X′))
P(X′) = —————————— X′ open ⊂ X
μ(T)
on that space.

TABLE I
Legend for Traces of Figures 8 and 9
---------+-------+-------+--------+-----+----------+-------+--------
Trace | | | | | | |
Number | 1 | 2 | 3 | 4 | 5 | 6 | 7
---------+-------+-------+--------+-----+----------+-------+--------
Symbol | X₂ | X₁ | γ | β | i | dξ₂/dτ | dξ₁/dτ
---------+-------+-------+--------+-----+----------+--------+-------
run No. 5| | | | | | |
| | | | | | |
signal |7½ Vrms|7½ Vrms| π ptop | |35.6 m cps| |
| | | | | | |
noise |16 Vrms|15 Vrms| π/9 | | | |
| | | ptop[5]| |sine wave | |
| | | | | | |
DC | 0 | 0 | | | | |
| | | | | | |
power s/n| 1/4 | 1/4 | 81/1 | | | 0 | 1/2[6]
| | | | | | |
terminal | | | | | | |
value | | | π/4 | π/4 | | |
---------+-------+-------+--------+-----+----------+--------+-------
run No. 6| | | | | | |
| | | | | | |
signal |7½ Vrms|7½ Vrms| π ptop | |35.6 m cps| |
| | | | | | |
noise | 0 | 0 | 0[7] | |sine wave | |
| | | | | | |
DC | -30V | 0 | | | | |
| | | | | | |
power s/n| ∞ | ∞ | ∞ | | | 0 | ∞
| | | | | | |
terminal | | | | | | |
value | | | π/4 | π/4 | | |
---------+-------+-------+--------+-----+----------+--------+-------

[5] Observed from Oscillogram

[6] Computed

[7] Observed from Oscillogram

Then (X,p(X)) is a stochastic space in our usual sense and x(T) is a stochastic variable. Two immediate consequences are:

P(X) is stationary (P(X) is not a function of t ∊ T), and no question of ergodicity arises.

NETWORKS OF NPO’S

A network of NPO’s may constitute anything from a SOM to a preprogrammed detector, depending upon the relative amount of preprogramming included. Two methods of preprogramming are: (1) Feeding a signal out of a permanent storage into some of the inputs of the network of NPO’s. This a priori copy need not be perfect, because the SOM will measure the angles Θᵢ anyhow. (2) Feedback, which, after all, is just a way of taking advantage of the storage inherent in any delay line. (We implicitly assume that any reasonable physical realization of an NPO will include a delay T between the x input and the ξ output which is not less than perhaps 10⁻¹ times the time constant of the internal feedback loop in the γ computation.)

Simulation of channels that possess a discrete component requires feedback path(s) to generate the required free products of the finitely generated groups. Then, such a SOM converges to a maximal subgroup of the group describing the symmetry of the signal that is a free product available to this SOM.

Because a single NPO with 1 ≤ n₀ ≤ K₀ is isomorphic (provides the same input to output mapping) to a suitable network of NPO’s with n₀ = 1, it suffices to study only networks of NPO’s with n₀ = 1.