Virtual Lateral Inhibition in Parallel Activation Models of Associative Memory

VIRTUAL LATERAL IHHIBITION IH PARALLEL ACTIVATION MODELS OF ASSOCIATIVE MEMORY*

James A. Reggia

Department of Computer Science University of Maryland College Park, MD 20742 USA

II PARALLEL ACTIVATION MODELS OF MEMORY

In memory models implemented as value­ passing systems, each processing node typically represents a "concept" or "hypothesis", and the LeveL of activation associated with a node represents the relevance of or confidence in the concept/hypothesis represented by that node [1,5,7]. For this reason, and because of the distributed nature of the computations involved, the term paraLLeL activation network is used for such models. Nodes communicate with each other using links which have one or more weights associated with them. If the link from node A to node B has a positive weight, indicating that activation of node A tends to increase activation of node B, then such a link is excitatory. Conversely, a negative weight indicates an inhibitory connect ion. There are both excitatory and inhibitory interconnections at the level of neuronal circuits in the nervous system. It is therefore not surprising that both types of interconnections have been adopted by way of analogy in higher-level cognitive networks.

It has often proven convenient to view parallel activation networks as partitioned into Layers of conceptually similar nodes, and t o conceive of information as initially entering one "lowest" layer (e.g., features) and propagating "upwards" to others (e.g., letters) [2, 10]. When nodes in a lower layer directly inhibit nodes in a higher layer such inhibition may be called forward inhibition since it is in the direction of initial flow of activation. Conversely, inhibition in the opposite directi on may be called backward inhibition, and inhibition between nodes in the same layer can be referred to as LateraL inhibition. Lateral inhibition has long been recognized to play an . important role in contrast enhancement in neural networks and has been argued to be an important aspect of selective behavior [6]. Explicit lateral inhibitory links have also often been used in parallel activation models of associative memory in produce selective representing one way cognitively-oriented processing paradigms modeling studies. For two mutually inhibitory cognitive science t o behavior [2,5,10], in which these recent models have borrowed from earlier example, Figure nodes n1 and n2. neural 1 shows With a

ABSTRACT

This paper describes a new theory of how spreading activation may occur in associative memory models formulated as parallel activation networks. The theory postulates that competition for activation by nodes/concepts in a network is a fundamental principle of memory retrieval. Using only excitatory connections between concepts, a specific implementation of this model is able to demonstrate "virtual lateral inhibition" between competitors and other interesting behaviors that have required use of explicit inhibitory connections in the past.

I INTRODUCTION

During the last several years there has been a great deal of interest in AI in determining what kinds of parallel architectures best meet the needs of various AI tasks. This paper is concerned with "value-passing systems," networks in which the processing elements communicate by passing around continuous quantities (numbers) and by performing simple arithmetic operations on these values [4]. Such architectures are often intended as models of associative memory, and frequently they are characterized by an analogy with neurobiological networks and processing paradigms. Recent examples include "connectionist models" [5], "interactive activation models" [10], the

Boltzman machine [7] and ACT [1].

This paper presents a new "competition­ based" theory about how spreading activation may occur in value-passing associative memory models. First some terminology and the need for a model of spreading activation that can support "virtual lateral inhibition" are discussed. Then a theory is introduced which postulates that competition between cognitive activities for limited resources is a fundamental organizing principle of memory retrieval. A specific instantiation of the theory is used to illustrate the concepts involved.

*Supported by the Office of Naval Research, the National Science Found~tion (DCR-8451430), and

Software Architecture and Engineering, Inc.

typical model for spread of activation even a transiently higher input to one node (say n 1 ) followed by equal inputs to both nodes can lead to stabilization of activation with one node maximally activated (n 1 ) and the other having zero activation (n2). This "winner-take-all" phenomenon [5] comes about because of the lateral inhibitory connections.

While lateral inhibition is a useful concept in parallel activation models, the use of explicit lateral inhibitory links to achieve lateral inhibition poses a number of difficulties for implementing real world models of associative memory. At the cognitive level, in contrast to the neurobiological level, there is at best limited empirical evidence for such expLicit "negative associations" between the concepts involved. Published tabulations of the associations between related concepts usually include only positive weights (frequencies). Since these empirical studies do not provide negative weights between competing concepts, one is faced with the problem of determining how such weights are to be assigned in building parallel activation networks where weights are based on probabilitites [11 ]. Furthermore, as the number of "competing" nodes grows, the number of mutual lateral inhibitory connections needed can grow quite rapidly. For example, in the print-to-word mapping, a single character node may connect to thousands of word nodes, each of which would apparently require a mutually inhibitory connection with all of its competing word nodes [10].

In the following an approach to parallel spreading activation is proposed that can resolve these problems. Specifically, this approach is capable of producing virtuaL LateraL inhibition: apparent lateral inhibition between competing nodes in the absence of explicit lateral inhibitory connections. This phenomenon is produced without giving up the notion that computations in parallel activation networks should be local: each node can only "see" the activation and link weights of its immediately adjacent neighbor nodes.

III COMPETITION-BASED SPREAD OF ACTIVATION

In previous parallel activation models, the activation flowing into a node is not determined by the level of activity possessed by the receiving node. Typically, the incoming activation "seen" by a node ni is a weighted sum or some other function of the activities of its neighbors [1,2,5,6,7,10]. This incoming activity is used by node ni to update its own activation level, which is then distributed by node n. during the next increment of time as output \o appropriate neighbors.

In the competition-based parallel activation theory described here, the spread of activation is determined in a different way. When a node ni assumes an activation level above its normal resting level, its neighbors actively compete for the "energy" possessed by node ni. Further, the ability of a neighboring node to compete for ni 1 s activity or resources is proportional to that neighbor's existing level of activation. Resources acquired by a neighbor node in this fashion occur at the expense of resources that are available to its competitors, leading one to predict that virtual lateral inhibition will occur. The metaphor used here is that the "stronger" a node is (i.e., the higher its level of activation), the more effectively it can compete with other nodes for a source of energy/activation.

To examine this idea, one possible instantiation of competition-based spreading activation is presented below (other formulations are possible and are currently being explored). In the formulation given here, the presence of an underlying associative network is assumed where the nodes in the network are partitioned into disjoint layers as illustrated in Figure 2. For convenience, we also assume that each node in one layer is directly connected to at least one node in each adjacent layer. (These assumptions are not an essential part of the theory.)

Each connection between a node in one layer and that in another has two weights reflecting the directionally-oriented frequencies of association between the "concepts" represented by the nodes. For example, if ni is a node in one layer associated with ~ . node. nj in. a different layer, then a b1d1rect1onal l1nk appears between ni and nj i~ the . netwo:k· One weight "attached" to thls l1nk 1~ .wij· representing the frequency (cond1t1onal probability estimate) with which the concept represented by ni occurs given that the concept represented by n · is known to be present. Similarly, the ad ached weight w j i represents the frequency with which nj occurs given that ni is known to be present. We restr1ct such weights to 0.0 ~ wst ~ 1.0; the non-negative nature of these weights distinguishes them from the possibly negative "synaptic weights" in neural models and in psychologically-oriented parallel activation models of associative memory [5, 10]. Nodes in this example network do not explicitly inhibit other nodes in either the same layer or in adjacent layers. Furthermore, permitting weights to be highly asymmetric (w. · ) . h thf~ ~ wji in general also distinguls es approach from others [7,8].

w

Figure 2: A word-sense disambiguation network.

As a specific "toy" example, consider a grossly simplified version of the problem of mapping a word into the appropriate word sense (Figure 2). Layer W represents word/morpheme units (assume there are just four possible words), layer S represents possible word senses or "meanings" (again, just four), and layer C, which we ignore for the time being, represents a number of possible semantic contexts in which word sense disambiguation can occur. Note that each word node Wi relates to multiple senses, e.g., node W2 is connected to Sl, S2 and S4, reflecting the ambiguity of words in natural language. Thus {S1,S2,S4} represents the nodes in layer S which are competitors for the title of "sense indicated by W2." Similarly, each word sense is connected to multiple possible words (e.g., synonyms).

In Figure 2, the weight w · i corresponding to spread of activation from no~e ni to node nj is written adjacent to nj. The weights ~n "outputs" from a node in one layer to nodes 1n an adjacent layer sum to 1.0, consistent with our earlier definition of weights as conditional probability estimates. Each node ni in memory has an activation level a -(t) at time t, constrained so that 0.0 ~ ai h) ~ 1.0, and we let a. ( t) represent the belief in the entity 1 represented by node ni. Each node also has a natural resting activation level ri and a decay rate d- reflecting how quickly ai (t) returns to the re 1 sting level in the absence of external influences. We make two assumptions. First, we assume that at time t the maximum rate at which node n- is capable of distributing activation to its c~peting neighbors in an adjacent layer is proportional to ai ( t). Second, we assume that n . parsimoniously "desires" to support at most a t~tal of one unit of activation in associated competing nodes in an adjacent layer. Thus, the total amount of activation ni distributes to an adjacent layer at any point in time decreases as the collective activity of its neighbors in that layer rises. For example, in going from words to word senses, this second assumption states that each word maps onto exactly one of its possible senses. These two assumptions can be approximated by stating that the total output of node n. to its neighbors at time t is given by

as long as this quantity is non-negative, and zero otherwise.

The idea of competition is introduced into this model by permitting the neighbors of ni in an adjacent layer to actively compete for the total output activity of "i· The ability of neighbor node nj t~ compete f?r ni's out~ut activity out -(t/ 1s proport1onal to 1ts "strength" a~(t), and to the weight of association w}i· Thus, the activation outji(t) transferred from ni to n j at time t is _given by

(the symbol 11 « 11 is read "is proportional to"). "Stronger" neighbors of ni therefore extract a greater portion of ni's finite activation energy, leaving a smaller portion for "weaker" competitors. It is the . f~ct tha~ aj(t), the activation of the rece1v1ng ne1ghoor node, appears in the formula for out j i ( t) abov~ that makes this a competition-based model. F1nally we define the total flow of activity into a node nj at time t to be

the sum of all its inputs from neighbors.

In summary, a specific form of spreading activation has been described where the portion of a node ni's output activation going to neighbor node nj is proportional to the ability of n - to compete for that activity (reflected by the Jformula for outji (t) above): ?ive~ this competition-based approach to d1str1but1on of activation, we can adopt an approach similar to that used by others to update a node's activation level (e.g., [ 10 ]) · Let the symbol Ii (t) indicate the net flow of activation into ni at time t, i.e.,

Then the rate ai(t) at which ni's activation changes is given by the net flow of activation into the node minus the decay:

The term ( 1 - a . ( t)) in this latter equation assures that ai ( t) approaches its maximum value asymptotically. Note that all of the above computations are local in the sense that ni only needs to "see" the activations and weights associated with its immediate neighbors.

Two numerical examples are now presented to demonstrate the behavior of the above competition-based parallel activation model. These examples are based on the network in Figure 2, and were implemented using PAN, a parallel activation network simulator. PAN is a LISP program that permits one to specify a network and method for spread of activation, and to describe external inputs to the network that are to occur during simulation. PAN then performs the indicated simulation while periodically displaying the activity level of nodes (PAN is similar in spirit to ISCON

Figure 3 illustrates a "simulation specification" as it is given to PAN. The first eight lines specify the four word and four word sense nodes of Figure 2, indicating that each node has both a resting activity and a decay rate of 0. 0. The next four lines specify the PARent connections INto the word nodes along with appropriate weights, and the subsequent four lines specify the corresponding SON connections INto the word senses (compare with Figure 2). The next line, indicating external INPUT to the network, has the format

(INPUT node start-time stop-time amount). Figure 3 thus indicates that an external INPUT of 1.0 units of activation enters word W3 during the first 6 units of time, simulating the occurrence of word W3. Next a constant DELTA of 0.1 units of time is specified, indicating the fineness of time quantization, and PAN is told to run the simulation for 20 units of time.

Upon giving the simulation specification in Figure 3 to PAN, the following output was produced by the above competition-based model:

This simple "lossless" network number of important properties illustrates a possible with competition-based spread of activation. First, the spread of activation is circumscribed in that it radiates only to nodes S2 and S3, the senses evoked by W3. Activation levels in all other nodes remain at zero. Second, although the input stimulus terminates after six units of time, activity in the activated nodes subsequently remains stable. This is reminiscent of "stable coalitions" [5]. Third, this example demonstrates virtual lateral inhibition between S2 and S3, with the dominant S2 rapidly suppressing activity in S3 indirectly by absorbing the majority of activition available from W3. Past models of spreading activation have only produced such lateral inhibition by having explicit inhibitory connections between nodes like S2 and S3. Finally, note that there is a brief initial period of time when the ratio of activity S3/S2 is relatively high. This initial "window of opportunity" makes possible some interesting context effects, as illustrated below.

For the second example, we illustrate how a prexisting "context" can result in the appearance of a switch being thrown to redirect the flow of activation. To do this, we use the same simulation specification as that given in Figure 3, except the previous single external INPUT statement is replaced with the following two statements:

The first input stimulus is exactly the same as in the preceding example. The second weaker input (0.2) is directed to S3 (recall that S3 was indirectly inhibited by S2 in the previous example). This latter "input" is used for illustrative purposes to simulate positive feedback from the "context" C2 in which disambiguation of word W3 is occurring (see layer C in Figure J.). In this situation, PAN produces the following listing of activations:

In this example, the absolute contextual effect produced by retrograde excitation to node S3 "switches" or "gates" the flow of activity from node W3 completely to S3 (contrast with the first example above). The absolute switching here is contingent upon the resting level of S2 and S3 being zero initially; in networks where ri might be a very small positive number, perhaps reflecting the relative frequency with which the concept represented by node ni occurs, switching/gating of the sort demonstrated here directs a small amount of activation to S2.

IV DISCUSSION

This paper has presented an approach to spreading activation in parallel associative networks that is distinguished from previous approaches by its competition-oriented nature. A theory of competition-based parallel activation as a model of associative memory has not been significantly studied in AI in the past, although there is some relevant related work. For example, the idea of nodes as active agents bears some resemblance to "actors" [ 14], and the "contract net framework" involves at least an implicit notion of competition [ 13]. However, both of these and similar models are "message passing systems" at the AI symbol processing level [4]. Others have postulated competition and/or parsimonious allocation of activation/energy as important influences in cognition, but this work has been at the "hardware level" of neural modeling and has been formulated quite differently [3,7,8,9].

As illustrated above, even in the absence of explicit inhibitory connections between nodes, a competition-based approach to spreading activation can exhibit a number of important properties: virtual lateral inhibition between appropriate nodes, circumscribed activation, stability of activation ("stable coalitions"), and context effects (e.g., switching). Our research group is currently investigating the feasibility of developing a full-scale model of the cognitive activities involved in the real world print-to-sound mapping [ 11 ]. This task should provide an excellent test of the theory of competition-based spread of activation proposed in this paper.