A chunking mechanism in a neural system for the parallel processing of a propositional production rules

84 Mathware and Soft Computing 2 (1995) 85-116 A chunking mechanism in a neural system for the parallel processing of propositional production rules ∗ E. Burattini, A. Pasconcino, and G. Tamburrini Istituto di Cibernetica C.N.R. I-80072 Arco Felice, Italy e-mail: [email protected].it Abstract The problem of extracting more compact rules from a rulebased knowledge base is approached by means of a chunking mechanism implemented via a neural system. Taking advantage of the parallel processing potentialities of neural systems, the computational problem normally arising when introducing chuncking processes is overcome. Also the memory saturation effect is coped with using some sort of “forgetting” mechanism which allows the system to eliminate previously stored, but less often used chunks. Even though some connection weights are changed in the process of storing or discarding chunks, we emphasize that this neural system cannot be regarded as a “connectionist” system, since a localist semantic interpretation is adopted and no classical learning algorithm is employed. ∗This work was partially supported by “Progetto Finalizzato Trasporti 2” of C.N.R. and by the jointly supported French-Italian project “Galileo”. 85 86 E. Burattini, A. Pasconcino & G. Tamburrini 1 Introduction The power law of practice is an experimental law of psychology asserting that reaction times in the execution of certain motor-perceptual and higher cognitive tasks decrease exponentially with the number of trials-until a lower bound, depending on the task, is reached. A tentative theoretical account of this regularity detected in human cognitive behaviour is the chunking theory of learning of Newell and Rosenbloom (1981), which hinges upon the chunking hypothesis formulated in Miller (1956): A human acquires and organizes knowledge of the environment by forming and storing expressions, called chunks, which are structured collections of the chunks existing at thetimeoflearning. Miller does not specify the nature of the primitive chunks on the basis of which humans form and store new chunks. In the SOAR system, which embodies the fundamental assumptions of Newell and Rosenbloom’s chunking theory of learning, these “pre-existing” chunks are identified with production rules. And, again under the form of production rules, the chunking mechanism of SOAR enables the system to store in memory new chunks isolated on the basis of previous problem solving activity. (See Laird et al. (1986), Laird et al. (1987), Newell (1990), p. 185f.) Independently of their cognitive plausibility, chunking mechanisms on production rules may play a significant role in AI applications, both for the automatic acquisition of knowledge bases and for the design of more efficient problem solving strategies. In this paper, we are concerned with the use of chunking mechanims for addressing the latter problem. In particular, we describe a chunking mechanism generating production rules which codify associations between initial data and final outcome of an inferential path, and thus enabling a rule-based system endowed with it to bypass that inferential path upon successive presentations of the same initial data. Chunking mechanisms generally give rise to what, following Tambe et al. (1990), may be called cognitive and computational effects. The cognitive effect is the reduction of the number of (inferential) steps A chunking mechanism in a neural system... 87 needed to carry out a given task. The computational effect is the increase of the time needed to carry out each individual step. Thus, what is gained in efficiency by reducing the number of steps is often lost by an increase of execution time for each step. Clearly, when chunks take the form of production rules, the time required for executing the matching process between data in working memory and the antecedents of production rules may increase. In fact, more rules have to be scanned, and the newly introduced rules may contain more complicated antecedents than those present in the original system of rules. Another related phenomenon may be called the memory saturation effect: given preassigned finite memory capacities, a system endowed with a chunking mechanism, but incapable of “forgetting” some of the previously stored chunks, will be eventually unable to make room for newly acquired and possibly more useful chunks. In view of the computational and memory saturation effects, an efficient use of chunking mechanisms requires a computational agent capable of (a) leaving unaltered the access time to knowledge when new chunks are added, and (b) attenuating the incidence of the memory saturation phenomenon. The chunking mechanism described below –extracting associations between initial data and final outcome of a forward chaining inferential path– does satisfy condition (a). Condition (b) is satisfied as well, if the relative frequency of use of chunks is regarded as a satisfactory criterion for deciding which chunks have to be “unlearned” by the system. This chunking mechanism is embedded into a system for parallel forward chaining on propositional production rules. This rule-based system can also perform goal-directed queries, in order to gather information useful to establish its current goals. And its justification module enables the user to get information about inferential paths that have been followed in establishing a given goal. The system is entirely formed by non-linear threshold neural elements. It is worth noticing that also the control of the inferential, query, chunking, and justification processes is entirely carried out by a neural network, too. 88 E. Burattini, A. Pasconcino & G. Tamburrini One may therefore legitimately qualify this system as a purely neural system. However, it cannot be regarded as a “connectionist” system, insofar as a localist semantic interpretation (as opposed to a distributed one) is adopted, and the classical learning algorithms used in connectionist systems are not employed here. In view of these qualifications, it should be evident that the choice of a neural architecture for this system is chiefly motivated by the idea of exploiting at best the parallel processing potentialities inherent in propositional production rule sets. AI applications of this system in diagnostic problem solving domains have been developed (see for more extensive discussion Burattini and Tamburrini (1992), and Aiello et al. (1995a, b)). Sections 2 to 6 provide an overall description of the system modular organization, neural architecture, and the implementation of forward chaining, query, and justification processes. Section 7 is exclusively devoted to the chunking mechanism. The appendix reports a trace of a forward chaining session, the recording of the appropriate chunk, and a new run of the augmented system of rules on the same initial data. 2 System overview In this section we describe the overall functional organization of the system. Figure 1 shows the main modules of the system. The labels “Maker”, “Process”, and “Recorder” associated to arcs in that figure refer to the algorithms that are respectively used for constructing the neural network, carrying out its inferential activity, and recording the new chunks isolated on the basis of previous runs of the system. Given a set of propositional production rules presented in a certain canonical form, the algorithm Maker yields a neural network for executing forward chaining, goal-directed query, and chunking on this system of rules, in addition to building an appropriate neural justification module for answering user’s queries. When this neural system has been constructed, and a list of n+m propositional literals representing ninitial data and mgoals is given in input, the Process algorithm simulates the activity of the network, by a synchronous updating of the state of neural units. Time is treated as A chunking mechanism in a neural system... 89 Figure 1: General Scheme a discrete variable, and the time interval needed by any neural element for processing the incoming information is assumed to be independent of the number of input channels and to be equal to 1. The ninitial data are transferred to the Chunk Module (CM)in order to recall the r(with r≥0) propositional literals that the system inferred if and when presented in previous runs with (a subset of) the same initial data. More specifically, CM checks whether the initial data match the antecedent parts of stored chunks (these chunks can be viewed as particular rules as well). Then the rdistinct literals appearing in the consequents of those chunks are retrieved by CM and immediately made available to the forward chaining layer of the Rule Module (RM). The RM module performs forward chaining on the system of production rules and goal-directed query. RM isstartedonthesetof ninitial data independently of what is the outcome of the chunk retrieval process, since (i) it may still infer other literals in addition to the rliterals retrieved by CM or (ii) it may have to provide, upon request, an appropriate justification for (the trace of an inferential path to) the literals obtained by the chunk retrieval process. Case (i) may apply if the antecedents of the chunks retrieved in CM contain only a proper subset of the set of ninitial data, or if responses to queries make available additional premises. The activity of RM terminates when no other rules can be acti- 90 E. Burattini, A. Pasconcino & G. Tamburrini vated by forward chaining, and no more information can be accrued by goal-directed query. At this stage, the system shows which, if any, of the mgoals have been established, and displays any other propositional literal which is (i) included in the initial data, (ii) declared by the external source to hold in response to a goal-directed query, (iii) obtained via the chunking mechanism or (iv) inferred by forward chaining starting from data obtained by (i) or (ii). The user can activate the Justification Module (JM) on any of the displayed propositional literals. JM indicates whether this literal satisfies (i) or (ii); if it does not, JM provides a trace of the shortest inferential paths to it. 1 At the end of each run of the system, the algorithm Recorder isolates a chunk <I,C>,where,fork,m ≥1, I={p1,...,p k}is the set of initial data provided to the system in that run and C= {q1,...,q m}is the set of literals derived by forward chaining in RM starting from I. These chunks should be interpreted as conditional statements p1∧...∧pk→q1∧...∧qm, where the literals in the antecedent are the elements of I, and the literals in the consequent are the elements of C. If the chunk <I,C>was already stored in CM as a result of previous runs of the system, this fact is signalled by CM, and the algorithm Recorder merely modifies the weights of the neural units that are devoted to storing data about the relative frequency of use of chunk <I,C>. Otherwise, the chunk <I,C>is stored in CM. In the latter case, the new chunk <I,C>may replace one of the previously stored chunks that have been less frequently used during the system operation. 3 Processing units and their semantic interpretation The network is formed by threshold neural units, whose activation at time tis determined by the equation uh(t)=1  n  j=1 uj(t−1)wjh −θh+EXTh(t) (1) 1Notice that JM provides such a trace also for literals obtained by chunking. A chunking mechanism in a neural system... 91 where -uh(t) is the state of unit hat time t; -uj(t−1) is the state at time (t−1) of unit j; -θhis the threshold value of unit h; -wjh is the weight of the direct connection, if any, from unit jto unit h, which can be modified only during the intervals between different runs of the system; -EXT h(t) is an input signal to unit hincoming at time tfrom a source external to the system. -1(x)=1x>0 0x≤0is the step function determining the state of the neural units; In view of the fact that the state function can assume only values 1 and 0, these threshold elements can provide, under a localist semantic representation, boolean-valued information about the literals they are associated to. For example, the system includes a layer of neurons called GOAL (see figure 6 in Appendix), which is formed by as many units as the distinguished consequents in the system of production rules; the unit in this layer associated to, say, literal pis in state 1 if and only if pis a current goal of the inferential process. The various kinds of boolean information provided by the neural units belonging to the main submodular components of RM,JM and CM are briefly described hereinafter. (For an example of how neural activity propagates through the network, and a figure sketching out the flow of information between the submodular components of the system, the interested reader is referred to the example reported in the Appendix). Let xbe a variable ranging over literals. Then, - if the neural representative of xin the block ANTECEDENT (and DATAIN) is active (its state is 1), then xbelongs to the set Iof literals constituting the initial data provided by the user; 92 E. Burattini, A. Pasconcino & G. Tamburrini - if the neural representative of xin FORWARD (and FORWARDBF) is active, then xfollows by application of the forward chaining process from the set I; - if the neural representative of xin INFERREDBF is active, then xfollows by application of the forward chaining process from the set I; with respect to the representative of xin FORWARD, however, the neural elements of INFERREDBF play the role of “temporal filters” as described in sect. 6 below; - if the neural representative of xin GOALACTIVE is active, then xbelongs to the set of goals of the system; - if the neural representative of xin SUBGOAL is active, then xis a temporary subgoal, generated by the system while attempting to establish its current goal; - if the neural representative of xin QUERY is active, then the external source is to be queried in order to decide whether x holds; - if the neural representative of xin QUERYTRUE is active, then the external source has asserted that xholds; - if the neural representative of xin QUERYFALSE is active, then the external source has asserted that xdoes not hold (or, equivalently, that the negation of xholds); - if the neural representative of xin QUERYNOTKNOW is active, then no information on xhas been obtained from querying the external source; - if the neural representative of xin CONTRADICTION is active, then the set of literals comprising initial data, data asserted by the external source, and results of forward chaining includes both xand ¬x; - if the neural representative of xin ACTIVEJ is active, then the user has asked information about the inferential and query paths that led the system to assert x; A chunking mechanism in a neural system... 99 a justification module exhibiting only the trace of the “minimal” inferential paths to x, and namely, those paths which require the least number of parallel processing steps from the activation of the input layer of neurons to the activation of the neural representative of xin FORWARDBF. Let us consider, for example, the following system of rules: (R1) a∧b→e (R2) b∧c→e (R3) d→c If the set of initial data is I={a, b, d}, then the system will reach ein one step by applying (R1), and in two steps by applying (R3) and (R2). Since the first inferential path requires less processing steps than the second one, the justification module exhibits only the trace of the first inferential path to e. Figure 4 shows the neural net providing a competitive filter for this system of rules, which enables the justification module to select the “minimal” inferential paths to e. Crucial to this filtering function are the inhibitory connections (represented by dashed arrows) between the neural representatives in INFERREDBF of the occurrences of ein (R1) and (R2). Indeed, if ebecomes active at time t,thene cannot become active at any later time, and conversely. Thus, when the user asks the justification for the assertion eby activating the neural representative of ein ACTIVEJ, at the next instant of time only the neural representative of the occurrence of ein (R1) will become active in INFERREDJ. The justification procedure is then applied to the literals constituting the antecedent of (R1), whose neural representatives in PREMISEJ become active, thus signaling that aand bare element of I. 7 Chunking mechanism In the previous sections we have described the modules for parallel forward chaining, query, and justification. Let us now turn to consider the module CM for the chunking process. The chunks stored in CM take the form <I,C>,whereI={p1,...,p k}is a set of literals 100 E. Burattini, A. Pasconcino & G. Tamburrini Figure 4: INFERREDBF Filter provided as initial data to the system and C={q1,...,q m}is the set of literals derived by forward chaining in RM starting from I.These associations enable the system to reduce processing time: whenever a set of input data coincides with or strictly contains the literals in the first element of a stored chunk, at the next step the system outputs the literals in its second element. Constructing a chunking mechanism of this sort, efficiently coping with the computational and memory saturation problems (see sect.1), involves solving the following problems: (i) recognizing an input pattern previously presented to the system in order to recall the chunks with antecedents matching the input pattern (or else storing an input pattern presented for the first time to the system); (ii) keeping track of how often the stored chunks are used during the system operation, in order to discard less often used chunks when new chunks have to be acquired; (iii) executing operations (i)-(ii) in a preassigned time, independently of the size of input patterns and the number of stored chunks. It is unlikely that problems (i)-(iii) can be efficiently solved using the typical learning methods used in connectionist systems. In fact, A chunking mechanism in a neural system... 101 (a) multilayer connectionist networks require, for effectively storing any newly presented input pattern, repeating the training session on the whole set of input patterns. This indicates the difficulty of using such networks for solving problem (i), in view of the fact that training by backpropagation may require exponential time in the number of input patterns (see Judd (1990)). (b) Hopfield’s nets (see Hopfield (1982), (1984)), when used as autoassociative memories, enable one to store patterns by a procedure (oneshot learning) determining the appropriate weights in linear time in the number of patterns. There are, however, interference effects between nonorthogonal patterns, and considerable processing time may be needed to converging into a stable state. (c) While Grossberg’s ART networks (see Carpenter and Grossberg (1987)) may provide a sensible solution for the plasticity-stability problem, they seem unsuitable for addressing problem (iii). Indeed, the performance of ART networks depends on (c1) the time tneeded to compare a previously unclassified input vector Xwith the stored prototypes having non-empty intersection with X, before assigning to Xa new class; tis a linear function of the number of such prototypes and therefore, if the number of prototypes is greater than the number of steps RM requires to complete the forward chaining process, then the introduction of an ART-like CM module would not improve the performance of the system; (c2) the time tneeded by the two competitive layers to converge to a stable state; the value of tcannot be fixed a priori, and a bound on it can be estimated only experimentally, because reaching a stable state depends essentially on the number of components in each competitive layer and on the relative intensity of the inputs to the competitive layers. The module CM affords a sensible solution to problems (i)-(iii). The algorithm Recorder stores each chunk <I,C>by constructing two different links, respectively connecting (*) every literal in Iwith 102 E. Burattini, A. Pasconcino & G. Tamburrini a given index j, and (**) index jwith all the literals in C. This mechanism enables one to eliminate interferences between non-orthogonal patterns affecting traditional neural associative memories, such as the multilayer perceptron (see Rumelhart and McClelland (1986)) and the linear associators (see Kohonen (1977), (1982)): links (*)-(**) establish a one-one correspondence between first and second element of each chunk. Let us now turn to describe the operation of CM.Uponpresentation to the system of an input set of literals I, three different cases may occur. Case 1: For every index jthe first element of the chunk <I j,C j> is different from Iand case 3 below does not hold. In this case, CM does not recall any stored chunk. However, when forward chaining on Iis completed and outputs a non-empty set of literals C, the algorithm Recorder selects a new index jand stores a new chunk <I j,C j>, with I=Ijand C=Cj. Case 2: There is an index jsuch that I=Ijfor some chunk <I j,C j>.CM recognizes this situation, and provides the elements of Cjas outputs of the forward chaining process. Case 3: For every index jthe first element of the chunk <I j,C j> is different from I, but there are indexes j1,...,j ksuch that IJ1,...,I jk are strictly included in I.ThenCM provides the elements of S= ∪{Cj1,...,C jk}as outputs of the forward chaining process. When forward chaining on Iis completed and outputs a non-empty set of literals C, the algorithm Recorder selects a new index jand stores a new chunk <I j,C j>,withI=Ijand C=Cj. The overall functional organization of the CM module4is shown in figure 5. Let us now describe in more detail how the network behaves in cases 1-3. CASE 1: When Iis given as input to CM at time t= 0 (and the neural units representing its elements in PATTERNON and PATTER4This configuration is not optimal with respect to the use of resources. In fact, a single layer could be designed which is functionally equivalent to the two layers PATTERNON and PATTERNOFF. The use of two such distinct layers was motivated by considerations of a semantic character. For more details see Pasconcino (1994). A chunking mechanism in a neural system... 103 Figure 5: Chunk Module (CM) NOFF become active at t= 1), the relation ∀jI=Ijis recognized to hold at time t= 2 at the next instant of time since, for every j, the neuron representing index jin the layer INDEX is inactive at that time. At time t= 3, the impulse from control neuron CLOCK2 activates the other control neuron CTRIND, whose activity is necessary and, together with impulses from PATTERNON (which are absent in this case), sufficient to activating subpatterns in SUBINDEX. Thus, at time t= 4 (resp. at time t= 5) all neurons of layers SUBINDEX (resp. of PATTERNOUT) are inactive. As a consequence, the neural activity triggered by the input set I in the CM module does not recall the second element of any chunk represented in the layer PATTERNOUT. So, at time t=6onlythe input set Iis transferred to the RM module. Finally, when forward chaining on Iis completed and outputs a non-empty set of literals C, the algorithm Recorder selects5a new index jand stores a new chunk <I j,C j>,withI=Ijand C=Cj. The recording of a new chunk consists of the change of the weights of the following connections: (1) the connections between the neural representatives of the elements of Iin PATTERNON and PATTERNOFF on the one hand, and the neural representatives of the selected 5See below the paragraphs under the heading “SELECTING INDEXES” for a description of the selection procedure and the role of the INDEXBF layer. 104 E. Burattini, A. Pasconcino & G. Tamburrini index jin INDEX and SUBINDEX on the other hand; (2) the connections between neuron jof SUBINDEX and the neural representatives of the elements of Cin PATTERNOUT. The weights of the connections between PATTERNON and INDEX are initialized with the following values wPon iIndexj=0 j=1,2,...,M;i=1,2,...,N; where Mis the maximum number of patterns which can be stored by the system (that is, the maximum number of index neurons available in INDEX), Nis the dimension or number of components of input patterns (that is, the number of neural units in each layer PATTERNON and PATTERNOFF), Indexjand Pon iare neurons of the INDEX and PATTERNON layers, respectively. The weights of the connections between PATTERNON and Indexj are updated according to the rule w Pon iIndexj=1/|I|if Pon iactive; wPon iIndexjotherwise; (6) where |I|= n  j=1 uPon j The weights of the connections between PATTERNOFF and INDEX are initialized with the following values wPoff iIndexj=−1; j=1,2,...,M;i=1,2,...,N; The weights of the connections between PATTERNOFF and Indexj are updated according to the rule w Poff iIndexj=0ifPoffiactive; wPoff iIndexjotherwise; (7) Rules (6) and (7) ensure that exactly one neuron in INDEX becomes active when case 2 occurs. (See Pasconcino (1994) for a detailed justification of this claim.) A chunking mechanism in a neural system... 105 The algorithm Recorder initializes the weights of the connections from units of SUBINDEX to the units of PATTERNOUT in the following way wSubndexjPout i=0 j=1,...,M, i=1,...,Nc; where Nc is the number of “consequents” in the system of rules, i.e., the number of the production rules. The weights of the connections from unit j’ active in SUBINDEX to the neural representatives of those “consequents” that are active6in PATTERNOUT are updated by the following rule w SubndexjPout i=1ifPout iactive; 0otherwise; (8) Rules (6), (7), and (8) ensure that when the input set Ijis presented to the network the neurons representing the elements of Cjin PATTERNOUT are activated, in the way described in CASE 2 below. CASE 2: ∃j:I=Ij.WhenIis given as input to CM at time t= 0, the neural units representing its elements in PATTERNON and PATTERNOFF become active at t=1. Attimet= 2, the neuron representing index jin the layer INDEX becomes active, as determined by rules (6) and (7). The system has identified Iwith Ij. When this identification is successfully completed, CM has to retrieve from index jthe second element of the chunk <I j,C j>. Since, at time t= 2, the index neuron jin INDEX is active, then at time t= 3 the neural unit in SUBINDEX representing the same index j will become active as well. And, at time t= 4, the neurons in PATTERNOUT representing the elements of Cj, as associated to the input pattern I=Ijby rule (8), will become active. Finally, at time t= 5, the neural representatives of elements of Cjin the forward chaining layer of RM are activated by direct connections from the PATTERNOUT layer of the CM module to the FORWARD layer of the RM module. CASE 3: ∀jI=Ij, but ∃j1...j k:Ij1⊂I∧...∧Ijk⊂I.I contains subpatterns Ij1,...,I jkwhich consist of the literals in the first 6These neurons are directly activated by the neurons representing the same literals in the layer INFERREDBF of the RM module. 106 E. Burattini, A. Pasconcino & G. Tamburrini element of already stored chunks. Then, the input set Iactivates in PATTERNOUT layer of CM the neural representatives of the elements of S=∪{Cj1,...,C jk}. Let us describe in more detail how this result is achieved. As in case 1, all neurons of INDEX are inactive at time t=2whenIis presented to CM and, at time t= 3, the impulse of control neuron CLOCK2 (see figure 5) activates the control neurons CTRINDOFF and CTRIND. At time t= 4, the impulse from CTRIND, combined with the impulses from the neural representatives of the elements of the sets Ij1,...,I jkin PATTERNON, activates the neurons jnin SUBINDEX with n=1,...,k.Thus,attimet= 5, all neural representatives of the elements of Sin PATTERNOUT are activated and, finally, at time t= 6, the neural representatives of the elements of Sin the FORWARD layer of RM module fire. The activation of the right neurons jnupon presentation of input pattern Iis determined by the weight values of connections from the PATTERNON layer to the SUBINDEX layer. These weights are initialized with the following values wPon iSubIndexj=0 j=1,...,M, i=1,2,...,N. The updating rule for these weights is analogous to (6): w Pon iSubIndexj=1/[I]ifPon iactive; wPon iSubIndexjotherwise .(9) One can easily show that rule (9) guarantees that, if Ijis a subpattern of the new input set I,thenattimet= 4 neuron jin SUBINDEX is active. SELECTING INDEXES: Let us now turn to describe the role of the layer INDEXBF and the selection criterion of indexes which is used by Recorder to store a new chunk. The algorithm Recorder modifies the weights of connections from neurons CTRIND and CTRINDOFF to the neurons of INDEXBF, in order to codify, for every chunk <I j,C j>, its frequency of recall, relative to the total number of network runs. In particular, the weight of the connection from the CTRIND neuron to neuron jin INDEXBF A chunking mechanism in a neural system... 107 is increased by one7if and only if the presentation of set Iactivates the neuron jin INDEXBF, that is to say, when the network recognizes the situation I=Ij, such as described in CASE 2. At the same time, the weight of the connection from the CTRINDOFF neuron to each neuron of INDEXBF is decreased with a real value (let us call it α). The parameter αcan be interpreted as a frequency threshold suitably chosen by the user. Thus, if the difference between the weighted impulses from CTRIND and CTRINDOFF to the neuron jis positive, then neuron jof INDEXBF is activated. This signals that the frequency of recall of chunk <I j,C j>is greater than the αthreshold (see Pasconcino (1994) for more details). Thus, when the CTRIND and CTRINDOFF neurons are activated (at time t= 3), at the next instant of time only those index neurons which have frequency of recall greater than αare active in INDEXBF. Every other neuron in INDEXBF is inactive either because no chunk is associated to it or because the associated chunk has recall frequency below the αthreshold. In order to acquire a new chunk in CM Recorder randomly selects an index j’ among the inactive neurons of INDEXBF. It may be the case that such “drawing” procedure selects an index j’to which a chunk <A j.Bj>,withAj=I, is associated, and therefore the new chunk <I j,C j>replaces the old one with a low frequency of use (below α). This simple criterion based on recall frequency provides a mechanism for managing the prefixed limited resources of the CM module. In other words, this drawing procedure provides a simple version of agarbage collector which, as is well known, does not eliminate the phenomenon of memory saturation, but simply reduces its incidence. In concluding this paper, we wish to emphasize that the algorithm Recorder acquires a new chunk when presented only once with input set Iand output set C. In fact, rules (6) and (7), which enable the system to acquire new chunks, eliminate the interference between the first elements of recorded chunks, as they change exclusively the weights of the input connections to the selected index neurons in the INDEX and SUBINDEX layers. Furthermore, let us point out that one can easily 7Except for the first updating of this weight which increases the initial value by one plus the total number of system runs plus the total number of indexes. 108 E. Burattini, A. Pasconcino & G. Tamburrini show that the computational complexity of the procedure Recorder is linear with respect to the size of the sets Iand C. A system endowed with this chunking mechanism can improve its performances on the basis of previous activity. Reduction of processing time is due both to the parallelism inherent in the general neural architecture of the system and to the specific architecture of the CM module; the latter guarantees that the computational cost of access to stored chunks is independent of the number of chunks that are in memory. It goes without saying that the actual exploitation of a reduction in processing times is contingent on the availability of a computational agent capable of modifying neural weights and executing the parallel computations allowed by this neural model. Appendix Let the rule knowledge base of the system be formed by the following set of rules (R1) a∧b→c (R2) c∧d→f (R3) f→h and let the system be started on the following set of initial data I= {a, b, d}and goal set G={h}. What follows is the list of the neural units that are active at each synchronous computational step of the network, whose submodular blocks are represented in figure 6 below. From this list and the connections between neural blocks sketched out in fig. 6, the interested reader may get a more precise idea of how neural activity flows within the network. The suffixes of the neuron labels listed below indicate which submodular block the active neuron belongs to (For example, the suffix in “d datain” indicates that neuron dbelongs to the block DATAIN.) We recall that section 3 describes what is the intended semantic interpretation of the neural elements in the main blocks. The first list, clock 0 to 13, is relative to the case in which the system is started, for the first time ever, on the given sets Iand G. A chunking mechanism in a neural system... 115 ACTIVE NEURONS( CLOCK : 11 ) Neuron Label( end ); Neuron Label( index6 indexbf ); Neuron Label( ctron goal ); Neuron Label( c patternout ); Neuron Label( ctron kb ); Neuron Label( f patternout ); Neuron Label( saturated ); Neuron Label( h patternout ); Neuron Label( h inferredbf ); Neuron Label( index6 subindex ); Neuron Label( f inferredbf ); Neuron Label( index6 index ); Neuron Label( c inferredbf ); Neuron Label( d patternon ); Neuron Label( h goalm ); Neuron Label( a patternon ); Neuron Label( h forwardbf ); Neuron Label( b patternon ); Neuron Label( f forwardbf ); Neuron Label( d patternoff ); Neuron Label( c forwardbf ); Neuron Label( a patternoff ); Neuron Label( d forwardbf ); Neuron Label( b patternoff ); Neuron Label( a forwardbf ); Neuron Label( true ); Neuron Label( b forwardbf ); References Aiello A., Burattini E., Tamburrini G. (1995a), Purely neural, rulebased diagnostic systems. Part I: Production rules, Int. J. of Intelligent Systems, 10, 735-749. Aiello A., Burattini E., Tamburrini G. (1995b), Purely neural, rulebased diagnostic systems. Part II: Uncertain reasoning, Int. J. of Intelligent Systems, 10, 751-769. Burattini E., Tamburrini G. (1992), A pseudo-neural system for hypothesis selection, Int. J. of Intelligent Systems, 7, 521-545. Carpenter G.A., Grossberg S. (1987), A Massively Parallel Architecture for a Self-Organizing Neural Pattern Recognition Machine, Comp. Vision, Graphics and Image Processing, 37, 54-115. Grossberg S. (1973), Contour Enhancement, Short-Term Memory and Constancies in reverberating neural networks, Studies Appl. Math., 52, 213-257. Grossberg S. (1976), Adaptive Pattern Classification and Universal Recoding. I. Parallel Development and Coding of Neural Feature Detectors, Biol. Cybern., 23, 121-134. Grossberg S. (1976), Adaptive Pattern Classification and Universal Recoding. II. Feedback, Expectation, Olfaction and Illusions, Biol. Cybern., 23, 187202. Hopfield J.J. (1982), Neural Networks and Physical Systems with Emergent Collective Computational Abilities, Proc. Natl. Acad. Sci. USA, 81, 2554-2558. 116 E. Burattini, A. Pasconcino & G. Tamburrini Hopfield J.J. (1984) Neurons with Graded response have collective computational properties like those of two-state neurons, Proc. Natl. Acad. Sci. USA, 81, 3088-3092. Kohonen T. (1977), Associative Memory: a system-theoretical approach, Springer Verlag. Kohonen T. (1982), Clustering, Taxonomy and Topological Maps of Patterns, in M. Lang (ed.), Proceedings of the Sixth International Conference on Pattern Recognition, Silver Spring, MD. IEEE Computer Society Press, 114-125. Judd J.S. (1990), Neural Network Design and the Complexity of Learning, The MIT Press. Laird J.E., Newell A. and Rosenbloom, P.S. (1986), Chunking in SOAR: The anatomy of a general learning mechanism, Machine Learning, 1, 11-46. Laird J.E., Newell A. and Rosenbloom, P.S. (1987), SOAR: An architecture for General Intelligence, Artificial Intelligence, 33, 1-64. Miller G.A. (1956), The magic number seven plus or minus two: Some limits on our capacity for processing information, Psychological Review, 63, 81-97. Newell A. (1990), Unified Theories of Cognition, Harvard University Press. Newell A. and Rosenbloom, P.S. (1981), Mechanisms of skill acquisition and the law of practice, in J. R. Anderson (ed.), Cognitive Skills and Their Acquisition, Lawrence Erlbaum Associates. Pasconcino A. (1994), Sistemi Esperti e Reti Neuroniche: realizzazione di un sistema composito parallelo, Tesi di Laurea, Universit`adegli Studi di Napoli “Federico II”. Rumelhart D.E., McClelland J.L. (eds.), Parallel Distributed Processing: Explorations in the Microstructure of Cognition, vol.I: Foundations, The MIT Press. Tambe M., Newell A., and Rosenbloom P.S. (1990), The problem of expensive chunks and its solution by restricting expressiveness, Machine Learning, 5(4), 299-348. Towell G.G., Shavlik J. W. (1994), Knowledge-based artificial neural networks, Artificial Intelligence, 70, 119-165.