Qualitative Reasoning on Complex Systems from Observations

Qualitative Reasoning on Complex Systems from Observations Gonzalo A. Aranda-Corral1, Joaquı´n Borrego-D´ıaz2,andJuanGal´an-P´aez2 1 Universidad de Huelva. Department of Information Technology. Crta. Palos de La Frontera s/n. 21819 Palos de La Frontera. Spain 2 Universidad de Sevilla. Department of Computer Science and Artificial Intelligence. Avda. Reina Mercedes s/n. 41012 Sevilla. Spain Abstract. A hybrid approach to phenomenological reconstruction of Complex Systems (CS), using Formal Concept Analysis (FCA) as main tool for conceptual data mining, is proposed. To illustrate the method, a classic CS is selected (cellular automata), to show how FCA can assist to predict CS evolution under different conceptual descriptions (from different observable features of the CS). 1 Introduction The task of understanding a phenomenon amounts to find a reasonably precise and concise approximation to this phenomenon and its behavior such that it can be grasped by the human brain. New methods and tools have to be developed in order to assist experimental design and interpretation for: Identifying relevant entities at a given time and space scale, characterizing interactions between entities, and finally assessing and formalizing the system behavior [7]. Formal epistemology can play a relevant role. An adequate selection of key features and their dynamics specification is the first step in order to reconstruct the phenomena. In multilevel CS, the selection task requires a complex analysis of the different abstraction layers and organization levels. In classical systems as Cellular Automata (CA), the selection is limited by geometric and topological constraints so it could be more feasible. Human observation of CA allows to conjecture simple rules about the local dynamics, in order to explain the system dynamics as well as to isolate key concepts to forecast its evolution. Formal Concept Analysis (FCA) [8] provides tools and methods for extracting semantic features from data. FCA is a mathematical theory for data analysis, using formal contexts and concept lattices as key tools. The aim of this paper is twofold. On the one hand, to show how FCA is used in the phenomenological reconstruction of CS dynamics, of qualitative nature. On the other hand it also aims to show how the selection of observable features influences the reconstruction, particularly the attributes on objects and interactions. To exemplify this idea, a well-known example, Conway’s game of life (GoL), has been selected as running example, although the methodology is applicable to a wide class of CA. Supported by TIC-6064 Excellence project (Junta de Andaluc´ıa) cofinanced with FEDER funds. Fig.1. Formal context, concept lattice, Basis and FCA-based reasoning on CS The next section reviews the basic elements of FCA, focusing on the use of implication basis (and association rules) for reasoning with formal contexts as basic data structure for qualitative observations. Sect. 3 succinctly presents contextual selection reasoning. In Sect. 4 GoL is used to show how CA is modeled by means of FCA which is also applied to a probabilistic Conway’s CA variant (Sect. 5). Sect. 6 is devoted to conclusions of the work and related work. 2 Background: Formal Concept Analysis According to R. Wille, FCA mathematizes the philosophicalunderstandingof a concept as a unit of thoughts composed of two parts: the extent and the intent. The extent covers all objects belonging to this concept, while the intent comprises all common attributes valid for all the objects under consideration. In this section, we succinctly present basic FCA elements (see [8] for a detailed exposition). A formal context M=(O, A, I)consists of two sets, O(objects) and A(attributes) and a relation I⊆O×A. Finite contexts can be represented by a 1-0-table (identifying Iwith a boolean function on O×A. See Fig. 1 top-left.The main goal in FCA is to compute the concept lattice extracted from the context. Given X⊆O,Y⊆Ait defines X:= {a∈A|oIa for all o∈X}and Y:= {o∈O|oIa for all a∈Y} A (formal) concept is a pair (X, Y )such that X=Yand Y=X. For example, concepts from formal context about living beings (Fig. 1, center) are depicted as a lattice. Actually in this lattice, each node is a concept, and its intension (or extension) can be formed by the set of attributes (or objects) included along the path to the top (or bottom). For example the node tagged with the attribute Legs represents the concept ({Legs, Mobility, NeedWater},{Cat,Frog})(which could be interpreted as the concept land animal in this context). Knowledge Bases (KB) in FCA are formed by implications between attributes.An implication is a pair of sets of attributes, written as Y1→Y2. It is true with respect to M=(O, A, I)according to the following definition. A subset T⊆Arespects Y1→Y2if Y1⊆ Tor Y2⊆T.Y1→Y2is said to hold in M(M|=Y1→Y2or Y1→Y2is an implication of M)ifforallo∈O,theset{o}respects Y1→Y2. Definition 2.1. Let Lbe a set of implications and Lbe an implication. 1. Lfollows from L(L|=L) if each subset of Arespecting Lalso respects L. 2. Lis complete if every implication of the context follows from L. 3. Lis non-redundant if for each L∈L,L\{L} |=L. 4. Lis a (implication) basis for Mif Lis complete and non-redundant. A particular basis is the so called Stem Basis (SB) [9]. SB for the context of Fig. 1 is shown (down). In this paper no specific property of the SB is used, so it can be replaced by any other. In order to reason with implications, a production system can be used [3]. Theorem 1. Let Sbe a basis for Mand {A1,...,A n}∪Y⊆A. The following statements are equivalent: 1. S∪{A1,...A n} pY(pis the entailment with the production system). 2. S|={A1,...A n}→Y 3. M|={A1,...A n}→Y. Implication basis are designed for entailing true implications only. When working on predictions Theorem 1 does not provide a sound method. In this case it is better to consider association rules (with confidence) from the Luxenburger Basis [17] instead of SB. The production system must be revised for working with confidence [4]. In FCA, association rules are also implications between sets of attributes. Confidence and support are defined as usual in data mining. The Stem Kernel Basis (SKB) is the subset of the SB formed by the implications with nonzero support. SKB are useful in a number of applications (cf. [3,2]). 3 Bounded (Automated) Reasoning on Complex Systems The general approach to FCA-based qualitative reasoning on CS is based on considering local interaction as objects, which have several (local, observable) features (attributes) (see Fig. 1 right). Once the observer selects the attributes to be studied on the system, He/she can consider local interactions or nodes as objects of a formal context. This context M(often a huge formal context) is built by means of data extraction, database processing, expert observations, data mining, etc. The observer has to select attributes and objects he considers relevant to determine CS dynamics, and the reasoning focuses on the associated subcontext (contextual selection). It is expected that reasoning with the contextual selection gives some information about the CS. In [4] this approach was applied using argumentative reasoning on contextual selections. Particularly interesting is the case of predicting events when Mrepresents attributes on past events. The inference process consists of three steps [4]: 1. A question raises on whether a new event (object) has a property (attribute). Some properties on the new object are known (attribute values) {A1,...A n}. 2. Selection provides a relatively small set of attributes, selected from own experience and beliefs, which are relevant on the object (according to observer’s opinion). 3. The production system is executed on L∪{A1,...A n},whereLis a basis for the context induced by attribute selection made in step 2. The results obtained are the attributes inferred about the new object. If the attribute Bis inferred by the production system, then Bis conjectured on the object. Fig.2. Modeling CA with FCA (left). An oscillator with its production system (right) Association rules are extracted from the contexts and used by the production system. From these association rules and some initial facts, based on the event we want to predict, the production system infers the confidence (probability) for each one of the possible values for unknown attributes on the event. Thus attributes constitute one of the most important and sensitive parts of the system. Lastly, attribute selection allows isolating a piece of Mwhere argument reasoning is based. 3.1 Describing CA Dynamics by Means of FCA The aim of the paper is to show how this method provides a phenomenological reconstruction of CA, a CS where information flow is closed, namely Conway’s Game of Life (GoL). Whilst in [4] the method is applied to a CS with external information flow. Thus It was not possible to validate the method beyond purely experimental considerations. In classic CA the new state of a cell only depends on the neighborhoodconfiguration at the preceding time step (even it is also possible to consider memory capabilities [1]). If σT idenotes the value of cell iat time step T, the evolution is an iteration of a mapping σ(T+1) i=φ({σ(T) j:j∈N i} where φis an arbitrary function which specifies the cellular automaton rule operating on the cells in the neighborhood Niof the cell i. The standard framework of CA can be extended by implementing memory capabilities in cells: σ(T+1) i=φ({s(T) j:j∈N i)} with s(T) jbeing a state function of the series of states of the cell jup to time-step T; s(T) j=s(σ(1) j,...,σ(T) j). The aim is to compute φfrom observable features of Ni(attributes) by means of FCA reasoning. Let M=(O,A,I)be the formal context whose objects Oare cells, and attributes Aare (computable) boolean properties (relation Ibetween objects and attributes) on the cells (for example, Is-Alive), considering, if it is necessary, past time steps (see Fig. 2, left). From this formal context, SB, SKB and association rules can be computed. These are the Knowledge Basis (KB) containinga full or partial representationof CA dynamics,to be used in the reasoning process (i.e. to predict the evolution of a CA when its rules are unknown). Also the attribute selection (that is, the selection of spatio-temporal features on cells, the observer thinks that are relevant to decide the future state) is a key step, and the logical complexity of the description depends on this selection. Fig.3. Attributes for cells using N-Neighbors (left) and Geometric representation (right) 4 Modeling Game of Life by Means of FCA In order to show how CA can be analyzed with the above described method, Conway’s Game of Life (GoL) (popularized by M. Gardner [10]) has been selected as running example, both the original one and an stochastic version. Attribute Selection. The framework is similar to when an observer aims to predict the future state of CA from the observation of its evolution after a number of transitions. Two steps are needed: 1) Choose topological/geometrical properties which are considered relevant to describe system’s evolution. 2) Conjecture, based on these properties, the rules governing the system. Two ways of describing current cell’s environment are considered, which correspond to two ways of feature selection by the observer: Attributes based on the number of alive neighbors (N-Neighbors): This modeling is specific for GoL, as it is based on the number of alive neighbors. The attribute set has 11 attributes (See Fig. 3 left for an example): 9 Attributes describing the neighborhood: {0-Live-Neighbors, ..., 8-Live-Neighbors}, one attribute describing current cell state: Is-Alive, and one attribute describing the cell state in the next generation: Will- Be-Alive(Target) (which is the target attribute in the reasoning process). Attributes based on each neighbor state (Geometric): This modeling is not specific for GoL, but is robust enough to be used with many diverse CA. The state of each neighbor is specified individually, considering the Moore neighborhood. This attribute set consists on 18 attributes (see Fig. 3, right): 16 Attributes specifying (geometrically) whether each neighbor is alive or dead: {Top-Left-Alive, Top-Left-Dead, ..., Bottom- Right-Alive, Bottom-Right-Dead}and the attributes Is-Alive and Will-Be-Alive(Target) as in the above representation. FCA Based Reasoning for CA.OnceM=(O,A,I)is built (as above described), the concept lattice (see Fig. 4, top) and SB, LGoL, are computed. In the case of N- Neighbors representation, It matches Conway’s rules. This implicational basis (LGoL) is the aforementioned KB. In Fig. 4 the meaning of a concrete rule (from the KB obtained using the N-Neighbors representation) is explained. Note that the concept cell that survives is extracted from the formal context. In fact, the following holds, LGoL |=2-live-Neighbors →(Is-Alive ↔Will-Be-Alive(Target)) which gives some insights on live persistence in GoL. Preliminary experimentsshowed that both representations described suffices for predicting GoL behavior. Using just one transition as KB, from time step N−1to N, it is possible to predict CA state in the time step N+1.SBusingtheGeometric Fig.4. Concept lattice (N-Neighbors) showing rule 3 (top) of its SB (bottom) representation has a considerably bigger size (more than 700 rules) than the SB using the N-Neighbors representation (3 rules). For instance, the recognition of persistence or oscillatory objects in GoL depends on FCA modeling and historic features of CA. For example, to recognize that the blinker (Fig. 2, bottom right) is an oscillator with period 2, it suffices to provethe two facts shown in Fig. 2 (top right) with the productionsystem (Ljis the SB for the transition step j). Soundness: The method on a bounded region of CA universe, depends on both the attribute selection and the size of the region observed. In the case of CA in which φ uses N-neighbors or Geometric attributes, φinduces a set of implications on attributes, denoted by Sφ, defined as follows. For the sake of simplicity, only geometric attributes are considered (the other case is similar). Let LNthe set of configurations of the neighborhood Non which φtakes the value Will-be-Alive and let DNits complement (on which φoutputs Will-be-Dead). It is described by means of two formulas  C∈LN C→Will-be-Alive,and  E∈DN E→Will-be-Dead where each C, E is a conjuction. Let be Sφ={C→Will-be-Alive :C∈LN} and Nφ={E→Will-be-Dead :E∈DN}. Note that Sφcharacterizes φ,soit can be considered as an equivalent characterization. In this case, the attribute Will-be- Dead should be also consideredin the representation. The soundnessis stated as follows (ahistoric CA, Moore neighborhood): Theorem 2. Let be a CA specified by a function φ. For any nontrivial initial population density δ(that is, 0<δ<1being the probability for a cell to be alive) it has lim MProb(KM|=Sφ∪Nφ)=1 where KMis the Stem Kernel Basis for the the first transition of the CA restricted to the rectangle IM=(−M,M)×(−M,M)⊂Z2 Table 1. Experiments. #P, #CTH and #runs are the number of intervals for P,CTH and number of runs resp. and SB average size for CTH =1.0)andP=1.0 CA modeling #P #CTH Nexec #runs SB average N-Neighbors 100 100 50 500,000 3.25 Geometric 50 50 717,500 735.91 5 Cellular Automata with Probabilistic Features The framework is extended to probabilistic CA’s for dealing with real world situations, where rules are unknown and the information available comes from observations. In the probabilistic CA, in each time step, Pis the probability for each cell to behave normally, and 1−Pthe probability to behave randomly. Since SB do not consider any rule exception, in order to deal with probabilistic CA (uncertain reasoning), it is more appropriate to choose association rules. Thus the production system used in this case is a bit different to the one mentioned before (it works like in [4]). As the confidence of association rules measures the truth degree of the rules within the context, a confidence threshold (CTH) is selected to choose a rule subset as KB in the reasoning process. 5.1 Experiments The goal of the experiments is to test the reliability of FCA-based reasoning for simulating CA dynamics. To this aim, one experiment for each of the two representations of CA is presented, in order to test the accuracy(measuringthe error rate) of the reasoning system for different values of CTH and P. Some parameters should be selected to set up the experimentation environment. 1) grid size (1000 cells). 2) Initial grid density (around 30% of alive cells1). 3) The transition used to build the KB (GenKB. From generation 1to 2). 4) The generation to be predicted by the reasoning system (Genquery. Generation 3). Finally, three dimensions were considered in order to perform different experiments and explore the results: 1) Confidence threshold CTH for the KB, 2) Probability Pfor the probabilistic GoL and 3) Number of cells the system could not predict properly (error rate). For each different value of CTH and Pthe system is executed Nexec times in order to obtain the average error rate in the prediction of the next state. Each execution is as follows: 1. CA grid is randomly initialized with a fixed initial density. 2. A first transition of the CA is simulated (with probability P) to obtain GenKB. 3. A formal context M=(O,A,I)is built with the information of GenKB. 4. Extraction of association rules set, using the threshold CTH to obtain the KB 5. For each cell an attribute set with the description of its neighborhood state in the 2nd generation is computed. The system is executed on these attributes, to infer whether the cell will be alive or dead in the 3rd generation, according to the selected criterion. 6. The error rate is measured. 1We have selected this initial demographic density for probabilistic experiments because the experiments showed long non-stable behaviors for most of Pvalues. (a) N-Neighbors rep. (b) Geometric rep. (c) Correlation Fig.5. Experimental results ((a), (b)) and Correlation between CTH and Pminimizing error rate for N-Neighbors representation 5.2 Discussion/Results Results of experiments are shown in Fig. 5 (plots a and b). As 1−Pis the probability of a random state change to occur in a cell, the error rate is expected to grow fast. When P<0.5, CA behavior tends to be chaotic and unpredictable. It is interesting to observe how the uncertainty introduced by Pis countered by the confidence of association rules. The values of Pand CTH are correlated in order to minimize the error rate. Fig. 5 (a, b) shows how the confidence threshold CTH decreases linearly with the probability Pin order to minimize the error rate (recall that randomness grows as Pdecreases). It is worth to note the case of N-Neighbors where the points minimizing the error rate form an almost perfect line when P≥0.1. When P<0.1the behavior of the CA is fully random. Fig. 5 (plot c) shows for each probability value P≥0.1,thevalueofCTH minimizing the error rate.Also the Pearson’s correlation coefficient for the same dataset is 0.863. This high correlation between the probability (uncertainty) of the CA and the confidence threshold used to select the rules set of the reasoning system shows system’s resistance against noise and randomness. Results show that geometric representation is less accurate (but acceptable). If we think in the fast and frugal way [12], this will be the representation to be used with any kind of CA based on the Moore neighborhood, as it is more robust when modeling any unknown problem. Finally, it is interesting to remark, that the huge difference between both representations in the SB size (Table 1) will not suppose a big difference in computation time. The reasoning system works with logical implication between attributes, thus once the implication basis has been computed, the execution of the reasoning system is quite light. Moreover, the Stem Basis is minimal, therefore SB size will be similar in any experiment where the size of the considered grid is big enough. 6 Conclusions and Related Work The methodology for short-term prediction of CS evolution, previously used in [4], allows to outline the relationship between the system’s features (attributes) choice and the complexity of the logical description of its evolution (by means of FCA). We have selected as running example the well-know GoL system, but the methodology can be applied to other more complex examples. In [4] it is shown how a sound attribute selection can make this prediction method better than classic learning systems. However, in [4], the soundness of the method is justified only in experimental terms, due to the fact that an information flow, external to the system, already exists. In the case of this work, the CS under study has a closed environment (without external information flow). Thus it has been shown that not only the method works, but also it correctness, in asymptotic terms, can be demonstrated. This method constitutes an hybrid method due to the fact that FCA does not consider non-deterministic reasoning. With respect to FCA-like approachesfor mining dynamics of systems, in [6] a notion of (deterministic) association rule for ordered data is proposed, proving that the result can be formally justified by using background knowledge, and FCA is applied on ordered contexts. Implications can be considered as a specialized Horn-like propositional clauses. Therefore, logical machinery designed for Horn logic reasoning can enrich the framework presented in this paper, particularly those which work with ordered data [5,6]. This question is the aim of a future work. With respect to CA field, the method produces logical representations of transitions which may be related with λparameter [13]. It could be useful to analyze the behavior of Stem basis in probabilistic versions of CA [22,15]. A FCA-based formalization for CA with memory can be a descriptional system on which validate specific conditions in future formal methods to specify emergence in CA [21]. Moreover, FCA also provides a strong relation between implications and the context. Classifications as that of given in [14] can be an interesting starting point to extend FCA with asymptotic studies on formal contexts which evolve. In [16] it is also shown a method for data mining of CA transition rules focused on geographic applications. In [20] the authors use genetic algorithmsin the learning phase whilst we could offer a logical argumentof the learning of rules. The probability δfor the initial population of experimentsis a key parameter in order to determine the evolution of the CA, thus the above mentioned limit strongly depends on its value. A similar (although more specific) question is studied in [11], where the existence of CA with fixed point configurations depending on initial density are considered. From the point of view of our paper, we could say that certain implicational description of the world has the formal context associated to the current state as fixed point. Entropy features of formal contexts should be considered, in order to relate FCA representation with asymptotic behavior of CA [19], as well as to extract conceptual structure in CA with similar behavior without human engineering [18]. Classical learning process does not provide a straightforward method to discover new geometrical concepts, as FCA can do (identifying some formal concepts as the FCA-based definition of stable colonies or gliders, by analyzing their extents) by expanding attribute set and Moore neighborhood(even by using geometric -non isotropicattributes) as well as attributes with bounded temporal stamps [1].