A Coincidence Detection Network for Spatio-Temporal Coding: Application to Nominal Composition

1 Introduction

The electrophysiology of the cerebral cortex reports an ability of the neurons to perform spatio-temporal coding. For example, [Abeles, 1982] shows that the firing of a neuron can elicit a spike in another one a few milliseconds later. This time-locking of activity between neurons leads to chains of synchronous firing units: synfire chains. This ability to detect event coincidence has already been implemented in formal neural networks, for example [Roques and Beroule, 1991] handles the application of guided propagation to sentence parsing.

For symbolic processing a fine observation of the network is necessary to deduce the emergent representations and to give their cognitive counterpart (cf. [Harris, 1990]). Therefore, the network presented here implements coincidence detection rather than correlation. The spikes in our model can be assimilated to bursts of spikes in one using correlation. The learning procedure naturally associated with units reacting to synchrony is the Hebbian rule [Little and Shaw, 1975] from [Hebb, 1949]. It enhances the links between synchronously firing units and brings forth the paths detecting spatio-temporal patterns of activity.

The application of a formal network to subtle linguistic problems like categorisation [Lakoff, 1987] and well-

2. 2 The topology

With a recurrent topology, repeating spatia-temporal patterns corresponding to cycles of synfire chains can be observed [Abeles, 1992]. To understand the basic phenomena, we have chosen a feed-forward organisation with non-overlapping events. The detection of fixed point or limit cycles is replaced by an observation and a comparison of output activities (Figure 2).

The stimuli patterns are fed into the input layer where they trigger the corresponding units. Then, a wave of activity shifts towards the output units. A subnetwork N with one output unit is characteristic of a sequence S of events if the introduction of S leads to a firing of the output unit. The firing should not be provoked by any subsequence of S or with any subnetwork of N.

2 · 3 The construction

The initial network is built accordingly to the parameter values defining its size and its connectivity. It is composed of C columns built from L layers of R rows (Figure 3).

Each unit which is not an output unit possesses a number of efferent links randomly chosen between C1 ali C2. Each link has an initial strengtl! wo (wo<l.O) and a temporal delay uniformly chosen between C3 and C4. Each link from a unit in the nth layer reaches a unit whose layer is a random number between n+ 1 and L. (100 . Cs)% of the connections are interior to a column. The other ones reach another column which is chosen randomly.

For the numerical application of 2.4, the values used for the parameters are: R = 12, L = 7, C1 = 5, C2 = 13, C3 = 1, C4 = 5 and Cs = 0.7. C has two values: 2 for cuisson+Prep+NP (used in 2.4) and 3 for Noun+a+Noun.

The optimisation of these parameters has been obtained with a simple genetic algorithm. The performance of a network is the evaluation of the quality of its answers on a training set composed of linguistic and logic examples. The genetic operator is the generation of a new network through small random variations of the parameters from their values in the network with the best performance. The absence of intrisic parallelism in this algorithm does not prevent it from staying in a local maximum.

2.4 A combinatorial study

Figure 2.1. The simultaneous activities on input units U 1, subnetwork characteristic of this particular coincidence. The U2, U3 and U4 is detected 6 time steps later by Uo.

Figure 2.2. The network of Figure 2.1 with different delays detects a sequence of non-simultaneous activities.

This section is intended to check that the ranges of the construction parameters give a rich enough combinatorial potentiality. The general problem being too complex, the question is limited to the detection of a sequence of two activities of input units. Such a sequence is given by i1 ali i2 the input units and by 0 and ot the times when the activities occur. We calculate the probability of finding a weights are equal to 0.5 and the thresholds are equal to 1.0 so that a postsynaptic neuron can only be triggered under the synchronous excitation of at least two neurons.

The different subnetworks of two or three layers characteristic of the two events are given by Figure 4. Let us find the probability of having the general subnetwork v:

where p1 is the probability of finding two efferent links from u1 and u2 reaching the same unit U3: if Cl == C2 == C3

if(c1 ==C2 *C3)or(ci *c2 andc1 * C3 andc2 * C3)

if Cl :jl: C2 and (Cl or C2 == C3)

where p2 is the probability that those links have the expected delays (we suppose that both delays belong to the interval [C3 C4], otherwise the probability would be null):

n is the average number of combinations of efferent links:

From (i), we deduce the probability of finding a network like (1) (Figure 4):

P((l). e. e + ot)

==P((ci, 1, n), (c2, 1, n), (C3, L, n), e, e + ot)

if c1 * c2 P((l). e. e + ot) == P' = 4.72 1o-s

if c1 == c2 P((1), e. e + ot) == P = 9.06 10-s

If Ot == 3, e can take any value between 1 and 2, C3 any value between 1 and C and n any value between 1 and R. Hence:

if Cl :: C2 P((l)) == 1 - (1 - P)2xCxR:: 2 C R P:: 4.35 10-3

The probabilities of the networks (2), (3) and (4) (Figure 4) are calculated similarly. Each network (x) is divided in two subnetworks, the upper one (x ') and the lower one (x") For a given layer of the hidden unit (13), the probability of having a subnetwork (2') is equal to P((1), e. e + ot ). The

probability of (2") depends on the value of 13: P((2")) = n p1 p2 = 0.0634/(L- 13)2 For a given 13: ifCI ==C2 P((2), h)== 1- (1- PP((2")))2x5xCxR = 1.38 1Q-3 . 1/(L- 13)2 if Cl * C2 P((2), 13) == 1 - (1 - P' P((2'')))2x5xCxR = 0.71 1Q-3 . 1/(L- 13)2 When 13 varies from 2 to L - 1: ifc1 ==C2 P((2)) ::1.38 1Q-3 · R C I,(l/(L -13)2):: 4.81Q-2 if c1 *c2 P((2)):: 0.71 1Q-3 · R CI.(l/(L- 13)2)= 2.5 1Q-2 Similarly, if Cl == C2 P((3)):: 8.6 1Q-3 and P((4)):: 1.23 1Q-3 if Cl * C2 P((3)):: 4.45 1Q-3 and ((4)):: 0.64 10-3

These results show that the probability of finding a topology characteristic of two events separated by ot, in two different columns, is 0.025. This value seems low but:

• Taking into consideration the subnetworks of more than 3 layers would slightly increase the probabilities.
• The average number of pairs of features for two 12-bits patterns is 36. The probability of detecting one of the 36 pairs is about 0.6, in the preceding conditions.
• The probability of detecting simultaneous events (ot == 0) in the same column is higher: 0.11 instead of 0.025. In this case the probability of detecting at least one cooccurrence of two features in a 12-bits pattern is 0.97.
• The problem can be extended to cooccurrences of three or more events. The subnetworks can also be organised into a hierarchy and detect coincidences of coincidences like the one given in Figure 8, section 3.2.

Nevertheless, the quality of the results depends on the match between the stimuli and the available topology.

2. 5 The learning rule

The aim of the learning procedure is to select topologies (and the associated links) which are characteristic of relevant feature cooccurrences. Therefore, the Hebbian learning rule is chosen to enhance the strength of the connections in case of transmission success and reduce· them in case of transmission failure. More concretely: let us assume that neuron Ni is linked to Ni by a connection with a delay olij and a strength Wij. If Ni triggers otij time steps after Ni:

Wij ( t + 1 ) == min( k1 Wij ( t ) , Wmax ) k1 > 1.0 and ifNi triggers without activity of Ni Otii time steps earlier or Ni triggers without activating Ni Otij time steps later· :

The value of the weight modification is independent from the distance Otii between both neurons. It is considered as a local law modifying the weight according to the correlation of an incoming spike and a triggering of the unit without consideration for the distance.

To avoid overactivity, the connections must have an

1 In [Little and Shaw, 75], transmission failures only occurs when the presynaptic firing does not induce a postsynaptic one.

initial strength wo which is low enough to prevent the spike of a presynaptic neuron from activating a postsynaptic one on its own. The initial connectivity is rich, but only a few links are enhanced during training. For example, in the experiment on Noun+a+Noun, out of 1,600 initial links, 1,000 are left unchanged, 450 vanish and 150 are enhanced. In this case only 9% of the links are significant.

2. 6 Learning and prediction

The learning is done by introducing repeatedly the training set into the network. 10 epochs are sufficient because the values chosen for the coefficients k1 and k2 are high.

The learning procedure enhances the afferent links corresponding to the coincidence of at least two events. After learning, the same coincidence can be detected if only one of both signals is present. This ability to detect partial information can be used for prediction on novel data.

When learning is achieved, the activity of the output units is recorded after each introduction of an input pattern (or of a sequence of patterns). The prediction of the network for a new stimulus relies on a comparison between the recordings of the output activities. The response is the stimulus from the training set which gave the closest activity on output units. The closeness is the number of common activities decreased by the number of distinct activities. Hence, the output units are not the output of the system as seen by the user but an intermediate representation. The final output is obtained through a classic comparison algorithm.

3 Application to nominal composition

3.1 Meaning and acceptabilities of 'N+a+N'

The Noun+a+Noun compounds are particularly interesting because they offer a wide range of interpretations. Some are strongly compositional like boite a ( chaussures + clous) [(shoe + nail) box]. when others have a conventional and idiomatic meaning like pied-<l-terre[pied-<l-te"e]. Whatever the compositionality is, the meaning of the whole depends on the meanings of its parts and on the operation performed by the preposition [Cadiot. 1989]. Similar phenomena have been modelled with the help of connectionist networks. For example, [Victorri, 1988] describes the interpretation of the polysemous adverb encore [yet, still, again] with a perceptron. It accounts for the different linguistic observations, their continuity and the various ambiguities.

The coincidence detection network can account for the correlations observed between the meaning of a compound noun and the acceptability values of different tests [Cadiot, 1992] (Figure 5).

Each array of acceptability values is fed into the input layer, and the activities of the output units are recorded for 30 time steps. The answer of the network to the novel compound noun is interpreted as its most plausible interpretation(s) (see Figure 6). When fed with the acceptabilities of ve"e a bordu.re doree[glass with a golden rim]. the network assigns correctly the interpretation non removable part. It gives the highest score to verre a pied[stemmed glass]. the compound from the training set having the same head noun and the same interpretation. However, four a gaz[gas oven] obtains a positive score because it has several common acceptabilities with ve"e a pied (and verre a bordure doree). This confirms that the quality of the response depends on the available topology and on the orthogonality of the different codes.

3. 2 Prepositional phrase understanding

The second application concerns the spatial interpretation of cuisson[cooking]+Prep+NP (see examples Figure 7). For the sake of clarity, the determiners are not taken into consideration in this experiment, they can be ignored in a first approximation.

The interpretation of the phrase (Figure 7) is a spatial schema [Langacker, 1987] characterised by the relative position of a trajector, the thing to cook, and a landmark, the place where it is cooked (see also [Vandeloise, 1986]).

The network has to infer the composition rules from a set of representative constructions using a rich enough variety of preposition I noun phrase combinations.

A sequence of words and an interpretation must be processed simultaneously. Such a dynamic binding can be found in works following Elman's recurrent feed forward network [Elman, 1988]. For example, [Jain, 1989] presents a network intended for parsing sentences with embedded clauses where words are represented by semantic micro­ features. In other works, the dynamic semantic role assignment is done by a localist network (one unit per word or per symbol) [Cottrell and Small, 1983].

In order to avoid localist or micro-localist representations, the data fed into the networks are the random codes of the constituents (the preposition and the noun phrase) and the meaning (the spatial schema). The coincidence detection allows for direct association between form and meaning [Langacker, 1987]. The topology is composed of two columns of 12 units. Each code is a random binary number between 1 and 21 2 - 1. At time step to the code of the preposition is fed into the first layer of the first column. At to+ot ( ot=3), the code of the noun phrase is fed into the first column simultaneously with the code of the spatial schema into the second column. Whatever codes are chosen, provided they are orthogonal enough, the network has to extract the relevant associations between the preposition, the noun phrase and the schema.

Figure 8 shows how the reinforced links of the network represent the direct association between the prepositions sur [on] and sous [Wider] and the associated semantics ON and U:r;.lDER. Such coding prepositions force their semantics to be the interpretation of the whole structure. Conversely neutral prepositions like a [at] call for an inference mechanism to calculate the meaning from the predicate

(cuisson [cooking]) and the argument (the noun phrase) [Cadiot, 1989].

The network can also be fed with incomplete data like structures without semantic interpretation. When fed with the novel compound sur Ia cocotte [in the casserole]. it associates correctly the most plausible interpretation ON (Figure 9). The three first scores of sur[on] are slightly different. This is due to the existence of spurious coincidences between sur and the three noun phrases le gril[the grill], Ia poele[the frying pan] and feu vif[a brisk heat]. These coincidences may be activated by Ia cocotte[the casserole] depending on the similarity of its code with the ones of the three other noun phrases.

4 Conclusion

This study presents a mechanism for processing complex patterns or sequences of patterns. A rich connectivity and a detection of event coincidences are associated with the Hebbian learning rule. When linguistic data are introduced into the network, the subnetworks corresponding to the relevant features and features associations have their links enhanced. The observation of these subnetworks confirms the predictions of linguistic studies for the modes of composition between noun predicates and arguments. Such a system can be used for complex semantic interpretations depending on interacting linguistic clues. It can help in extracting implicit categorisation from sets of well-formed expressions.