Asynchronous Spiking neural P systems with structural plasticity

Asynchronous Spiking Neural P Systems with Structural Plasticity? Francis George C. Cabarle1, Henry N. Adorna1, Mario J. P´erez-Jim´enez2 1Algorithms & Complexity Lab, Department of Computer Science University of the Philippines Diliman Diliman, 1101, Quezon City, Philippines; 2Department of Computer Science and AI Universidad de Sevilla Avda. Reina Mercedes s/n, 41012, Sevilla, Spain [email protected], [email protected], [email protected] Summary. Spiking neural P (in short, SNP) systems are computing devices inspired by biological spiking neurons. In this work we consider SNP systems with structural plasticity (in short, SNPSP systems) working in the asynchronous (in short, asyn mode). SNPSP systems represent a class of SNP systems that have dynamic synapses, i.e. neurons can use plasticity rules to create or remove synapses. We prove that for asyn mode, bounded SNPSP systems (where any neuron produces at most one spike each step) are not universal, while unbounded SNPSP systems with weighted synapses (a weight associated with each synapse allows a neuron to produce more than one spike each step) are universal. The latter systems are similar to SNP systems with extended rules in asyn mode (known to be universal) while the former are similar to SNP systems with standard rules only in asyn mode (conjectured not to be universal). Our results thus provide support to the conjecture of the still open problem. Key words: Membrane computing, Spiking neural P systems, Structural plasticity, Asynchronous systems, Turing universality 1 Introduction Spiking neural P systems (in short, SNP systems) are parallel, distributed, and nondeterministic devices introduced into the are of membrane computing in [7]. Neurons are often drawn as ovals, and they process only one type of object, the spike signal represented by a. Synapses between neurons are the arcs between ovals: neurons are then placed on the vertices of a directed graph. Since their introduction, several lines of investigations have been produced, e.g. (non)deterministic ?An improved version of this article will appear at the 14th Unconventional Computation and Natural Computation (2015), Auckland, New Zealand. 92 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez computing power in [7][14]; language generation in [4]; function computing devices in [11]; solving computationally hard problems in [9]. Many neuroscience inspirations have also been included for computing use, producing several variants (to which the previous investigation lines are also applied), e.g. use of weighted synapses [16], neuron division and budding [9], the use of astrocytes [10]. Furthermore, many restrictions have been applied to SNP systems (and variants), e.g. asynchronous SNP systems as in [6], [3], and [15], and sequential SNP systems as in [6]. In this work the variant we consider are SNP systems with structural plasticity, in short, SNPSP systems. SNPSP systems were first introduced in [1], then extended and improved in [2]. The biological motivation for SNPSP systems is structural plasticity, one form of neural plasticity, and distinct from the more common functional (Hebbian) plasticity. SNPSP systems represent a class of SNP systems using plasticity rules: synapses can be created or deleted so the synapse graph is dynamic. The restriction we apply to SNPSP systems is asynchronous operation: imposing synchronization on biological functions is sometimes “too much”, i.e. not alway realistic. Hence, the asynchronous mode of operation is interesting to consider. Such restriction is also interesting mathematically, and we refer the readers again to [6], [3], and [15] for further details. In this work we prove that (i) asynchronous bounded (i.e. there exists a bound on the number of stored spikes in any neuron) SNPSP systems are not universal, (ii) asynchronous weighted (i.e. a positive integer weight is associated with each synapse) SNPSP systems, even under a normal form (provided below), are universal. The open problem in [3] whether asynchronous bounded SNP systems with standard rules are universal is conjectured to be false. Also, asynchronous SNP systems with extended rules are known to be universal [5]. Our results provide some support to the conjecture, since neurons in SNPSP systems produce at most one spike each step (similar to standard rules) while synapses with weights function similar to extended rules (more than one spike can be produced each step). This work is organized as follows: Section 2 provides preliminaries for our results; syntax and semantics of SNPSP systems are given in Section 3; our (non)universality results are given in Section 4. Lastly, we provide final remarks and further directions in Section 5. 2 Preliminaries It is assumed that the readers are familiar with the basics of membrane computing (a good introduction is [13] with recent results and information in the P systems webpage (http://ppage.psystems.eu/) and a recent handbook [14] ) and formal language theory (available in many monographs). We only briefly mention notions and notations which will be useful throughout the paper. We denote the set of positive integers as N={1,2, . . .}. Let Vbe an alphabet, V∗is the set of all finite strings over Vwith respect to concatenation and the Asynchronous Spiking Neural P Systems with Structural Plasticity 93 identity element λ(the empty string). The set of all non-empty strings over Vis denoted as V+so V+=V∗− {λ}. If V={a}, we simply write a∗and a+instead of {a}∗and {a}+. If ais a symbol in V, we write a0=λand we write the language generated by a regular expression Eover Vas L(E). In proving computational universality, we use the notion of register machines. A register machine is a construct M= (m, I, l0, lh, R), where mis the number of registers, Iis the set of instruction labels, l0is the start label, lhis the halt label, and Ris the set of instructions. Every label li∈Iuniquely labels only one instruction in R. Register machine instructions have the following forms: •li: (ADD(r), lj, lk), increase nby 1, then nondeterministically go to ljor lk; •li: (SUB(r), lj, lk), if n≥1,then subtract 1 from nand go to lj, otherwise perform no operation on rand go to lk; •lh:HALT, the halt instruction. Given a register machine M, we say Mcomputes or generates a number nas follows: Mstarts with all its registers empty. The register machine then applies its instructions starting with the instruction labeled l0. Without loss of generality, we assume that l0labels an ADD instruction, and that the content of the output register is never decremented, only added to during computation, i.e. no SUB instruction is applied to it. If Mreaches the halt instruction lh, then the number nstored during this time in the first (also the output) register is said to be computed by M. We denote the set of all numbers computed by Mas N(M). It was proven that register machines compute all sets of numbers computed by a Turing machine, therefore characterizing NRE [8]. A strongly monotonic register machine is one restricted variant: it has only one register which is also the output register. The register initially stores zero, and can only be incremented by 1 at each step. Once the machine halts, the value stored in the register is said to be computed. It is known that strongly monotonic register machines characterize SLIN, the family of length sets of regular languages. 3 Spiking neural P systems with structural plasticity In this section we define SNP systems with structural plasticity. Initial motivations and results for SNP systems are included in the seminal paper in [7]. A spiking neural P system with structural plasticity (SNPSP system) of degree m≥1 is a construct of the form Π= (O, σ1, . . . , σm, syn, out), where: •O={a}is the singleton alphabet (ais called spike); •σ1, . . . , σmare neurons of the form (ni, Ri),1≤i≤m;ni≥0 indicates the initial number of spikes in σi;Riis a finite rule set of σiwith two forms: 1. Spiking rule: E/ac→a, where Eis a regular expression over O,c≥1; 2. Plasticity rule: E/ac→αk(i, N), where Eis a regular expression over O, c≥1, α∈ {+,−,±,∓},k≥1, and N⊆ {1, . . . , m}−{i}; 94 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez •syn ⊆ {1, . . . , m}×{1, . . . , m}, with (i, i)/∈syn for 1 ≤i≤m(synapses between neurons); •out ∈ {1, . . . , m}indicate the output neuron. Given neuron σi(we also say neuron ior simply σi) we denote the set of neuron labels with σias their presynaptic (postsynaptic, resp.) neuron as pres(i), i.e. pres(i) = {j|(i, j)∈syn}(as pos(i) = {j|(j, i)∈syn}, resp.). Spiking rule semantics in SNPSP systems are similar with SNP systems in [7]. In this work we do not use forgetting rules (rules of the form as→λ) or rules with delays of the form E/ac→a;dfor some d≥1. Spiking rules are applied as follows: If neuron σicontains bspikes and ab∈L(E), with b≥c, then a rule E/ac→a∈Rican be applied. Applying such a rule means consuming cspikes from σi, thus only b−c spikes remain in σi. Neuron isends one spike to every neuron with label in pres(i) at the same step as rule application. A nonzero delay dmeans that if σispikes at step t, then neurons receive the spike at t+d. Spikes sent to σifrom tto t+d−1 are lost (i.e. σiis closed), and σican receive spikes (i.e. σiis open) and apply a rule again at t+dand t+d+ 1, respectively. If a rule E/ac→ahas L(E) = {ac}, we simply write this as ac→a. Plasticity rules are applied as follows. If at step twe have that σihas b≥c spikes and ab∈L(E), a rule E/ac→αk(i, N)∈Rican be applied. The set Nis a collection of neurons to which σican connect to or disconnect from using the applied plasticity rule. The rule application consumes cspikes and performs one of the following, depending on α: •If α:= + and N−pres(i) = ∅, or if α:= −and pres(i) = ∅, then there is nothing more to do, i.e. cspikes are consumed but no synapses are created or removed. Notice that with these semantics, a plasticity rule functions similar to a forgetting rule, i.e. the former can be used to consume spikes without producing any spike. •for α:= +,if |N−pres(i)| ≤ k, deterministically create a synapse to every σl, l∈Nj−pres(i). If however |N−pres(i)|> k, nondeterministically select k neurons in N−pres(i), and create one synapse to each selected neuron. •for α:= −,if |pres(i)| ≤ k, deterministically delete all synapses in pres(i). If however |pres(i)|> k, nondeterministically select kneurons in pres(i), and delete each synapse to the selected neurons. If α∈ {±,∓} : create (respectively, delete) synapses at step tand then delete (respectively, create) synapses at step t+ 1. Only the priority of application of synapse creation or deletion is changed, but the application is similar to α∈ {+,−}. Neuron iis always open from tuntil t+ 1, but σican only apply another rule at time t+ 2. An important note is that for σiapplying a rule with α∈ {+,±,∓}, creating a synapse always involves an embedded sending of one spike when σiconnects to a neuron. This single spike is sent at the time the synapse creation is applied, i.e. whenever σiattaches to σjusing a synapse during synapse creation, we have σi immediately transferring one spike to σj. Asynchronous Spiking Neural P Systems with Structural Plasticity 95 Let tbe a step during a computation: we say a σiis activated at step tif there is at least one r∈Rithat can be applied; σiis simple if |Ri|= 1, with a nice biological and computing interpretation, i.e. some neurons do not need to be complex, but merely act as spike repositories or relays. We have the following nondeterminism levels: rule-level, if at least one neuron has at least two rules with regular expressions E1and E2such that E16=E2and L(E1)∩L(E2)6=∅;synapselevel, if initially Πhas at least one σiwith a plasticity rule where k < |N−pres(i)|; neuron-level, if at least one activated neuron with rule rcan choose to apply its rule ror not (i.e. asynchronous). By default SNP and SNPSP systems are locally sequential (at most one rule is applied per neuron) but globally parallel (all activated neurons must apply a rule). The application of rules in neurons are usually synchronized, i.e. a global clock is assumed. However, in the asynchronous (asyn, in short) mode we release this synchronization so that neuron-level nondeterminism is implied. A configuration of an SNPSP system is based on (a) distribution of spikes in neurons, and (b) neuron connections based on syn. For some step t, we can represent: (a) as hs1, . . . , smi where si,1≤i≤m, is the number of spikes contained in σi; for (b) we can derive pres(i) and pos(i) from syn, for a given σi. The initial configuration therefore is represented as hn1, . . . , nmi, with the possibility of a disconnected graph, or syn =∅. A computation is defined as a sequence of configuration transitions, from an initial configuration, and following rule application semantics. A computation halts if the system reaches a halting configuration, i.e. no rules can be applied and all neurons are open. A result of a computation can be defined in several ways in SNP systems literature. For SNP systems in asyn mode however, and as in [3] [5] [15], the output is obtained by counting the total spikes sent out by σout to the environment (in short, Env) upon reaching a halting configuration. We refer to Πas generator, if Πcomputes in this asynchronous manner. Πcan also work as an acceptor but this is not given in this work. For our universality results, the following simplifying features are used in our systems as the normal form: (i) plasticity rules can only be found in purely plastic neurons (i.e. neurons with plasticity rules only), (ii) neurons with standard rules are simple, and (iii) we do not use forgetting rules or rules with delays. We denote the family of sets computed by asynchronous SNPSP systems (under the mentioned normal form) as generators as NtotSNPSPasyn: subscript tot indicates the total number of spikes sent to Env as the result; Other parameters are as follows: +synk(−synj, respectively) where at most k(j, resp.) synapses are created (deleted, resp.) each step; ndβ, β ∈ {syn, rule, neur}indicate additional levels of nondeterminism source; rulemindicates at most mrules (either standard or plasticity) per neuron; Since our results for kand jfor +synkand −synjare equal, we write them instead in the compressed form ±synk, where ±in this sense is not the same as when α:= ±. A bound pon the number of spikes stored in any neuron of the system is denoted as boundp. We omit ndneur from writing since it is implied in asyn mode. 96 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez             j a→a k a→a la a→a ia a→ ±1(i, {j, k}) Fig. 1. An SNPSP system Πej . To illustrate the notions and semantics in SNPSP systems, we take as an example the SNPSP system Πej of degree 4 in Fig. 1, and describe its computations. The initial configuration is as follows: spike distribution is h1,0,0,1ifor the neuron order σi,σj,σk,σl, respectively; syn ={(j, k),(k, l)}; output neuron is σl, indicated by the outgoing synapse to Env. Given the initial configuration, σiand σlcan become activated. Due to asyn mode however, they can decide to apply their rules at a later step. If σlapplies its rule before it receives a spike from σi, then it will spike to Env twice so that Ntot(Πej) = {2}. Since k= 1 <|{j, k}| and pres(i) = ∅,σinondeterministically selects whether to create synapse (i, j) or (i, k); if (i, j) ((i, k), resp.) is created; a spike is sent from σito σj(σk, resp.) due to the embedded sending of a spike during synapse creation. Let this be step t. If (i, j) is created then syn0:= syn ∪ {(i, j)}, otherwise syn00 := syn ∪ {(i, k)}. At t+ 1, σideletes the created synapse at t (since α:= ±), and we have syn again. Note that if σldoes not apply its rule and collects two spikes (one spike from σi), the computation is aborted or blocked, i.e. no output is produced since a2/∈L(a). 4 Main results In this section we use at most two nondeterminism sources: ndneur (in asyn mode), and ndsyn. Recall that in asyn mode, if σiis activated at step tso that an r∈Ri can be applied, σican choose to apply ror not. If σidid not choose to apply r, σican continue to receive spikes so that for some t0> t, it is possible that: rcan never be applied again, or some r0∈Ri, r06=r, is applied. For the next result, each neuron can store only a bounded number of spikes (see for example [3][6][7] and references therein). In [6], it is known that bounded SNP systems with extended rules in asyn mode characterize SLIN, but it is open whether such result holds for systems with standard rules only. In [3], a negative answer was conjectured for the following open problem: are asynchronous SNP systems with standard rules universal? First, we prove that bounded SNPSP systems in asyn mode characterize SLIN, hence they are not universal. Lemma 1 NtotSNPSPasyn(boundp, ndsyn)⊆SLIN, p ≥1. Proof. Taking any asynchronous SNPSP system Πwith a given bound pon the number of spikes stored in any neuron, we observe that the number of possible configurations is finite: Πhas a constant number of neurons, and that the number of spikes stored in each neuron are bounded. We then construct a right-linear Asynchronous Spiking Neural P Systems with Structural Plasticity 97 grammar G, such that Πgenerates the length set of the regular language L(G). Let us denote by Cthe set of all possible configurations of Π, with C0being the initial configuration. The right-linear grammar G= (C,{a}, C0, P ), where the production rules in Pare as follows: (1) C→C0,for C, C0∈ C if Πhas a transition C⇒C0in which the output neuron does not spike; (2) C→aC0,for C, C0∈ C if Πhas a transition C⇒C0in which the output neuron spikes; (3) C→λ, for any C∈ C in which Πhalts. Due to the construction of G,Πgenerates the length set of L(G), hence the set is semilinear. ut Lemma 2 SLIN ⊆NtotSNPSP asyn(boundp, ndsyn), p ≥1. The proof is based on the following observation: A set Qis semilinear if and only if Qis generated by a strongly monotonic register machine M. It suffices to construct an SNPSP system Πwith restrictions given in the theorem statement, such that Πsimulates M. Recall that Mhas precisely register 1 only (it is also the output register) and addition instructions of the form li: (ADD(1), lj, lk). The ADD module for Πis given in Fig. 2. Next, we describe the computations in Π.               HHH Hj ?- lia→a1 aq/a →a for 1 ≤q≤p l1 i a→ ±1(l1 i,{lj, lk}) ljlk Fig. 2. Module ADD simulating li: (ADD(1) : lj, lk) in the proof of Lemma 2. Once ADD instruction liof Mis applied, σliis activated and it sends one spike each to σ1and σl1 i. At this point we have two possible cases due to asyn mode, i.e. either σ1spikes to Env before σl1 ispikes, or after. If σ1spikes before σl1 i, then the number of spikes in Env is immediately incremented by 1. After some time, the computation will proceed if σl1 iapplies its only (plasticity) rule. Once σl1 iapplies its rule, either σljor σlkbecomes nondeterministically activated. However, if σ1spikes after σl1 ispikes, then the number of spikes in Env is not immediately incremented by 1 since σ1does not consume a spike and fire to Env. The next instruction, either ljor lk, is then simulated by Π. Furthermore, due to asyn mode, the following “worst case” computation is possible: σlhbecomes activated (corresponding to lhin Mbeing applied, thus halting M) before σ1 spikes. In this computation, Mhas halted and has applied an mnumber of ADD instructions since the application of li. Without loss of generality we can have the 98 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez arbitrary bound p>m, for some positive integer p. We then have the output neuron σ1storing mspikes. Since the rules in σ1are of the form aq/a →a, 1≤q≤p,σ1consumes one spike at each step it decides to apply a rule, starting with rule am/a →a, until rule a→a. Thus, Πwill only halt once σ1has emptied all spikes it stores, sending mspikes to Env in the process. The FIN module is not necessary, and we add σlhwithout any rule (or maintain pres(lh) = ∅). Once Mhalts by reaching instruction lh, a spike in Πis sent to neuron lh.Πis clearly bounded: every neuron in Πcan only store at most pspikes, at any step. We then have Πcorrectly simulating the strongly monotonic register machine M. This completes the proof. ut From Lemma 1 and 2, we can have the next result. Theorem 1 SLIN =NtotSNPSP asyn(boundp, ndsyn), p ≥1. Next, in order to achieve universality, we add an additional ingredient to asynchronous SNPSP systems: weighted synapses. The ingredient of weighted synapses has already been introduced in SNP systems literature, and we refer the reader to [16] (and references therein) for computing and biological motivations. In particular, if σiapplies a rule E/ac→ap, and the weighted synapse (i, j, r) exists (i.e. the weight of synapse (i, j) is r) then σjreceives p×rspikes. It seems natural to consider weighted synapses for asynchronous SNPSP systems: since asynchronous SNPSP systems are not universal, we look for other ways to improve their power. SNPSP systems with weighted synapses (in short, WSNPSP systems) are defined in a similar way as SNPSP systems, except for the plasticity rules and the synapse set. Plasticity rules in σiare now of the form E/ac→αk(i, N, r), where r≥1, and E, c, α, k, N are as previously defined. Every synapse created by σiusing a plasticity rule with weight rreceives the weight r. Instead of one spike sent from σito a σjduring synapse creation, j∈N,rspikes are sent to σj. The synapse set is now of the form syn ⊆ {1,2, . . . , m}×{1,2, . . . , m} × N. We note that SNPSP systems are special cases of SNPSP systems with weighted synapses where r= 1, and when r= 1 we omit it from writing. In weighted SNP systems with standard rules, the weights can allow neurons to produce more than one spike each step, similar to having extended rules. In this way, our next result parallels the result that asynchronous SNP systems with extended rules are universal in [5]. However, our next result uses ndsyn with asyn mode, while in [5] their systems use ndrule with asyn mode. We also add the additional parameter lin our universality result, where the synapse weight in the system is at most l. Our universality result also makes use of the normal form given in Section 3. Theorem 2 NtotWSNPSPasyn(rulem,±synk, weightl, ndsyn) = NRE, m ≥9, k ≥ 1, l ≥3. Asynchronous Spiking Neural P Systems with Structural Plasticity 99 Proof. We construct an asynchronous SNPSP system with weighted synapses Π, with restrictions given in the theorem statement, to simulate a register machine M. The general description of the simulation is as follows: each register rof Mcorresponds to σrin Π. If register rstores the value n,σrstores 2nspikes. Simulating instruction li: (OP(r) : lj, lk) of Min Πcorresponds to σlibecoming activated. After σliis activated, the operation OP is performed on σr, and σljor σlkbecomes activated. We make use of modules in Πto perform addition, subtraction, and halting of the computation. Module ADD: The module is shown in Fig. 3. At some step t,σlisends a spike to σl1 i. At some t0> t,σl1 isends a spike: the spike sent to σris multiplied by two, while 1 spike is received by σl2 i. For now we omit further details for σr, since it is never activated with an even number of spikes. At some t00 > t0,σl2 inondeterministically creates (then deletes) either (l2 i, lj) or (l2 i, lk). The chosen synapse then allows either σljor σlkto become activated. The ADD module thus increments the contents of σrby 2, simulating the increment by 1 of register r. Next, only one among σljor σlkbecomes nondeterministically activated. The addition operation is correctly simulated.                  - - ? l1 i a→a r 2 li a→a l2 i a→ ±1(l2 i,{lj, lk},1) ljlk Fig. 3. Module ADD simulating li: (ADD(r) : lj, lk) in the proof of Theorem 2. Module SUB: The module is shown in Fig. 4. Let |Sr|be the number of instructions with form li: (SUB(r), lj, lk), and 1 ≤s≤ |Sr|.|Sr|is the number of SUB instructions operating on register r, and we explain in a moment why we use a size of a set for this number. Clearly, when no SUB operation is performed on r, then |Sr|= 0, as in the case of register 1. At some step t,σlispikes, sending 1 spike to σr, and 4|Sr| − sspikes to σl1 i(the weight of synapse (li, l1 i)). σl1 ihas rules of the form ap→ −1(l1 i,{r},1), for 3|Sr| ≤ p < 8|Sr|. When one of these rules is applied, it performs similar to a forgetting rule: pspikes are consumed and deletes a nonexisting synapse (l1 i, r). Since σl1 ireceived 4|Sr| − s spikes from σli, and 3|Sr| ≤ 4|Sr| − s < 8|Sr|, then one of these rules can be applied. If σl1 iapplies one of these rules at t0> t, no spike remains. Otherwise, the 4|Sr| − sspikes can combine with the spikes from σrat a later step. In the case where register rstores n= 0 (respectively, n≥1), then instruction lk(respectively, lj) is applied next. This case corresponds to σrapplying the