Self-constructing Recognizer P Systems

Self-constructing Recognizer P Systems Daniel D´ıaz-Pernil1, Francisco Pe˜na-Cantillana2, Miguel A. Guti´errez-Naranjo2 1Research Group on Computational Topology and Applied Mathematics Department of Applied Mathematics - University of Sevilla, 41012, Spain [email protected] 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, 41012, Spain [email protected], [email protected] Summary. Usually, the changes produced in the membrane structure of a P system are considered side effects. The output of the computation is encoded as a multiset placed in a specific region and the membrane structure in the halting configuration is not considered important. In this paper we explore P systems where the target of the computation is the construction of a new membrane structure according its set of rules. The new membrane structure can be considered as the initial one of a new self-constructed P system. We focus on the self-construction of recognizer P systems and illustrates the definition with a study of the self-construction P systems working as decision trees for solving Machine Learning decision problems. 1 Introduction In many Membrane Computing models, changing the membrane structure of a P system along the computation is a common process. The changes are produced via division of membranes (based on cellular mitosis), via creation of new membranes from objects (based on cellular autopoiesis, see [7]) or dissolution of membranes. The rules producing such changes have been deeply studied and the capability of the P systems for solving hard problems are linked to the use of such rules (see, e.g., [4, 5, 16]). Nonetheless, the changes of the membrane structure produced along a computation are not considered a target itself. The changes are usually produced in order to compute an output, which is usually encoded as a multiset (or as a single distinguished object) in the corresponding output region. The membrane structure obtained in the halting configuration is not important. It is merely a collateral effect. In this paper, we focus on P systems where the target of the computation is exactly the opposite to the usual one. We study P systems whose aim is to 138 D´ıaz-Pernil et al. develop a membrane structure. Such P systems will take a multiset as input and they will change their membrane structure according to such input, the set of rules and the non-deterministic choices, if any. The membrane structure obtained in the halting configuration will be considered as the output of the computation. This new membrane structure, together the remaining ingredients of the P system (alphabet, set of labels, set of rules, . . . ) can be considered as a new P system, able to receive a new input and perform a new computation. In this way, we will consider that this second P system (which is similar to the original one, but with a new initial membrane structure) has been self-constructed, since a (potentially) complex membrane structure has been obtained from a simple one (maybe from an initial membrane structure with the skin as unique membrane) according to the application of their own rules. Of course, different final membrane structures may be obtained from different inputs, but also with the same input due to the non-determinism. The self-construction of a complex membrane structure can be a target by itself, as shown in [3, 6], but in this paper, the self-constructed P system is thought for a second use. From this general target, we focus here on the self-construction of recognizer P systems, i.e., the P system with this new membrane structure can be now used as recognizer P systems for solving decision problems in the usual way: An instance of the decision problem is provided to the P system as an input encoded as an appropriate multiset and an object yes or no (but no both) is sent to the environment in the last step of the computation. In this way, two different uses for the P system are considered: •Firstly, given a P system, a multiset is placed in the corresponding input membrane and the computation starts. According to the input and the non deterministic choice of applicable rules, the initial membrane structure is modified along the computation. As usual, a halting configuration is reached if no more rules can be applied. The self-construction of the recognizer P system is finished. •Secondly, we consider a new computation of the P system, but in this stage, the membrane structure obtained in the halting configuration of the previous stage is considered as the initial one. This new computation also needs a new input, which is placed in the corresponding input membrane. In this stage, the output will be a specific object (yes or no, but no both) which is placed in the output region in the halting configuration. The paper is organized as follows: Next, we recall the definition of recognizer P system used in this paper. In Section 3, our case study is presented, the selfconstruction of a P system from a training set which works as a decision tree and the classification (decision problem) of new instances as in Machine Learning theory. We provide the formal framework, the general construction of the P systems, an example and some theoretical considerations. Finally, Section 4 finishes the paper with some conclusions. Self-constructing Recognizer P Systems 139 2 Recognizer P Systems Recognizer P systems were introduced in [11] and they are the natural framework to study and solve decision problems, i.e., problems were a Boolean total function θXmust be defined on a set of instances IX. Recognizer P systems are associated in a natural way with P systems with input and with external output, i.e., each instance of the problem is codified by a multiset placed in an input membrane. The output of the computation (yes or no) is sent to the environment. Due to the nondeterminism, the definition of recognizer P system claims that the output of all the computations must be the same. Since one can find slightly different approaches in the literature (see [9, 15]), we recall the definition used in this paper: Definition 1. AP system with input is a tuple (Π, Σ, iΠ), where: (a) Πis a P system, with working alphabet Γ, with pmembranes labelled by 1, . . . , p, and initial multisets w1, . . . , wpassociated with them; (b) Σis an (input) alphabet strictly contained in Γ; the initial multisets are over Γ−Σ; and (c) iΠis the label of a distinguished (input) membrane. Let mbe a multiset over Σ. The initial configuration of (Π, Σ, iΠ)with input m is (µ, w1, . . . , wiΠ∪m, . . . wp). Definition 2. Arecognizer P system is a P system with input, (Π, Σ, iΠ), and with external output such that: 1. The working alphabet contains two distinguished elements yes,no. 2. All its computations halt. 3. If Cis a computation of Π, then either some object yes or some object no (but not both) must have been released into the environment, and only in the last step of the computation. We say that Cis an accepting computation (respectively, rejecting computation) if the object yes (respectively, no) appears in the external environment associated to the corresponding halting configuration of C. 3 A Case Study: Decision Trees Decision trees is one of the most widely used structures in Computer Science. They are used to classify an input by sorting it down the tree from the root to some leaf node, which provides the classification of the instance. Instances are usually written as sets of pairs ⟨Attribute, V alue⟩and each node in the tree determines a test of some attribute. Each branch descending from that node corresponds to one of the possible value for this attribute. An instance is classified by starting at the root node of the tree, testing the attribute specified in this node and moving down the branch corresponding to the value of the instance in this attribute. The leaves are labelled with values of the classification and they are the output associated to the instances that reach them. In this way, if the possible classifications are 140 D´ıaz-Pernil et al. Table 1. A classic example of training set adapted from [14]. Day Outlook Temperature Humidity Wind PlayTennis D1 Sunny Hot High Weak No D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes D5 Rain Cool Normal Weak Yes D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes D8 Sunny Mild High Weak No D9 Sunny Cool Normal Weak Yes D10 Rain Mild Normal Weak Yes D11 Sunny Mild Normal Strong Yes D12 Overcast Mild High Strong Yes D13 Overcast Hot Normal Weak Yes D14 Rain Mild High Strong No Y ES and NO, a decision tree can be thought as a Boolean mapping on the set of instances which decides the classification of the instance according to the values of the attributes. Let us illustrate the process with a classic example adapted from [14]. It consists on a database with fourteen days. Each day is represented by the values of the attributes Outlook,Temperature,Humidity and Wind. Each day has also associated its classification with respect to the attribute PlayTennis (see Table 1). From a learning point of view, the database can be seen as a training set. The target is to generate a decision tree from this database which can be used to classify new instances. Figure 1 shows a decision tree consistent with the training set shown in Table 1, i.e., a tree which classifies correctly all the examples in the training set. According to this tree, a day with Outlook =Sunny,T emperature =Cool,Humidity = Normal and W ind =Strong (which does not belong to the training set) will be classified as Y ES. 3.1 The P System Model The definition of self-construction in P system is independent of the P system model, i.e., it can be considered in the framework of cell-like, tissue-like or whatever other graph structure and it can be adapted to different semantics. The unique restriction that the P system must satisfy is the ability of modifying the initial membrane structure according to the input. In this way, the concept can be considered in many scenarios. In this paper, we will illustrate the definition with a P system model were the data are encoded as strings [1, 13] and the changes in the membrane structure are performed via membrane creation [5, 10]. Self-constructing Recognizer P Systems 141 Outlook Overcast Humidity NormalHigh No Yes Wind Strong Weak No Yes Yes Rain Sunny Fig. 1. An example of tree obtained from the training set shown in 1. The image is available from http://www.cs.cmu.edu/afs/cs.cmu.edu/user/mitchell/ftp/mlbook.html. Formally, a self-constructing P system with strings and membrane creation is a construct of the form Π= (O, H, L, R) where: 1. Ois the alphabet of objects; 2. His a finite set of labels; 3. Lis a finite languages over O; 4. Ris a finite set of rules, of the following forms: a) [wp+wq→∑kwk]hwhere h∈H,wp,wqand wkare strings over O. These are 2-cooperative evolution rules: The simultaneous occurrence of the strings wpand wqin the membrane hproduces a finite set of strings in the same membrane. As usual, wpand wqare consumed. b) wp[ ]h→[wq]hwhere h∈H;wpand wqare strings over O. These are sendin communication rules. A string is introduced in the membrane possibly modified. c) [wp]h→[ ]hwqwhere h∈H;wpand wqare strings over O. These are sendout communication rules. A string is sent out of the membrane possibly modified. d) [a→[M]h2]h1where h1, h2∈H,a∈Oand Mis a finite language over O. These are creation rules. An object aplaced in a membrane with label h1 creates a new membrane with label h2. This new membrane has associated an initial finite language M. We will consider that the self-constructing P system with strings and membrane creation always has a unique membrane (the skin) in the initial membrane structure, such membrane is the input membrane and the output region is the environment. The multiset Lis placed in the skin at the initial configuration. Rules are applied according to the following principles: •Rules are used as usual in the framework of Membrane Computing, that is, in a maximal parallel way. In one step, each string in a membrane can only be used 142 D´ıaz-Pernil et al. for one rule (non deterministically chosen when there are several possibilities), but any string which can evolve by a rule of any form must do it (with the restrictions below indicated). •All the strings which are not involved in any of the operations to be applied remain unchanged. •The rules associated with the label hare used for all membranes with this label, irrespective of whether or not the membrane is an initial one or it was obtained by creation. •Several rules can be applied to different objects in the same membrane simultaneously. 3.2 Self-constructing P Systems for Decision Trees Learning Next, we will provide a family of self-constructing P system with strings and membrane creation for Decision Trees Learning. Such self-constructed P system will receive instances of the problem and will output yes or no, i.e., they are tools for solving decision problems. In a first stage, the P system takes a finite language, codifying a training set, as input. Each example in the training set will be encoded as a string. The set of these strings will be the initial language Land it will be placed in the unique initial membrane of the P system, as defined above. After a finite number of steps, the computation halts and the membrane structure has been (probably) modified. The P system with this halting membrane structure is the recognizer P system which has been self-constructed according with the training set provided as input. The self-constructed recognizer P system with the membrane structure obtained in the halting configuration is now prepared to receive an instance of the decision problem and will provide an answer yes or not. Let us start by considering a training set D={(v1, c1), . . . , (vn, cn)}where, for each i∈ {1, . . . , n},viis a tuple of pairs ⟨Attribute, V alue⟩and ci={Y ES, NO} is the classification for a concept1. We will consider a set of attributes ATR = {A1, . . . , Ak}and, for each i∈ {1, . . . , k},V ALi={v1 i, . . . , vji i}is the set of values of the attribute Ai. We will consider that the sets V ALiare disjoint pairwise. We will also consider V AL =V AL1∪... ∪V ALkand Γ=AT R ∪V AL ∪ {Y ES, NO}. The set Γwill be called a training set alphabet. Notice that many different training sets can have the same alphabet Γ. By using this notation, we will represent each example (vi, ci) as a string over the set Γand a training set can be considered as a finite language over this set. The example (vi, ci) will be represented by the string of 2k+ 1 symbols A1vi 1A2vi 2. . . Akvi kci, where vi jis the value of the attribute Ajin the i−th example of the training set and ci∈ {Y ES, NO}is the value of the classification. For example, the string 1A formal description of the principles of Machine Learning is out of the scope of this paper. A detailed introduction can be found in, e.g., [8]. Self-constructing Recognizer P Systems 143 Outlook Sunny Temperature Hot Humidity High Wind Weak NO is the representation of the first example of Table 1. In the first stage, the finite language codifying the training set is placed in the skin and the self-construction starts. When it finishes, the halting membrane structure is prepared for accepting new inputs and deciding on it. The new input will be similar to the encoding of an example, but the last object of the string will be ? instead of Y ES or NO. For example, in order to know the classification of a day not with Outlook =Sunny,T emperature =Cool,Humidity =Normal and Wind =Strong, the string Outlook Sunny T emperature Cool Humidity Normal Wind Strong ? will be placed in the input membrane (the skin) and a new computation will start. Next we provide the formal definition of a self-constructing P system with strings and membrane creation associated to a training set Γ. The P system is a 4-uple Π= (O, H, L, R) where: 1. O=Γ∪ {Y ESaux, Y ESact,?, NOaux, NOact, new}is the alphabet of objects; 2. H={skin} ∪ V AL. The possible labels are the values of the attributes plus the initial label skin; 3. L={Y ESaux, NOaux}Two strings, each of them with only one object, are placed in the skin in the initial configuration; 4. We split the set Rof rules into two groups, the rules used in the selfconstruction stage and the rules used in the decision stage: Rules for the self-construction stage. R1.[xY ES +Y ESaux →xY ES +Y ESact ]h [xNO +NOaux →xNO +NOact ]h}for h∈H. where xis a string over Γcomposed by pairs (Attribute, V alue). If the string xY ES and Y ESaux occur simultaneously in the same membrane, then xY ES remains unchanged, but Y ESaux is consumed and Y ESact is produced. Analogously for the NO case. R2.[Y ESact +NOact →new]hfor h∈H. If the strings Y ESact and NOact are placed simultaneously in the same membrane, both are consumed and the string new is produced. R3.[new +xAiy→xAiy+v1+. . . +vs]hfor h∈H. If the strings new and xAiyoccur in the same membrane (where xAiyis a string including the object Ai, which denotes an attribute), then the string new is consumed, the string xAiyremains unchanged and all the strings vi j from V ALiare produced. Let us notice that this set of rules produces a high 144 D´ıaz-Pernil et al. degree of non-determinism. On the one hand, many different strings xAiycan simultaneously occur in the same membrane and, on the other hand, several Aimay be chosen from the same string. Nonetheless, since there can exists at most only one string new in each membrane at each time unit, only one of these rules will be applied. R4.[v→[Y ESaux NOaux]v]hfor h∈H Each string v∈V AL creates a new membrane. Such membrane will have v as a label and it will contain the strings Y ESaux and NOaux. R5. xAivy [ ]v→[xy ]vfor Ai∈AT R and v∈V ALi Each string xAivy (where Aiis an object which denotes an attribute and v is the next symbol in the string, denoting one of the values of Ai) out of a membrane with label vwill be sent into the membrane. The application of the rule will transform the string into xy, which is xAivy after deleting the substring Aiv. These rules are applied in parallel and several strings can cross out the same membrane simultaneously. Rules for the decision stage. R6. xAvy? [ ]v→[xy? ]vfor v∈V AL. If a string ended with ? and containing an object v∈V AL is out of a membrane with label v, then the string is sent into the membrane. The application of the rule also produces a change in the string since the object v and the previous object in the string (the object Adenoting the corresponding attribute) are deleted. R7.[x? + Y ESact →Y ESout +Y ESact ]h [x? + NOact →NOout +NOact ]h}for h∈H. where xis a string over Γcomposed by pairs (Attribute, V alue). If the string x? and Y ESact occur simultaneously in the same membrane, then Y ESact remains unchanged, but x? is consumed and Y ESout is produced. Analogously for the NO case. R8.[Y ESout ]h→[ ]hY ESout [NOout ]h→[ ]hNOout }for h∈H. when an object Y ESout (resp. NOout) is produced, the decision is made. This set of rules sends such object from the membrane where is produced to the environment. Such objects are the answers to the decision problem Self-constructing Recognizer P Systems 145 Outlook sunny T emperature hot Humidity high W ind weak NO Outlook sunny T emperature hot Humidity high W ind strong NO Outlook overcast T emperature hot Humidity high W ind weak Y ES Outlook rain T emperature mild Humidity high W ind weak Y ES Outlook rain T emperature cool Humidity normal W ind weak Y ES Outlook rain T emperature cool Humidity normal W ind strong NO Outlook overcast T emperature cool Humidity normal W ind strong Y ES Outlook sunny T emperature mild Humidity high W ind weak NO Outlook sunny T emperature cool Humidity normal W ind weak Y ES Outlook rain T emperature mild Humidity normal W ind weak Y ES Outlook sunny T emperature mild Humidity normal W ind strong Y ES Outlook overcast T emperature mild Humidity high W ind strong Y ES Outlook overcast T emperature hot Humidity normal W ind weak Y ES Outlook rain T emperature mild Humidity high W ind strong NO Fig. 2. Finite language encoding the training set from Table 1. 3.3 An example As an example of self-construction P systems for Decision Tree Learning, let us consider the training set from Table 1. According to the encoding previously described, such training set can be written as shown in Fig. 2. Let us consider an initial configuration C0which has only one membrane with label skin. Such membrane contains the language codifying the training set from Fig. 2, together with Y ESaux and NOaux. From this initial configuration only two rules from R1 are applied. The application of such rules consumes Y ESaux and NOaux and produces Y ESact and NOact. In the second step of the computation, only the rule from R2 is applied. The objects Y ESact and NOact are consumed and new appears in the skin. In this way, the configuration C2has only one membrane, the skin, where the codification of the training set and the object new are placed. From this configuration C2, one and only one of the rules from R3 is nondeterministically chosen and applied. In the choice, one of the strings encoding an example from the training set is taken and in this string, one of the objects encoding an attribute is also selected. Let us suppose that the string Outlook sunny T emperature hot Humidity high Wind weak NO is chosen and the object Outlook is selected. The application of the rule consumes the object new, keeps unchanged the string encoding the example and three new objects rain,sunny and overcast appear. Therefore, the configuration C3has only one membrane, the skin, where the codification of the training set and the objects rain,sunny and overcast are placed. In the next step, the changes in the membrane structure start. The objects rain,sunny and overcast create new membranes. Each membrane has the objects Y ESaux and NOaux inside and the corresponding value rain,sunny or overcast as label, i.e., 152 D´ıaz-Pernil et al. Lemma 1. Let us consider an elementary membrane at the step nsuch that there are no strings in its father membrane (it can also be the skin in the initial configuration) and its content is Y ESaux,NOaux, and a non-empty set of examples such that all of them end with Y ES or all of them end with NO. Then, the computation in this membrane finishes at step n+ 1. Proof. Let us consider that all the examples end with Y ES (the case NO is analogous). In the described conditions, only one rule can be applied (from R1) and in the step n+ 1, the membrane contains the same set of examples and Y ESact and NOaux. It is easy to check that no more rules can be applied and the computation finishes at this step. From this lemma, we obtain that if all the examples in the initial set provided to the skin in the initial configuration end with Y ES or NO, then the computation of the self-constructing stage end after one computation step. Lemma 2. All the examples inside a membrane have the same length. Proof. It is trivial to check that it is true in the initial configuration, since if the training set has kattributes, then, all the initial examples have length 2k+ 1. For the next steps, we only need to consider that the rules which sends examples from one membrane into other belongs tho the set R5, the application of these rules always decreases the length of the example in two units and all the examples arrive to the membrane simultaneously. Lemma 3. Let us consider an initial training set without noise. If in a membrane there is at least one example of length 1, then all of them are Y ES or all of them are NO. Proof. By, Lemma 2, we can consider that all the examples in the membrane have length 1. If the training set has kattributes, then all the examples in the initial configuration have length 2k+ 1 and, by construction, these examples of length 1 came from these original one after deleting two objects ktimes. In this process, if two examples are sent to the same membrane, then both share the same value for one attribute. If both examples are in the same membrane after kdeletions, then they share the values of the kattributes and, since their no noise, the classification must be the same. Lemma 4. Let us consider an elementary membrane hat the step nsuch that there are no strings in its father membrane (it can also be the skin in the initial configuration) and its content is Y ESaux,NOaux, and a non-empty set of examples of length lsuch that at least one of them ends with Y ES and at least one of them ends with NO. Then, at step n+ 5, the membrane hdoes not contains strings. It only contains elementary membranes such that contain Y ESaux,NOaux and examples of length l−2. Self-constructing Recognizer P Systems 153 Proof. In the described conditions, at the step n+ 1 the membrane contains the set of examples plus Y ESact and NOact (by R1); at the step n+ 2, it contains the set of examples and new (by R2); at n+ 3, it contains the set of examples plus v1,. . . ,vs, where v1,. . . ,vsare the values of one of the attributes (by R3). By application of rules from R4, at the step n+ 4, the membrane contains the set of examples plus selementary membranes, one for each value. Each of these membranes contains the strings Y ESaux and NOaux. Finally, rules from R5 are applied and all the examples from the membrane hare sent into the elementary membranes by deleting two objects. Finally, the Statement 1, can be proved from these lemmas. Proof. Proof of the Statement 1. If the training set has kattributes, then the examples placed in the skin in the initial configuration have length 2k+ 1. Two cases are possible: •If all of them have the same classification, i.e., all of them end with Y ES or all of them end with NO, then, by Lemma 1, the computation finishes in the configuration C1. •If all of them do not have the same classification, then the conditions of Lemma 2 hold and the configuration C5has elementary membranes with Y ESaux, NOaux and examples of length 2(k−1) −1. Each of these membranes is in the same conditions that the skin in the initial configuration, but the length of the examples has decreased in two units. This process goes on and each elementary membrane stops after 1 + 5psteps with p∈ {0, . . . , k}. Lemma 3 is considered to ensure that all the examples in the elementary membrane end in Y ES or NO and then, the computation halts as shown in Lemma 1. Next, we will prove the second statement of the theorem. Now the P system has been self-constructed. Only elementary membranes have strings. As shown in Lemma 1, in the halting configuration, these membrane have a set of examples and the pair Y ESaux and NOact or Y ESact and NOaux, depending of the classification of the examples. Any computation in the decision stage starts by placing a string x? as input in the skin, where vis a string of pairs Attribute Value. Since all the examples in each membrane have the same classification and no more examples are supplied, then the rules from sets R1 to R5 cannot be applied. Only rules from R6,R7 and R8 must be considered. The statement is the following Any computation in the decision stage gives 2p+ 2 steps with p∈ {0, . . . , k}and sends to the environment Y ESact or NOact (but no both) in the last step of computation. (C2) Proof. First of all, let us notice that rules from R6,R7 and R8 cannot be applied simultaneously, because the conditions of applicability are disjoint and only one string x? is provided as input in the skin in each computation. From this observation, rules from R7 are firstly applied ptimes with p∈ {0, . . . , k}. After these psteps, the elementary membrane where Y ESact or NOact is placed and in the 154 D´ıaz-Pernil et al. step p+ 1, the object Y ESact or NOact (but no both) is produced. After psteps more, in the step 2p+ 1, Y ESact or NOact arrives to the skin by application of rules from R8. In the following step, 2p+ 2, the object Y ESact or NOact is sent out to the environment and the computation halts. In the third statement, we consider the self-constructed P system and take an example from the training set xC, with C∈ {Y ES, NO}and replace Cby ?. The statement claims that if we provide x? to the P system in the decision stage, we obtain the same classification that the original one. The statement is The recognizer P system obtained at the end of any computation of the self-constructing stage is consistent with the training set. (C3) Proof. In order to fix ideas, let us consider that the original example was xY ES. The other case is analogous. By rules from R6,x? will be sent to an elementary membrane where all the examples have the same classification. One of these examples was originally the xY ES and Y ESact occurs in this elementary membrane. Then, by application of one rule from R7 and later with rules from R8, the object Y ESout is sent to the environment.