Evidence Sets and Contextual Genetic Algorithms

This dissertation proposes a systems-theoretic framework to model biological and cognitive systems which requires both self-organizing and symbolic dimensions. The framework is based on an inclusive interpretation of semiotics as a conceptual theory used for the simulation of complex systems capable of representing, as well as evolving in their environments, with implications for Artificial Intelligence and Artificial Life. This evolving semiotics is referred to as Selected Self-Organization when applied to biological systems, and Evolutionary Constructivism when applied to cognitive systems. Several formal avenues are pursued to define tools necessary to build models under this framework.

In the Artificial Intelligence camp, Zadeh's Fuzzy Sets are extended with the Dempster-Shafer Theory of Evidence into a new mathematical structure called Evidence Sets, which can capture more efficiently all recognized forms of uncertainty in a formalism that explicitly models the subjective context dependencies of linguistic categories. A belief-based theory of Approximate Reasoning is proposed for these structures, as well as new insights as to the measurement of uncertainty in nondiscrete domains. Evidence sets are then used in the development of a relational database architecture useful for the data mining of information stored in several networked databases. This useful data mining application is an example of the semiotic framework put into practice and establishes an Artificial Intelligence model of Cognitive Categorization with a hybrid architecture that possesses both connectionist and symbolic attributes.

In the Artificial Life camp, Holland's Genetic Algorithms are extended to a new formalism called Contextual Genetic Algorithms which introduces nonlinear relationships between genetic descriptions and solutions for a particular problem. The nonlinear relationship is defined by an indirect scheme based on Fuzzy Sets which implements the simulation of dynamic development after genetic transcription. Genetic descriptions encode dynamic building blocks that self-organize into solutions. Since the self-organizing process may depend on environmental information, the process is thus contextualized. The main advantage of this scheme is the ability to reduce dramatically the information requirements of genetic descriptions, it also allows the transformation of real-encoded to binary-encoded problems. The scheme is used successfully to evolve Neural Network architectures as well as Cellular Automata rules for non-trivial tasks. It is also used to model the biological process of RNA Editing. Contextual Genetic Algorithms are an instance of the semiotic framework proposed and of Selected Self-Organization in particular.

Keywords: Complex Systems, Systems Science, Adaptive Computation, Evolutionary Algorithms, Artificial Intelligence, Artificial Life, Data Mining, Information Technology, Fuzzy Logic, Interval-Valued Fuzzy Sets, Dempster-Shafer Theory of Evidence, Uncertainty, Cognitive Categorization, Context, Relational Databases, Embodiment, Constructivism, Self-Organization, Natural Selection, Evolutionary Systems, Semiotics, Representation, RNA Editing, Development, and Situated Cognition.

Dedication

To my family

who cultivated in me the notion of knowledge as power,

and

who gave me all the support and love needed to try to achieve it.

Acknowledgments

Many people, ideas, and places have influenced and contributed, directly and indirectly, to this dissertation. More or less chronologically, I would especially like to thank:

My parents for unreserved love, support, and encouragement. À Mãe por todos os sacrifícios que nos tem dedicado, e também por me mostrar que podemos sempre fazer melhor. Ao Pai pela inspiração em todas as coisas científicas que despoletou em mim, e por sempre me apoiar mesmo nas decisões mais ousadas.

My brother for being my life long best friend, and trusting me beyond any doubt. Todos aqueles telefonemas deliciosos pela manhã, acredita, foram inúmeras vezes aquela "forcinha" necessária para passar os problemas do dia a dia de cabeça erguida.

The few teachers from junior to high school who took the extra time to deal with me! In particular my Physics, Philosophy and Geometry teachers.

Barata Marques and Luciano Faria for giving me a hand in college.

Helen Swannell for showing me sweetness in life. Thanks for your dreams and passions!

Pedro e Guida Medina Martins for encouraging my ambitions.

Francisco Carvalhal for such strong guidance and teaching me the pleasure of team work.

Susana Santos for truly happy times e muita paciência!

Gordon Pask, Heinz von Foerster, and Gerard de Zeeuw for encouraging me beyond words, and pointing the way towards a more humanistic science. Thank you so much!

Francis Heylighen and Cliff Joslyn for really getting me into this Systems Science thing.

Chuck Henry and Nancy Todd for opening the door and for listening power.

George Klir for unbounded interest and guidance. Thank you for such creativity, hard work, and willingness to foster my pursuits.

Howard Pattee first for swamping me with such an array of interesting problems, and then for proposing the most eloquent and balanced solutions. Thank you for discussing and reading my often half-baked manuscripts with such prompt response.

Don Gause for making me work 16 hours a day happily! Thank you for all the time and interest in discussing myriad different problems, and for truly inspirational teaching methods.

Eileen Way for captivating discussions over the connectionist debate, and for making me put reason where there was only blabber.

John Dockery for amazing support and interest. I owe the condensation of this dissertation into a presentable shape to an evening of your guidance.

Fernando Carvalho Rodrigues for tremendous support and creativity!

Howard Pattee's and George Klir's research groups for most intersting discussions and comments: especially Robin Beckerman, Bo Yuan, David Harmanec, Ute St. Clair, George Fridrich, Ira Glickestein, Barbara Harris, and Dario Nardi.

All those who have contributed to the ideas here pursued with lively debates, presentations, or overall scientific support: Gertrudis van de Vijver, Jon Umerez, Peter Cariani, Eric Minch, Robert Rosen, George Kampis, Arantza Etxeberria, Bernard de Baets, Vladik Kreinovich, Stan Salthe, Jerry Chandler, Gert de Cooman, Alvaro Moreno, Ranulph Glanville, Clara Pinto Correia, Erich Prem, Melanie Mitchell, Wim Hordik, John Casti, and many others .

My life long friends so necessary to maintain my sanity. Tomi Erkkila for being my buddy and having the patience to, among other things, ski with me -- Tracey, you are a lucky girl! Manuel Cardenas for unbelievable patience, friendship, and mathematical help (and chicken wings!). Virginia Cole for being such a source of stability in graduate school (and all the movies!). Jon Umerez and Gabriela Chotro for being so sane! Jon, thanks for all sorts of most valuable discussions. Matt Hochberg (for musical satisfaction), Maureen O'Connor (for those wonderful action-packed days!), Dolly Varkey (oh the Rat!), Marco Busatto (for not really wussing out), Sezai Dogdu (Thursday night fever!), Johan Bollen (the coolest net dude!), Jim Gattiker, Ray Barnes, Olokunmi Johnson, Carolin Auer, Tabea Linhard (the world needs a Tambourine Girl!), Mina Caravagio, Amy McNichols, Michella Scotto, Thomas Uthup, and all other friends who I do not name here.

Debbie, thank you for your love and patience so dearly appreciated especially in this final "dissertating" stretch.

The work here presented was supported from 1992 to 1996 by a scholarship awarded by the Programa CIENCIA, Junta Nacional de Investigação Científica e Tecnológica, Lisbon , Portugal.

TABLE OF CONTENTS

CHAPTER 1

INTRODUCTION 1

Motivation 1

Preliminary Background 2

Aims and Claims 5

Outline 5

Application Areas 8

CHAPTER 2

SELECTED SELF-ORGANIZATION AND EVOLUTIONARY CONSTRUCTIVISM 9

1. Selected Self-Organization 9

1.1 Self-Organization 9

1.2 Emergent Classification and Constructivism 10

1.2.1 Cybernetics and Eigenbehavior 10

1.2.2 Complexity Theory, Emergent Representation, and Emergent Morphology 10

1.2.3 Self-Organization and Constructivism 12

1.3 Emergence and Levels of Description 12

1.3.1 Explanatory Emergence 13

1.3.2 Semantic Emergence 14

1.4 Memory and Selected Self-Organization 15

1.4.1 Variety of Classification and the Edge of Chaos 15

1.4.2. Structural Change and Emergent Classification 16

1.4.3 Distributed Memory 17

1.4.4 Embodiment 18

1.5 Descriptions and Symbols 18

1.5.1 Von Neumann and Description-Based Selection 18

1.5.2 Descriptions require a Symbol System 19

1.5.3 Parts, Symbols, and Embodiment 20

1.5.4 The Symbolic Advantage 20

1.6 Semantic Closure and Open-Endedness 21

1.6.1 Finite Symbol-Part System 22

1.6.2 Dynamic Part Compounds 22

1.6.3 Development: Constraints on Evolution 23

1.6.4 Selected Self-Organization with Local Memory 24

1.6.5 The Credit Assignment Problem 24

1.7 Evolving Semiotics 25

2 Evolutionary Constructivism 26

2.1 Material Basis: Selected Self-Organization and Constructivism 27

2.1.1 Radical Constructivism 27

2.1.2 Physical Constructivism 28

2.1.3 Constructionism 29

2.1.4 Situated Cognition 29

2.2 Realism and Evolutionary Epistemology 30

2.3 Critical Realism 31

2.4 Language Theory and Evolutionary Constructivism 32

2.4.1 Selected Self-Organization 33

2.4.2 Improving Structural Perturbation 34

2.4.3 Metaphor 35

2.4.4 Constraints and Evolutionary Contructivism 35

CHAPTER 3

EVIDENCE SETS: CONTEXTUAL CATEGORIES 37

1. Cognitive Categorization 37

1.1 Models of Cognitive Categorization 38

1.2 The Classical View 38

1.3 Prototype Theory and Fuzzy Sets 39

1.4 Dynamic Categories 40

1.5 Fuzzy Objectivism 41

2. Mathematical Background 41

2.1 Measures 41

2.2. Dempster-Shafer Theory of Evidence 42

2.2.1 Basic Probability Assignment 42

2.2.2 Belief and Plausibility 42

2.2.3 Focal Elements and Bodies of Evidence 43

2.2.4 Dempster's rule of combination 43

2.2.5 Joint Bodies of Evidence 43

2.2.6 Inclusion 44

2.3 Fuzzy Sets and Interval Valued Fuzzy Sets 44

2.4 Uncertainty 45

2.4.1 Conflict 46

2.4.2 Nonspecificity 47

2.4.3 Fuzziness 47

3. Sets and Cognitive Categorization 48

3.1 Fuzzy Sets and the Prototype Combination Problem 48

3.2 Interval Valued Fuzzy Sets 49

3.3. Set complement and intuitionistic sets 50

4 Evidence Sets: Membership and Belief 51

4.1 Consonant Evidence Sets 51

4.2 Non-Consonant Evidence Sets 52

4.3 Complexity of Computation 52

4.4 Contextual Interpretation of Evidence Sets 52

5. Relative Uncertainty and Evidence Sets 54

5.1 Nonspecificity 54

5.1.1 A General Measure 54

5.1.2 Absolute Nonspecificity 55

5.1.2 Relative Nonspecificity 59

5.2 Conflict 62

5.2.1 Absolute Conflict 62

5.2.2 Relative Conflict 63

5.3 Fuzziness 64

5.4 3-D Uncertainty 65

5.4.1 Nonspecificity in Evidence Sets 65

5.4.2 Conflict in Evidence Sets 66

5.4.3 3-D Uncertainty Cube 66

6. Belief-Constrained Approximate Reasoning 67

6.1. Uncertainty Increasing Operations Between Evidence Sets 67

6.1.1 Complementation 67

6.1.2 Intersection 68

6.1.3 Union 68

6.1.4 Increasing Uncertainty 68

6.2 Uncertainty Decreasing Operation Between Evidence Sets 68

6.3 The Pet-Fish Example 70
72

7.1 Upper and Lower Probabilities Interpretation 72

7.2 Belief Interpretation 72

7.3 Generalized Dempster-Shafer Theory 73

7.4 Evidence Sets : Independent Membership 73

CHAPTER 4

CONTEXTUAL GENETIC ALGORITHMS 75

1 Models with both Dynamic and Selective Dimensions 75

2 Semiotics of Living Organizations 75

2.1 Two Type Symbol System: Contextual Environmental Information 76

2.2 Embodiment and Implementation Dependence: Selected Self-Organization 77

3. Contextual Genetic Algorithms 78

4. Exploring Syntax and RNA Editing 80

4.1 RNA Editing 80

4.2 A Formal Model of Genetic Editing 83

5. Development and Material Constraints 87

5.1 Development in Artificial Life 87

5.2 Fuzzy Development Programs: Emergent Classification in Contextual Genetic Algorithms
88

5.2.1 Fuzzy Sets as Dynamical States 88

5.2.2 Fuzzy Development Programs 90

5.2.3 Information Requirements of Fuzzy Development Programs 90

5.2.4 General Purpose Genetic Algorithm with Developmental Indirect Encoding: Emergent Classification 92

5.2.5 Computational Issues: Fuzzy Indirect Encoding as Solution Approximation 93

CHAPTER 5

IMPLEMENTING CONTEXTUAL STRUCTURES FOR DATA MINING 95

1. Computing Categories in Relational Databases: Linguistic Categories as Consensual Selection of Dynamics 95

1.1 Nakamura and Iwai's Fuzzy Information Retrieval System 96

1.1.1 The Long-Term Networked Memory Structure: Semantic Closure 97

1.1.2 Short Term Categorization Processes 97

1.1.3 Document Retrieval 99

1.1.4 Adaptive Alteration of Long-Term Structure by Short-Term Categorization: Pragmatic Selection 100

1.2 Contextual Expansion With Evidence Sets 101

1.2.1 Distances from Several Relational Databases: The Extended Long-Term Memory Structure 101

1.2.2 Extended Short-Term Categorization 102

1.2.3 Document Retrieval 105

1.2.4 Adaptive Alteration of Long-Term Structure 105

1.2.5 Categories as Linguistic, Metaphorical, Structural Perturbation 105

1.2.6 Open-Ended Structural Perturbation 106

1.2.7 TalkMine: The Implemented Application 106

2. Emergent Morphology and Evolving Solutions in Large State Spaces 112

2.1 Implementation Details 112

2.2 Continuous Variables: Evolution of Neural Network Weights 113

2.2.1 Hand-Written Character Recognition: The Network Architecture 113

2.2.2 Results from Back-Propagation 114

2.2.3 Results from Real-encoded GA 115

2.2.4 Results from CGA with Fuzzy Indirect Encoding 117

2.3 Discrete Variables: Evolution of Cellular Automata Rules 119

2.4 The Effectiveness of Computational Embodiment: Epistasis and Development 124

CHAPTER 6

SIMULATIONS OF EMBODIED EVOLVING SEMIOSIS 126

1. What Would Invalidate EES? 128

2. What Does EES Have to Offer to AI and AL? 129

2.1 Evolutionary Constructivism and AI 129

2.2 Selected Self-Organization and AL 131

3. Limitations of EES 131

3.1 The Origin Problem 131

3.2 Computational Limitations 132

4. Future Directions and Conclusions 133

REFERENCES 135

INDEX 144

CHAPTER 1

INTRODUCTION

"In recent years increasing need has been felt for a body of systematic theoretical constructs which will discuss the general relationships of the empirical world. This is the quest of General Systems Theory... Somewhere however between the specific that has no meaning and the general that has no content there must be, for each purpose and at each level of abstraction, an optimum degree of generality." [Boulding, 1956, page 197]

"The essence of mental life and bodily life are one, namely "the adjustment of inner to outer relations." [James, 1892, page .xxviii]

"The question of how symbols acquire semantics has been subsumed [in Artificial Intelligence and Artificial Life] into questions of syntax, how symbols relate to each other. And just as systematically, questions of pragmatics, why symbols come to have the semantic and syntactic relations they do, have been left out of the picture entirely." [Cariani, 1989, page vii]

Motivation

To define general relationships in the empirical world is the quest of Systems Science. The price of generalization, however, may be the curse of the cybernetic age, as widely encompassing synthetic theories, armed with powerful computer resources, tend to disregard the intricacies of particular systems. I am particularly impressed by attributes shared by cognitive and biological systems. Are these attributes only relevant if we abstract such systems enough, or are they at the core of the distinctions that uniquely classify living and cognitive systems? Furthermore, can we and do we have anything to gain from incorporating such attributes in computational applications?

The commonality I see follows from the symbolic/representational attributes of life and cognition. Unfortunately, symbol and representation are terms that carry a heavy weight of undesirable connotations. It is often argued that symbols are subjective constructs unnecessary to explain living and cognitive systems, which are nothing but highly interconnected networks of bio-chemical processes following perfectly determined rules. According to this view, these rules are all we need to explain biology and cognition. Some further argue that accepting a symbolic and representational dimension is misleading because living and cognitive systems do not represent an environment but rather construct it with the stabilities produced by the dynamics of their constituent bio-chemical networks. This view is often referred to as the self-organizing paradigm.

On the other extreme of the materialist and constructivist view above, are those identified with the symbolic paradigm who think of symbols as purely computational constructs. This form of computationalism defines representation as the mapping of categories from one domain to another: from environmental to genetic or mental categories. It thus ignores the material constraints of biological and cognitive systems, which are considered irrelevant to define such systems, accepting genetic and mental categories as mirroring (through the mapping) real world categories. The term representationalism has been identified with this view.

I shall argue that both representational and self-organizing approaches avoid the central issue of how matter and symbols co-evolve. Representationalism denies the particular aspects of a system's embodiment, while the self-organizing paradigm refuses to accept the evolutionary advantage of a pragmatic (selected), symbolic, relationship with an environment. I believe that an inclusive approach should be pursued which considers the syntactic, semantic, and pragmatic aspects of living and cognitive systems. Pragmatism is understood as a context-dependent, multi-level constraint satisfaction of material, developmental, and evolutionary requirements. Furthermore, this semiotic approach though general enough to encompass biology and cognition, should offer a set of specific requirements to distinguish living and cognitive systems from other complex systems, defining a valid systems theoretic conceptual framework. My motivation is precisely geared to add some more concepts and tools for the establishment of such a framework already proposed by other systems researchers with similar goals.

The aim of the present work is to advance arguments to substantiate the view that the modeling of cognitive and biological systems should utilize concepts emanating from both the self-organizing and representationalist paradigms. Indeed, both paradigms offer only an incomplete account of the nature of life, biological or cognitive, which is given a more realistic explanation when both paradigms are understood as complementary. Philosophical and conceptual arguments are given to substantiate this inclusive position, and how it relates to a web of existing philosophical viewpoints. The position is strengthened by the definition of mathematical and computational formalisms which show its relevance in the creation of practical computational applications for information technology.

Preliminary Background⁽¹⁾

Traditionally, Artificial Intelligence (AI) and Artificial Life (AL) have been associated with a computational approach to cognition and biological systems. Models involve systems that manipulate symbols which stand for external observables: a representational scheme. This manipulation follows computational rules, and has lead to the idea of mind and life as a program. With this approach, the particular substrate which implements symbols and rules is irrelevant as long as the desired computation is achieved. It is usually referred to as the Symbolic or Computational Paradigm.

The alternative view, brought back to life in the 1980's with the revival of earlier cybernetic ideas, uses physical laws as the basis of its models. It attempts a dynamic explanation of cognition and life by building models inspired by the dynamics of the brain and living matter. The functions that the symbolic paradigm attempts to directly represent and compute, are seen on this alternative approach as emergent properties of the dynamics. It is usually referred to as a Connectionist, Emergent, Dynamic, Subsymbolic, or Self-Organizing Paradigm:

"One of the most interesting aspects of this alternative approach in cognitive science is that symbols, in their conventional sense, play no role. In the connectionist approach, symbolic computations are replaced by numerical operations - for example, the differential equations that govern a dynamical system. These operations are more fine grained than those performed using symbols; in other words, a single, discrete symbolic computation would, in a connectionist model, be performed as a result of a large number of numerical operations that govern a network of simple units. In such a system, the meaningful items are not symbols; they are complex patterns of activity among the numerous units that make up the network." [Varela, Thompson, and Rosch, 1991 page 99]

The early 1990's were prolific in debates on the differences between the Symbolic and Connectionist paradigms [e.g. Ramsey, Stich, and Rumelhart, 1991 (eds); Dinsmore, 1992 (ed)]. Today, in most of AI, these distinctions have boiled down to the opportunistic utilization of techniques from both camps according to particular aspects of designed applications. Applied AI journals and magazines will just as likely publish the latest advances in expert systems driven by logic engines (classical, modal, or fuzzy), as the latest neural network, cellular automata, or genetic algorithm schemes. In fact, hybrid architectures tend to be the most favored items found on these publications. On a more conceptual level, it has been generally accepted that looking at cognition with symbolic or dynamic tools is a question of finding a comfortable level of description for the properties we desire to model. Those working within a symbolic paradigm are most often preoccupied with models of natural language and human reasoning and categorization processes, while those utilizing dynamic tools focus on pattern recognition and dynamic classification models.

In theoretical biology, evolutionary systems theory, or AL, a similar feud is defined between those that understand life as essentially a genetic variation engine subjected to natural selection (neo-Darwinism, functionalism) [e.g. Dawkins, 1987; Maynard-Smith, 1986; Dennett, 1995], and those that stress that life is essentially a property of the self-organization and development of dissipative material structures (structuralism) [e.g. Thom, 1975; Nicolis and Prigogine, 1977; Haken, 1977; Maturana and Varela, 1987; Kauffman, 1991; Goodwin, 1994]. Unlike what happens in cognitive science, in evolutionary systems theory it has been somewhat easier to propose inclusive approaches based on the hierarchical aspects of biological systems [e.g. Gould, 1989; Pattee, 1974; Salthe, 1985, 1993], though none of these proposals has had the widespread success of the genetic reductionism view.

The symbolic paradigm of AI and the genetic reductionist approach of evolutionary systems can be referred to generally as the representationalist view of life and cognition. Basically, it is based on the existence of discrete, static, entities that linearly stand for phenotypic traits in a living system they uniquely define, or for real world categories that a cognitive system must classify. Natural selection is the process that statistically biases these symbolic entities in population distributions of living systems, resulting in increased phenotypic adaptation to a given environment. The symbolic nature of the heritable results of natural selection, has lead to the widespread success of genetic models of artificial living systems which do not depend on a specific materiality [Langton, 1989]. Cognitive science has not been as lucky in defining an overall process responsible for the adaptation of mental to real world categories, or learning. Natural selection is proposed as an engine for phylogenetic learning in theories of evolutionary epistemology [Lorenz, 1981, Campbell, 1987, Wuketits, 1990] and even account for grammatical constraints of language [Pinker, 1993]. Ontogenetic learning is still very much the subject of theoretical strife. Regardless of the true nature of learning, representationalism considers that mental categories essentially mirror real world categories, and that the material aspects of cognitive systems are largely irrelevant.

The Connectionist paradigm of current day cognitive science, and the structuralist approach to evolutionary systems can be referred to generally as the self-organizing view of life and cognition. It is based on the existence of networks of simple components following simple state-transition rules, whose dynamic global behavior is essentially dependent on a small number (compared to the number of components) of dynamic basins of attraction. The process that leads the system from any initial state to one of the basins of attraction is understood as self-organization. These basins of attractions are not localized in identifiable components, but distributed and superposed [van Gelder, 1991] through the whole network. In evolutionary systems, this view emphasizes that life is largely dependent on the spontaneous organization of order which exists with or without natural selection. Further, evolution is believed to be restricted to the dynamic trajectories of these systems, that is, the history of the attractor landscape of a given dynamics as its structure is perturbed. This implies that not all phenotypic traits, regardless of their fitness in an environment, can be obtained, unless they stem from the set of possible dynamical stabilities in a given dynamic trajectory. In cognitive systems, this view likewise stresses that classification of an environment depends on the existence of dynamic stabilities of connectionist systems. Only those aspects of the environment whose interaction with the network lead to internal stabilities can be recognized and classified.

The morphology of living systems and the classification capabilities of connectionist systems are considered to be emergent properties of a complicated dynamics. That is, a multitude of highly interrelated simple components produce a dynamic behavior not completely described by the operative rules of the components. Morphology and classification are said to be emergent properties of self-organizing networks. But are emergent properties nothing but a different way to look at the complicated dynamics responsible for this emergence (reductionism), or do these properties establish a genuinely novel and distinct organization? At first glance, and if we desire to maintain the non-dualist, materialist, tenets of modern science, we seem to have no choice but to accept the reductionist stance expressed on the first interpretation of emergent properties: everything is ultimately explained by a lower-level dynamic set of laws and distinctions between levels exist only in the eye of the beholder who chooses to work on a particular level of description. The question is thus one of explanatory power and of levels of description.

The present work elaborates the view that emergent properties, though embedded on some lower dynamics, present a true novel organization which is not completely derivable from the lower level descriptions. The notion of emergence here defended is based on the explanatory power of different levels of description, and it is akin to Clark's [1996] recent ideas, which are related to Rosen [1985, 1995] and Cariani's [1989] emergence relative to a model framework. Particularly relevant is the concept of emergent classification which is discussed in detail. I shall argue that emergent classification can be improved when classifying systems are capable of establishing a clear form of symbolic interaction (semiosis) with their environments, which is both effectively representational and dynamically constructed. The argument for this situated semiosis is strongly grounded on Von Neumann's [1966] self-reproducing automata scheme, which is an argument for construction under symbolic control, as well as on an extended formulation of his Parts Problem. Stricter definitions of emergence exist (for a deeper discussion see Cariani [1989], Salthe [1991]), but to pursue my argument, the explanatory notion of emergence will suffice.

Both representational and self-organizing approaches to living and cognitive systems avoid the concept of semiosis. Representationalism denies the particular aspects of a system's situated embodiment with its contextual constraints, while the self-organizing paradigm refuses to address the utility of the concept of symbol and its evolutionary relationship with an environment.

I call for an inclusive approach that considers the syntactic, semantic, and pragmatic aspects of biological and cognitive life. To do this, I develop mathematical and computational tools that improve the simulation of certain mental and biological processes beyond pure representational or pure self-organizing models. These models are imbedded in a selection-grounded Constructivist framework. In other words, classification of an environment is highly dependent on the classifier's dynamical structure, it is not fully open-ended or based on mappings of real world categories to internal categories, but a result of internal construction of stabilities. However, there must be an element of effective representation, or the classifier system would not survive and reproduce in a given environment. This constructed, contextual, intentionality is a result of some form of selection by the environment, which I call evolutionary constructivism.

Aims and Claims

More explicitly, the aim of the present work is to advance an inclusive framework for the systems-theoretic study of biological and cognitive systems that utilizes both self-organization and representation. Such undertaking is pursued by:

Arguing the necessity of complementary levels of description for complex systems (emergence).
Arguing for a more complete understanding of symbol and representation based on the three semiotic dimensions of syntax, semantics, and pragmatics.
Showing that the coupling of symbolic controls to material self-organization defines enabling and restraining constraints on the living organization.
Developing models with self-organizing and symbolic characteristics for AI and AL and investigate their computational advantages.

The following is the list of the claims that are defended in the present dissertation in order to establish this framework named Embodied, Evolving Semiosis:

The living organization requires a system of structural perturbation of self-organizing dynamics, to be able to evolve new classifications (cognitive or phenotypical) of its own interaction with an environment.
If the system of structural perturbation is symbolic, then this evolution is open-ended.
Material symbol systems (used for the system of structural perturbation) are constrained in what can be represented in them.
Evidence Sets model cognitive categories which establish a system of structural perturbation of long-term, connectionist memory banks.
Contextual Genetic Algorithms model material genetic systems and their enabling and restraining constraints.

These claims are approached in different ways. a and b are defended by means of a synthetic gathering of evidence from several existing theories. c is argued in the same way as a and b, but is also validated by results from the formal models defined for points d and e, which are implemented computationally. Next, an outline of the organization of the dissertation is given.

Outline

I intend the present work to be organized in a semiotic way with semantic, syntactic, and pragmatic areas made explicit. This way, the problem is explored philosophically, formally, and computationally respectively. I do not expect the three areas to fully support one another. The philosophical part lays out the problem in general terms and proposes conceptual arguments that should stand on their own. The formal parts, can also stand alone since they represent mathematical constructs valid in their own right. In any case, they are proposed as formal tools to deal with certain aspects of the larger philosophical issues. Finally, the computational parts give some pragmatic validation to certain aspects of the formal tools, by creating computational models of the larger conceptual issues as well as practical applications valid on their own. These computational applications, useful for the fields of data-mining and optimization algorithms, offer the desired pragmatic validation of the philosophical positions advanced. In so doing, they show that there are important advantages to be gained from more inclusive, complementary, theories of artificial intelligence and artificial life that acknowledge both self-organization and representation.

The philosophical and conceptual part of the dissertation starts with a discussion of the divisions between representationalism and self-organization. Self-organization is presented within a framework of emergence and of levels of description. The constructivist position is examined in this context. I introduce the notion of selected self-organization as the backbone of the evolutionary constructivist position, and defend the existence of a symbolic dimension as a pragmatic result to increase the effectiveness of selected self-organization. I further discuss how these ideas relate to the study of natural language and evolutionary systems. Following these ideas, I next propose an evolving semiotic conceptual framework for this inclusive form of self-organization with both representational and constructed facets.

With natural language in mind, I develop a mathematical tool based on fuzzy set and evidence theories called evidence set, proposed as a more accurate model of cognitive categorization processes. Evidence sets extend interval valued fuzzy sets to a belief based framework, creating a method of formally modeling the contextual constraints of cognitive categories. Evidence sets are representational artifacts, but are also constrained by subjective belief structures, which are two key elements of evolutionary constructivism. In addition, evidence sets capture all forms of uncertainty recognized in generalized information theory, uncapturable by other set structures. Finally, an extended theory of approximate reasoning is proposed based on set-theoretic operations defined for evidence sets.

With evolutionary systems and artificial life in mind, I discuss the idea of contextual genetic algorithms. These computational models of natural selection are based on the existence of intermediate levels between genotype and phenotype. In other words, genetic descriptions do not encode directly for phenotypic traits, but for the boundary conditions of intermediate dynamical systems which self-organize into a set of phenotypical traits. The indirect encoding of solutions for a particular problem in genetic algorithms is referred to as contextual since the intermediate dynamical systems may depend on inputs other that just the genetic description, such as environmental observables. That is, expression of chromosomes to solutions does not depend solely on genetic information, but also on the system's context. Indirect genetic encoding is not only a more biologically correct model of genetic natural selection, but it also allows the evolution of different solutions from the same descriptions, which is important for adaptation, and additionally yields tremendous genetic information compression. Furthermore, conceptually, the marriage of selection and self-organization is the crux of evolutionary constructivism in evolutionary systems theory.

In order to validate evidence sets and contextual genetic algorithms as relevant models, I explore them computationally in a number of problem areas. Evidence sets are utilized in the development of a search method which acts on several relational databases. This search is based on the reduction of uncertainty stemming from conflicts between the information stored in the various databases which define several contexts. Contextual genetic algorithms are utilized in two distinct models. The first a model of RNA editing which shows that environmental factors can control genetic translation ontogenetically. The second an indirect encoding scheme based on fuzzy logic designed to attain important information compression of genetic descriptions, which is validated in the evolution of neural networks and cellular automata. Both of these models show how the specific materiality of evolutionary systems, or embodiment, both constrains and enables emergent, evolutionary, classification, which is the thrust of evolutionary constructivism.

The general layout of the dissertation is organized according to figure 1, where chapter 2 refers to the philosophical discussion of evolutionary constructivism and selected self-organization, chapters 3 and 4 refer to the mathematical discussion of evidence sets and contextual genetic algorithms, chapter 5 refers to the computational models developed, and chapter 6 refers to the final discussion of all the issues discussed before. The following table condenses the organization of the present work.

Topics by Chapter
Chapter 2	Selected Self-Organization and Evolutionary Constructivism	Biological and Cognitive Systems Require Both Self-Organization and Symbolic Representation.
Chapter 3	Evidence Sets and Cognitive Categorization	The ideas of chapter 2 are explored mathematically to deal with the modeling of cognitive categories, which are defined as temporary, subjective constructions grounded in several contexts. Evidence Sets are extensions of Fuzzy Sets defined to better simulate cognitive categories within a logic of belief that captures conveniently all forms of uncertainty recognized
Chapter 4	Contextual Genetic Algorithms	The ideas of chapter 2 are explored formally to deal with the modeling of Natural Selection seen as a process that is both dynamic (material) and symbolic (representational)
Chapter 5	Computer Applications	Practical results are obtained by using the concepts of chapters 3 and 4 to relational databases and evolutionary computation algorithms
Chapter 6	Embodied, Evolving Semiosis: Discussion	The results from chapter 5 are discussed by emphasizing the shortcomings of purely computational models of the ideas defended in chapter 2

Application Areas

The problem areas discussed in this dissertation pertain broadly to the areas of cognitive science, evolutionary systems, and information technology. In particular, to fuzzy logic and evidence theory, as well as evolutionary and adaptive computation and self-organizing systems. The mathematical structures developed have applications to artificial intelligence, reliable computation, relational databases, artificial life, and modeling and simulation. The computational models created have implications for Data Mining, Fuzzy Logic, Genetic Algorithms, Neural Networks, and Cellular Automata.

CHAPTER 2

SELECTED SELF-ORGANIZATION AND EVOLUTIONARY CONSTRUCTIVISM

1. Selected Self-Organization⁽²⁾

1.1 Self-Organization

Self-organization is seen as the process by which systems of many components tend to reach a particular state, a set of cycling states, or a small volume of their state space, with no external interference. All the mechanisms dictating its behavior are internal to the system: self-organization as opposed to externally imposed organization. Thus, it is reasonable to further demand that for a system to observe self-organizing behavior, its order cannot be imposed by special initial conditions, which would amount to a special creation. Therefore, to guarantee that a system is self-organizing, we start it with random initial conditions and see if it attains the desired order, or attractor behavior.

Thus, self-organizing behavior is the spontaneous formation of well organized structures, patterns, or behaviors, from random initial conditions. The systems used to study this behavior computationally are referred to as dynamical systems or state-determined systems, since their current state depends only on their previous state. They possess a large number of elements or variables, and thus high-dimensional state spaces. However, when started with some initial conditions they tend to converge to small areas of this space (attractor basins) which can be interpreted as a form of self-organization. Examples of computational dynamical systems are boolean networks and cellular automata. Since such formal dynamical systems are usually used to model real dynamical systems such as chemical networks of reactions, non-equilibrium thermodynamic behavior [Nicolis and Prigogine, 1977], or even mineral osmotic growths [Leduc, 1911; Zeleny, Klir, and Hufford, 1989], the conclusion is that in nature, there is a tendency for spontaneous self-organization which is therefore universal [Kauffman, 1993].

The existence of attractors is identified with the dissipation of some form of energy, therefore, self-organizing structures can only be maintained by a constant flux of energy through them, and are therefore not in equilibrium. These attractors may be chaotic in which case the emergent behavior becomes too disorganized to grasp (disorganized complexity). The behavior of interest is often found in the transition between order and chaos -- edge of chaos-- and classified as a kind of organized complexity [Weaver, 1948; Langton, 1990]. This behavior -- many parts working together to achieve some order -- is also known as synergetics [Haken, 1977].

1.2 Emergent Classification and Constructivism

1.2.1 Cybernetics and Eigenbehavior

The cybernetician Heinz von Foerster [1981] equated the ability of a self-organizing system to classify its environment with the notion of eigenbehavior. He postulated the existence of some stable structures (eigenvalues) which are maintained in the operations of an organization's dynamics [Rocha, 1994b, 1995b, 1996a]. Following Piaget, he observed that any specific instance of observation of such an organization, will still be the result of an indefinite succession of cognitive/sensory-motor operations [von Foerster, 1977]. This reiterated the constructivist position that observables do not refer directly to real world objects, but are instead the result of a cascade of cognitive and sensory-motor operations in some environment/subject coupling. "Eigenvalues represent the externally observable manifestations of the (introspectively accessible) cognitive [operations]". [von Foerster, 1977, page 278, italics added]. Further, "Ontologically, Eigenvalues and objects, and likewise, ontogenetically, stable behavior and the manifestation of a subject's 'grasp' of an object cannot be distinguished." [von Foerster, 1977, page 280]. Eigenbehavior is thus used to define the behavior of self-organizing, cognitive systems, which through the closure of the sensory-motor interactions in their nervous systems, give rise to perceptual regularities as objects [Varela, 1979, chapter 13].

Notice that eigenvalues are specific to the particular cognitive operations and how they recognize observables, that is, to the system's structure and the corresponding dynamics⁽³⁾. Any system, cognitive or biological, which is able to relate internally, self-organized, stable structures (eigenvalues) to constant aspects of its own interaction with an environment can be said to observe eigenbehavior. Such systems are defined as organizationally closed because their stable internal states can only be defined in terms of the overall dynamic structure that supports them. Organizationally closed systems are also informationally open [Pask, 1992], since they have the ability to classify their constructed environment in what might be referred to as emergent representation

1.2.2 Complexity Theory, Emergent Representation, and Emergent Morphology

It is perhaps easier to think about these concepts in the modern terminology of dynamical systems and complexity theory. The coupling of many simple elements into a network allows the establishment of highly recursive dynamical systems which can observe a wide range of attractor behaviors. Kauffman [1993], for instance, has studied in detail the workings of random boolean networks and their attractor behavior ranges, showing that boolean networks can be made equivalent to most other computational models of self-organization such as cellular automata.

An eigenvalue of an organizationally closed system can be seen as an attractor of a self-organizing dynamical system. The global "cooperation" of the elements of a dynamical system which spontaneously emerges when an attractor state is reached is understood as self-organization [von Foerster, 1960; von Foerster and Zopf, 1962; Ashby, 1962; Haken, 1977; Prigogine, 1985; Forrest, 1991; Varela, Thompson and Rosch, 1991; Kauffman, 1993]. The attractor behavior of any dynamical system is dependent on the structural operations of the latter, e.g. the set of boolean functions and connections in a boolean network. Speaking of an attractor makes sense only in relation to its dynamical system, likewise, the attractor landscape defines its corresponding dynamical system. Furthermore, attractor values can be used to refer to observables accessible to the self-organizing system in its environment, and thus perform environmental classifications (e.g. classifying neural networks). This classification capacity was identified in the cybernetic terminology as eigenbehavior. It is also the crux of the constructivist position [Glanville, 1981]. Not all possible distinctions in some environment can be "grasped" by the self-organizing system: it can only classify those aspects of its environment/sensory-motor/cognitive interaction which result in the maintenance of some internally stable state or attractor (eigenvalue). In other words, not everything "out there" is accessible; only those things that a particular physiology can construct with the stabilities of its own dynamics are.

A classifying self-organizing system is autonomous if all structural processes that establish and sustain its dynamics are internally produced and re-produced over and over again. Autonomy was previously referred to as organizational closure. A computational neural network by itself can classify an environment, but the processes (e.g. a backpropagation algorithm) that make it improve its classifying ability are external to the network. In this sense, the network itself is not autonomous, though the network together with the algorithm that changes its structure may be argued to be. It is precisely the ability of an autonomous system to change its structure in order to better classify a changing environment that defines emergent representation. For a classifying self-organizing system to change its classification ability, structural changes must be performed to alter its attractor landscape (this point is developed ahead). When the structure responsible for a given dynamics is changed, we obtain a new environmental classification (e.g. weight changes in a neural network).

Similarly, living organisms in order to adapt to their environment must be able to change the structure that establishes their own dynamic morphology. It is indeed a similar problem if we regard evolution as a search through a space of possible morphologies. In this case, living organisms must come up with mechanisms for evolving appropriate morphologies for a given environment: emergent morphology. This can be seen as the problem of classification of a morphological space given a certain changing environment, as much as emergent representation is a problem of classification of a space of cognitive representations given a certain changing environment. Natural selection is the living organism's method of structural (genetic) perturbation of self-organizing networks of components. Computational models of this emergent morphology are often based on boolean networks standing for genetic regulatory networks [Kauffmann, 1993], which can be coupled to genetic algorithms [Dellaert and Beer, 1994; Packard, 1988]. In these models, the structure of the boolean network (connections, functions and so on) is changed by the genetic algorithm, leading to different dynamic behavior which in turn stands for different morphologies, appropriate to a problem specified by the genetic algorithm's fitness function. These morphologies self-organize from and are emergent to the boolean network's dynamics, and can be regarded as the classification of an appropriate dynamic configuration for the given selective pressures.

The process of obtaining novel classifications of an environment, by an autonomous self-organizing system, can be referred to as emergent classification. Emergent because it is the result of the local interaction of the basic components of the self-organizing system and not from a global controller. This bottom-up definition of emergence [Langton, 1989] is generally accepted in artificial life and connectionist artificial intelligence as the guiding conceptual framework of models of life and cognition. In the following, I will refer to systems that are capable of emergent classification as complex systems. In section 1.3 I attempt to better specify the concept of emergence.

1.2.3 Self-Organization and Constructivism

Let me now make the connections between the terminologies of second-order cybernetics and complexity theory regarding self-organizing systems explicit by presenting figure 1. This relationship may be taken in some quarters as commonsensical, since most of the cybernetic principles of self-organization as defined by von Foerster and other participants of his program of research at the Biological Computer Laboratory in Urbana, Illinois in the 1960's and 1970's, were proposed within larger philosophical frameworks. In any case, the empirical basis for those theories depends on material and computational systems with the self-organizing characteristics outlined above. It is this empirical foundation of self-organization that I am exploring here, and not the related higher level interpretations of eigenbehavior. The single philosophical issue that I intend to pursue is that of the dependence of an autonomous system's environmental classification on its own dynamics, usually referred to as constructivism.

Autonomous systems must construct their reality by using stable structures internally available. Objects are constructed by peculiarities of cognitive operators (the maintenance of stable structures) and are not accessible through a direct representation of real world categories. Constructivism, the philosophical cornerstone of second-order cybernetics, does not merely entail the idea that objects are not accessible but that objects are constructed by cognition and constitute its basic building blocks. Today, most of us agree one way or another with this principle which shall be discussed in more detail in section 2 of this chapter in the context of cognitive science. However, what must still be addressed is how do these stable eigenvalues become eigenbehaviors, in other words, what is the nature of the structural coupling (to use the autopoietic terminology [Maturana and Varela, 1987]) between an autonomous, self-organizing system, and its environment? How do the internally constructed eigenvalues refer to aspects of the environment? How can we increase the variety of eigenbehavior? Can this variety be open-ended?

1.3 Emergence and Levels of Description

There are three levels that need to be addressed when dealing with the notion of emergent phenomena in self-organizing systems, in particular, of emergent classification. First, there is the material, dynamical, substrate, which will be the causal basis for all other levels that we may further distinguish⁽⁴⁾. Second, we have the attractor behavior of this dynamics. Finally, we have the (possible) utilization of the set of attractors as referents for some aspects of the interaction of the dynamical system itself with its environment (e.g. the pattern recogntion abilities of neural networks).

1.3.1 Explanatory Emergence

Robert Rosen's concept of emergence defines it as the deviation of the behavior of a natural system from a model of it [Rosen, 1985, 1991, 1995]. Peter Cariani [1989] has developed this notion and renamed it emergence relative to a model.

"Emergence relative to a model, then is the result of the finite and hence incomplete character of all models of the world. At some point in time we can, if we are fortunate, construct a model which will deterministically capture the behavior of the physical system. The behavior predicted by the model will, for some period of time, correspond to the observed behavior of the physical system, because it was constructed to do so. But eventually, if one waits long enough, all physical systems will diverge from their models, but some will diverge before others. Physical systems can thus be sorted out according to whether they will exhibit emergence over some finite observational period." [Cariani, 1989, page 164]

I prefer to see emergence relative to a model as an observer's switching between different models offering different modes of explanation, rather than a temporal mismatch (and thus increasing lack of explanatory power) between a model and the observed phenomena. As Howard Pattee [1978] has pointed out, due to the subject-object or observer-system dichotomy, a given observed phenomenon possesses several modes of description, none of which exhibits full explanatory power. In other words, models of physical phenonoma explain only certain aspects of them, and to increase our understanding of the world we need complementary, at times irreducible, modes of description [Pattee, 1978].

Returning to the issue of self-organizing systems and emergence, we observe that the level of attractor behavior is emergent to the dynamics because it cannot be explained solely by a description of the latter. Stability of dynamical states is not expressed in the language of the interactions between the components of a dynamical system. At this lower level, there is no distinction between a stable and an unstable state, between attractor and transient states. For instance, the transition rules of Conway's game of Life cannot describe what "blinkers" and "gliders" are. Likewise, when the attractor landscape is utilized to classify an environment, a new level is created to define the representations necessary for this classifying function: a semantic relation is created. This self-organizing classification is emergent to the attractor landscape level since the latter can only describe stabilities of the dynamics and not any "standing for" relation with the environment. To continue with the previous example, the level of attractor behavior descibes what a glider or a "glider gun" is in the Game of Life, however it cannot describe streams of gliders as information carriers in a universal computer built out of Life patterns [Poundstone, 1987]. The utilization of a glider as a bit of information requires a semantic relation imposed on the level of attractors.

1.3.2 Semantic Emergence

"We must distinguish the syntactical emergence of symmetry-breaking and chaotic dynamics from the semantic emergence of non-dynamical systems which stand for a referent." [Pattee, 1989, pp. 72-73]

No physical or formal description of the dynamical system and its attractors alone will completely explain the "standing-for", or semantic, dimension [Pattee, 1995a]. In figure 2, this third semantic level is depicted by a triangle whose left corner stands for a dynamic attractor, the right corner represents the world "out there", and the top corner represents the system of representation (denoted by a question mark) by virtue of which an internal attractor can be related to its environment. It is also a system of reference, as the representational link between dynamic attractors and an environment is established in reference to a third component. This system defines a cut between what is internal and external [Medina-Martins and Rocha, 1992] to the system, as Pattee [1995b] (following von Neumann [1966]) puts it, between the "knower" and the "known", that is, it defines an epistemic cut. We have then environmental events and a system's representation of those, by virtue of some representational relation. This triadic relationship is often equated in terms of Peircian semiotics [Salthe, 1995], and shall be explored in section 1.7.

The emergence of level 2 (attractor behavior) from level 1 (dynamics) and of level 3 (classification) from level 2 is based on explanatory emergence defined above as the existence of complementary modes of description. However, the emergence of classification from attractor behavior introduces a more specific form of semantic emergence as it establishes a representational relation between the classifying system and its environment. In the following, I shall argue that this emergent representation does not imply a commitment to open-ended representationalism, where symbols are free to represent everything in the environment of the classifying system. Rather, it implies an evolutionarily grounded constructivist stance.

The hierarchy of modes of description discussed in this section is very dear to systems-theoretic approaches to complex systems [Wuketits, 1990]. It requires a broader view of causality. As discussed before, I maintain that classification is materially caused by the attractor behavior of a particular dynamical system. The emergence of the third level of classification, which can also be referred to as a functional level, is often shown to require a more Aristotelian view of causation where final cause is interpreted as functional or intentional cause [Minch, 1995; Salthe, 1995; Rosen, 1991]. Also, if classifying systems are autonomous, then they change their own dynamical structure in order to accommodate different classification abilities (as it will be explored in detail next). In a sense, we have then a closure of cause and effect. For this reason, some have defended that complex systems require a sort of network or feedback causality [Riedl, 1977, 1984, Wuketis, 1990]. At least, a distinction between functional/informational and dynamical causal systems descriptions must be made [Hooker, 1995]. This is precisely the goal of Pattee's epistemic cut and semantic emergence concepts. Recently, Clark [1996] has similarly defended the necessity of complementary models of description in artificial life and artificial intelligence which succumb to neither a pure dynamical systems, self-organizing, vocabulary nor a pure functional, homuncular⁽⁵⁾, description of classifying systems. It is precisely the necessity of emergence, or different levels of description, that makes systems with emergent classification complex.

1.4 Memory and Selected Self-Organization

"What do complex systems have to be so that they can know their worlds? By 'know' I don't mean to imply consciousness; but a complex system like E. Coli bacterium clearly knows its world. It exchanges molecular variables with its world, and swims upstream in a glucose gradient. In some sense, it has a representation of that world." [Kauffman, 1995, page 336]

"Metaphorically, life is matter with meaning. Less metaphorically, organisms are material structures with memory by virtue of which they construct, control, and adapt to their environment." [Pattee, 1995b, page 24]

Self-organizing systems such as neural networks clearly have the ability to discriminate inputs. Generally, the attractors of their dynamics are used to represent events in their environments: depending on inputs, the network will converge to different attractors. If this ability to classify an environment is implemented by the self-organizing system itself, then we can say that it is an autonomous (classifying) system. As previously stressed, not all possible distinctions in some environment can be "grasped" by the autonomous system: it can only classify those aspects of its environment/sensory-motor interaction which result in the maintenance of some internally stable state (attractor). Another way of looking at this is to say that autonomous systems do not represent their environment, they construct it. Autonomous classification is not open-ended but dependent on a system's dynamics.

1.4.1 Variety of Classification and the Edge of Chaos

Self-organizing approaches to life (biological or cognitive), in particular second-order cybernetics [Pask, 1992], take chaotic attractors as the mechanism which will be able to increase the variety (physiological or conceptual) of self-organizing, classifying, systems. External random perturbations will lead to internal chaotic state changes; the richness of strange attractors is converted to a wide variety of discriminative power. However, for any classification to have survival value, it must relate its own constructed states (attractors) to relevant events in its environment, thus, similar events in the world should correspond to the same attractor basin. Chaotic systems clearly do not have this property due to their sensitivity to initial conditions. Ordered systems follow this basic heuristic. If on the "edge of chaos" Langton [1990], ordered systems may in addition allow for higher information exchange and perhaps more 'clever' (evolvable) categorization mechanisms.

"Organisms and other entities which interact with their worlds are likely to couple to those worlds in such a way that smooth classification occurs, and the world is seen as relatively stable. Then the 'knower' should not be chaotic, nor should its classification, the 'known', be. It is a reasonable guess that both the knowing system and the known world are in the [ordered] regime, perhaps near the edge of chaos. [Kauffman, 1993, page 234]"

Kauffman [1993, page 232] further hypothesizes that "living systems exist in the [ordered] regime near the edge of chaos, and natural selection achieves and sustains such a poised state". This hypothesis is based on Packard's [1988] work showing that when natural selection algorithms are applied to dynamic systems such as boolean networks, with the goal of achieving higher discriminative power⁽⁶⁾, the parameters are changed generally to lead these systems into this transitional area between order and chaos. This idea is very intuitive, since chaotic dynamical systems are too sensitive to parameter changes, that is, a single mutation leads the system into another completely different behavior (sensitive to damage). By contrast, ordered systems are more resilient to damage, and a small parameter change will usually result in a small behavior change which is ideal for smooth adaptation (hill-climbing) in correlated fitness landscapes. However, even though very ordered systems can adapt by accumulation of useful successful variations (because damage does not propagate widely), they may not be able 'step out' of certain areas of their fitness landscapes. It is here that systems at the edge of chaos enter the scene, they are not as sensitive to damage as chaotic systems, but still they are more sensitive than fully ordered systems. Thus, some mutations will accumulate (by causing minor changes) and some others will cause major changes in the dynamics allowing more distant searches in fitness spaces. Simultaneous mutation buffering (to small changes) and dramatic alteration of behavior (in response to larger changes) has been shown to be ideal for evolvability [Conrad, 1983, 1990].

1.4.2. Structural Change and Emergent Classification

Chaotic classifications cannot grasp an ordered interaction with an environment, while point attractors and simple limit cycles may not allow enough behavior change for a good increase in variety. The edge of chaos regime seems to offer a good, intuitive, compromise. However, whatever the regime of a dynamic system, self-organization alone cannot escape its own attractor behavior. A given dynamic system is always bound to the complexity its attractor landscape allows. Even a strange attractor, though undoubtably endowed with a much richer variety of behavior than limit cycles or point attractors, is restricted to a very small volume of the state space of the respective dynamic system. If the classification variety of the self-organizing system is restricted to such small volumes, then the ability to classify a changing environment is severely constrained, indeed, it is minimal.

For a dynamic system to observe genuine emergence of new classifications, that is, to be able to accumulate useful variations, it must change its structure. Creativity, or open-ended variety can only be attained by structural perturbation of a dynamical system. One way or another, this structural change leading to efficient classification (not just random change), has only been achieved through some external influence on the self-organizing system. Artificial neural networks discriminate by changing the structure of their connections through an external learning procedure. Evolutionary strategies rely on internal random variation which must ultimately be externally selected. In other words, the self-organizing system must be structurally coupled [Maturana and Varela, 1987] to some external system which acts on structural changes of the first and induces some form of explicit or implicit selection of its dynamic representations: selected self-organization.

Explicit control of a classifying system's structure would amount to the choice of a particular dynamics for a certain task and can be referred to as learning⁽⁷⁾. Under implicit control, the self-organizing system is subjected to some variation of its structure which may or may not be good enough to perform our task. Those self-organizing systems which are able to perform the task are thus externally selected by the environment to which they are structurally coupled. If reproduction is added to the list of tasks these systems can produce based on their dynamic memories, then we have the ingredients for natural selection: heritable variation and selection.

1.4.3 Distributed Memory

The dynamical approach of von Foerster [1965] to cognition emphasized the concept of memory without a record. By utilizing functionals to change the functions of state-determined systems, von Foerster formalized the idea that memory can be observed in systems which are able to change their own structure and therefore its dynamics and attractor behavior. Today, we name this kind of memory distributed, and refer to the kind of models of memory so attained as connectionist. The categories a distributed memory system classifies are not stored in any particular location, they are nowhere to be found since they are distributed over the entire dynamics established by some network of processes [van Gelder, 1991]. They exist however in the form of attractors which are nonetheless discrete at a higher level of description. Categories are not stored in any particular location of the network, but are identified with particular dynamic attractors, for which we need a new, emergent, level of description. Since classified categories are lumped into the attractor landscape of a dynamical system of many components, they are not merely distributed in the sense of being extended over a number of components, they are in fact superposed in the network of component relationships [van Gelder, 1991]. It is precisely because of this superposition that a new level of description is required, since mere knowledge of component interactions cannot describe the classified categories of a connectionist system. Clark [1993], has discussed in detail how connectionism changed our understanding of cognitive categorization processes. More about cognitive categorization in section 2 of this chapter and chapter 3.

Now, for a self-organizing system to be informationally open, that is, for it to observe emergent classification of its own interaction with an environment, it must be able to change its structure, and subsequently its attractor basins, explicitly or implicitly. Whatever the form of selection, this kind of self-organization must be able to classify its interaction with an environment by utilizing its own distributed memory. For selection to occur we must have some internal vehicle for classification -- there must be different alternatives. The attractor landscape, or eigenvalues, offer these vehicles. However, and this is an important point, selection is ultimately not performed on the memory vehicles themselves, but on what they stand for, not on eigenvalues but on eigenbehavior. It is not the pattern of activation of a boolean network which is selected, but its ability to perform a particular task with repercussions on its environment. In other words, it is not the memory which is selected, but the particular repercussions it will lead the self-organizing system to perform in its environment. In terms of the hierarchy of emergence outlined previously, selection takes place on the representational (informational/functional) level (level 3 in figure 2) -- a selection of semantics.

This form of self-organization can be referred to as distributed memory selected self-organization. Its relying on some system-environment coupling of structure has been stressed most notably within second-order cybernetics and systems research. Maturana and Varela [1987] propose structural coupling as the general mechanism for variety increase, Pask [1976] refers to it as conversation in the cognitive realm. Both of these approaches owe a lot to von Foerster's eigenbehavior notions. More recently, in the realm of complex systems and evolutionary systems theory, Kauffman [1993] and others have relied on the notion of autocatalytic sets which are (structurally) mutable, self-replicating, self-organizing systems with distributed memory, evolvable through natural selection. What is yet to be discussed is the potential of this kind of self-organization for efficient, open-ended variety.

1.4.4 Embodiment

So far I have maintained that eigenvalues or attractors represent the building blocks of any system capable of discriminating its environment through some thus embodied construction. However, eigenbehavior (emergent classification) and its variety increase needs a structural coupling of these eigenvalues with some externally selective environment. This kind of selected self-organization obliges us "to understand perception not just as an interactive dynamical structure, but as a process that arises from a more fundamental embodiment that makes it possible for evolution to create structures that are internally assigned interactive roles." [Etxeberria, 1995].

Perhaps the most important characteristic of this distributed memory selected self-organization is the fact that its specific material dynamics both constructs the classification of the environment and ultimately defines selection. That is, distributed memory cannot classify everything, only those aspects of the environment that create internal stabilities. Also, selection eventually acts on the functional characteristics of the dynamics (desired for some task) and not on memory itself. The consequence of this fact for biological systems is that natural selection (acting on this form of self-organization) is not free to evolve any organism, but it is constrained by the dynamic properties of the materiality of the organisms it acts upon -- evolution with both a self-organizing and selection component. The consequence for cognitive systems, is that what can be classified is also constrained by the particular materiality of the classifying system at stake -- not everything "out there" can be grasped. In other words, the particular self-organizing dynamics of a particular classifying system constrains the universe of its classification. However, we should look into how this process can be made more efficient, and allow for genuine open-ended emergence of variety in classification.

1.5 Descriptions and Symbols

1.5.1 Von Neumann and Description-Based Selection

Von Neumann [1966] defended the idea that a threshold of complexity exists, before which complexity degenerates, and after which complexity can increase in an open-ended fashion. He proposed a self-replicating scheme based on the notion of a memory-stored description (A) that can be interpreted by a universal constructor A to produce A itself. However, to avoid a logical paradox of self-reference, the description, which cannot describe itself, must be both copied (uninterpreted role) and translated (interpreted role ) into the described automaton. This way, in addition to the universal constructor, an automaton B capable of copying any description, , is included in the self-replication scheme. A third automaton C is also included to effect all the necessary manipulation of descriptions. To sum it up, the self-replicating system contains the set of automata (A + B + C) and a description (A + B + C); the description is fed to B which copies it and to A which constructs another automaton (A + B + C); the copy is then handled separately to the new automaton which together with this description is also able to self-reproduce (figure 3).

As Von Neumann [1966] discussed, if the description of the self-reproducing automata is changed (mutated), in a way so as to not affect the basic functioning of (A + B + C) then, the new automaton (A + B + C) will be slightly different from its parent. Von Neumann used a new automaton D to be included in the self-replicating organism, whose function does not disturb the basic performance of (A + B + C); if there is a mutation in the D part of the description, say D, then the system (A + B + C + D) + (A + B + C + D) will produce (A + B + C + D) + (A + B + C + D). Von Neumann [1966, page 86] further proposed that non-trivial self-reproduction should include this "ability to undergo inheritable mutations as well as the ability to make another organism like the original", to distinguish it from "naive" template-based self-reproduction like growing crystals. Notice that changes in (A + B + C + D) are not heritable, only changes in the description, (A + B + C + D) are inherited by the automaton's offspring and are thus relevant for evolution. This ability to transmit mutations through descriptions cast in separate memories is precisely at the core of the principle of natural selection of modern Darwinism. Through variation (mutation) of memories, populations of different organisms are produced; the statistical bias these mutations impose on reproduction rates of organisms will create survival differentials (fitness) on the population which define natural selection. In principle, if the language of description is rich enough, an endless variety of organisms can be evolved. This is what open-ended emergent evolution means. This point needs to be further elaborated.

1.5.2 Descriptions require a Symbol System

Von Neumann's model clearly does not rely on a distributed but on a local kind of memory. Descriptions entail a symbol system on which construction commands are cast. These commands are not distributed (superposed) over patterns of activation of the components of a dynamic system, but instead localized on "inert" structures which can be used at any time -- a sort of random access memory. By "inert" I mean material structures with many dynamically equivalent states, in other words, the semantic relation, or what the structures are used to refer to, must possess a large degree of arbitrariness so that certain representations are not much more probable than others. In the genetic system, most any sequence of nucleotides is possible, and its informational value is almost completely independent of the particular dynamic behavior of DNA or RNA.

Notice that according to Von Neumann's own formulation, a symbol system utilized for the construction of self-reproducing systems is not an isolated artifact. Rather, in the context of construction, a symbol system entails a set of available parts. That is, construction blueprints are cast on a symbol system whose primitives are a finite set of parts. In the case of self-reproducing automata, these parts are "and", "or" and other logical operators, and in the case of the genetic code the parts are the set of aminoacids (the symbols are codons or sets of 3 nucleotides). It is in this sense that open-ended evolution must be understood. A given material symbol system cannot represent everything, only what its primitive parts can construct. Natural selection is open-ended for any form that can be constructed through folding aminoacid chains.

1.5.3 Parts, Symbols, and Embodiment

This parts problem can be rephrased as one of the aspects of embodiment. A particular materiality is tied to specific construction building blocks. The richer the parts, the smaller the required descriptions, but also the smaller the number of classifiable categories or constructed morphologies. For instance, Von Neumann used simple building blocks such as "and" and "or" gates to build his automaton, which in turn required a 29 state cellular automata lattice and very complicated descriptions. Arbib[1966, 1967] was able to simplify von Neumann's model greatly by utilizing more complicated logical building blocks. Likewise, the genetic system does not need to describe all the chemical/dynamical characteristics of a "desired" protein, it merely needs to specify an aminoacid chain which will itself self-organize (fold) into a functional configuration with some reactive properties. In other words, a given materiality, that is, a given set of parts such as amino acids, provides intrinsic dynamic richness which does not have to be specified by the symbol system on which construction commands are cast [Moreno, et al, 1994] making descriptions much smaller. Embodiment provides this kind of material information compression. The other side of Embodiment, is that it also constrains the universe of possible constructions (universe of open-endedness). Living organisms are morphologically restricted to those forms that can be made out of aminiacid chains through the genetic code, while in principle, a formal symbol system, stripped as it is from any materiality, can describe anything whatsoever. Of course, this 'in principle' is seriously, and easily, constrained by computational limits, as formal descriptions are much larger than material ones. A complete formal description of a protein would have to include all of its physical characteristics from the atomic to the chemical level, while a gene needs only a description of an aminoacid sequence. In chapter 5 I discuss how to incorporate the notion of embodiment in computational models, in order to obtain some form of descriptional information compression.

1.5.4 The Symbolic Advantage

Why then is there an advantage of local memory over distributed memory self-replication? Von Neumann's argument maintains that if we do not have symbolic descriptions directing self-replication, then an organism must replicate through material self-inspection of its parts. In other words, the dynamics must be able to produce copies of itself by template identification of parts existing in its environment. The simplest way would be to have every part of the structure individually heritable. Clearly, as systems grow in complexity, self-inspection becomes more and more difficult [Pattee, 1995a]. The existence of a language, a symbol system, allows a much more sophisticated form of communication. Functional, dynamic structures do not need to replicate themselves, they are simply constructed from physically non-functional (dynamically inert) descriptions. For instance, for an enzyme to replicate itself, it would need to have this intrinsic property of self-replication "by default", or it would have to be able to assemble itself from a pool of existing parts. But for this, it would have to "unfold" so that its internal parts could be reconstituted for the copy to be produced [Pattee, 1995a]. With the genetic code, however, none of these complicated "gimmicks" are necessary: functional molecules can be simply folded from inert messages. This method is by far more general since any functional molecule can be produced from a description, not merely those that either happen to be able to self-reproduce, or those that can unfold and fold at will to be reproduced from available parts. The evolution of distributed memory based self-organizing systems is restricted to this type of trivial (in von Neumann's sense) or through self-inspection reproduction [Kampis, 1991].

The symbol system, with its utilization of inert structures, opens up a whole new universe of functionality which is not available for purely dynamical self-replication. In this sense, it can evolve functions in an open-ended fashion. We can refer to this mechanism as description based evolution. It is the foundation of the neo-Darwinist position and of all genetic based schemes found in evolutionary computation. Its power is obviously immense. It is however at odds with the notions of self-organization depicted previously. For the purely formal von Neumann scheme, all constructions are possible, that is, in principle, there is nothing a formal symbol system cannot describe in a given set of primitive parts. All classifications, all functions, all morphologies can be attained from a finite set of parts by such a mechanism: open-endedness. In contrast, self-organization tells us that a given autonomous system will be able to classify or morphologically achieve only a (small) subset of all possible system/environment configurations; precisely those for which it can construct dynamic stabilities.

It can always be argued that the random access memory the genetic system establishes, is nothing but complicated dynamics, and the symbolic dimension is just the result of our subjective observation. In other words, again the distinction between the levels of attractor behavior and semantic emergence discussed earlier. But why stop there? The same argument may be applied to the dynamic level itself, since it too is constructed by our subjective observations. The genetic dimension has established a new hierarchical level in evolutionary systems [Laszlo, 1987] which allows a greater level of control of the purely self-organizing dynamics. Failing to recognize this emergent symbolic level, does not allow the distinction between self-organizing systems such as autocatalytic networks [Kauffman, 1993], from living systems whose genetic memory does not require larger and larger autocatalytic networks to develop more and more complicated morphologies. Distributed memory self-organization requires more and more complicated gimmicks to increase the complexity of its organization. There is inherited memory, but it is severely constrained as discussed above.

In evolutionary systems this is at the core of the feud between those who claim that natural selection is the sole explanation for evolution and those who stress that other aspects of evolutionary systems, such as developmental constraints, also play an important role. It is no wonder then that the first group stresses the symbolic description, the gene, as the sole driving force of evolution [Dawkins 1976, Dennett, 1995]. While the second group likes to think of the propensities of matter or historical contingencies as being of at least equal importance in evolution [Gould, 1989, Salthe 1985, 1993, Kauffman 1993]. In pragmatic terms, however, most evolutionary theorists, one way or another, will ackowledge that all these factors play important roles [Eldridge, 1995]. Then, is there some conceptual mechanism that will welcome inclusive approaches to evolutionary systems with both description based selection and self-organizing dimensions? Yes, Pattee's [1982, 1995a] semantic closure principle offers such a conceptual avenue. Also, and as we shall see later in chapter 5, in the field of Artificial Life models have been built that incorporate these views with no big fuss.

1.6 Semantic Closure and Open-Endedness

"The symbol vehicle is only a small material structure in a large self-referent organization, but the symbol function is the essential part of the organization's survival and evolution. This autonomous structure-function self-referent organization is what is entailed by my term semantic closure" [Pattee, 1995a, page 14]

The notion of description implies a self-referential linguistic mechanism. A description must be cast on some symbol system while it must also be implemented on some physical structure. Since many realizations of the same symbol system are possible, viewing descriptions only as physical systems explains nothing about their symbolic nature in the control of construction. When Von Neumann's universal constructor A interprets a description to construct some automaton, a semantic code is utilized to map instructions into physical actions to be performed. When the copier B copies a description, only its syntactic aspects are replicated. Now, the language of this semantic code presupposes a set of material primitives (e.g. parts and processes) for which the instructions are said to "stand for". In other words, descriptions are not universal as they refer to some material constituents which cannot be changed without altering the significance of the descriptions. We can see that a self-reproducing organism following this scheme is an entanglement of symbolic controls and material constraints which is closed on its semantics, inasmuch as the semantic code it utilizes is defined by the system itself and not from outside, that is, it relies on autonomous coding. Howard Pattee [1982, 1995a] calls such a principle of self-organization semantic closure.

A given semantically closed system is based on some sort of coding mechanism between inert and functional structures. However, the code and the associated construction are built on some material substrate constraining the whole semantic closure. I can think of two aspects related to this material dependence that are important: the finite number of available parts, and the dynamic, self-organizing, nature of the coded processes.

1.6.1 Finite Symbol-Part System

The symbolic code is defined by a small, finite, number of symbols (e.g. codons in DNA), which can encode a finite number of primitive parts (e.g. aminoacids). Hence, there is a finite number of functional structures which may be constructed with a given set of parts. This defines the representational power of a given symbol system. In other words, the larger the number of possible equally dynamically inert structures, the larger the universe of functionality that can be represented in them. This implies that systems utilizing Von Neumann's scheme of self-replication (biological organisms in particular) cannot evolve any functional structure whatsoever, since the finite properties of a code constrains the domain of evolvable structures. Nevertheless, the number of possible functional combinations attainable even with a small set of symbols and parts (4 and 20 respectively in the DNA-protein code system⁽⁸⁾) is very large, easily beyond computational limits⁽⁹⁾. In this sense, the emergence of functionality is open-ended though not infinite and universal.

1.6.2 Dynamic Part Compounds

"Organisms have hosts of emergent characteristics. In other words, genes interact in a nonlinear way. It is the interaction that defines the organism, and if those interactions, in a technical sense, are nonadditive - that is, if you can't just say that it's this percent of this gene plus that percent of that gene - then you cannot reduce to the lower-level entities, because the nonadditive features have emerged. These features don't exist until you get into the higher level." [Gould, 1995, page 62]

More important for the constraints applied to a selection mechanism based on a Von Neumann type coding system, are the dynamic characteristics of the coded products. A symbol-part system, even with finite number of symbols and parts, is open-ended in the sense discussed above. That is, from coded messages, a trans-computational number of products can be constructed. However, since the products are dynamic and not symbolic structures, they will have different dynamic characteristics (for which they are ultimately selected). Moreover, the messages encoded stand for some arrangement of parts (strings of aminoacids, phrases in natural language) and not just the parts themselves. An arrangement of dynamic structures, however simple, tends to form a complex dynamic compound which will self-organize according to physical laws. This establishes the sort of network causality described earlier in the discussion of self-organizing systems: e.g. folding of aminoacid chains into proteins in the DNA system.

These self-organized, coded, compounds can the interact with one another in many levels of organization which establish the hierarchical nature of evolution [Pattee, 1973; Laszlo, 1987]. Gould [1995], in particular refers to this hierarchy of levels as linked through non-linear relations, meaning that through the network causation of complex dynamic systems we cannot separate individual causes at a lower level from causes at a higher level. This argument is often used to discredit the genetic reductionist stance of Dawkins [1976], as the isolation of genes coding for particular phenotypic traits becomes impossible except for the simplest of cases. Notice that nonlinear behavior is a term often used instead of emergent behavior in complex systems, it is a different way to think about the same phenomenon created by network causality. For instance, the definition of distributed memory as the existence of superposition of representations, as opposed to mere extension of representations across several components, can be rephrased by saying that distributed memory relies on nonlinear representations which are extended across several components of the memory system. If representations were linear, it would mean that, even though extended across components, the percent to which the latter would affect the former would be quantifiable.

In any case, and more relevant here, is to recognize the principle of semantic closure as comprised of symbolic messages that code for self-organizing compounds of material parts. In the computational lingo of Artificial Life, we can say that there is not a linear mapping of coded messages to functional products, rather messages encode dynamic structures which are then left to their own devices as they self-organize. I have referred to this procedure previously as emergent morphology. This concept is developed in chapters 4 and 5 in the context of artificial life and evolutionary computation

1.6.3 Development: Constraints on Evolution

The notion of emergent morphology, as implied by semantic closure, has important implications for evolutionary systems and for cognitive systems. This importance lies on the constraints imposed on the evolution of organisms by natural selection, or the environmental classification performed by cognitive systems. As discussed earlier, self-organizing systems cannot classify or construct everything, as they converge to preferred dynamic pathways defined by their attractor landscape. A given dynamic system has in general only a relatively small number of possible final configurations [Kauffman, 1993]. If complex systems are based on the multi-level hierarchies of interacting dynamic systems built out of initially coded dynamic parts discussed above, then the number of possible final configurations (constructed morphologies or constructed representations) is constrained by this whole hierarchy of dynamic network causality. In other words, not everything can be evolved, as the initial encoded arrangement of parts will have to self-organize under the complicated influence of all sorts of levels of dynamic organization.

The process of reaching a multi-level structure through the self-organization of many dynamic parts is known as development. This process of hierarchical organization has been studied extensively by many in the context of evolutionary systems [e.g. Salthe, 1993; Goodwin, 1994; Buss, 1987]. Under semantic closure, development is seen as an orchestration of dynamic material building blocks and contextual environmental factors, under the initial direction of symbolic controls indispensable for the open-endedness of the process of natural selection according to Von Neumann's model. Some aspects of the notion of development are approached computationally in chapter 5.

1.6.4 Selected Self-Organization with Local Memory

We can then think of semantic closure as a conceptual principle that includes both description based evolution and self-organization, in other words, it implies a description based harnessing of self-organizing structures: selected self-organization with local memory. Figure 4 presents a taxonomy of self-organization dependent on some kind of memory. Notice that distributed memory selected self-organization can achieve plenty of the characteristics of semantic closure I have been discussing, however, without the attributes of local memory, that is, the symbolic dimension of descriptions, we cannot achieve the sort of open-endedness discussed earlier, since construction is not arbitrarily mediated by a code system [Umerez, 1995], but dependent on only those structures that happen to be able to be communicated by template reproduction or self-inspection. This point was discussed in 1.5.

It is here that the emphasis on the symbolic level of open-ended evolutionary systems must be tamed. Strong Darwinism, has emphasized the nature of the symbolic description of living systems. However, semantic closure with its description based selected self-organization is not reiterating this position. The symbolic component of evolutionary systems is stressed, but the material, dynamic, self-organizing characteristics of matter are equally stressed. It is the ultimate inclusive approach which is neither reductionist nor dualist [Pattee, 1995a]. While it is maintained that a purely physical description of dynamics will not explain symbolic function (as several material systems may implement the same function), it is also maintained that different material structures will not have identical domains of potentially evolvable functions. The important idea is that evolution relies both on self-organization and selection, and only those self-organizing systems able to harness their dynamics to obtain a symbolic dimension can have open-ended evolutionary potential.

1.6.5 The Credit Assignment Problem

To wrap up the concept of selected self-organization let me make a summary of the points expressed earlier:

A self-organizing dynamics cannot escape its attractor behavior unless its structure is changed.
To evolve, a self-organizing dynamics needs to accumulate useful variations of structure. In other words, it needs to classify its interaction with its environement. This amounts to the construction of some sort of memory.
Dynamic systems such as boolean networks have distributed memory, which, from an evolutionary perspective, entails a selected construction, or dynamically constrained representation, of their world. Not everything can be classified, only those interactions that lead to dynamically stable behavior and survive in some environment can.
Descriptions (local memory) allow for a more effective form of self-replication based on Von Neumann's scheme.
Von Neumann's scheme of description based evolution does not include dynamics. It is a purely informational, representational, approach. Everything can be classified.
Semantic closure offers a hybrid conceptual approach with both description based (symbolic) controls, and dynamic (self-organizing) constraints. Evolution is the symbolic control or harnessing of self-organization.

Following the previous discussion of emergence, we can see that a pure representational approach, that is, Von Neumann's scheme, utilizes only the third level of description portrayed in figure 2. It disregards all sorts of dynamic constraints that a given material substrate imposes on the classifying function. It formalizes the power of natural selection, which is probably the most important engine of evolution, but it fails to recognize its material constraints which many see as an important part of the evolutionary picture [Gould, 1995]. In fact, these constraints may not just limit the scope of representation, but they may also enable important changes in evolutionary trajectories [Salthe, 1993]. Further, some propose that these dynamic constrains obey universal laws or organization [Kauffman, 1993]. These constraints exist at many levels, from the materiality of specific information carriers, to the mechanisms of symbolic expression (e.g. RNA editing, see chapter 4), to ontogenetic developmental constraints, and all the way to social constraints [Wilson and Sober, 1994].

Semantic closure calls for the so-called credit assignment problem⁽¹⁰⁾. That is, evolutionary structures are subjected to several different controls and constraints, which must be weighted according to their particular relevance in specific organizations. The problem is posed in trying to establish how much of an evolving complex system can be explained by physical laws, self-organization, development and context, historical contingency, and symbolic driven selection. The inclusive nature of semantic closure implies that models of these systems should include as most of these aspects as possible, and not be committed to one single explanatory mode.

1.7 Evolving Semiotics

"The term 'semiotic' goes back to the Greek medical tradition which considered semiotic, embracing diagnosis and prognosis by signs, as one of the three divisions of medicine. The Stoics gave semiotic the dignity of a basic division of philosophy co-ordinate with physics and ethics, and included within it logic and the theory of knowledge. The whole Hellenistic philosophy centered around the semiotic, and in particular the problem of empiricism versus metaphysics was formulated as a problem of the limits of signifying by signs, the Stoics arguing that there were signs ("indicative signs") which could give necessary knowledge about things beyond the limits of observation; the Epicureans holding that while signs gained their signification through experience, some signs (such as 'atom' and 'void') could, though only with probability, refer to what was not capable of direct observation; the Sceptics questioned the whole edifice of metaphysics on the ground that signs could refer only to that which was observable, serving to recall (as "commemorative signs") that which had been observed even though it was not at the moment of reference directly observable." [Morris, 1946, pp. 285-286]

Semiotics concerns the study of signs/symbols in three basic dimensions: syntactics (rule-based operations between signs within the sign system), semantics (relationship between signs and the world external to the sign system), and pragmatics (evaluation of the sign system regarding the goals of their users) [Morris, 1946].

"[...] pragmatics is that portion of the semiotic which deals with origin, uses, and effects of signs within the behavior in which they occur; semantics deals with the signification of signs in all modes of signifying; syntactics deals with combinations of signs without regard to their particular significations or their relation to the behavior in which they occur.

When so conceived, pragmatics, semantics, and syntactics, are all interpretable within a behaviorally oriented semiotic, syntactics studying the ways in which signs are combined, semantics studying the signification of signs, and so the interpretant behavior without which there is no signification, pragmatics studying the origin, uses, and effects of signs within the total behavior of the intepretants of signs. The difference does not lie in the presence or absence of behavior but in the sector of behavior under consideration. The full account of signs will involve all three considerations." [Morris, 1946, page 219]

The importance of this triadic relationship in any sign system has been repeatedly stressed by many in the context of biology and genetics [e.g. Waddington, 1972; Pattee, 1982, 1995a]; in particular, Peter Cariani [1987, 1995] has presented an excellent discussion of the subject. It is a particularly intuitive way of thinking about Selected Self-Organization. Indeed, the three dimensions of semiotics can be mapped to the key aspects of semantic closure. First and foremost, semiotics reminds us that the essential attribute of complex systems with emergent classification is the symbolic, that is, the existence of memory tokens that stand for dynamical configurations. The syntactic dimension can be equated with whatever type of memory tokens⁽¹¹⁾ are utilized to refer to aspects of the complex system's environment (Level 3 in figure 2). The semantic dimension refers to actual (self-organizing) dynamical configurations and their relation to the memory tokens. The pragmatics dimension refers naturally to the selection of the complex system according to its behavior in an environment. Thus, selected self-organization refers to complex systems that observe an embodied evolving semiosis with their environments, which can be open-ended if the natural symbol systems they implement are symbolic and follow von Neumann's scheme (Pattee's semantic Closure). Embodied evolving semiosis is the main concept pursued in this dissertation. It takes the form of selected self-organization in biological systems, and evolutionary constructivism in cognitive systems as discussed in the next section. The implications of its application to AI and AL, which is pursued in chapters 3, 4 and 5, is discussed in chapter 6.

2 Evolutionary Constructivism

In section 1 selected self-organization was presented mostly within the context of theoretical biology, particularly in the study of evolutionary systems. In this section, I attempt to pinpoint more explicitly what evolutionary constructivism stands for in cognitive science, by basing it on the understanding of selected self-organization developed in section 1.

2.1 Material Basis: Selected Self-Organization and Constructivism

Selected Self-Organization relies on the following concepts discussed in section 1:

Self-Organization
Embodiment (materiality, dynamics, environmental interaction)
Classifications as internal stabilities
Constrained Classification power
Hierarchical Development

Semiotic control
Contextual Level integration
Network causality
Selection

Adaptation to an environment
Pragmatics, fitness, consensus
Semantics, function

Constructivism, notably in systems research, has emphasized points 1 and 2 above. The idea that classifications are internally constructed and contextually integrated in a hierarchy of development [Piaget, 1971] is its basic starting point. Classifications are not representations of an environment, but re-presentations generated by cognitive systems in their embodied interaction with an environment [von Glasersfeld, 1995]. Re-presentations refer to the mechanisms by virtue of which a previously constructed classification is re-presented (replayed, re-constructed) from memory given some sensory interaction with the environment. This is understood precisely in the same way as connectionist machines re-create their classifications from previously learned inputs, not so much a direct link to localized memory banks containing fixed representations of the world, but rather an active, dynamic, re-construction of patterns of activation. In fact, constructivism arises hand in hand with the cybernetic fixation on the connectionist machines of McCulloch and Pitts [1943] and von Foerster [1965]. The ability to increase the variety and creation of new re-presentations relies on psychological development primordially based on physiological primitives [Piaget, 1971; Medina-Martins and Rocha, 1992], which progressively generate hierarchies of re-presentations that can be accessed by the structural coupling of cognitive systems to their environments [Maturana, 1979] or through conversations with other such systems [Pask, 1976]. In other words, cognitive systems start with a variety of sensory primitives that are defined by the systems' physiology. This specific embodiment allows a number of interactions with an environment to create internal stabilities (attractors, eigenvalues) used precisely to classify such interactions. All cognitive capabilities are developed from this ability for emergent classification or eigenbehavior, by virtue of a process of learning that works by associating new classifications with existing re-presentations.

2.1.1 Radical Constructivism

Different breeds of constructivism exist. Traditionally, it has been identified with the radical constructivist position of von Glasersfeld [1995], that many fear much more solipsist than it actually is. Mostly because of the practice of its research program (largely implemented in education science), it has left the impression that radical constructivism stands for the sort of relativism found in the deconstructionist, post-modernist, breed of humanities [Derrida, 1977]: the idea that knowledge is personally or socially constructed, with the conclusion that there is no difference between science and humanities, and we can never fully understand our environments since everything is a construction anyway. Alas, this is not the case. Even the most radical of constructivists like von Glasersfeld recognize point 3 of the chart above, that is, they recognize that a level of pragmatics exists that leads constructed re-presentations to refer to relevant events in an environment. However, they tend to either consider cognitive development as the key process to achieve this relevance of classifications, or they are simply not concerned with this aspect of cognition, preferring to work on the construction side of cognition which they believe to be much more relevant.

Radical Constructivism asserts that speaking of representations is an illusion [Von Glassersfeld, page 115, based on arguments by Bickhard and Richie, 1983] that cannot be accepted. The argument is based on the notion of representation as an information-theoretic construct. When a semantic code is established, one can only speak of representation and information transfer if not only the signifiers but also the signifieds are accessible. If one cannot explicitly access all the elements of the set of possible items that one wants to symbolize, then an information channel cannot be defined between the world of signifieds and the language of signifiers, and thus no representational relation can be established.

However, by abandoning the notion of representation as a mapping of internal structures to the world outside, constructivism locks itself inside the autonomy of complex systems it so dearly embraces and restricts cognition to internal coherence models. Psychological development is defined as the process of constructing more and more complicated re-presentations from interaction with an environment comprised of other cognitive agents. What is subsumed in development are the mechanisms of selection of re-presentations which by being selected from outside (socially or ecologically) become effective representations (categorizations) of the classifying system's environment. Constructivism has a problem with accepting explicit external selection, thus the resistance to or downplay of natural selection by the theory of autopoiesis, for instance. As soon as one accepts external, explicit, selection, one must accept a relation (or correspondence) between the world and internal re-presentations which become, effectively, representations (intentionality).

Somehow, cognitive systems construct their classifications of an environment, but misclassifications of an environment may result in ecological or social death, and thus have no survival value. An herbivore in the African savannah should not construct a lion as an edible bush. If a lion triggers such a re-presentation in the herbivore, chances are that it will not survive long. We can say in this evolutionary, pragmatic, sense, that the herbivore misrepresented its environment, an expression which radical constructivism refuses. Such a notion of representation does not have to be seen as an information-theoretic definition. The herbivore's re-presentation of lion, insofar as it allowed the herbivore to survive in the savannah, is effectively a representation of the herbivore's environment where it exists in situated interaction. Such a distinction is possible without explicit access to the environment. A representation is an experiential re-presentation with identifiable repercussions in an environment. It is a pragmatically grounded re-presentation that can be communicated (internally or externally). Evolutionary Constructivism, as developed in more detail ahead, is precisely interested in the study of how communicable (linguistic) representations can establish a more open-ended system of recontextualization of internally coherent re-presentations, that can model cognitive creativity more efficiently.

2.1.2 Physical Constructivism

Heylighen and Joslyn [1992] have proposed a breed of Constructivism named Physical Constructivism which attempts to subsume dynamic, developmental, and evolutionary constraints into a physical dimension. Physicalism tends to reduce the influence of natural selection to laws of dynamics and complexity, stripping it off its pragmatic dimension, and thus preventing any discussion of functionality and representation. If Physical Constructivism merely demands that cognition be understood in terms of the physical processes which manifest cognition, then it is a more reductionist proposal than radi