Luis Rocha's
Current Research Projects

Statement of Research Interests

Complex Adaptive Systems and Computational Intelligence

Almost all interesting processes in nature are highly cross linked. In many systems, however, we can distinguish a set of fundamental building blocks, which interact nonlinearly to form compound structures or functions with an identity that requires more explanatory devices than those used to explain the building blocks. This process of emergence of the need for new, complementary, modes of description is known as hierarchical self-organization, and systems that observe this characteristic are defined as complex . Examples of these systems are: gene networks that direct developmental processes; immune networks that preserve the identity of organisms; social insect colonies; neural, physiological, and technological networks that produce intelligence; ecological networks; social networks comprised of transportation, utilities, and telecommunication systems, as well as economies.

I am interested on basic and applied research on simulations and analysis of complex adaptive systems, as well as on the development of informatics applications to understand and control such systems. Therefore, I work in the interdisciplinary area of systems science and complex systems; more specifically, in the sub-fields of complex adaptive systems (CAS) and computational intelligence (CI). Please check the research group on Complex Adaptive Systems and Computational Intelligence (CASCI) I lead, for a more details about our research and how to collaborate and study with us.

Bioinformatics, Computational Biology and Artificial Life

There are today a number of projects aiming at the understanding how the cell regulates collections of genes. Such projects are merging biology with informatics and other areas of computational science. Techniques in information retrieval, text mining, knowledge discovery, machine learning, computational learning theory, and information management present us with the opportunity to make new discoveries in biology. In addition to the research in this area described below, I have also been involved in educational endeavors in this area. I regularly teach an introductory course in Bioinformatics at the Instituto Gulbenkian da Ciencia, Portugal, where I am also in the direction of a PhD Program in Computational Biology and the director of the FLAD Computational Biology Collaboratorium. Additionally, I have advised various graduate students in this area. Likewise, I have long been involved in Artificial Life, having, for instance, recently chaired Alife X and organizing the next ECAL 07, the leading conferences in the field. I also taught what was apparently the first course taught on Artificial Life

Bibliome Informatics: Literature Mining

Biology was until recently essentially a hypothesis driven science in which experiments were carefully designed to answer one or very few specific questions — e.g. test the function of a specific protein in a specific context. In the last decade, fueled by the widespread use of high-throughput technology, we have witnessed the emergence of a more data-driven paradigm for biological research. Since high throughput experiments are frequently conducted for the sake of discovery rather than hypothesis testing, and due to the sheer amount of measured variables they entail, it is very difficult to interpret their results. Moreover, since the goal of many experiments is to uncover bio-chemical and functional information about genes and proteins, there is an obvious need to understand the linkages amongst biological entities in literature and databases which allow us to make inferences. Literature mining [Jensen, Saric, and Bork ,2006; Shatkay and Feldman ,2003] is expected to help with those inferences; its objective is to automatically sort through huge collections of literature and suggest the most relevant pieces of information for a specific analysis task, e.g. the annotation of proteins. Another application is to uncover similarities of genes according to "publication space", or the more tongue-in-cheek term "bibliome".

Until now, literature mining has been applied essentially to help annotate and characterize molecular entities such as genes and proteins. In the next few years the field is expected to move to aid the discovery and automatic annotation of relationships among such entities, e.g. protein-protein and gene-disease interactions. Indeed, the second Biocreative competition, which we participated in ([Abi-Haidar et al,2008], [Abi-Haidar et al, 2007]), includes a series of tasks on extraction of protein-protein interaction information from the literature. As the field moves to uncovering relations rather than entities, our complex network approach to biomedical literature mining [Verspoor et al,2005], which we tried on the first BioCreative competition, makes all the more sense. Additionally, since literature mining hinges on the quality of available sources of literature as well as their linkage to other electronic sources of biological knowledge, it is particularly important to study the quality of the inferences it can provide. We have been working in the large-scale validation of bibliome algorithms [Maguitman et al,2006], with applications to proteomics [Rechtsteiner et al ,2006]. For an excellent collection of publications in the area, see the Biomedical LIterature and text Mining Publications (BLIMP), maintained by Hagit Shatkay

.

Relevant Publications and resources:

Microarray Analysis

I have been interested in clustering methods for microarray analysis which allow multiple membership of genes in clusters. In particular, with various collaborators, we became very interested in using spectral analysis methods, such as Singular Value Decomposition (SVD), very familiar from our work in computational intelligence and very appropriate, from a complex systems perspective, to uncover global patterns of gene expression. We also looked at other methods such as association rule mining, fuzzy clustering, and the general systems problem solver. We wrote a "manual" for how to use SVD and the related principal component analysis, for microarray data, which included a overview of the method and some insights about its relationship to Fourrier analysis [Wall, Rechtsteiner, and Rocha ,2003]. We also applied this method to uncover novel expression patterns in human cells subjected to Human Cytomegalovirus (Herpes) infection [Challacombe, et al,2004] in a collaboration with the life sciences division at Los Alamos and the Shenk lab at Princeton University.

Related Publications and Resources:

Models of RNA Editing

Evolutionary models in theoretical biology at large, and computational biology and artificial life in particular, rarely deal with ontogenetic, non-inherited alteration of genetic information because they are based on a direct genotype-phenotype mapping. In contrast, in Nature several processes have been discovered which alter genetic information encoded in DNA before it is translated into amino-acid chains. Ontogenetically altered genetic information is not inherited but extensively used in regulation and development of phenotypes, giving organisms the ability to, in a sense, re-program their genotypes according to environmental clues. An example of post-transcriptional alteration of gene-encoding sequences is the process of RNA Editing. When the process of RNA Editing became well known in 1993 [Benne, 1993], it became quite clear that there were more complicated linguistic-like processes at play in gene regulation in biology. Since then I have been working on computational models to study the evolutionary implications of genotype editing in the living organization. This research is described in greater detail in the separate Evolutionary Models of Genotype Editing page. Our latest agent-based model of genotype editing presents a novel architecture for evolving agents in which coding and non-coding genetic components are allowed to coevolve. Our goal is twofold: (1) to study the role of RNA Editing regulation in the evolutionary process, and (2) to investigate the conditions under which genotype edition improves the optimization performance of evolutionary algorithms. We have shown that genotype edition allows evolving agents to perform better in several classes of fitness functions, both in static and dynamic environments. We are also investigating the ways in which t the indirect genotype/phenotype mapping resulting from genotype editing lead to a better exploration/exploitation compromise in the search process.

Relevant Publications and resources:

Bio-semiotics: interplay between self-organization and selection

From my studies with Howard Pattee, I became preoccupied with the observation that while processes of a seemingly informational and indeed linguistic nature are fundamental to evolution in biology, computers which are based on the purely syntactic aspects of language were so non-adaptive. Therefore, I became interested in the linguistic/symbolic aspects of the living organization (the gene as a carrier of information, and DNA as memory) which play a large role in the seemingly open-ended evolution defined by natural selection. But this symbolic vision of biology (bio-semiotics), at first glance, seemed to be at odds with notions of self-organization so dear to complex systems scientists and a more developmental approach to biology. This lead me to study the interplay between self-organization and natural selection, introducing the concept of selected self-organization[Rocha ,1996a; Rocha ,1998a].

Due to this work on the interplay between selection and self-organization, and highly influenced by Pattee's work on the origin of life and origin of information, I became particularly interested on the problem of how information, symbols, representations and the like can arise from a purely dynamical system of many components. It became clear that the study of the inter-dependencies of symbol and matter is a necessary component of the study of evolutionary and also cognitive systems, and so I pursued the issue with various computational models. In particular, I have conducted simulations of evolving agents with different kinds of reproduction strategies (self-inspection and via a symbolic genotype-phenotype mapping). For these simulations I developed a genetic algorithm with an indirect encoding implemented with Fuzzy Development Programs, which model self-organizing development processes. More information on these simulations is available in the Fuzzy Development Programs' Resource page, which contains publications and software for understanding and using these. You can also check a paper where these simulations are detailed. The figure below depicts a run of my agent model where agents which reproduce via a genotype-phenotype mapping completely overtake a population, in a few generations, also containing agents which reproduce by self-inspection without such mappings.

Relevant Publications and resources:

Embodied Cognition, Bio-inspired computing, and Complex Networks

I am generally interested on the problem of how information, symbols, representations and the like can arise from a purely dynamical system of many components. Moreover, I am interested in using design principles from nature, particularly from biological systems dealing with information and memory, to improve information technology. These biologically-inspired design principles are typically distributed, that is, they are organized as complex networks, the characteristics of which I am interested in studying. For these reasons I have been very involved in Embodied Cognition, Bio-inspired computing, and Complex Systems by organizing meetings such as the International interdisciplinary seminar on new robotics, evolution and embodied cognition in Lisbon in 2002, editing a special issue of the Artificial Life Journal on embodied cognition, and being a member of projects such as the Principia Cybernetica Project, etc. I have also been involved in educational endeavors in this area, by teaching a course such as I-590 - Biologically-inspired Computing.

Material Representations and Emergent Computation in Cellular Automata

Due to my work dealing with language-like aspects of evolutionary systems (usefulness and characteristics of genotype-phenotype mappings), I became particularly interested on the problem of how information, symbols, representations and the like can arise from a purely dynamical system of many components. This is a topic of particular interest in Cognitive Science, where the notions of representation and symbol often divide the field into opposing camps. Of particular concern to me, was the observation that in the area of Embodied Cognition the idea of self-organization in dynamical systems lead many researchers to reject representational or semiotic elements in their models of cognition. Because I fundamentally agree with the embodied cognition approach, this attitude seemed not only excessive, but indeed absurd as it ignored the informational processes so important for biological organisms. Therefore, I have been working both on a re-formulation of the concept of representation for embodied cognition, as well as on simulations of dynamical systems (using Celular Automata) where one can study the origin of representations.

The Evolving Cellular Automata experiments of Crutchfield, Mitchell et al, in the late 1990's were very exciting, as the ability of evolved cellular automata to solve non-trivial computation tasks seemed to provide clues about the origin of representations and information from dynamical systems [Mitchell, 1998] [Rocha ,1998b]. I conducted additional experiments which extended the density classification task with more difficult logical tasks [Rocha ,2000; Rocha, 2004]. Later, with Wim Hordijk, I have proposed a re-formulation of the concept of representation in cognitive science and artificial life which is based on this work, but argues that the type of emergent computations observed in these experiments do not produce representations quite as rich as those as observed in biology and cognition [Rocha and Hordijk ,2005]. These experiments allow us to think about how to evolve symbols from artificial matter in computational environments. The figure above, depicts a space-time diagram and particle model of a CA rule evolved to solve the AND task . Some additional Figures and experiment details of CA rules for logical tasks in our experiments are also available. More recently, with Manuel Marques-Pita and Melanie Mitchell [2008a, 2008b], we have been looking at Conceptual Structure in the emergent computation of CA, using Manuel's Aitana algorithm.

Relevant Publications and resources:

The Adaptive Web and Bio-inspired designs for Recommendation Systems

I have been working on producing intelligent information retrieval methods that can pro-actively cater to the changing demands of user communities. Classic information retrieval algorithms did not effectively use the implicit knowledge accumulated from usage patterns. In other words, information retrieval used to rely exclusively on users pulling the information they needed from a passive environment. More recently, much effort has been posited on developing a different paradigm for information retrieval which relies much more on computational environments that “push” relevant information to users according to previous patterns of information retrieval. This kind of information retrieval has been described as Active Collaborative Filtering, Knowledge Mining, and even Knowledge Self-Organization in distributed information systems (DIS).

I have been developing active recommendation systems for DIS based on adaptive environments which are both collaborative and content-based, as they integrate information from the patterns of usage of groups of users and also categorize database content or semantics in a manner relevant to those groups. One of these systems, TalkMine, further allows the (adaptive) transmission of information across databases, as users may search several databases at the same time. TalkMine entails an open-ended human-machine symbiosis, which can be used in the automatic, adaptive, organization of knowledge in DIS such as library databases or the Internet, facilitating the rapid dissemination of relevant information and the discovery of new knowledge. TalkMine is based on several bio-inspired mechanisms: cognitive categorization as modeled by Fuzzy Set Theory and Dempster-Shafer Theory of Evidence, a connectionist memory architecture, and Hebbian learning for adaptive memory organization.

The recommendation systems I have been investigating aim at the creation of adaptive knowledge networks that facilitate collaboration among individuals, each with various search personalities. Indeed, I have been particularly interested in collaborative systems that are also strong on personalization---preserving distinct search personalities for each user. The systems we have developed aim at the open-ended self-organization and adaptation of DIS to the particular, diverse needs of their users. We refer to these systems as Adaptive Webs. The TalkMine system, in particular, was originally developed for the library without walls project of the Los Alamos National Laboratory research library. A testbed for TalkMine was development under the Active Recommendation Project. Other recommendation systems based on network models have been developed and are currently implemented in the MyLibrary Web Service at Los Alamos. The figure above depicts an associative network of more than a thousand journal titles accessed by the users of MyLibrary, where the links denote strong co-occurrence associations. The figure below depicts the web interface of this service.

Relevant Publications and resources:

Artificial Immune Systems for Spam Detection

Recently, with Alaa Abi-Haidar and Jorge Carneiro, we started to look at using Carneiro's Model of Cross-regulation in T-Cell dynamics to produce bio-inspired algorithms for Spam Detection. Our first results are encouraging and allow us to produce a competitive spam-detection algorithm, as well as gain further insights about T-Cell Cross-regulation in the vertebrate Immune System..

Relevant Publications and resources:

Semi-metric Network Analysis

The prime example of a Document Network (DN) is the World Wide Web (WWW). But many other types of such networks exist: bibliographic databases containing scientific publications, social networking services, as well as databases of datasets used in scientific endeavors. Each of these databases possesses several distinct relationships among documents and between documents and semantic tags or indices that classify documents appropriately. For instance, documents in the WWW are related via a hyperlink network, while documents in bibliographic databases are related by citation and collaboration networks. Furthermore, documents can be related to semantic tags such as keywords used to describe their content. Given these relations, we can compute distance functions (typically via co-occurrence measures) amongst documents and/or semantic tags, thus creating associative, weighted networks between these items---which denote stronger or weaker co-associations. The figure below represents such an associative network of people names extracted from co-occurrence in documents in a database as described in an internal report. You can also see a 3D Video (Real Video) of this network.

I have been compiling evidence and developing mathematical models to settle the hypothesis that the metric characteristics of the distance functions defining these associative networks, can be used as an indicator of the relevance of indirectly associated documents, users, and semantic tags. In particular, the hypothesis that strong semi-metric associations (items whose distance relation breaks the triangle inequality) can be used to identify trends, items with a higher probability of co-occurring in the future, as well the dynamics of such networks in general. This methodology has been successfully applied to networks of published documents, recommender systems for digital libraries at the Los Alamos National Laboratory, web search and recommendation by the givealink.org project, networks of felons obtained from intelligence records, and gene networks. This work has been pursued in the Identification of Interests, Trends and Dynamics in Document Networks Project as well as in a Los Alamos Homeland Security LDRD DR project, "Advanced Knowledge Integration (LDRD Reserve)" to discover latent associations in social networks (internal report available).

Recently, we have also been exploring appropriate isomorphisms between Fuzzy Graphs and distance (weighted) networks. With Eliot Smith and Rob Goldstone, we have obtained an NSF grant from the Human and Social Dynamics program to investigate how future social interactions can be predicted from the structure and dynamics of document networks extracted from social online services---this project recently received some attention in the media. This work includes agent-based models of peer-selection based on the adaptive recommendation methods I previously developed, the study of metric characteristics of distance networks, and a study of human subjects using online social networking services. It has also lead to a more in depth stochastic treatment of the growth of scale-free networks with cutoffs.

Relevant Publications and resources:

Agent-based modeling

The term agent is used today to mean anything between a mere subroutine to a conscious entity. There are "helper" agents for web retrieval and computer maintenance, robotic agents to venture into inhospitable environments, agents in an economy, etc. Intuitively, for an object to be referred to as an agent it must possess some degree of autonomy, that is, it must be in some sense distinguishable from its environment by some kind of spatial, temporal, or functional boundary. It must possess some kind of identity to be identifiable in its environment. To make the definition of agent useful, we often further require that agents must have some autonomy of action, that they can engage in tasks in an environment, independently or without external control. This is, in effect, a definition of agency directly related to the one put forward in the XIII century by Thomas Aquinas: an entity capable of election, or choice.

This is a very important definition indeed; for an entity to be referred to as an agent, it must be able to step out of the dynamics of an environment, and make a decision about what action to take next---a decision that may even go against the natural course of its environment. By this, simplistically, I mean that an agent (say in a steep incline) can opt to go uphill rather than roll with the force of gravity. Since choice is a term loaded with many connotations from theology, philosophy, cognitive science, and so forth, I prefer to discuss instead the ability of some agents to step out of the dynamics of its interaction with an environment and explore different behavior alternatives. In physics we refer to such a process as dynamical incoherence . In computer science, Von Neumann, based on the work of Turing on universal computing devices, referred to these systems as memory-based systems. That is, systems capable of engaging with their environments beyond concurrent state-determined interaction by using memory to store descriptions and representations of their environments. Such agents are dynamically incoherent in the sense that their next state or action is not solely dependent on the previous state, but also on some (random-access) stable memory that keeps the same value until it is accessed and does not change with the dynamics of the environment-agent interaction. In contrast, state-determined systems are dynamically coherent (or coupled) to their environments because they function by reaction to present input and state using some iterative mapping in a state space.

Let us then refer to the view of agency as a dynamically incoherent system-environment engagement or coupling as the strong sense of agency, and to the view of agency as some degree of identity and autonomy in dynamically coherent system-environment coupling as the weak sense of agency. The strong sense of agency is more precise because of its explicit requirement for memory and ability to effectively explore and select alternatives. Indeed, the weak sense of agency is much more subjective because the definition of autonomy, a boundary, or identity (in a loop) are largely arbitrary in dynamically coherent couplings.

I have been working on various types of agent models that are either based on the strong sense of agency detailed above, or attempt to study the emergence of such agency from dynamically coherent environments. The strong sense of agency has been further detailed in an overview of agent models for a previous project of the modeling of socio-technical systems as well as in an overview of research on complex systems modeling I wrote. Examples of agent-based models I have worked on are: the simulations of evolving agents with different kinds of reproduction strategies using Fuzzy Development Programs, the agent-based model of genotype editing, the evolving cellular automata experiments, the soft computing agents for recommendation systems, the immune-inspired spam detection algorithm, etc.

Relevant Publications and resources:

Uncertainty and Generalized Information Theory

I have been working in mathematical models of uncertainty such as Fuzzy Set Theory and the Dempster-Shafer Theory of Evidence (DST). In particular, I developed a set structure named Evidence Sets, which extended Fuzzy Sets with the DST. Evidence sets were developed to address the shortcomings of fuzzy sets as models of linguistic/cognitive categories previously discussed by George Lakoff by providing a set structure capable of dealing better with the contextual nature of cognitive categories while preserving their prototypical effects as observed by Eleanor Rosch. To make evidence sets useful, I developed new measures of uncertainty for continuous domains, since, in their membership degrees, they capture three distinct types of uncertainty: fuzziness, nonspecificity and conflict. I have also used evidence sets and their measures of uncertainty to develop soft computing agents for a digital library and web tool named TalkMine, which is capable of adapting to different user personalities and learning new terms for existing documents. More information about evidence sets is available in a separate page. The figure below depicts a non-consonant evidence set.

Relevant Publications and resources:

Research Team

Below is the roster of current and previous students and postdocs who work or have worked with me in all the projects above. Also see the research group on Complex Adaptive Systems and Computational Intelligence (CASCI) I lead, for a more up to date list.

Current Students and Postdocs:

Previous Students and Postdocs:

Collaborators and Relevant Research Groups

Below is a group of past and present collaborators, including graduate students, postdoctoral fellows and fellow researchers. I acknowledge all of them as contributing to different elements of the research described above. There is also a list of past and present research groups I am or have been involved with.

People with whom I share at least a publication:

People with whom I am currently working on yet unpublished work:

Present and Past affiliated Research Groups:

For more information contact Luis Rocha at rocha@indiana.edu. Check the Web Design Credits, for due credit.
Last Modified: May 29, 2009